1. 프로그래밍 인사이트에서 발간한 알고리즘 트레이닝을 시작했습니다.
2. 첫장에 재귀를 사용해서 부분집합을 구하는 알고리즘이 나오는데 재귀 함수 따라가다가 멘붕이 와서 정리해둡니다. 으악!
Q. 원소가 n개인 집합의 모든 부분집합을 생성해보자.
ex) {1, 2, 3}의 부분집합은 공집합{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} 입니다.
이 부분집합을 재귀 알고리즘을 이용해 구한 예제 코드가 있습니다. (C++)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <vector>
#include <iostream>
using namespace std;
vector<int> subset;
int n = 3;
void print(std::vector<int> const& input)
{
cout << "subset 확인 { ";
for (auto const& i : input) {
std::cout << i << " ";
}
cout << "}\n";
}
void search(int k) {
cout << "###################### search(" << k << ") START ######################\n";
if (k == n + 1) {
cout << "k값이 원소 개수보다 큼. exit...\n";
}
else {
print(subset);
cout << "subset PUSH 현재 search(" << k << ") 실행중...\n";
subset.push_back(k);
print(subset);
search(k + 1);
print(subset);
cout << "subset POP 아직 search(" << k <<") 실행중...\n";
subset.pop_back();
print(subset);
search(k + 1);
}
cout << "###################### search("<< k <<") END ######################\n";
//print(subset);
}
int main()
{
search(1);
}
|
cs |
핵심 로직은 간단합니다.
k값이 원소 개수보다 작으면
subset 배열에 k를 push 한 후 search(k+1)을 호출!
search 함수가 종료되면, subset의 값을 pop한 후 다시 search(k+1)을 호출!
이걸 반복하는 겁니다.
계속 search 함수를 재귀호출 하는거죠~
그런데 문제는 제 머리가 이거를 못따라간다는거 ㄷㄷ
결과
| ###################### search(1) START ###################### subset 확인 { } subset PUSH 현재 search(1) 실행중... subset 확인 { 1 } ###################### search(2) START ###################### subset 확인 { 1 } subset PUSH 현재 search(2) 실행중... subset 확인 { 1 2 } ###################### search(3) START ###################### subset 확인 { 1 2 } subset PUSH 현재 search(3) 실행중... subset 확인 { 1 2 3 } ###################### search(4) START ###################### k값이 원소 개수보다 큼. exit... ###################### search(4) END ###################### subset 확인 { 1 2 3 } subset POP 아직 search(3) 실행중... subset 확인 { 1 2 } ###################### search(4) START ###################### k값이 원소 개수보다 큼. exit... ###################### search(4) END ###################### ###################### search(3) END ###################### subset 확인 { 1 2 } subset POP 아직 search(2) 실행중... subset 확인 { 1 } ###################### search(3) START ###################### subset 확인 { 1 } subset PUSH 현재 search(3) 실행중... subset 확인 { 1 3 } ###################### search(4) START ###################### k값이 원소 개수보다 큼. exit... ###################### search(4) END ###################### subset 확인 { 1 3 } subset POP 아직 search(3) 실행중... subset 확인 { 1 } ###################### search(4) START ###################### k값이 원소 개수보다 큼. exit... ###################### search(4) END ###################### ###################### search(3) END ###################### ###################### search(2) END ###################### subset 확인 { 1 } subset POP 아직 search(1) 실행중... subset 확인 { } ###################### search(2) START ###################### subset 확인 { } subset PUSH 현재 search(2) 실행중... subset 확인 { 2 } ###################### search(3) START ###################### subset 확인 { 2 } subset PUSH 현재 search(3) 실행중... subset 확인 { 2 3 } ###################### search(4) START ###################### k값이 원소 개수보다 큼. exit... ###################### search(4) END ###################### subset 확인 { 2 3 } subset POP 아직 search(3) 실행중... subset 확인 { 2 } ###################### search(4) START ###################### k값이 원소 개수보다 큼. exit... ###################### search(4) END ###################### ###################### search(3) END ###################### subset 확인 { 2 } subset POP 아직 search(2) 실행중... subset 확인 { } ###################### search(3) START ###################### subset 확인 { } subset PUSH 현재 search(3) 실행중... subset 확인 { 3 } ###################### search(4) START ###################### k값이 원소 개수보다 큼. exit... ###################### search(4) END ###################### subset 확인 { 3 } subset POP 아직 search(3) 실행중... subset 확인 { } ###################### search(4) START ###################### k값이 원소 개수보다 큼. exit... ###################### search(4) END ###################### ###################### search(3) END ###################### ###################### search(2) END ###################### ###################### search(1) END ###################### |
재귀함수는 조금만 복잡해져도 따라가기가 힘드네요...
저렇게 하나하나 찍어보지 않으면 머릿속에서 따라가다가 끈을 놓쳐요!! 아오!!
호출 스택을 그림으로 그려도 헷갈리고.. 저렇게 하나씩 찍어보는게 차라리 가독성이 좋은 것 같습니다.
추가로 해당 vector들을 set에 담아서 유니크한 vector만 남기면 기대하던 부분집합이 나옵니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include <vector>
#include <iostream>
#include <set>
using namespace std;
vector<int> subset;
set<vector<int>> uniqueSubset;
int n = 3;
void print(std::vector<int> const& input)
{
cout << "subset 확인 { ";
for (auto const& i : input) {
std::cout << i << " ";
}
cout << "}\n";
}
void search(int k) {
cout << "###################### search(" << k << ") START ######################\n";
if (k == n + 1) {
uniqueSubset.insert(subset);
cout << "k값이 원소 개수보다 큼. exit...\n";
}
else {
print(subset);
cout << "subset PUSH 현재 search(" << k << ") 실행중...\n";
subset.push_back(k);
print(subset);
search(k + 1);
print(subset);
cout << "subset POP 아직 search(" << k <<") 실행중...\n";
subset.pop_back();
print(subset);
search(k + 1);
}
cout << "###################### search("<< k <<") END ######################\n";
//print(subset);
}
int main()
{
search(1);
cout << "재귀 함수 종료...\n";
for (auto const& subset : uniqueSubset) {
for (auto const& i : subset) {
std::cout << i << " ";
}
cout << "\n";
}
}
|
cs |
| 재귀 함수 종료... 1 1 2 1 2 3 1 3 2 2 3 3 |
알고리즘도 그렇지만 C++도 잘 몰라서 손에 익으려면 많이 써봐야겠네요.
예전에 구매한 udemy 강좌를 다시 봐야할듯... 엉엉...
머리가 팽팽 돌아가면 좋을텐데... 뭐 열심히 하는 수밖에 없겠지요....!
'알고리즘' 카테고리의 다른 글
| 숫자 대각선 나열하기 (0) | 2017.12.07 |
|---|---|
| 약수의 합 javascript (0) | 2017.11.09 |
| 제일 작은 수 제거하기 python (0) | 2017.11.09 |
| 최대공약수 최소공배수 javascript (0) | 2017.11.09 |
