[1] 분할 정복 (Divide and conquer) 알고리즘

[SW예비학교] 인공지능과 컴퓨팅사고

2023-01-14 

 

복잡한 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘인 분할 정복 알고리즘에 대해서 학습한다.

 

 

분할 정복 (Divide and conquer) 알고리즘

- 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘

- 분해 기법을 사용하여 어려운 문제를 해결

 

 

 

설계 요령

-1. Divide: 어려운 문제를 작은 문제로 분할

-2. Conquer: 작은 문제를 해결

-3. Combome: 작은 문제의 해답을 모아서 원래의 문제를 해결

 

 

 

 

분할 정복 알고리즘의 응용

 

-1. 거듭제곱 계산 (Exponentiation)

거듭제곱은 자신을 여러 번 곱해야 하므로 많은 시간이 소요됨.

 

Q. 3^8 =?

A. 

★-1. Divide: 3^8 = 3^4 x 3^4 =  (3^4)^2 = (((3^2))^2)^2)

★-2. Conquer: 3^2의 계산

★-3. Combine: ((3^2)^2)^2를 통해 3^8을 얻음

 

 

 

 

 

-2. 이진 탐색 (binary search)

정렬된 배열의 중앙에 위치한 원소와 비교를 되풀이하여 키워드와 매치되는 원소를 찾는 탐색 방법

 

이진 탐색의 기본 가정

1. 숫자들의 리스트가 있음

2. 숫자들은 크기 순으로 정렬되어 있음

 

Q. [1, 3, 5, 6, 7, 9, 11, 20, 30, 56] 리스트에서 30을 찾기

A. 

★-1. Divide: 리스트를 두 개의 서브 리스트로 나눈다.

★-2. Conquer: 리스트의 중앙에 있는 값을 탐색 값과 비교한다.

                       만약 일치하면 탐색 값을 찾은 것이므로 종료

                       만약 탐색 값이 중앙값보다 크면 우리가 찾고자 하는 값은 리스트의 후반부에 있을 것

                       리스트의 전반부는 탐색의 범위에서 제외할 수 있다.

★-3. Divide: 남아 있는 리스트를 두 개의 서브 리스트로 나눈다.

★-4. Conquer: 리스트의 중앙에 있는 값을 탐색 값과 비교한다.

                        만약 일치하면 탐색 값을 찾은 것이므로 종료

                        만약 탐색 값이 중앙값보다 크면 우리가 찾고자 하는 값은 리스트의 후반부에 있을 것

                        리스트의 전반부는 탐색의 범위에서 제외할 수 있다. 

★-5. Divide: 남아 있는 리스트를 두 개의 서브 리스트로 나눈다.

★-6. Conquer: 리스트의 중앙에 있는 값을 탐색 값과 비교한다.

                        만약 일치하면 탐색 값을 찾은 것이므로 성공

                        

★-7. Combine: 

 

※ 만약 Conquer 과정에서 탐색 값이 리스트의 중앙에 있는 값보다 작을 경우 전반부에 있을 것

 

 

 

 

순차 탐색 vs 이진 탐색

 

순차 탐색은 리스트의 처음부터 끝까지 순차적으로 키워드와 해당 원소를 비교하면서 찾는 방법

이진 탐색은 일반적으로 탐색 횟수가 순차 탐색에 비해서 훨씬 적음.

 

숫자 리스트에서 30을 찾기 예제에서의 탐색 횟수

- 이진탐색 -> 총 3번

- 순차탐색 -> 총 9번

 

10억 개의 원소가 있는 리스트에서의 탐색 횟수

- 이진탐색 -> 최대 30번

- 순차탐색 -> 최대 10억 번, 평균 5억 번

 

 

 

 

 

 

분할 정복 알고리즘 적용 예

-숫자 추측 게임

컴퓨터가 1~100 사이의 정수를 임의로 선택

이를 사용자가 숫자를 입력하여 컴퓨터가 선택한 정수를 알아맞힌다.

입력한 숫자가 맞지 않을 경우에는 컴퓨터가 선택한 정수와 비교하여 입력한 숫자가 크다/작다를 알려준다

이진 탐색 기법을 적용을 하면 입력 횟수를 줄일 수 있음.

※ 최대 log2(100) ~=7번 입력하면 찾을 수 있음

 

 

 

 

참고하면 좋을 영상

https://www.youtube.com/watch?v=WjIlVlmmNqs