[Algorithm] 알고리즘 기초 (2)

+ 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다.

알고리즘 설계 과정

- 크고 복잡한 문제의 해법을 바로 설계하는 것은 어렵다.

 

=> 문제를 분석하여, 풀 수 있는 크기의 작은 문제들로 나누고, 이 문제들을 푼 후, 각 문제들 간의 관계를 이용하여 해법을 연결한다.

---

하노이 탑 문제

기둥 1에 있는 n개의 원반을 어떻게 규칙을 만족하면서 기둥 3으로 옮길 것인가?

 

규칙 1. 언제나 원반은 1개씩 옮길 수 있다.

규칙 2. 작은 원반위에 큰 원반은 옮길 수 없다.

 

n = 1, 2인 경우에는 쉽게 풀 수 있으나 조금만 커지면 직접 푸는 것은 어렵다.

 

=> 알고리즘 설계 기법 중 되부름(recursion, 재귀)을 이용한다.

 

< 수학적 귀납법 풀이 >

n = 1인 경우, 그냥 옮긴다.

n = k인 경우, 옮길 수 있다고 가정한다.

n = k + 1인 경우, 위 방법을 이용하여 k개의 원반을 기둥 2로 옮기고, k + 1번째 원반을 기둥 3으로 옮긴다.

k개의 원반을 다시 기둥 3으로 옮긴다. 

 

즉, 쉽게 풀 수 있을 때까지 문제의 크기를 줄인다.

 

< 원반의 이동 횟수 >

- T(n): n개의 원반이 있을 때 하노이 탑 문제에서 원반의 이동 횟수

 

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

T(n)을 수열로 생각하면, an = 2an-1 + 1

an + 1 = 2an-1 + 2 = 2(an-1 + 1)

즉, 공비가 2인 등비수열이 된다.

= 2^n - 1

---

Stable Marriage 문제 (신장 이식)

n명의 남자와 n명의 여자가 있을 때, 다음 조건을 만족하게 모든 남자와 여자를 1 : 1로 짝 지을수 있는가?

 

조건 1. 모든 남자와 여자는 이성에 대해 1등부터 n등까지 선호도가 있다.

 

조건 2. 예를 들어 (남자, 여자)의 쌍이 (a, b), (c, d)로 있는데, b가 a보다 c, c가 d보다 b를 더 좋아한다면 이들은 쌍을 깨고 새로운 쌍을 만들게 된다. 이러한 일(불륜)이 생기지 않게 쌍을 정한다.

 

< Gale & Shapley 알고리즘 >

남자 ABCD와 여자 WXYZ의 선호도

1. 순서대로 여자가 가장 선호하는 남자와 짝을 짓는다. (남자 기준으로 해도 같다.)

=> (B, W), (D, X), (A, Y)

 

2. 가장 선호하는 남자가 겹친다면, 그 남자가 더 선호하는 여자로 짝을 짓는다.

=> Z 차례에서 충돌이 발생한다. B는 W보다 Z를 더 선호하므로 B와 Z가 짝을 짓는다.

=> (B, Z)

 

+ 짝이 변경되었다면 그 다음으로 선호하는 사람과 짝을 시도한다. (반복)

=> 짝이 바뀐 W가 다음으로 선호하는 남자 A를 시도한다. A는 Y보다 W를 선호하므로 A와 W가 짝을 짓는다.

 

< 정확성과 시간 복잡도 >

1. 위 알고리즘은 정확하다.

- 알고리즘 수행 과정에서 모든 남성, 여성은 반드시 짝을 갖게 된다.

- 조건 2에 어긋나는 경우는 알고리즘 수행 과정에서 제거된다. (짝이 바뀌는 것이 더 좋은 변화)

- 자기 자신은 자신이 좋다는 사람 중 가장 좋은 사람과 연결된다,

 

2. 위 알고리즘은 반드시 종료한다.

- 여성 기준으로 알고리즘 수행 과정에서 파트너가 바뀔 때마다 여성 파트너의 선호도는 감소한다. (파트너였던 남성의 선호도는 증가한다.)

- 따라서 한 남성이 n번 이상 파트너가 바뀔 수 없고 모든 남성이 총 n의 제곱 번 이상 파트너가 바뀔 수 없으므로 시간 복잡도는 O(n^2)이다.

---

최적성의 증명

모든 알고리즘 중 이보다 더 좋은 시간 복잡도를 얻을 수 없음을 증명하는 것이다.

(모든 문제의 최적성을 증명할 수는 없다.)

 

"문제를 풀기 위해서 반드시 필요한 일"의 크기를 재고, 최소한 이만큼 일을 해야 하기 때문에 더 잘 할 수 없다는 것을 보인다.

 

예) 시험 문제를 풀 때 걸리는 시간: 문제를 읽는 시간 + 답을 적는 시간