알고리즘 설계기법 정리

알고리즘이란?

- 문제를 해결하는 방법을 순서대로 명확하게 기술한 것
- 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것
- 문제 해결에 필요한 계산 절차 또는 처리 과정의 순서
- 제한된 시간과 공간 안에서 데이터를 어떻게 처리할 것인지 정의한 로직
- 알고리즘을 통해 특정한 입력을 받아서 실행한 결과인 해를 출력

1. 분할정복(Divide and Conquer)

1.1 정의

주어진 문제를 같은 유형의 더 작은 부분 문제들로 더 이상 나눌 수 없을 때까지 나눈다. 그리고 각각의 부분 문제들을 해결한 후, 다시 합병하여 문제의 답을 얻는 알고리즘이다.

1.2 전략

① 분할(Divide) : 문제를 동일한 유형의 여러 하위 문제로 나눈다.

② 정복(Conquer) : 가장 작은 단위의 하위 문제를 해결한다. 보통 재귀적 방법으로 해를 구한다.

③ 합병(Merge) : 하위 문제들의 해를 합쳐 원래 문제의 해를 구한다.

1.3 적용

이진 탐색(Binary search)

합병 정렬(Merge sort)

퀵 정렬(Quick sort)

선택(Selection)

2. 욕심쟁이(Greedy)

2.1 정의

문제를 해결하는 과정에서 선택의 순간에 최적이라고 생각되는 결정을 선택하여 해를 구한다. 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자는 모토를 가진 알고리즘 설계 기법이다. 전체를 보지 못하고 국소적인 관점에서 해를 구하게 되므로, 최종적으로 얻은 해가 궁극적으로 최적이라는 보장이 없다.

2.2 적용

Kruskal 알고리즘

Prim 알고리즘

Dijkstra 알고리즘

허프만 코드(Huffman code)

배낭 문제(Knapsack problem)

트리 정점 분할(Tree Vertex Splitting Problem: TVSP)

3. 동적 프로그래밍(Dynamic Programming)

3.1 정의

복잡한 문제를 간단한 여러 개의 작은 문제로 나누어 푸는 알고리즘. 분할 정복과는 달리, 부분 문제들이 서로 겹친다. 동적 프로그래밍에서는 작은 문제에서 나온 해를 저장해 두었다가 상위 문제의 해를 구할 때 이용한다. 따라서 이전 단계의 해를 이용하기 위해 그것을 기억할 수 있는 저장소가 필요하다.

3.2 전략

① 하나의 큰 문제를 여러 개의 부분 문제로 나눈다.

② 가장 작은 단위의 하위 문제를 해결한다. 이 때, 작은 문제들의 해들을 저장소에 저장한다.

③ 이 하위 문제의 해답을 이용해 상위 부분문제들의 해를 구해 나간다.

3.3 적용

다단계 그래프(Multistage graphs)

Ford 알고리즘

문자열 편집

0/1 배낭 문제

4. 퇴각검색(Backtracking)

4.1 정의

어떤 문제의 최적해를 구하기 위해 모든 가능성을 시도하는 방법이다. 후보 해들을 단계적으로 생성해 가는 과정에서 기준 함수를 통해 평가하여 최종 해가 될 수 없다고 판단되면 탐색을 멈추고 이전 분기점으로 돌아가서 다른 후보 해를 탐색한다. 튜플들의 상태를 담고 있는 트리를 구성하여 해 공간을 체계적으로 탐색하고 문제의 해를 구한다.

4.2 용어

문제 상태(problem state) : 트리에 포함된 각 노드
해 상태(solution state) : 문제 상태들 중, 루트로부터 그 노드까지의 경로가 해가 될 수 있는 튜플
해답 상태(answer state) : 해 상태들 중, 제약조건들을 만족하는 해 상태
상태 공간 트리(state space tree) : 이러한 해 공간에 대한 트리 구성
정적 트리(static tree) : 항상 같은 형태로 만들어지는 상태 공간 트리
동적 트리(dynamic tree) : 문제의 사례에 따라 서로 다른 형태로 만들어지는 상태 공간 트리
살아있는 노드(live node) : 이미 생성되었으나 아직 자식 노드들이 모두 생성되지 않은 노드
E-노드 : 살아있는 노드 중, 현재 자식을 생성하고 있는 노드
죽은 노드(dead node) : 이미 생성된 노드로서 확장될 수 없거나 자식들이 모두 생성된 노드

4.3 적용

N-queen 문제

부분집합의 합

그래프 채색

5. 분기한정법(Branch and Bound)

5.1 정의

퇴각검색과 유사하지만, 최적화 문제에만 적용할 수 있다. 모든 후보 해를 상태 공간 트리를 이용하여 체계적으로 탐색하고, 한 노드가 최종 해가 될 수 없다고 판단되면 그 노드를 제거해 나가는 방식을 사용한다. 정해진 범위(Bound)를 벗어나는 값들은 가지치기(Branch)를 하여 결과 해를 찾는 것이다.

5.2 전략

① 상태 공간 트리의 각 노드를 검색할 때마다 그 노드가 유망한지 여부를 결정하기 위해 한계치(bound)를 계산한다.

② 그 한계치는 그 노드로부터 확장하여 얻을 수 있는 해답의 한계치를 나타낸다.

③ 만약 그 한계치가 지금까지 찾은 최적의 해보다 좋은 경우는 탐색을 계속한다. 그렇지 않으면 탐색을 멈춘다.

5.3 적용

15-퍼즐 문제