분할정복(백준 알고리즘 5904번)

♣ 문제 이해

 

moo 수열이 규칙에 따라 반복되는데, 주어진 n번째 글자가 m인지 o인지를 판별하는 문제이다. 

 

 

♣ 문제 해결

분할정복으로 분류되어 있지만 마치 DP처럼 풀었다. 어떤 부분에서 분할정복과 DP를 구분할 수 있는지 잘 모르겠다. 

 

DP처럼 함수를 만드는데, 조건을 네 가지로 나누어서 코드를 구성하였다.

 

1. 예외 처리

n이 3과 같거나 작아서 0번째 Moo 수열에서 판별이 가능할 때 

 

 

2. 예외 처리가 되지 않을 때는 이전 단계의 Moo 수열의 길이, 중간에 들어갈 m + o *(k+2) 의 길이, 이번 단계의 Moo 수열의 길이를 이용하여 세 가지 경우로 나눈다. 

2-1. n이 이전 단계의 Moo 수열의 길이보다 작거나 같을 때. 

이전 단계에서도 구할 수 있으므로 k-1 단계에서의 Moo 수열을 구한다. 

2-2. n이 이전 수열에다가 중간에 들어갈 m + o*(k+2) 를 더한 값과 같거나 작을 때

new_moo 는 첫 번째 글자만 m이고 그 이후로는 모두 o로 이뤄져 있다. 따라서 n이 이전 단계보다 1 큰 수이면 m에 해당할 것이고, 그 외의 경우라면 모두 o이다. 

2-3. n이 이전 수열에다가 중간에 들어갈 m + o*(k+2) 를 더한 값보다 클 때

이 경우, n에서 (이전 수열에다가 중간에 들어갈 m + o*(k+2) 를 더한 값)을 뺀 값에 해당하는 글자를 이전 수열에서 찾는 것과 답이 같다. 어차피 m + o*(k+2) 이후로 이전 수열이 한 번 더 반복되기 때문이다. 

 

이 모든 단계를 담은 함수이다. 

 

마지막으로 while문을 사용하여 n과 같거나 큰 Moo 수열이 되는 단계를 구한다. 

 

몇 번째 단계(k)의 Moo 수열에서 n번째 글자를 찾아야 하는지 알게 되면 moo(n, k)를 실시한다. 

 

 

♣ 전체 코드

 

 

♣ DP vs 분할정복

DP와 분할정복은 문제를 작게 쪼개서 가장 작은 단위로 분할한다는 점에서 비슷한 형태의 알고리즘으로 보인다. 하지만 차이점이 있는데, DP는 상향식 접근법을 사용하고 분할정복은 하향식 접근법을 사용한다는 것이다. 

 

DP에서는 가장 작은 해답을 저장한 후, 해당 결과값을 이용해서 상위 문제를 풀어간다. DP 방식대로 위의 문제를 해결했더라면 while문에서 최종적인 k단계를 얻어서 moo를 실행하는 게 아니라, k를 1씩 늘려가면서 moo 를 실행해서 각 단계에 맞게 순차적으로 Moo 수열을 구했을 것이다. 

 

실제로 나는 DP와 분할정복을 잘 구분하지 못해서 처음에는 문제를 DP로 풀려고 코드를 아래와 같이 짰다. 

 

 

while문의 조건을 만족하는 k를 얻을 때까지 상향식으로 moo(n, k)를 실시하려고 한 것이다. 그런데 이러면 원하는 k단계에 이르기 전까지의 모든 단계의 return 값을 print 하게 된다. 

 

하지만 위의 코드에서는 while문으로 적합한 k단계를 구하고, 이에 해당하는 Moo 수열을 먼저 구한 후 하향식으로 내려간다. k 단계 이전의 Moo 수열의 길이보다 n이 작으면 moo(n, k-1) 을 실행하는 것이다. 즉 최종 단계의 Moo 수열을 구한 후 조건에 맞게 이전 단계를 탐색하는 과정을 진행한다. 

 

코드를 보면 어느 부분이 다른지 이해되지만, 문제만 읽고서는 DP인지 분할정복인지 구분하기가 어려웠다. DP에서는 메모이제이션을 사용할 수 있고, 분할정복은 하향식이므로 메모이제이션을 사용하지 않는다고는 한다. 대신 분할정복에서는 재귀함수를 주로 사용한다. 분할정복과 DP 문제를 좀 더 풀어보면서 구분되는 사항을 더 찾아봐야겠다. 

 

 

 

♣ 참고 자료

https://devraphy.tistory.com/67

Advanced Algorithm - 동적 계획법(DP) & 분할정복(Divide&Conquer)

https://syujisu.tistory.com/entry/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95-Dynamic-Programming%EA%B3%BC-%EB%B6%84%ED%95%A0-%EC%A0%95%EB%B3%B5-Divide-and-Conquer-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer) 알고리즘