45. 부분집합의 합 (subset sum) 알고리즘

1. 개요

부분집합의 합 알고리즘은 조금 까다로움.

아직 머릿속으로 정확한 개념이 완전히 잡히지 않음.

확실한 건 DP 방식은 초기 테이블 즉, 가장자리 부분을 초기화 한 뒤

이 초기화 한 값으로 문제를 풀이해 나감.

그렇기에 처음 초기화하기 위한 공간을 위해 일반 배열보다 1씩 더 클 수 있음.

또한 이번 문제에서 메모이제이션과 DP 방식의 속도는 엇 비슷할 줄 알았는데

처음으로 예상이 엇나감.

아마 메모이제이션을 잘못 짰다고 생각. 

더 좋은 방식있으면 수정.

부분집합의 합이란 집합 내의 원소 n개를 더해서 숫자 m을 만들 수 있는 지 확인하는 문제.

2. 문제

주어진 집합 n개의 원소로 총합 m을 만들 수 있는 프로그램을 작성하시오.

(재귀, 메모이제이션, DP, 그리고 부분집합은 무엇인지 출력하시오.)

3. 코드

3-1) Brute_Force()

3-2) Memoization()

3-3) Dynamic_Programming()

3-4) Back_Track()

3-5) n == 5 출력

3-6) n == 10 출력

3-7) n == 15 출력

3-8) n == 25 출력

3-9) n == 35 출력

결과 값 1은 가능하다는 것, 0은 불가능

4. 정리

 위의 출력 값을 보면 메모이제이션보다 DP 방식이 훨씬 빠르다. 아마 내가 메모이제이션 방식을 잘못 짠 부분이

있을 것이다. 하지만 그것을 제외하고서라도 아직 두 방식의 정확한 접근이 기초 수준인것 같다. 알듯 알듯 

손아귀를 빠져나간다. 조금 더 생각하고 노력하자.