[종만북 요약] 4~5. 알고리즘 분석 (P-NP, 알고리즘 정당성 증명)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)을 읽으며 유용한 내용을 정리해 보도록 하겠습니다. 모든 내용을 요약하는 것은 아니며, 대회에 포커싱을 맞춘 부분은 다루지 않을 수도 있습니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 수행 시간 어림짐작은 유용하지만, 엄밀하지는 않으니 최적화 시에는 여러 인자들을 함께 고려해 보자.

2. 알고리즘의 정당성 증명은 해당 알고리즘의 통찰을 이해함에 있어 중요하다.

3. 알고리즘의 정당성 증명 방법은 귀납법, 반복문 불변식, 귀류법, 비둘기집의 원리, 구성적 증명 등이 있다.

---

*챕터 2 에서는 한 번 되짚어 볼 만한 내용을 일부 발췌해 정리해 보겠습니다.

 

수행 시간 어림짐작하기

일반적으로 우리는 Time Complexity 를 계산할 때, 최고차항의 차수를 이용해 효율성을 판단한다. 따라서 만약 O(N^3 + 999 * (N^2) * logN + 100000N + 234943) 같은 시간 복잡도가 나온다고 하면, N 의 크기에 따라 시간 복잡도를 단순히 N^3 라고 가정하는 것은 약간의(혹은 생각보다 상당한) 오차를 낳을 수도 있다.

이렇듯, 최고차항의 계수만 가지고 시간 복잡도를 판단하는 '주먹구구' 법칙은 엄밀하다고 보기 어려우며, 실제로는 다음과 같은 인자들을 고려할 필요도 있다.

• 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우 : 최고차항 이외의 계수에 대한 비용을 고려
• 반복문의 내부가 복잡한 경우
• 메모리 사용 패턴이 복잡한 경우 : 주로 캐시의 Locality 와 Temporality 등이 연관된다.
• 언어와 컴파일러의 차이 : 최적화 옵션도 꽤나 큰 영향을 끼치기도 한다.
• 구형 컴퓨터를 사용하는 경우

 

예제 : 최대 연속 구간 합 문제를 풀어보자. 예를 들어, 배열 [-7, 4, -3, 6, 3, -8, 3, 4] 에서 최대 합을 갖는 부분 구간은 [4, -3, 6, 3] 으로 합은 10이다.

-> 이 문제의 경우, O(N^3), O(N^2), O(NlogN), O(N) 의 여러 경우가 있다. DP 를 이용하면 O(N) 으로 풀 수 있다.

int fastestMaxSum(const vector<int>& A)
{
    int N = A.size(), ret = INT_MIN, psum = 0;
    for (int i = 0; i < N; ++i)
    {
        psum = max(psum, 0) + A[i];
        ret = max(ret, psum);
    }
    return ret;
}

 

 

P, NP, NP-Complete

예를 들어 주어진 N 개의 정수를 정렬하는 문제가 있다고 하자. 우리는 이 문제를 다항식 시간 안에 풀 수 있다는 것을 알 수 있다.

이처럼, 다항 시간에 풀 수 있는 문제를 P 문제라고 한다. 반면, NP 문제는 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제의 집합이다.

예를 들어, '부분 집합 합 (subset sum) 문제'를 보자. 이 문제는 'N개의 수가 있을 때 이 중 몇 개를 골라내서 그들의 합이 S 가 되도록 할 수 있는가?'라는 문제다.

이 문제에 대한 답이 있다고 하면, 우리는 주어진 집합이 모집합의 부분집합인지, 그리고 합이 S 인지를 다항 시간 내에 확인할 수 있다.

즉, 모든 P 문제는 NP 문제에 속하게 된다. 그런데 NP 문제가 왜 중요할까? NP 문제보다 더 어려운 SAT 문제를 한 번 보자.

충족 가능성 문제(充足可能性問題, satisfiability problem, SAT)는 어떠한 변수들로 이루어진 논리식이 주어졌을 때, 그 논리식이 참이 되는 변수값이 존재하는지를 찾는 문제이다. 만족성 문제, 만족도 문제, 만족 문제, 불린 충족 가능성 문제(boolean satisfiability problem)라고도 부른다.

출처 : 위키피디아

위의 논리식을 참으로 만드는 변수의 조합을 찾는 문제인데... 문제는, 이 문제를 다항 시간 내에 풀 수 있는 방법을 찾지 못했다는 것이다. 이렇듯, 다항 시간 내에 풀 수 없는 문제를 NP-Hard 문제라고 한다. 그리고 NP-Hard 이면서 NP 인 문제를 NP-Complete 문제라고 부른다. 위의 부분 집합 문제도 NP-Complete 문제 중 하나이다!

참고로, NP-Hard 처럼 다항 방정식으로 풀 수 없다는 것은, 결정성이 있는 다항식으로 풀 수 없다는 뜻이다. 😅

