알고리즘 설계
일반화가 가능한 완벽한 알고리즘은 존재하는가?
모든 문제에 적용할 수 있고, 항상 문제해결이 가능하며, 효율적으로 동작하는 완벽한 일반화 알고리즘 설계 기법은 존재하지 않는다. 알고리즘은 입력되는 데이터, 문제해결의 목적, 문제를 해결하는 상황이나 조건과 같은 제약조건, 환경 등에 따라 달라지며, 상황에 맞는 최적의 알고리즘을 선택해야 한다.
또한 동일한 문제라도 여러 가지 해결 방법(알고리즘)이 존재할 수 있으며, 그 중에서도 효율적인 문제해결이 가능하도록 알고리즘을 효율적으로 설계하는 일은 매우 중요하다.
상황에 따라 알고리즘이 달라져야 함을 보여주는 예시
1에서 10 까지의 숫자가 하나씩 담긴 리스트가 있고, 여기에서 ‘7’ 이라는 숫자를 찾아야 한다고 가정해보자. 어떠한 알고리즘을 적용할 수 있을까?
(1) 순차 탐색
1에서 10까지의 숫자가 무작위로 섞여있는 상황을 가정해보자. 이 상황에서는 리스트 안의 모든 숫자를 순차적으로 꺼내어 7인지 확인하는 탐색 방법이 필요하다.
1
2
3
4
5
6
7
8
9
numbers = [5, 2, 4, 1, 3, 6, 7, 10, 9, 8]
for i, number in enumerate(numbers):
if number == 7:
print('7은 리스트의 ', i+1, '번째에 있습니다.')
print('탐색 횟수 : ', i+1, '회')
# >> 7은 리스트의 7번째에 있습니다.
# >> 탐색 횟수 : 7회
(2) 이진 탐색
이번에는 1에서 10까지의 숫자가 순서대로 섞여있는 상황을 가정해보자. 이 상황에서 가장 효율적인 탐색 방법은 바로 이진 탐색이 될 것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
left = 0
right = len(numbers) - 1
count = 0
while left <= right:
mid = (left + right)//2
count = count + 1
if numbers[mid] == 7:
print('7은 리스트의', mid, '번째에 있습니다.')
brek
elif numbers[mid] < 7:
left = mid + 1
elif numbers[mid] > 7:
right = mid - 1
print('탐색 횟수 : ', count, '회')
# >> 7은 리스트의 7번째에 있습니다.
# >> 탐색 횟수 : 3회
결론 : 알고리즘은 상황에 따라 달라져야 한다
결론적으로, 문제의 특성에 따라 알고리즘은 달라질 수 있으며, 매우 흡사한 문제더라도 제약조건과 상황, 입력데이터 등에 따라 그 알고리즘이 달라져야 할 수도 있다.
그렇다면 어떻게 알고리즘을 설계해야 하는가
많은 유형의 문제에서 효과정으로 사용할 수 있는 대표적인 알고리즘 설계 기법 세가지를 소개한다.
| 알고리즘 설계 기법 | 설명 |
|---|---|
탐욕 알고리즘욕심쟁이 방법 greedy algorithm |
- 각 단계마다 최선의 최적해를 구하는 방법 - 국부적으로 최적해를 구하면 전체적인 최적해를 구할 수 있을 것이라는 희망적 기대를 가지는 알고리즘 |
분할 정복devide and conquer |
- 문제를 더이상 나눌 수 없을 정도의 작은 문제로 분할한 뒤 - 분할된 개별적 문제를 해결한 결과를 합쳐서 전체 문제를 해결하는 방식 |
동적 프로그래밍dynamic programming |
- 작은 문제들의 해를 구해 저장하고 - 저장한 해를 이용해 보다 더 큰 문제의 해를 구하는 상향식 접근 방법 |
탐욕 알고리즘 Greedy Algorithm
탐욕 알고리즘이란
탐욕 알고리즘(Greedy Algorithm)은 탐욕적 방법, 그리디 알고리즘, 욕심쟁이 방법 등 여러 명칭으로 불리는 알고리즘 설계 방법으로, 해(문제의 답)을 구하는 일련의 단계들로 이루어진 과정에서, 각 단계마다 가장 최선이라고 여겨지는 국부적인 최적해를 선택해나가는 방법이다.
탐욕 알고리즘은 각 단계마다 국부적인 최적해를 찾는 것이 곧 전체적인 최적해를 찾는 것이라는 희망적인 기대를 가지고 설계된 알고리즘이다. 희망적이라는 단어가 사용된 이유는, 국부적인 최적해의 모임이 항상 전체적인 최적해를 보장하는 것은 아니기 때문이다.
예를 들어 패션을 조합하는 문제를 생각해보자. 옷을 입을 때 ‘가정 멋진 모자’, ‘가장 멋진 상하의’, ‘가장 멋진 구두’은 각각을 놓고 봤을 때에는 가장 멋진 아이템일 수 있다. 하지만 이들을 한 번에 조합했을 때 전체적으로 조화롭지 않을 수도 있다.
탐욕 알고리즘도 마찬가지다. 각 단계에서 최선의 선택을 했더라도 전체적으로는 최적의 해답이지 않을 수도 있는 것이다. 개별적으로는 최적의 해답으로 보이지만, 이를 모두 합쳤을 때 기대했던 최적의 결과가 아닐 수도 있음을 명심해야 한다.
대표적인 문제 : 거스름돈 문제
거스름돈 문제는 가장 적은 개수의 동전으로 특정 금액을 거슬러 주는 문제이다. 탐욕 알고리즘으로 접근하면 다음과 같다.
1
2
3
1. 가장 큰 단위의 동전부터 최대한 많이 사용한다.
2. 남은 금액에 대해 다음으로 큰 단위의 동전을 사용한다.
3. 2번을 반복하여 남은 금액이 0이 될 때까지 진행한다.
예를 들어 760원을 거슬러줘야 하는 경우, 아래와 같이 계산할 수 있다.
1
2
3
4
5
6
7
# 760원 거슬러주기
500원 단계 : 1개
100원 단계 : 2개
50원 단계 : 1개
10원 단계 : 1개
>> 총 5개
만약 단위가 ‘220원’인 동전이 새로 생겼다고 가정해보자. 탐욕적 알고리즘으로는 아래와 같이 풀어나갈 수 있다.
1
2
3
4
5
6
# 760원 거슬러주기
500원 단계 : 1개
220원 단계 : 1개
10원 단계 : 4개
>> 총 6개
탐욕 알고리즘을 사용해 문제를 풀었지만, 두 번째 경우에서는 오히려 동전의 개수가 증가한 것을 볼 수 있다. 즉, 각 단계에서의 최적의 선택이 항상 전체적인 최적해를 보장하지 않는다는 점을 유의해야 한다.
탐욕 알고리즘의 요약
| 구분 | 내용 |
|---|---|
| 탐욕 알고리즘 | - 각 단계마다 최선이라고 여겨지는 국부적인 최적해를 선택해나가는 방법 |
| 장점 | - 빠르게 최적해에 근사한 근사해를 찾을 수 있다. |
| 단점 | - 국부적인 최적해가 항상 전체적인 최적해를 보장하지는 않는다. |
| 예시 | 다익스트라 알고리즘(최단 경로), 크루스칼 알고리즘(최소 신장 트리) |
분할 정복 Divide and Conquer
분할 정복이란
분할 정복(Divide and Conquer)은 주어진 문제를 더 이상 나눌 수 없을 때까지 작은 문제로 분할하고, 이렇게 분할된 작은 문제들을 개별적으로 해결한 뒤, 작은 문제들의 해(해답)를 결합하여 원래의 주어진 문제의 해를 구하는 방식을 뜻한다. 즉 문제를 작게 쪼개서 푸는 방법이다. 하향식(top-down) 접근 방법에 해당한다.
분할 정복은 분할, 정복, 결합이라는 단계를 거친다.
| 단계 | 설명 |
|---|---|
| 분할 divide |
- 주어진 문제의 입력을 여러 개의 작은 문제로 분할한다. |
| 정복 conquer |
- 작은 문제들을 더 이상 나눌 수 없는 크기까지 순환적으로 분할한다. - 더 이상 나눌 수 없을 정도로 작으면, 그 작은 문제에 대한 해를 구한다 |
| 결합 combine |
- 작은 문제에 대해 정복된 해를 결합해 원래 문제의 해를 구한다. |
분할 정복은 다음과 같은 특징을 가진다.
(1) 분할된 작은 문제들을 합치면 원래 문제와 동일하다.
문제를 작은 단위로 나누더라도, 각 하위 문제의 구조는 원래 문제와 동일하다. 즉, 입력의 크기만 작아졌을 뿐, 해결해야 할 문제의 본질은 변하지 않는다.
(2) 분할된 문제는 서로 독립적이다.
분할된 문제들은 서로 영향을 주지 않으며, 개별적으로 해결할 있는 독립적인 문제들로 나뉜다. 또한 각각의 해결 결과를 결합해 최종적으로 전체 문제를 해결할 수 있다.
대표적인 문제 : 이진 탐색
이번에는 1에서 10까지의 숫자가 순서대로 섞여있는 상황에서 원하는 숫자의 위치를 찾는 문제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
left = 0
right = len(numbers) - 1
count = 0
while left <= right:
mid = (left + right)//2
count = count + 1
if numbers[mid] == 7:
print('7은 리스트의', mid, '번째에 있습니다.')
brek
elif numbers[mid] < 7:
left = mid + 1
elif numbers[mid] > 7:
right = mid - 1
print('탐색 횟수 : ', count, '회')
# >> 7은 리스트의 7번째에 있습니다.
# >> 탐색 횟수 : 3회
분할 정복 알고리즘 요약
| 구분 | 내용 |
|---|---|
| 분할 정복 | - 문제를 작은 부분 문제로 나눈 뒤, - 이를 해결한 결과를 합쳐서 전체 문제를 해결하는 방식 |
| 장점 | - 문제를 재귀적으로 해결해, 복잡한 문제도 체계적으로 접근 가능 - 정렬, 탐색에서 매우 효율적임 |
| 단점 | - 모든 문제에 적용할 수 있는 것은 아님 - 부분 문제를 해결한 결과를 합치는 과정이 복잡할 수 있음 |
| 예시 | 퀵 정렬, 병합 정렬, 이진 탐색 |
동적 프로그래밍 Dynamic Programming
동적 프로그래밍이란
동적 프로그래밍은 입력의 크기가 가장 작은 부분부터 해를 구해 저장하고, 저장한 해를 이용해 입력의 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 방식이다. 상향식(bottom-up) 접근 방법이다.
한 번 사용한 작은 문제의 해답이 더 큰 문제에서 재활용될 수 있으므로 중복 계산을 줄일 수 있으며, 따라서 작은 문제들은 서로 독립적일 필요가 없다.
동적 프로그래밍 요약
| 구분 | 내용 |
|---|---|
| 동적 프로그래밍 | - 이전 단계의 결과를 저장해 재활용함으로써 중복 계산을 줄이는 방식 |
| 장점 | - 중복 연산을 줄여 시간 복잡도를 감소시킬 수 있음 - 최적화 문제에서 매우 강력한 성능 |
| 단점 | - 해를 저장해야 하므로 메모리를 많이 사용할 수 있음 - 부분 문제 성질이 있는 문제에만 적용이 가능 |
| 예시 | 피보나치 수열, 배낭 문제, 최장 공통 부분 수열 |