문제
- 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.
입력
- 첫 줄에 총 항수 N(1<=N<=10)이 주어집니다.
출력
- 첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래 츌력예제와 같은 순서로 출력한다.
- 단 공집합은 출력하지 않습니다.
입출력 예제
풀이방식
이번 문제는 이진트리와 재귀함수를(을) 사용하여 푸는 문제이다.
재귀함수에 대한 자세한 설명은 아래 글을 참조하길 바랍니다.
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 1. 재귀함수(스택프레임)
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 1. 재귀함수(스택프레임)
문제 자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성하세요. 입력 첫 번째 줄은 정수 N(3
silverji.tistory.com
설계과정
1. 각 원소를 사용함, 사용안함으로 구분하여 트리 형식으로 부분집합을 만들어보자.
2. 원소별로 사용여부 값을 저장하는 배열을 만든다.
3. 원소 개수만큼 돌면서 사용여부를 확인하는 재귀함수를 수행한다.
4. 다 돌았으면 배열에 사용한다는 값이 들어있는 원소들을 출력한다.
풀이과정
1. 전역변수로 N과 배열 ch[ ] 를 선언한다.
- 전체적으로 쓰일 변수이기에 전역으로 선언한다.
- N : 집합에서 원소의 개수를 의미한다.
- ch[ ] : 부분집합의 사용여부 값을 저장할 배열이다.
2. 메인에 각 변수를 선언하고 DFS() 메소드를 수행하는 코드를 작성한다.
- ch[ ] 배열은 해당 배열의 인덱스 번호를 원소로 사용하기 위해 1을 더한다.
- DFS(1) 을 통해 DFS() 메소드에 1이라는 값이 전달되도록 한다.
3. DFS() 메소드를 작성하자.
3. L이 N+1 값과 같고, ch[i] 값이 1이라면 i 값들을 출력한다.
- L 이 N+1과 같다는 것은 배열의 끝에 도달했다는 것을 의미한다.
- ch[i] 값이 1이라는 소리는 해당 원소를 사용한다는 의미이다.
4. L이 N+1과 같고, tmp의 길이가 0보다 크다면 tmp를 출력한다.
- tmp.length() 가 0이면 공집합을 의미한다.
- 즉, tmp가 0보다 길다는 것은 tmp에 있는 값들을 전부 출력하라는 의미이다.
5. L이 N+1이 아니라면 else문에 있는 코드를 수행하는데, 이에 대한 자세한 설명은 아래를 참조해보자.
- ch[L] 의 값이 1이라는 것은, 해당 원소를 사용한다는 의미이다.
- ch[L] 의 값이 0이라는 것은, 해당 원소를 사용하지 않는다는 의미이다.
- 위쪽에 작성된 DFS(L+1) 는 왼쪽 노드를 의미한다.
- 아래쪽에 작성된 DFS(L+1) 는 오른쪽 노드를 의미한다.
해당 문제는 배열, 스택, 트리 3 가지를 통해 자세히 알아볼 것이다.
맨 처음의 형태는 다음과 같다.
이제 S.DFS(1) 을 수행해보자.
1. L에 1이 들어오고, if문에 부합하지 않으므로 else 문으로 넘어간다.
2. ch[L] = 1 코드를 통해 원소 1은 사용한다는 의미의 값 1로 변경되고, 배열은 아래와 같이 된다.
- 위쪽은 기존 인덱스에서 1씩 더한 값으로, 원소값과 동일하게 취급한다.
- 아래쪽은 각 원소의 값들이다.
3. DFS(L+1) 코드를 통해 DFS(2)가 만들어지고, 트리와 스택은 다음과 같다.
- DFS(1)과 복귀주소 line 19이 스택에 저장되고 L=1 이므로 사용한다(o) 를 트리로 표현한다.
4. DFS(2) 가 수행되고 19 line 까지 수행하여 배열, 스택, 트리는 다음과 같다.
- DFS(2)과 복귀주소 line 18이 스택에 저장되고 L=1 이므로 사용한다(o) 를 트리로 표현한다.
5. DFS(3) 가 수행되고 19 line 까지 수행하여 배열, 스택, 트리는 다음과 같다.
6. DFS(4)를 수행하면 N+1 이 4가 되므로 if 문으로 들어간다.
7. ch[ ] 배열에서 원소값이 1인 원소들의 인덱스를 출력한다. 그 후에 DFS(4)는 스택에서 pop() 된다.
- 출력값 : 1 2 3
8. DFS(3)에 19 라인으로 복귀해서 그 다음 20 라인부터 수행한다.
- 20 라인을 수행하면 3에는 0이 들어가고, 이는 즉 사용하지 않는 원소임을 의미한다.
9. 21 라인을 수행하면, DFS(4)가 호출되고 스택은 다음과 같이 쌓인다.
- DFS(3)의 복귀주소인 21 라인이 저장되고, DFS(4)는 쌓인 후에 pop() 된다.
10. DFS(3)로 복귀한 후에 더 수행할 코드가 없어 종료되면 원소값이 1인 원소들을 출력한다.
- 출력값 : 1 2
11. 스택에 남아있는 DFS(2)를 호출하여 19 라인으로 복귀한 후에 20 라인부터 수행한다.
- 20 라인을 수행하면 2에는 0이 들어가고, 이는 즉 사용하지 않는 원소임을 의미한다.
- 21 라인을 통해 DFS(3)이 수행되고, 3에는 1이 들어간다.
- 그리고 다시 DFS(4)가 호출되면서 if문에 걸려서 종료된다.
- 출력값 : 1 3
11. 위 과정을 반복해서 모든 부분집합을 찾아낸다.
5. 결과값을 출력한다.
답안소스
public class Subset {
static int N;
static int[] ch;
public void DFS(int L) {
if(L == N + 1) {
String tmp = "";
for(int i=1; i<N+1; i++) {
if(ch[i] == 1) {
tmp += (i + " ");
}
}
if(tmp.length() > 0) {
System.out.println(tmp);
}
} else {
ch[L] = 1;
DFS(L+1);
ch[L] = 0;
DFS(L+1);
}
}
public static void main(String[] args) {
Subset S = new Subset();
N = 3;
ch = new int[N+1];
S.DFS(1);
}
}해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.