1) 결정성(Deterministic) 알고리즘 : 각 단계에서 그 다음 단계가 유일하게 결정되는 알고리즘이다. 예를 들어 A -> B로 결정되어 있음을 뜻한다.
​
2) 비결정성(Non-Deterministic) 알고리즘: 그 다음 단계가 유일하게 결정되지 않는 알고리즘이다. A 이후 B 인지 C 인지 D 인지 정해지지 않았다는 뜻이다.

 

밀레니엄 수학 난제로 P = NP 문제가 있다. 이는 P 와 NP 가 같은지를 확인하는 것인데, 만약 NP-Hard 중 하나를 다항 시간에 풀 수 있다면, 이 알고리즘을 이용해 NP 에 속한 모든 문제를 다항 시간에 풀 수 있다. 이 경우 NP 에 속한 모든 문제를 다항 시간에 해결할 수 있어 P = NP 임을 알 수 있다. 반대로, NP 문제 중 하나가 P 에 포함되지 않음을 증명하면 P != NP 임을 보일 수 있다. 직접 해결하진 못하겠지만... 재미있는 담론이라고 생각한다. 만약 풀려고 하는 문제가 NP-Hard 가 될 것 같다면, 이를 우회하도록 하자. 🤣

 

 

알고리즘의 정당성 증명

많은 사람들은 알고리즘의 정당성을 직접 증명하기보다는 적절한 알고리즘을 뽑아 쓰는 것에 만족한다. 하지만 알고리즘의 정당성을 증명하는 과정에서 해당 알고리즘의 핵심 원리에 대한 통찰을 얻어 갈 수 있으므로, 직접 정당성을 증명하는 것은 좋은 습관이 될 수 있다. 아래에서 대표적으로 사용되는 방법을 소개한다.

 

수학적 귀납법과 반복문 불변식

귀납법은 고등학교 때에도 수없이 했던 것이지만, 정리하면 다음 스텝으로 나뉜다.

• 단계 나누기
• 첫 단계 증명 : A(1) 일 경우
• 귀납 증명 : A(K) 가 성립할 때, A(K+1) 도 성립하는지 확인

귀납법을 이용할 때는 반복문 불변식(loop invairant) 라는 개념이 유용하게 쓰인다. 이는 반복문의 내용이 한 번 실행될 때마다 중간 결과가 원하는 길에 잘 있는지 명시하는 조건이다!

대표적인 예시로, 이진 탐색 문제가 있다.

 

귀류법

이 방법 또한 학창 시절 수없이 사용했던 기법이다. 😅

잘 알겠지만... 우리가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해 결론이 잘못되었음을 찾아내는 방법이다!

 

비둘기집의 원리 

비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다. 이 원칙을 응용해, 순환 소수를 한 번 찾아보자.

만약 1/11 이 입력으로 주어지면, 답은 0.09090909009· ·  로 무한히 반복되게 된다. 그런데 식을 잘 보면...

a % b 의 결과는 [0, b-1] 이 된다. 즉, while 루프가 b+1 번 돌때부터는, 같은 결과가 반복될 것임을 유추할 수 있다! 😮

 

구성적 증명

추가로, 구성적 증명(constructive proof) 라는 것도 있다. 예를 들어, 하늘을 나는 교통 수단을 만들 수 있음을 증명한다고 할 때, 구성적 증명은 비행기를 만들어서 보여주거나, 만드는 설명서를 건네 준다. 즉, '이렇게 만들면 된다'라고 하는 것이 구성적 증명이다.

예를 들어, 안정적 결혼 문제(Stable marriage problem)을 보자. 안정적 결혼 문제란, N 명의 남성과 N 명의 여성이 모두가 각각 선호하는 순서로 된 파트너 목록을 가질 때, 모두가 매칭이 되면서 동시에 서로에 대한 선호도가 높은 짝이 맺어지는 방법을 찾는 문제이다. 답은 다음과 같다.

1. 여성들이 가장 선호하는 남성에게 프로포즈를 한다. 남성은 그 중 제일 맘에 드는 여성을 고르고, 나머지는 제자리로 돌아간다.
2. 선택받지 못한 여성들은 다음으로 마음에 드는 남성(짝이 있어도 상관없음)에게 프로포즈한다. 남성은 만약 더 맘에 드는 여성이 왔다면, 새 여성에게 넘어가고 기존 여성은 제자리로 돌아간다.
3. 더 프로포즈할 여성이 없을 때까지 2번 항목을 반복한다.

이 알고리즘은 다음 2가지 요점을 통해 증명할 수 있다.

• 종료 증명 : 각 여성은 최대 N 명의 남성에게 프로포즈하므로, 탐색은 언젠가 반드시 종료한다.
• 모든 사람들이 짝을 찾는지 증명 : 귀류법을 이용하면, 짝을 찾지 못하는 남성이 존재할 수 없음을 알 수 있다.

 

 

읽을거리

생각하는 프로그래밍 : ACM 학회지에 연재되었던 프로그래밍 에세이. 훌륭한 통찰들을 여럿 담고 있다.