포스트

알고리즘 0. Map

게시 업데이트
By 신희곤
17 분읽는 시간
알고리즘 0. Map

건국대학교 알고리즘 김성열 교수님의 수업을 정리한 내용입니다.

결정, 비결정 문제

결정 문제란 예, 아니요로 답할 수 있는 문제다. 예를 들어 ‘주어진 숫자 n이 소수인가?’, ‘그래프가 모든 정점을 연결하고 있는가?’는 결정문제다. 닫힌 질문과 같다.

비결정 문제란, 예, 아니요로만 답할 수 없는 문제다. 예를들어 ‘그래프의 두 노드 사이의 최단 경로가 무엇인가?’ 와 같이 구체적인 해답을 요구한다. 열린 질문과 같다.

많은 비 결정 문제는 결정 문제로 변환할 수 있다. 예를 들어, 두 그래프의 최단 거리가 무엇인가? 와 같은 문제는 두 그래프의 최단 거리가 k 이하인가? 와 같이 변환할 수 있다. 어떤 프로그램이 주어진 입력에 대해서 종료하는가? 와 같이 변환할 수 없는 문제도 존재한다.

비결정 문제를 결정 문제로 변환할 수 있는 기준이 무엇일까? Halting Problem과 같이 계산 자체가 불가능하거나, 그래프나 경로 등의 ‘구조’를 문제에서 요구하거나, 문제에 여러가지 조건이 걸려있는 경우 변환할 수 없다. 다만 최적화 문제의 경우는 가장 큰 ~는 무엇인가? 를 크기가 k인 ~가 존재하는가?와 같이 변환 가능하다.

P, NP, NP-Complete, NP-Hard

P는 Polynomial time의 약자로, 다항 시간 \(O(n^k)\) 안에 해결할 수 있는 결정 문제들의 집합이다. NP는 Nondeterministic Polynomial time의 약자로, 다항 시간 안에 해결될 지 결정할 수 없는 결정 문제들의 집합이다. 답이 맞는지 검증하는 것은 빠르게 (다항 시간 내에) 가능하다. 모든 P 문제는 \(O(n^k)\) 안에 해결되므로, 답을 쉽게 찾을 수 있으면 검증 또한 쉽게 할 수 있다. 따라서 P는 NP의 부분집합 관계에 있다. NP-Hard는 모든 NP 문제가 어떤 한 문제로 다항 시간 내에 변환 가능하면, 그 문제를 NP-Hard라고 부른다. 즉 NP-Hard 문제는 NP 문제를 더 넓은 범위로 일반화한 문제 집합이다. 결정 문제 뿐 아니라 더 넓은 범위의 의미로 사용된다. NP-Complete는 NP 문제이면서 동시에 NP-Hard의 성질을 가진 문제 집합이다. 만약 NP-Complete 문제가 다항 시간안에 풀린다면, 모든 NP 문제가 자동으로 다항 시간안에 풀리게 된다. 다항 시간안에 문제가 풀리면 그 문제는 P이므로 \(P=NP\) 관계가 성립한다. NP-Complete 문제를 풀기만 하면 모든 NP 문제를 다항 시간안에 깔끔하게 풀어버릴 수 있지만, 아직 그것은 난제로 남아있다.

P 문제는 그냥 일반적으로 알려진 효율적인 알고리즘을 사용하여 쉽게 풀 수 있다. (정렬, 그래프 탐색 등..) NP 문제는 Brute-force, DP, Backtracking, Divide and Conquer, …와 같은 기법들을 사용해야 한다. NP-Complete는 일반적으로 다항 시간 안에 해결이 불가능하며, 해답에 가까운 근사치를 다항 시간 내에 구하는 알고리즘을 사용하거나, 문제를 단순화하여 해결하려는 시도를 해야한다.

Pseudo-polynomial Algorithm

알고리즘의 시간이 input의 크기가 아니라, input 자체에 의존하는 경우 Pseudo-polynomial Algorithm이라고 한다. 왜 ‘가짜 다항식’이냐면, 만약 \(\{ n \}\)을 입력한다고 하면, 그 알고리즘은 \(O(1)\)의 입력을 가진다. 그 알고리즘 안에 for (int i = 0; i < n; i++)과 같은 코드가 존재하면 입력값 자체에 따라 시간복잡도가 달라지게 된다. 따라서 마치 \(O(1)\)처럼 보이지만 실제로는 \(O(n)\)의 시간복잡도를 가지기 때문에 Pseudo-polynomial라고 부른다.

