코딩으로 보는 문제 해결 전략

코딩에서 사용되는 문제 해결 전략 4가지를 소개하고자 합니다.

1. Brutu-Force Approach

2. Divde and Conqure Approach

3. Dynamic programming Approach

4. Greedy Approach

이번 포스팅에서는 간단하게 4개에 대한 소개 및 간략한 예시를 보여 드리겠습니다.

다음 포스팅에서부터 각각에 대한 자세하게 코딩과 설명을 같이 해보려고 합니다!

일단! 대망의 첫 번째!!

1. Brutu-Force Approach

한국어로 표현하자면 '전수조사 알고리즘' 입니다.

전수조사는 모든 경우의 수를 찾아보는 것으로, 전수조사 알고리즘도 똑같이 모든 경우의 수를 찾아보는 것입니다.

한 가지 예를 들어보겠습니다.

A가 서울에서 부산까지 가려고 합니다.

여러분들이 서울에서 부산을 가려고 할 때는 가장 안막히고, 가장 빠른 길을 선택 하겠죠?

A 또한 그럴 것입니다. A는 서울에서 부산까지 가장 빠른 길을 찾기 위해 갈 수 있는 모든 길을 찾아보기로 했습니다.

A는 대전이나 원주를 지나쳐 부산을 갈수도 있고, 아니면 길을 잘 몰라서 전라도 쪽으로 갔다가 부산을 갈 수도 있습니다.

서울에서 부산을 가는 방법이 수백, 수천, 수만가지가 될텐데 이걸 전부다 조사해서 걸리는 시간을 알아보는 것이 바로 전수조사 입니다.

경우의 수가 많은 경우에는 모든 것을 알아봐야 하기 때문에 시간이 많이 듭니다.

정리하자면, Brute-Force Approach(전수조사)는 모든 case에 대해 계산을 해보고 그 중에서 가장 빠른 것을 찾는 것 입니다.

2. Divde and Conqure Approach

한국어로 표현하자면 '분할정복 알고리즘' 입니다.

하나의 큰 문제를 잘게 잘라서 나눠서 계산을 수행하는 것입니다.

파X바게트에서 큰 케익을 하나 삿다고 생각해봅시다.

이 큰 케익을 한번 자르게 되면 두 개가 되겠죠?

그럼 큰케익 하나를 먹는 것 보다는 두 개로 나뉜 것 중 하나만 먹는게 더 쉽게 먹을 수 있겠죠?

아직도 먹기에 버거우신가요?!

그럼 한번 더 반씩 나눠봅시다.

그럼 총 4조각()이 되죠?

그럼 한 번 더 나눠보도록 하죠.

이제는 총 8조각()이 되었습니다.

큰 케익을 이렇게 계속 반씩 나눠가면 점점 작아지면서 균일하게 반씩 나눠지게 됩니다 (1:1로 나눠지지 않아서 1:2로 나누는 경우도 있습니다). 충분히 먹을 수 있을만큼 작아지면 이제 먹기 시작합니다.

그럼 위에서 나눈 8조각을 먹어보도록 하겠습니다.

한 조각씩 먹게 되면 큰 케익을 통째로 먹는 것보다 편하게 먹을 수 있습니다.

분할정복 알고리즘도 위의 케익 문제와 비슷하게 큰 문제를 잘게 나누어 문제를 푸는 방법입니다.

3. Dynamic Programming Approach

한국어로 표현하자면 '동적 계획법' 입니다.

동적 계획법은 주어진 문제를 하위로 나누어서 해결하는 것입니다.

언뜻 보기에는 위에서 설명한 분할정복과 같아 보입니다. 그러나 가장 큰 차이점이 있습니다!

동적 계획법은 하위 문제가 서로 종속성을 가질 때 사용됩니다.

즉, 위에서 말한 Divde and Conqure Approach(분할정복)는 병렬적으로 해결 되므로 종속성이 없는 것에서 사용 가능하고, 동적 계획법은 하위 문제가 서로 종속성을 가질 때 사용됩니다.

일단, 분할정복을 먼저 보면, 분할정복은 위의 케익 문제에서 8개로 잘라진 케익들이 서로 종속적인 관계가 없을 때 사용하는 방법입니다. 즉, 잘라진 케익에서 오른쪽에 있는 케익과 왼쪽에 있는 케익을 서로 합쳤을때는 전에 자르기 전의 케익이 나오는데, 자르기 전의 케익의 옆에 있는 케익과는 전화 관련이 없는 것과 같은 것 입니다.

아래와 같이 8조각이 있었을 때, 파란색에 해당하는 2조각은 초록색에 해당하는 2조각과는 전혀 상관 없습니다 (물론 전체를 합치면 연결되어 있지만 한번 잘라지면 거기서는 관련이 없어집니다). 

만약, 파란색에 해당하는 1조각이 초록색, 파란색 둘다 관련이 있게 되는데, 초록색의 1조각이 파란색에 해당하는 1조각이 변할 때 같이 변하게 되면, 그 때는 종속성을 가집니다.

그러므로, 이 케익은 종속성을 가지므로 '동적 계획법'을 이용해서 문제를 풀어야 합니다.

4. Greedy Approach

한국어로 표현하자면 '탐욕 알고리즘' 입니다.

탐욕 알고리즘은 동적 계획법과 상당히 비슷합니다.

그러나, 탐욕 알고리즘과 동적 계획법의 큰 차이는 부분을 보고 판단하는 것과 전체를 보고 판단하는 것에 차이가 있습니다.

동적 계획법은 주어진 문제를 하위로 나누어서 해결할 때, 하위 문제와 상위 문제들 전체를 판단한 최적해를 이용하나,

탐욕 알고리즘의 경우는 하위 문제에서 최적해를 바로 찾아버리고 다음으로 넘어가게 되는 것이 됩니다.

간단하게, 서울에서 부산을 가는 최단 시간을 찾는 알고리즘을 구현하고자 할 때, 서울에서 갈때 대전(2시간 반), 원주(1시간 반), 충주(2시간)를 거쳐가는 방법이 있다고 했었을때, 서울에서 원주로 갈때가 가장 빠르게 가는 것이라면 원주를 선택하는 것을 '탐욕 알고리즘'이고, 서울에서 부산을 갈때 대전을 통해서 가는 것이 전체적으로 봤을때는 최단 시간이라면 대전을 선택하는 것이 '동적 계획법' 입니다 (종속성이 있다고 가정하에).

	대전	원주	충주
서울	2시간 30분	1시간 30분	2시간
부산	3시간	4시간 30분	4시간
총 시간	5시간 30분	6시간	6시간

이것처럼 몇 개가 안되는 변수가 있는 경우는 동적 계획법을 이용하는 것이 '최적해'를 찾기에 좋고, 변수가 많은 경우에는 계산 시간이 오래 걸리기 때문에 탐욕 알고리즘을 이용해서 계산 하는 것이 효율적입니다.

출처 - T 아카데미 중급 알고리즘 강의, 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략(책)