알고리즘과 설계기법

알고리즘이란?

---

 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산절차 또는 처리과정의 순서를 뜻한다. 프로그램명령어의 집합을 의미하기도 한다. 다음은 알고리즘 개발의 정형적인 단계이다.

문제 정의 → 모델 고안 → 명세 작성 → 설계 → 검증 → 분석 (복잡도 등) → 구현 → 테스트 → 문서화

알고리즘 설계기법

---

훌륭한 알고리즘 중에는 문제를 해결하는 방법과 고속화의 테크닉에 있어서 공통점을 가진 알고리즘이 많이 있다. 예를들면 퀵 정렬과 합병 정렬은 정렬 대상이 되는 데이터가 들어 있는 배열을 두 개로 나눠서 두 배열을 각각 정렬한 후, 그들 두 배열을 연결한다는 점에서 공통점을 갖고 있다. 이러한 기본적인 테크닉을 알고리즘의 설계 기법이라고 부른다. 프로그래머는 해결해야 할 새로운 문제에 접했을 때 기존의 알고리즘 설계 기법을 응용할 수 있는지 어떤지를 생각하는 것은 새로운 알고리즘 개발에 필요한 시간과 경비를 줄일 수 있다는 점에서 매우 중요하다. 이 관점에서 여기서 3가지 알고리즘 설계 기법을 소개하기로 한다.

 

1. 동적 계획법(Dynamic Programming)

재귀적인 기법은 문제를 간단히 부분 문제로 분할할 수 있고, 부분 문제의 크기의 합을 적게 유지할 수 있는 경우에 유효하다. 그러나, 크기가 n인 문제를 단순히 분할해서 각 부분 문제의 크기가 균형이 맞지 않는 문제로 분할되었을 때에는 재귀적 알고리즘의 복잡도는 아마 지수 함수적으로 증가할 것이다. 이런 경우에는 「동적 계획법」이라는 기법을 이용하면 효율좋은 알고리즘을 설계할 수 있다. 한번 구한 부분 문제의 결과 값을 저장해두고 재사용을 하게 된다면 매우 효율적으로 계산을 하게 될 것이다.

간단히 말하자면 동적 계획법은 주어진 문제를 작은 문제로 나누어 푸는 알고리즘이라고 할 수 있다.

 

DP는 두 가지 속성을 만족해야 동적 계획법으로 문제를 풀 수 있다. 피보나치 수열을 예로 들어보겠다.

피보나치 수열은 앞의 두 수를 더한 수가 다음 수가 되는 수열이다. 

F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2 (n ≥ 2)

위의 식으로 알 수 있는 것은 피보나치는 재귀적인 관계를 가지고 있다는 점이다.

 

Overlapping Subproblem : 중복되는 부분 문제

F4 = F3 + F2 F4 = F2 + F1 + F2

피보나치의 과정을 살펴보면 같은 부분 문제가 계속해서 중복해서 나타난다는 점을 알 수 있다

F4를 구하기 위해서는 F3과 F2의 값을 알아야 한다. 그때 F3은 F2 + F1임으로 부분 문제가 중복된다는 점을 알 수 있다.

이 부분은 분할 정복과의 큰 차이라고 할 수 있다. 분할 정복에서의 부분 문제는 중복되지 않는다

이렇게 중복된 문제의 결과는 저장되어져서 쉽게 해결될 수 있다

 

Optimal Substructure : 최적 부분구조

이 조건은 어떤 문제의 최적의 해결책이 부분 문제의 조합으로 찾을 수 있어야 한다는 것이다. 그리고 이때 여러 부분 문제에서의 정답은 항상 일정하다

 

2. 분할 정복법(Divide and conquer)

분할 정복법에서는 해결하려고 하는 문제 (크기를 n 이라고 한다) 를 크기가 보다 작은 여러 개의 부분 문제로 분할한다. 단, 이 때 크기가 작은 부분 문제에 대한 답으로부터 원래의 문제에 대한 해답을 쉽게 얻을 수 있게 분할할 필요가 있다.