실제 입력 크기는 숫자를 표현하는데 필요한 비트수와 비례하므로, \(O(4)\)가 아닌 \(O(\log N)\)이 더 정확하다. 만약 Pseudo polynomial 시간이 \(O(n)\)이라면, \(n=2^{\log n}\)이므로 지수적으로 증가하는 시간복잡도와 같다.

Algorithm

알고리즘으로 문제를 푸는 것은, 문제를 푸는 일관적인 방법을 찾아내는 것과 같다. 만약 한 문제에서 여러 상황의 데이터가 주어지는데, 어떤 경우는 예외 케이스로 이렇게, 어떤 경우는 예외 케이스로 이런 방식으로 문제를 푸는 경우가 있다. 이는 임시방편적인 방법이며, 알고리즘으로 문제를 푸는 것과 거리가 멀다.

따라서 대부분의 알고리즘에서는 모든 경우를 다 따져야 한다. 얼마나 효율적이게 따지냐에 따라서 알고리즘 성능이 갈리고, 효율적이게 따지는 ‘기법’들이 많이 있다.

  1. 그냥 무식하게 모든 경우를 다 체크하면 Brute-Force, Recursion, Divide and Conquer
  2. 우선순위를 따져 최고의 경우만 체크하면 Greedy
  3. 모든 경우를 체크하는데, 중복되는 계산이 많으면 Dynamic Programming
  4. 재귀 도중 굳이 안따져도 되는 경우를 걸러내면 Backtracking (또는 가지치기 Pruning)

P 문제는 잘 알려진 효율적인 알고리즘(정렬, DFS 등..)으로 풀 수 있다. NP 문제는 모든 경우를 다 따져봐야 한다. 먼저 재귀, Divide and Conquer로 해보고, 풀리면 DP, Backtracking 등으로 최적화한다. 안된다면 다른 방법으로 잘 따져야한다. NP-Complete 문제는 모든 경우를 다 따질 경우 다항 시간안에 해결할 수 없다고 알려져있다. 따라서 State Space를 그려서 Backtracking을 적용하여 필요한 부분만 효율적으로 탐색한다.

  • Basic Data Structures
  • Basic Algorithms
    • Sorting
      • 비교 정렬의 최소값은 \(O(n\log n)\)
        • Quick Sort \(O(n\log n)\)
        • Merge Sort \(O(n\log n)\)
      • Counting Sort \(O(n)\)
        • 데이터의 개수를 세는 방법.
      • Radix Sort \(O(w(n+k))\)
        • 자릿수로 Counting Sort 하는법.
        • \(w\)=자릿수, \(k\)=자릿수의 개수
    • Search
      • 기본적으로 \(O(n)\)
      • 정렬된 자료구조에서는 \(O(\log n)\)
      • 해쉬 함수를 사용하면 \(O(1)\)
    • Graph
      • Traversal \(O(n+m)\)
      • Find Connected Component \(O(n+m)\)
      • Pre Number, Post Number \(O(n + m)\)
      • Find Shorest Path \(O((n+m)\log n)\)
        • Tree의 경우, LCA를 찾으면 되기 때문에 \(n *O(1) = O(n)\)
      • Find Cut Vertex \(O(n+m)\)
      • Find Biconnected Component \(O(n+m)\)
      • Topological Sort \(O(n+m)\)
      • Find Strongly Connected Component \(O(n+m)\)
      • Randomized Minimum Spanning Tree \(O(n+m)\)
      • Lowest Common Ancestor
        • Preprocessing \(O(n)\), Find LCA \(O(1)\)
        • or Preprocessing \(O(n\log n)\), Find LCA \(O(\log n)\)
  • Solving Technique
    • Brute-Force
    • Recursion
    • Greedy
    • Divide and Conquer
    • Dynamic Programming
    • Backtracking
  • Utils
    • DFS Tree
    • Event Queue
    • DAG
    • Supergraph
    • State Space

Algorithm Verification

알고리즘을 만들면, 항상 답을 찾는지 검증해야 한다. 검증은 일반적인 표현식, 수식을 도입하라. 또, 증명에는 전체적인 경우를 모두 포괄해야 한다. 예시를 봐야 이해할 수 있는건 다 이해한게 아니다.

수학적 귀납법

\(P(1)\)이 참이고, \(P(n-1) \to P(n)\)이 참이면, \(P(n)\)은 모든 자연수 \(n\)에 대하여 참이다. 재귀를 사용하는 알고리즘을 증명할 때 유용하다.

[!example]- example{title} sum(x) = 1 + 2 + … + x 함수 증명

  1. 무엇을 증명해야 하는가? -> sum(x)는 1+2+…+x를 리턴한다.
  2. 증명 sum(1) => 1을 리턴함. 참. sum(x-1)가 1+2+…+x-1를 리턴한다고 치면, sum(x)는 1+2+…+x-1+x를 리턴하므로 전제가 참임.

