본문 바로가기

오늘은 뭘 배울까?/알고리즘12

Union-Find 쉽게 이해하기 1. 개념 1-1. 큰 개념 1-2. Find 1-3. Union 2. 로직 3. 코드 1. 개념 1-1. 큰 개념 위 그림과 같은 그래프가 있다고 하자. 1-2-3 이 연결되어 있고 4-5-6이 연결되어 있다. "2랑 6은 서로 같은 그룹에 속해있나요?"라고 누군가 묻는다면 "아니요"라고 대답할 것이다. 질문을 받으면 우리 머릿속에서는 다음과 같은 계산이 이루어질 것이다. "음... 2가 어디 있지? 그래 왼쪽 그룹에 있구나. 그러면 6은... 6은 오른쪽 그룹에 있네?" "그러면 두 숫자는 서로 다른 그룹에 속해있구나!" 이와 같은 계산을 컴퓨터가 하려면 어떻게 해야 할까? 그게 바로 지금부터 설명할 Union-Find 알고리즘이다. 1-2. Find 찾다라는 뜻을 가지고 있다. 어떤 원소가 속한 그.. 2021. 9. 9.
접미사 배열(Suffix array) 개념과 예제 1. 접미사 배열 1-1. 개념 1-2. 예제 2. LCP 2-1. 개념 2-2. 예제 3. 그래서 이걸 어디다 써먹을 수 있는데? 1. 접미사 배열 1-1. 개념 접미사 어떤 낱말 뒤에 붙어 다른 낱말을 이루는 말을 뜻한다. ex) 임금님, 사장님, 의느님 -> '-님'이 접미사 접미사 배열(Suffix Array) 어떤 문자열의 모든 접미사를 사전 순으로 나열한 배열 LCP와 주로 같이 쓰인다. 2-2. 예제 mommy라는 문자열로 예시를 들어보자 우선 접미사의 종류를 만든다. -y -my -mmy 이런 식으로! 접미사가 들어있는 배열을 사전순으로 나열한 것을 '접미사 배열'이라고 부른다. 우측 표는 접미사 배열이 완성된 모습이다. 접미사는 보기 편하게 우측 정렬로 접미사 배열은 비교가 쉽게 좌측 정.. 2021. 9. 2.
전위순회, 중위순회, 후위순회란? 1. 개념 2. 예제 1. 개념 전위 순회 부모 노드를 먼저 방문하는 순회 방식 우선순위: 부모 노드 > 왼쪽 노드 > 오른쪽 노드 중위 순회 왼쪽 노드를 먼저 방문 후 부모 노드를 방문하는 순회 방식 우선순위: 왼쪽 노드 > 부모 노드 > 오른쪽 노드 후위 순회 하위 노드를 먼저 방문 후 부모 노드를 방문하는 순회 방식 우선순위: 왼쪽 노드 > 오른쪽 노드 > 부모 노드 이름이 굉장히 헷갈릴 수 있는데 항상 부모 노드를 중심으로 생각하면 기억하기 쉽다. 부모 노드를 언제 방문하는지를 기준으로 네이밍을 했다는 점을 기억하자. 전위 순회: 부모 노드 > 왼쪽 노드 > 오른쪽 노드 중위 순회: 왼쪽 노드 > 부모 노드 > 오른쪽 노드 후위 순회: 왼쪽 노드 > 오른쪽 노드 > 부모 노드 2. 예제 위 예제 .. 2021. 8. 16.
중위 표기법과 후위 표기법 1. 개념 1-1. 중위 표기법이란? 1-2. 후위 표기법이란? 2. 중위 표기식을 후위 표기식으로 바꾸는 법 2-1. 괄호가 없는 경우 2-2. 괄호가 있는 경우 3. 계산 3-1. 후위 표기식을 사칙연산하는 법 1. 개념 1-1. 중위 표기법이란? 1+1, 2+2, 3+3 ... 흔히 우리는 숫자와 숫자 사이에 더하기 빼기와 같은 연산자를 넣어서 식을 표현하곤 한다. 이렇게 피연산자 사이에 연산자가 위치하는 식을 중위 표기식이라고 하며 이렇게 표기하는 방법을 중위 표기법이라고 한다. 연산자가 '중'간에 위치하기 때문에 '중'위 표기법이라고 기억하면 쉽다. 1-2. 후위 표기법이란? 11+, 22+, 33+ ... 중위 표기식과 다르게 후위 표기식은 연산자가 뒤에 위치한다. 이렇게 표기하는 방법을 후위.. 2021. 8. 8.
힙(Heap) 이란? 1. 힙(Heap) 1-1. 힙이란? 1-2. 힙의 종류 1-3. 힙의 활용 1-4. 예시(힙 삽입) 1. 힙(Heap) 1-1. 힙이란? 맨 처음에 힙을 들었을 때 엉덩이(hip)가 생각날 수도 있지만 힙은 heap이다. 무언가를 차곡차곡 쌓아 올린 더미라는 뜻이다. 힙(Heap)은 완전이진트리의 형태로 만들어진 자료구조이다. 돌더미, 작장더미, 쓰레기 더미...처럼 위로 갈수록 노드의 수가 줄어드는 모습을 하고 있다. 1-2. 힙의 종류 최대 힙(Max Heap): (완전 이진 트리) + (부모 노드 > 자식 노드) 최소 힙(Min Heap): (완전 이진 트리) + (부모 노드 < 자식 노드) 힙은 위처럼 두 종류로 나뉜다. 다시 풀어서 설명하자면 최대 힙은 완전 이진 트리이면서 부모 노드가 자식 .. 2021. 6. 25.