[회고] 신입 iOS 개발자가 되기까지 feat. 카카오 자세히보기

💻 CS/알고리즘 연습

[알고리즘 연습] 부분집합 (DFS)

inu 2021. 2. 5. 15:06

부분집합

  • 자연수 N을 입력받는다.
  • 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하시오.

입력예제

3

출력예제

1 2 3 1 2 1 3 1 2 3 2 3

풀이

#include <iostream> using namespace std; int n; int ch[11]; void DFS(int level) { ​​​​if (l > n) { ​​​​​​​​int i; ​​​​​​​​for (i=1; i<=n; i++) { ​​​​​​​​​​​​if (ch[i]==1) cout << i << " "; ​​​​​​​​} ​​​​​​​​cout << endl; ​​​​​​​​return; ​​​​} ​​​​ch[level] = 1; ​​​​DFS(level+1); ​​​​ch[level] = 0; ​​​​DFS(level+1); } int main() { ​​​​cin >> n; ​​​​DFS(1); ​​​​return 0; }
  • DFS를 활용하는 문제이다.
  • 1부터 N까지이므로, 1부터 N까지 내려가면서 부분집합에 해당 수가 포함되는지 여부를 체크하면 된다.
  • 1~N까지를 level 변수로 표현했다.
  • ch[level] = 1일 경우 level단계의 수가 부분집합에 포함된다는 것이고, ch[level] = 0일 경우 level단계의 수가 부분집합에 포함되지 않는 것이다.
  • 아직 재귀함수 및 DFS에 익숙하지 않은 것 같다. 많이 연습하자.