🖥 Computer Science/알고리즘

🧐 NP-Hard(NP 난해) Problem X가 다음 조건을 만족하면 이를 NP-Hard라 부릅니다. 어떠한 Y $\in$ NP 에 대해서도, Y $\leq_p$ X 가 성립니다. 즉 NP에 속한 어떠한 문제에 대해서도 X로의 Polynomial Time Reduction이 존재해야 합니다. Halting Problem(정지 문제)은 NP-Hard에 속하는 대표적인 문제입니다. 🧐 NP-Complete(NP 완전) Problem X가 다음 조건을 만족하면 이를 NP-Complete라고 부릅니다. 1) 어떠한 Y $\in$ NP 에 대해서도, Y $\leq_p$ X 가 성립니다. 2) X $\in$ NP 여야 합니다. 즉 NP-Complete는 NP-Hard이면서 NP인 문제들을 의미합니다. Haltin..

🧐 Problem 이전 글에서 살펴보았던 problem에 관련한 개념들을 다시 살펴보도록 하겠습니다. Problem Instance : 어떤 문제(problem)를 정의하는 input이며, 이때 해당 input을 일종의 binary string으로 생각할 수 있습니다. Problem : 어떤 조건을 만족시키는(YES라 답하는) problem instance들의 집합을 의미합니다. 이때 Problem에 속하는 instance들을 YES instance라 합니다. Algorithm : 어떤 problem X에 대하여, 어떤 mapping 함수 A가 임의의 s $\in $ X에 대하여 A(s) = YES이고, 역( A(s) = YES일 경우 s $\in$ X )도 성립하는 경우 A를 problem X를 해결하..

🧐 Reduction 어떠한 문제 X와 Y를 가정하도록 하겠습니다. (엄밀한 정의는 아닙니다) 이 때 Y를 해결하는 어떠한 알고리즘이 존재하고, 해당 알고리즘을 이용하여 문제 X를 해결하는 알고리즘을 디자인 할 수 있는 경우, 문제 X에서 Y로의 Reduction이 가능하다고 합니다. (X is reducible to Y) 이를 보통 X $\leq$ Y 로 표현합니다. 즉 X $\leq$ Y 인 경우, X를 해결하는 것은 Y를 해결하는 것보다 절대로 어려울 수 없습니다. 다른 말로는 Y를 해결하는 것은 적어도 X를 해결하는 것 만큼 어렵다고 할 수 있습니다. Reduction은 특정 문제를 해결하는 알고리즘을 디자인하거나, 어떤 문제를 해결하는 알고리즘이 존재하지 않는(혹은 매우 해결하기 힘든) 것을 증..

🧐 Non-Comparison Sort 이전 글에서 Comparison Based Sort는 Lower Bound가 Ω(n log n)이라는 것을 살펴보았습니다. 이번에 살펴볼 알고리즘은 시간 복잡도가 O(n)인 정렬 알고리즘입니다. 이는 Comparison Based Sort가 아니기 때문에 이전에 구한 Lower Bound는 잘못되지 않았음을 미리 밝히고 넘어가겠습니다. 🧐 Counting Sort (계수 정렬) 우선 배열 A[0, ..., n]를 1부터 k 사이의 정수 배열이라 하겠습니다. 계수 정렬은 다음과 같이 이루어집니다. 크기가 k인 Counter 배열 C[0, 1, 2, ..., k]를 정의합니다. 해당 값들을 모두 0으로 초기화합니다. A[0]부터 A[n]까지 읽으면서 $0 \leq i ..

🧐 Lower Bound Upper Bound는 빅오 표기법을 사용해 보였다면 이미 아실 것이라 생각합니다. Lower Bound 역시 이와 비슷합니다. 어떤 문제가 주어졌을 때, `해당 문제를 해결하는 알고리즘의 Lower Bound가 T이다.`의 의미는 다음과 같습니다. (어떤 가정 하에서) 해당 문제를 T 시간보다 더 빨리 해결할 수 없다. 이때 가정은 계산 모델, 추가 사용 공간 등의 여러가지 가정이 있을 수 있습니다. 또한 빅-오메가(Ω) 표기법을 사용하여 표기합니다. 예시를 하나 살펴보겠습니다. 길이 n인 배열에서 최대값을 찾는 알고리즘의 lower bound는 Ω(1)이라고 표현할 수도 있고, Ω(n)이라 표현할 수도 있습니다. 이 경우 Ω(n)으로 나타내는 것이 더 우수한(유용한) Lowe..

🧐 플로이드 와샬 알고리즘 플로이드 와샬 알고리즘은 음의 사이클이 없는 그래프 상에 존재하는 모든 정점에 대하여, 각 정점 간의 최단거리를 구할 수 있는 알고리즘으로, 기본 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것입니다. V = { 1, 2, ..., n } 으로 두고, G의 임의의 두 정점 i, j에 대하여 dist(i, j, k)를 다음과 같이 정의합니다. 정점 (1, 2, ..., k) 만을 path의 중간 정점(intermediate vertex)으로 포함시킬 수 있을 때, i 에서 j로의 최단 경로의 길이 🧐 Recurrence Relation Base Case( k = 0 ) dist (i, j, 0) = 0 : i = j 인 경우 dist (i, j, 0) = w(i, j)..

🧐 최단 경로 문제 그래프 G = (V, E) 상에서 정점 u에서 v로의 가장 짧은 path의 길이를 구하는 문제를 의미합니다. 유명한 방법으로는 다익스트라 알고리즘이 있습니다. 그러나 다익스트라 알고리즘은 음수 가중치를 가지는 간선이 없는 그래프에 대해서만 올바르게 동작한다는 제약이 있습니다. 🧐 Bellman-Ford 알고리즘 최단 경로 문제를 해결하는 dp 기반의 알고리즘입니다. 다익스트라 알고리즘과 마찬가지로 시작 정점 s에서 그래프 G에 존재하는 다른 모든 정점으로의 최단경로를 구하며, 매 단계마다 해당 최단거리의 길이를 업데이트하며 진행되는 알고리즘입니다. 기본적으로는 방향(directed) 그래프를 가정하지만, 무방향 그래프에 대해서도 이를 방향 그래프로 생각하여 적용할 수 있습니다. 벨만포..

🧐 Edit Distance 어떤 단어와 비슷한(가까운) 단어는 어떻게 정의할 수 있을까요? 예를 들어 Word의 spell check 기능을 보면 다음과 같이 비슷한 단어들을 알려주는 것을 알 수 있습니다. Edit distance는 두 string이 얼마나 가까운지 나타내는 척도입니다. 두 문자열 $S_1$ 과 $S_2$ 간의 edit distance는 $S_1$ 에서 아래 3가지 종류의 연산을 최소한 몇 번 수행하여 $S_2$ 를 만들 수 있는가로 정의됩니다. Insertion : $S_1$ 의 아무 위치에 문자 하나를 추가합니다. MONDT -> MONEDT Deletion : $S_1$ 의 아무 위치에서 문자 하나를 제거합니다. MONEDT -> MOMED Substitution : $S_1$ ..