분할 정복법의 원리

 이와 같이 전체를 분할해서 각각을 따로 처리하고 마지막에 통합하는 방법을 분할 정복법이라고 한다.

 

 하노이의 탑이라는 게임을 예로 들어보겠다. 그림과 같이 세 개의 막대가 있을때 이 게임의 목적은 원판을 막대에서 막대로 한번에 하나씩 이동해서 모든 원판을 막대 B 로 옮기는 것이다. 단, 어떠한 경우에도 적은 원판 위에는 큰 원판을 둘 수 없다.

 이 게임은 다음과 같은 단순한 알고리즘으로 해결할 수 있다는 것을 알 수 있다. 막대가 삼각형의 형태로 배치되어 있다고 하고 홀수 번째에는 가장 작은 원판을 시계 방향으로 하나만 이동하고, 짝수 번째에는 제일 작은 원판을 제외한 나머지 원판 중에서 이동할 수 있는 것만을 하나 이동한다.
이 알고리즘은 간단하고 정당하지만 왜 정당한지를 금방 알기는 어렵지만 다음과 같은 분할 통치법을 이용하면 정당성도 금방 이해할 수 있을 것이다.

하노이의 탑

 

 원판 n 장을 A 에서 B 로 이동하는 문제는 크기가 n - 1 인 두 개의 부분 문제로 구성된 것이라고 생각할 수 있다.

첫번째 문제: n - 1장의 원판을 막대 A 에서 막대 C 로 옮기면 막대 A 에 있던 n 번째 작은 원판 (가장 큰 원판) 을 옮길 수 있 상태가 되므로 그 원판을 A 에서 B 로 옮긴다. 두번째 문제:  n - 1 장의 원판을 막대 C에서 B로 이동한다.

n-1장의 원판을 옮기기 위해서는 이 방법을 재귀적으로 사용하면 되는데, 여기서 이동하는 n - 1 장의 원판은 다른 어느 원판보다도 작으므로 이동할 때에 막대 A, B, C 의 제일 윗부분에는 어떠한 원판이 있는지를 생각할 필요가 없다. 실제로 여러 개의 원판이 어떻게 이동하는지는 알기 어렵고, 재귀 호출이 반복되므로 이것을 하나하나 체크하기는 힘들지만, 이 알고리즘의 아이디어는 이해하기 쉽고 정당하다는 것을 증명하는 것도 비교적 쉽다. 일반적으로 이와 같은 분할 통치법을 이용한 알고리즘은 그렇지 않은 알고리즘보다 효율이 좋다.
분할 통치법을 이용해서 알고리즘을 설계할 때에는 문제를 분할하는 방법 및 각 부분 문제에 대한 답을 통합시키는 방법도 고려해야 한다. 특히 부분 문제의 답에서 전체의 문제에 대한 답이 비교적 간단하게 얻어지지 않으면 이 기법은 사용할 수 없는 것이라고 생각해야 한다. 문제의 분할법도 알고리즘의 성능에 영향을 미치기 때문에 중요한다, 대부분의 경우 가능한 균등한 크기로 분할하는 것이 바람직하다.

부분 문제를 해결하기 위해서는 같은 프로시저를 재귀적으로 호출하는 것이 간단하고, 이 재귀 호출은 데이터수가 1 이 될 때와 같이 문제의 답이 분명하게 되는 시점에서 종료하게 된다.

3. 탐욕적 알고리즘, 탐욕법 (Greedy Alogorithm)

탐욕법은 해답에 접근하는 방법중 가장 단순한 것으로 현재의 상황에서 보아 가장 좋은 경우를 택해서 나아가는 방법이다.

탐욕법의 본질적인 문제점은 국소적인 관점에서 가장 좋은 선택이 대국적인 관점에서 보았을 때도 좋은 선택이라는 보증이 없다는 것이다. 즉 눈앞의 이익에 급급해서 큰 이익을 놓칠 우려가 있다. 그러나 문제에 따라서는 국소적인 최선과 대국적인 최선이 일치하는 경우가 있는데 그러한 경우에는 매우 유효한 기법이다. 

동전 문제를 예로 들어보겠다. 동전문제는 금액이 주어질때 동전의 총 개수를 최소로 하여 구하는 문제이다.

이때 금액에서 가장 큰 동전이 금액부터 동전을 소모해 개수를 매기게 된다.

 

---

이렇게 해서 3가지의 알고리즘 설계기법을 알아보았다. 앞으로 알고리즘 문제를 풀어가면서 문제마다 해당하는 알고리즘을 잘 이용해서 문제를 해결할 것이다.

참고자료

http://www.aistudy.co.kr/algorithm/design_park.htm#_bookmark_1ecb980

알고리즘 설계 기법 : 박정호

https://kangworld.tistory.com/48

[Algorithm] 동적 프로그래밍 (DP, 동적 계획법) 이해하기 (+ 예제 코드)