알고리즘 문제풀이

최소 공통 조상? 트리에서 임의의 두 노드(u, v)에서의 최소 공통 조상은 "u와 v의 공통 조상노드들 중 가장 깊이가 깊은(=루트로 부터 거리가 먼)노드"로 정의할 수가 있다. 최소 공통 조상은 여러가지 분야에서 응용될 수 있지만, 트리 상에서 두 노드의 거리를 구할 때 많이 이용되는 알고리즘이다. 아래와 같은 트리가 있다고 가정해보자. 트리의 최상위 루트 노드는 루트노드를 제외한 모든 노드들의 조상 노드임을 알 수 있다. 깊이가 다른 노드 3과 6의 조상 노드들은 무엇이 있을까? (0, 1)번 노드가 3,6의 공통 조상일 것이다. 그 중, 최소 공통 조상은 공통 조상 중 depth가 가장 깊은 1이 된다. 다음으로는 깊이가 같은 4,5번 노드의 최소 공통 조상은 무엇이 있을까? 최상위 루트 노드인 ..

Trie 자료구조? Prefix Tree 라고 불리는 Trie 자료구조는 특정 문자열을 탐색하는데 최적화 된 자료구조이다. 문자열 배열에서 특정 문자열 ${S_i}$를 탐색하는데 걸리는 시간은 ${O(length(S_i))}$ 가 된다. 이러한 시간복잡도는 문자열 배열에서 정확하게 특정 문자열만 탐색하여야 가능한 시간복잡도이다. 어떤 방식으로 이렇게 시간복잡도를 최적화 하였을까? Trie 는 트리형 자료 구조를 기반으로 하는 탐색에 특화 된 자료구조이다. 보통, 탐색을 위해 트리형 자료 구조를 사용하는 경우 탐색을 위한 key와 해당 되는 키에 매핑되는 value 형태로 저장하는데 (이를, Associative array 라고 한다 https://en.wikipedia.org/wiki/Associativ..

1975년에 발표된 Manacher 알고리즘은 "특정 문자를 중심으로 하는 팰린드롬 중 가장 긴 홀수 팰린드롬의 길이"를 찾는 알고리즘이다. Manacher알고리즘은 Polynomial time을 가지는 문자열 알고리즘과 동일하게 "이미 탐색한 것에 대해서는 다시 돌아보지 않는다는 측면"에서 맥이 같다고 볼 수 있다. Manacher알고리즘은 팰린드롬에서 가지는 대칭성을 이용하여 이전에 한번 탐색한 구간에 대해서 이전에 구했던 정보를 활용한다. 예를 들어서 다음과 같은 경우가 있을 것이다. 여기서 [L, R]은 이전까지 탐색했던 범위라고 가정을 하자. 즉 j < i 인 j 에 대하여, 이미 j번째에서 [L,R] 구간까지 탐색을 완료했다는 뜻이 된다. 그리고 현재, 우리는 i번째 문자에 대하여 "i번째 문..

정의 Counter-Clockwise 알고리즘은, 벡터의 외적을 통해서 한 정점을 기준으로 나머지 2개의 정점의 위치 관계를 파악하는 알고리즘이다. 벡터의 외적? ${\vec{a}}$ x ${\vec{b}}$ 는 다음과 같이 정의된다. ( ${\mid{\vec{a}} \mid}$ ${\mid{\vec{b}} \mid}$ ${\sin\theta}$) $\vec{v}$, [v는 a,b의 법선벡터, $\theta$는 a벡터에서 b벡터까지 반시계 방향으로 잰 각의 크기] 각의 크기 $\theta$는 180도인 $\pi$ 이하의 각도. (약 더 큰 각도라면 각의 변환을 통해서 ${0 \leq \theta \leq \pi}$ 내로 변환을 해주어야한다.) 또한 벡터의 평행이동을 활용하면 세 점의 좌표를 통해서 바로 ..

서로소 집합 ( Disjoint Set Unit, DSU ) 이란 ? 공통 원소가 없는 상호베타적인 부분 집합들로 나눠 진 원소들에 대한 정보를 저장하고 조작하는 자료구조. DSU는 해당 원소가 같은 집합 내에 포함되어 있는지 빠르게 확인하기 위해서 사용되는 자료구조이다. 공통 원소를 포함하고 있지 않는 집합이므로, 교집합 or 차집합 등의 연산은 불필요하다.(= 의미가 없다) 핵심 연산( Union - Find ) Union 연산 : 2개의 DSU를 하나의 Set으로 합쳐주는 연산 Find 연산 : 어떤 element 가 주어 질 때, 이 Element가 속해있는 집합의 대표원소를 반환 *대표 원소가 같다 -> 같은 서로소 집합 에 속해 있다는 것. Disjoint Set은 Array, Linked L..

삽입정렬 ( Insertion Sort ) 기본 IDEA : 배열의 원소들을 카드라고 생각하자. 정렬된 카드를 왼손에 배치한다고 생각했을 때, 정렬되지 않은 카드들을 한개씩 뽑아서 매번 적절한 위치에 배치시킨다. 이 과정을 탁자위의 카드가 한개도 남지 않을 때 까지 반복하면 결국 손에 남아 있는 카드들은 정렬 된 상태를 유지한다. 입력 : n개의 수들로 이루어진 수열 { $a_1$, $a_2$, $a_3$, .... , $a_n$ } 출력 : $a'_1$ $\leq$ $a'_2$ $\leq$ $a'_3$ $\leq$ .... $\leq$ $a'_n$ 을 만족하는 입력 수열의 재배치 STEP : PSEUDO CODE ( 의사 코드 ): 0. Insertion_sort( A ){ 1. for j = 2 to..