[SW 정글 14일차] 분할 정복

1. 분할 정복

분할 정복은 주어진 문제를 원래 문제와 유사하지만 크기가 작은 몇 개의 부분 문제로 분할하고 부분 문제를 재귀적으로 풀고 찾은 해를 결합하여 원래 문제의 해를 만들어 내는 방법이다.

분할 정복으로 해결할 수 있는 예시는 하노이탑이 대표적일 것이다.

세 개의 기둥이 있고 n개의 원판이 있으면 규칙을 지키며 첫 번째 기둥에서 세 번째 기둥으로 옮겨야한다.

우리는 여기서 1 ~ n-1개의 원판을 두번째에 옮기고 n번째 원판을 세 번째 기둥으로 옮기고 마지막으로  1 ~ n-1개의 원판을 세번째 기둥으로 옮기면 문제가 해결된다.

즉, 전체 문제를 풀어해치는 것이 아닌 분할하여 재귀적으로 답을 얻어내는 것이다.

 

분할 정복은 세 가지 단계로 구성된다.

① 분할: 현재의 문제를 같은 문제를 다루는 다수의 부분 문제로 분할하는 과정

② 정복: 부분 문제를 재귀적으로 풀어서 정복

③ 결합: 부분 문제의 해를 결합하여 원래 문제의 해가 되도록 만드는 과정

 

출처: <파이썬 알고리즘 인터뷰>  p.548, 책만, 2020

 

 

분할 정복을 사용하기 위해서는 문제를 보고 어떻게 부분 문제로 쪼개어서 그 부분 문제를 해결하고 다시 합치는 것을 생각해내는 것이 중요한 것 같다.

처음에는 너무 어려웠고 지금도 너무 어렵다.

분할 정복에 대한 설명을 더 할 것이 없어 오늘 푼 문제들 중 분할 정복을 사용한 문제 풀이를 해보며 글을 마치려고 한다.

https://www.acmicpc.net/problem/1629

1629번: 곱셈

위 문제는 백준 온라인 저지에 있는 곱셈이라는 문제이다.

문제에 대한 설명을 간단히 하자면 입력값으로 세개의 자연수가 들어오고 순서대로 A, B, C라고 한다면 A를 B번 곱한 수를 C로 나눈 나머지를 출력하는 문제이다.

간단하게 A ** B % C로 풀려고 하면 오버플로우가 나기 때문에 분할 정복을 통해 값을 줄인 상태에서 연산을 진행하고 합쳐야한다.

 

이 문제를 풀기 위해서는 수학적 지식이 필요한 것같다.

나는 아래의 사이트에서 힌트를 얻을 수 있었다.

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-multiplication

모듈로 곱셈 (개념 이해하기) | 암호학이란? | Khan Academy

요점만 얘기하면 (A * B) mod C = (A mod C * B mod C) mod C라는 것이다.

이 원리를 이용하면 A ^ B가 아무리 크더라도 작은 수로 쪼개고(분할)

쪼개어진 수를 C로 나눈 나머지 값을 구하고(정복)

다시 구하고자 하는 값을 위해 합쳐주면 된다.(결합)

 

문제에서 주어진 예시를 이용하여 어떻게 진행되는지를 말해보면 일단은 전체 문제는 (10 ** 11) % 12를 구하는 것이다.

여기서, ( ((10 ** 5) % 12) * ((10 ** 5) % 12) * 10) % 12로 더 작은 수의 나머지를 구하는 것으로 바꿀 수 있다.

이 후에 더 작은 값, 제곱수가 1이 될때까지 쪼개어서 나머지를 계산하기 위해 재귀함수를 사용하고 다시 합치면 된다.

 

분할 정복을 경험한 후기는 이분 탐색처럼 문제 접근 개념은 간단하지만 어떻게 부분 문제로 쪼개야할지, 쪼개고 나서 어떻게 다시 합쳐야할지가 생각이 쉽게 나지 않는 것이다.

익숙해지기 위해 더 많은 문제들을 접하며 연습할 필요성을 느꼈다.

 

---

[오늘의 나는 어땠을까?]

오늘은 정글에 들어온 지 2주만에 부모님의 얼굴을 보았다.

내가 직접 집으로 간 것은 아니고 집이 가까워 부모님이 오셔서 같이 점심을 먹고 커피를 마시며 얘기를 했다.

오랜만에 봐서 반갑고 기쁜 마음도 있지만 한편으로는 뭔가 슬픈 마음도 있었다.

대학교 4학년 2학기부터 집으로 올라와 부모님과 같이 약 1년정도 살았지만 항상 부모님의 얼굴을 보면 늙어가고 있다는 것을 느껴본 적이 없다.

어쩌면 그때는 그러한 것을 신경쓰지 않았을지도 모른다.

하지만, 오늘은 부모님의 얼굴을 보았을 때 눈가에 진 주름과 피부를 보면 늙어가고 있구나 하는 것을 순간 느꼈다.

이것을 느낀 순간, 울컥했고 조금이라도 더 보면 눈물이 나올 것같았다.

하지만 꾹 참고 태연하게 대화를 이어가고 부모님과 다시 작별인사를 하고 강의실로 돌아왔다.

지금 이 글을 순간도 다시 그 장면을 생각하며 글을 쓰니 눈물이 난다.

나 뿐만 아니라 부모님도 간절히 바라는 나의 사회 생활 시작 즉, 취업을 해서 부모님의 걱정을 빨리 덜어드리고 싶고 주기적으로 부모님과 시간을 보내고 싶다.

그렇다고 섣불리 아무 곳이나 취업을 할 생각은 없고 지금 정글에서 쌓는 역량, 경험을 가지고 나의 성장을 이어나갈 수 있는 IT 서비스 회사로 취업을 할 것이다.

지금은 나 자신이나 나를 바라보는 부모님이나 많이 힘들지만 미래의 나의 모습을 기대를 하며 꿋꿋히 달려나갈 것이다.