따라서 수학적 귀납법에 의해 sum(x)는 모든 자연수 x에 대하여 1+2+…+x를 리턴한다.

수학적 귀납법은 \(P\)이면 \(Q\)이다 라는 \(P\to Q\) 명제를 보장하는 것이지. \(P\)가 아니면 \(Q\)가 아니다를 보장하는 것은 아니다. \(P\)가 아니면 \(Q\)는 맞을 수도 있고, 아닐 수도 있다. 이 두가지 Case를 Vacuous True라고 부르며 따지는 것이 의미가 없다.

예를들어, ‘100점을 맞으면 치킨을 사줄게.’ 라는 \(P \to Q\)라는 명제가 존재한다. 100점을 맞았을 때 치킨을 사준다면 명제가 True고, 100점을 맞았는데 치킨을 안사줬다면 명제가 False이다. 하지만 100점을 맞지 않았을 때 치킨을 사주는 것도 True다. 치킨을 안사주는 것도 True이다. 두 경우가 공허한 참인 경우이다.

이 논리를 수학적 귀납법에 적용해보자 \(P(n-1) \to P(n)\)이 참이면, \(P(n)\)은 모든 자연수에 대해서 참이다. 이는 \(P(n-1) \to P(n)\)이 참인 경우만 따지자는 것이고, 참이 아닌 경우는 생각하는 의미가 없으므로 고려하지 않는다.

Loop Invariant

반복문이 실행되는 동안 항상 참인 조건을 반복문 불변식, Loop Invariant라고 한다. Loop를 사용하는 알고리즘을 증명할 때 유용하다.

반복문이 실행되는 동안 Invariant가 유지된다면 자동으로 증명되도록 Invariant를 잘 설정하면 된다. 이후 초기에 Invariant가 만족하는지, 반복하는 동안 Invariant가 깨지지 않는지, 종료되었을 때 Invariant가 유지되었는지 체크하면 된다.

예를들어, Binary Serach를 증명하기 위해 Invariant를 두개를 만든다. (1) \(left < right\), (2) \(mid\)는 항상 left, right 사이에 위치한다. 이 Invariant가 초기, 반복, 종료 과정에서 깨지지 않으면 반복문이 left와 right를 점점 좁혀갈 것이고 최종적으로 원하는 값을 Search함을 증명하게 된다.

귀류법

명제가 참임을 증명하는 아주 유용한 도구다. 명제의 반대를 가정하고, 모순을 찾아내어 명제의 반대가 거짓임을 밝혀내어 명제를 증명한다.

Time Complexity

알고리즘이 얼마나 빠른지도 체크해야 한다. 입력 Size를 Lower Bound로 설정하고, 브루트 포스했을 때 구해지는 시간 복잡도를 Upper Bound라고 했을 때 우리가 만든 알고리즘의 시간 복잡도는 Lower Bound <= X <= Upper Bound일 것이다. 시간 복잡도를 Lower Bound로 만드는 것을 목표로 해야 한다.

시간 복잡도는 최악의 경우를 고려하는 Big-O Annotation을 사용한다.

Recursion

재귀를 사용하는 알고리즘은 다음과 같이 시간복잡도를 계산할 수 있다.

1
2
3

T(n) = 1 + T(n-1)
T(n) = 1 + 1 + T(n-2) = n
T(n) = O(n)

Master Theorem

Divide And Conquer의 시간 복잡도는 \(\displaystyle T(n) = aT\left( \frac{n}{b} \right) + O(n^d)\)와 같고, 이때 마스터 정리를 사용할 수 있다. \(a\)는 하위 문제로 쪼개지는 개수, \(b\)는 문제의 입력 사이즈를 몇 배 줄일지, \(\displaystyle \frac{n}{b}\)는 하위 문제의 크기, \(O(n^d)\)는 합치는데 사용하는 시간이다.

만약 시간 복잡도 \(T(n)\)을 하위 재귀식이 주도한다면, 즉 \(a > b^d\)이면 \(\displaystyle T(n) = O(n^{\log_{b}a})\)와 같다. \(T(n)\)이 하위 문제와 추가 작업이 균형을 이룬다면, 즉 \(a=b^d\)이면 \(T(n) = O(n^d \log n)\)와 같다. \(T(n)\)을 Merge가 주도한다면, 즉 \(a<b^d\)이면 \(T(n)=O(n^d)\)와 같다.

IT, 알고리즘
결정 문제 비결정 문제 P NP NP-Complete NP-Hard 알고리즘 시간 복잡도