[알고리즘] Meet in the middle 알고리즘

백준 1450번 (냅색문제)를 풀기위해 학습한 Meet in the middle 알고리즘을 정리하고자 한다.

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

1450번: 냅색문제

 

Meet in the middle, 말 그대로 중간에서 만나자!

그럼 왜 중간에서 만나야 하며, 어떻게 중간에서 만날까?

 

위 문제를 바탕으로 한번 소개해 보겠다.

 

위 냅색 문제는

세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.
N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

가방에 넣을 수 있는 방법의 수를 구하는 것이다. 

 

만약 입력이

N =7 , C가 5라고 하면 밑에 과정을 봐보자,

위와같은 방법으로 left에 있는 모든 수에 대해 진행해 주면 된다.

!!!주의)) 위에서는 설명하기 위해 쓰지 않았지만, left, right에 각각 값 0도 들어가야 한다. (해당 문제는 하나도 가방에 넣지 않을 수도 있기때문, and left나 right에서 어떤것도 넣지 않았을 경우)

만약 n이 주어질 수 있는 최대 값인 30이 주어진다면.. ( 문제에서 정의) 

(2)번 과정에서, 모든 합의 경우의 수를 구해야 하기 때문에, 만약 left , right를 나누지 않는다면,

 

2(넣거나 안넣거나)^30 이 되는 것을 볼 수 있다. 약 10억 자리의 수가 나오는 걸 알 수 있을것이다.

하지만 left,right를 나누게 된다면.. 2^15 * 2 반으로 나누는 것만으로도 65,536개로 엄청나게 줄어든 걸 확인 할 수 있다.

이처럼, 모든 경우의 수를 찾아야 하나(브루트 포스, 완탐) 많은 수의 연산을 해야될때, 위와 같이 Meet in the middle 알고리즘,

즉, left와 right를 나눠서 해결방법을 찾는것이다.(어느 문제든 되는건 아니다.)