[Inflearn] 합이 같은 부분집합(DFS) (Amazon interview source)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - 두 개의 부분집합으로 나누었을 때 두 부분집합 원소의 합이 서로 같은 경우가 존재하는가

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

> 입력이 아래와 같을 때,

6

1 3 5 6 7 10

부분집합 {1,3,5,7}, {6,10} 의 각 원소들의 합은 16으로 같은 경우가 존재한다.

일단 주어진 배열이 있으니까 이진트리로 그려보자

          1

   3              5

6     7     10

이... 이진트리 같..

이전 문제에서는 주어진 배열이 없었기때문에

자식노드의 index를 신경쓰지 않았지만 

이번 문제는 배열이 주어졌으므로 자식노드에 접근할 때 idnex를 신경써주어야 할 것이다.

이전문제와 비슷하게 풀어내면 될 것 같은데..

이진트리같은 Sound..

이진트리로는 안 풀릴 것이고,

배열의 index로 각 원소를 참조해야할 것 같다.

이럴땐 뭐라고~~~!?

스택을 그려보면서 해보자!

먼저 f(1) 이 들어갈 것이다.

f(1)

f(1) 에서 {1 3} {1 5} {1 6} .. {1 3 5} {1 3 6} .. 

이렇게 하나씩 붙여가면서 부분집합을 만들 수 있다.

이 문제도 함수의 호출 구조를 이진트리로 만들어보자.

                                                                             f(1)    

                                 f(3)                                                                        f(3)                       

               f(5)                                   f(5)                                  f(5)                                   f(5)

      f(7)              f(7)                f(7)               f(7)          ....

f(10)    f(10)    f(10)    f(10)    f(10)     f(10)     f(10)    f(10)     ...

두둥.. 거대한 이진트리가 생성되었다. 

이 문제도 이전 문제와 유사하게 Lv 로 접근하면서 마지막에 출력대신 sum 을 구해주고

아, 일단 여기서 배열 요소의 최대 합 크기만큼의 배열이 필요할 것 같다.

N이 커지면 힘들어지겠지만 우선은.. 

if(lv == n + 1) 

{ 

사용된 원소들의 sum 을 구해주고 sumList 에서 해당 sum 이 나온 적이 있는지 확인

나온 적이 없다면 sumList 의 해당 sum index 에 1을 표시해주고

나온 적이 있다면 YES 를 출력해주고 return 0;

(NO main() 에서 해줘야겠쥬?)

}

else

{

a[lv] = 1;

f(lv + 1);

a[lv] = 0;

f(lv + 1);

}

>> 아무리 디버깅해봐도 잘못된 부분이 없는데 계속 틀리다고하는 1개의 test case 가 있어서

강사님의 힌트를 보았는데..

와 문제를 완전 잘못 이해하고 있었네..

심각한 실수다..

입력된 수들은 자연수 집합이고 이 집합을 "두 개의 부분집합으로 나누었을 때" 두 부분집합의 원소의 합이다.

1 3 5 6 7 10 이라는 부분집합이 있을 때,

{1, 5, 7, 10} 을 사용하여 부분집합을 만들었다면 {3, 6} 이라는 나머지 수로 부분집합을 만들어서 나누라는 말이다..

와.. 문제 제대로 이해하고 풀자ㅠㅠ

그래도 만들어놓은 코드에서 조금만 수정할 수 있다.

if(lv == n + 1) 

{ 

사용된 원소들의 sum 을 구해주면서, 사용되지 않은 원소들의 sum 도 같이 구해준다.

그 다음 두 부분집합의 sum 을 비교해서 같다면 YES 를 출력해주고 종료시키면 된다.

(NO main() 에서 해줘야겠쥬?)

}

else

{

a[lv] = 1;

f(lv + 1);

a[lv] = 0;

f(lv + 1);

}

이제 문제 제대로 이해하고 재정의한 후 풀어야겠다.

정말.. 후아..

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N, set[11], chk[11];
 
void DFS(int lv)
{
    int i, sum1 = 0, sum2 = 0;
 
    if (lv == N + 1)
    {
        for (i = 1; i <= N; i++)
        {
            if (chk[i] == 1)
                sum1 += set[i];
            else
                sum2 += set[i];
        }
 
        if (sum1 == sum2)
        {
            printf("YES\n");
 
            exit(0);
        }
    }
    else
    {
        chk[lv] = 1;
        DFS(lv + 1);
 
        chk[lv] = 0;
        DFS(lv + 1);
    }
}
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int i, sum = 0;
 
    scanf("%d", &N);
 
    for (i = 1; i <= N; i++)
        scanf("%d", &set[i]);
 
    DFS(1);
 
    printf("NO\n");
 
    return 0;
}

#. Other code

#include<stdio.h>
 
int n, a[11], total=0;
bool flag=false;
 
void DFS(int L, int sum){
    if(sum>(total/2)) return;
    if(flag==true) return;
    if(L==n+1){
        if(sum==(total-sum)){
            flag=true;
        }        
    }
    else{
        DFS(L+1, sum+a[L]);
        DFS(L+1, sum);
    }
}
 
int main(){
    int i;
    scanf("%d", &n);
 
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
        total+=a[i];
    }
 
    DFS(1, 0);
 
    if(flag) printf("YES\n");
    else printf("NO\n");
 
    return 0;
}

sum 을 인자로 넘겨주면서 더 효율적인 코드가 되었다..!

line 7 은 넘어온 sum 이 total/2 보다 클 경우 return 을 해준다.

이 이유는 sum 과 total-sum 을 비교해서 답을 구하는데 sum이 total/2보다 크다면

그 다음 단계들도 정답이 될 수 없으므로 불필요한 작업을 줄여주는 것이다. 

line 8 에서는 sum == total-sum 인 두 부분집합이 존재한다면 return 을 해준다.

flag가 전역변수로 true로 저장되어있다면 넘어오는 호출들이 다 종료가 될 것이다.

line 10~11 에서 마지막 레벨까지 도달했을 때 sum 값을 확인한다.

total 은 모든 원소들의 합으로 total-sum 을 해주면 사용되지 않은 원소들의 합을 알 수 있다.

나는 계속 for문을 돌리면서 사용된 원소들의 합과 사용되지 않은 원소들의 합을 구했는데.. 굉장히 비효율으로..흑

line 15~16 에서 다음 레벨로 이동하는데, sum 을 같이 넘겨준다.

해당 원소를 사용할 경우 sum 에 더해서 넘겨주고,

해당 원소를 사용하지 않을 경우 sum 만 넘겨주도록 되어있다.

완전히 이해하고 넘어가는게 좋을 것 같아서,

강사님 말씀처럼 이 과정들을 그림으로 그려보려고 한다.

첫 번째 인자는 level, 두 번째 인자는 sum 이다.

D(level, sum)

sum 이 total/2(16) 보다 클 경우 더이상 계산해볼 필요가 없으므로 return 해준다.

line 15, 16 과정을 그려보았는데 두 줄의 코드가 이렇게나 많은 연산을 하게 된다..

비워둔 경우를 모두 채우기에는 버거워서.. 이정도만 그려본다.

누적된 값이 필요한 경우 이렇게 sum 을 인자로 함께 넘겨주는 방법도 좋은 것 같다.

아직도 헷갈린 부분이 있지만 하다보면 익숙해지겠지..

#. Result

  - Input --------------------------------------------------------

6

1 3 5 6 7 10

------------------------------------------------------------------

  - Output --------------------------------------------------------

YES

------------------------------------------------------------------