[Inflearn] 부분집합(DFS) (MS 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

     - 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력

  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

  1. 아직 재귀함수 사용이 익숙하지 않다..

     많이 접하다보면 익숙해지겠지...?

  2. 결국 강사님의 힌드를 얻었다..

     N = 3 일 경우,

      1 2 3

      1 2

      1 3 

      1 

      ... 

     출력 형식을 따라야 하므로,

     아래와 같은 이진 트리를 그릴 수 있다.

                                 f(1)

                 f(2)                            f(2)  

         f(3)            f(3)             f(3)            f(3)

     f(4)    f(4)     f(4)    f(4)    f(4)    f(4)    f(4)    f(4)

     여기서 왼쪽으로 내려갈 경우 n 을 사용한 부분집합이 되고,

     오른쪽으로 내려갈 경우 n 을 사용하지 않은 부분집합이 된다.

     n+1 크기의 배열을 만들어두고,

    집합의 사용 여부를 1 or 0 으로 저장한다. 

    그 후 f(4) 가 호출될 때 배열을 탐색하면서 1로 체크된 index 를 출력하면 된다.

    스택을 그려보면서 어떻게 구현해야할지 생각해보자.

    

f(1)

f(1) 이 호출되면 먼저 왼쪽 자식부터 탐색을 한다.

왼쪽으로 내려갈 경우 배열에 1로 체크를 해야하므로,

(+각 Level 의 정보를 저장할 변수가 필요할 것 같다.)

lv = 1;

if(lv == n + 1) { 출력 }

else

{

    a[lv++] = 1;   // 배열의 index 번째 자리에 1로 표시를 한다.

    f(x*2);   // 왼쪽 자식을 탐색한 후

}

먼저 배열에 담고 호출을 해야할 것 같다. f(4) 에서 출력을 해주어야 하므로.

그럼 배열에 담고 다음 line 으로 이동하여 자식 노드를 호출한다.

 

1	2	3
1

f(2)

f(1)

...

1	2	3
1	1	1

f(8)

f(4)

f(2)

f(1)

lv 이 4가 되었으므로 배열의 원소가 1인 index 들을 출력해준다.

1 2 3

1	2	3
1	1	1

f(4)

f(2)

f(1)

f(8) 은 stack 에서 삭제되고 다음 f(9) 차례다.

함수가 끝날 때, lv 을 감소시켜줘야 할 것 같다. 

if(lv == n + 1) { 출력 }

else

{

    a[lv++] = 1;   // 배열의 index 번째 자리에 1로 표시를 한다.

    f(x*2);   // 왼쪽 자식을 탐색한 후

    a[lv++] = 0;

    ff(x*2+1);

}

lv--;

1	2	3
1	1	0

f(9)

f(4)

f(2)

f(1)

여기도 마찬가지로 lv 이 4가 되었으므로 배열의 원소가 1인 index 들을 출력해준다.

1 2 

f(9) 은 stack 에서 삭제되고 f(4) 도 모든 동작이 끝났다.

f(4) 도 stack 에서 삭제해준다.

1	2	3
1	1	0

f(2)

f(1)

그 다음은 f(2) 의 다음 라인 오른쪽 자식으로 내려갈 차례이다.

...

이와 같은 방법으로 대충 어느정도 구현이 잡힌 것 같다.

if(lv == n + 1) { 출력 }

else

{

    a[lv++] = 1;   // 해당 Lv의 배열 자리에 1로 표시를 한다.

    f(x*2);   // 왼쪽 자식을 탐색한 후

    a[lv++] = 0;   // 해당 Lv의 배열 자리에 0으로 표시를 한다.

    ff(x*2+1);  // 오른쪽 자식을 탐색

}

lv--;   // 함수가 끝나면 lv을 감소시켜준다.

긴가민가 하지만 이 과정대로 한번 구현을 해볼까..?

#. Code

1. 띠용하게 짰던 코드

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N, Lv = 1;
int a[11];
 
void DFS(int x)
{
    if (Lv == N + 1)
    {
        int i;
 
        for (i = 1; i <= N; i++)
        {
            if (a[i] == 1)
                printf("%d ", i);
        }
 
        puts("");
    }
    else
    {
        a[Lv++] = 1;
        DFS(x * 2);
 
        a[Lv++] = 0;
        DFS(x * 2 + 1);
    }
 
    Lv--;
}
 
int main(void)
{
    //freopen("input.txt", "rt", stdin);
 
    scanf("%d", &N);
 
    DFS(1);
 
    return 0;
}

어느정도 시뮬레이션을 하면서 대략적인 코드를 짜놓고

실제 코드로 옮기니까 바로 실행될 수 있었다.

재귀함수는 복잡한만큼 나처럼 천재가 아닌 이상은..

그냥 머리로만은 해결하기 힘든 것 같다..

스택에 직접 과정을 그려보면서 동작을 간략하게 코드로 짜놓으면

구현하기 좋을 것 같다.

전에는 맨날 머리로만 하려고 하다가 결국 구현해내지 못 했는데..

뭔가 재귀함수에 대한 깊은 깨달음이다..!

--

내가 실수(?)는 아니지만 바보같은 짓을 해버렸다.

이진트리를 접근하는 것처럼 짜버려서 불필요한 변수가 생기고, 불필요한 연산을 해버렸다.

물론 함수의 호출 구조가 "이진트리처럼" 생긴건 맞지만 이진트리를 사용하고 있는건 아니지 않은가...!

허허..

                                 f(1)

                 f(2)                            f(2)  

         f(3)            f(3)             f(3)            f(3)

     f(4)    f(4)     f(4)    f(4)    f(4)    f(4)    f(4)    f(4)

풀이에서 그려본 이 이진트리는 함수의 호출 구조를 그린 것이다.

트리를 접근하는 것이 아니라.

그래서 DFS(x+1)이 오른쪽 자식노드도 되고, 왼쪽 자식노드도 될수 있는 것이다.

재귀함수를 너무 이진트리라고만 생각했었다..

2. 깨달음을 얻고 다시 짠 코드

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N, a[11];
 
void DFS(int x)
{
    if (x == N + 1)
    {
        int i;
 
        for (i = 1; i <= N; i++)
        {
            if (a[i] == 1)
                printf("%d ", i);
        }
 
        puts("");
    }
    else
    {
        a[x] = 1;
        DFS(x+1);
 
        a[x] = 0;
        DFS(x+1);
    }
}
 
int main(void)
{
    scanf("%d", &N);
 
    DFS(1);
 
    return 0;
}

#. Other code

#include <stdio.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, ch[100];
 
void DFS(int L){
    int i;
    if(L==n+1){
        for(i=1; i<=n; i++){
            if(ch[i]==1) printf("%d ", i);
        }
        puts("");
    }
    else{
        ch[L]=1;
        DFS(L+1);
        ch[L]=0;
        DFS(L+1);
    }
}    
 
int main(){
    freopen("input.txt", "rt", stdin);
    scanf("%d", &n);
    DFS(1);
    return 0;
}

내가 크게 착각하고 있던게 있었다.

이진트리처럼 접근해야하는 줄 알고 

자식 노드의 index에 접근하기 위해 * 2, * 2 + 1 을 해주고 있었다...

여기서 만들었던 이진트리는 함수의 호출이 이진트리 모양으로 이루어진다는 것이었는데...

또 깊은 깨달음을..

#. Result

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

3

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

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

1 2 3

1 2

1 3

1

2 3

2

3

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