문제
입력
- 첫째 줄에 자연수 n(3<=n<=33)과 r(0<=r<=n)이 입력됩니다.
출력
- 첫째 줄에 조합수를 출력합니다.
입출력 예제
풀이방식
이번 문제는 DFS에 대한 문제이다.
설계과정
문제 이해는 아래 이미지를 보면 쉽게 이해할 수 있다.
2. R이 0이면 1을 리턴한다.
3. N과 R이 동일하면 1을 리턴한다.
4. 메모리제이션을 위해 2차원 배열을 선언하고, 배열의 값이 0보다 크면 배열[N][R] 값을 리턴한다.
5. 그렇지 않다면 배열에 재귀함수를 각각 호출하여 리턴한다.(DFS(N-1, R-1) + DFS(N-1, R))
풀이과정
1. 메모리제이션을 위해 2차원 배열을 선언한다.
2. N이 R과 동일하면 1을 리턴한다.
3. R이 0이면 1을 리턴한다.
4. 2차원 배열의 값이 0보다 크면 배열[N][R] 값을 리턴한다.
5. 그렇지 않다면 배열에 재귀함수를 각각 호출하여 리턴한다.(DFS(N-1, R-1) + DFS(N-1, R))
- 호출 파라미터는 문제를 보면 알 수 있다.
더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다.
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)
문제 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 입력 첫 줄에 총 항수 N(1
silverji.tistory.com
해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.
'알고리즘 > 인프런' 카테고리의 다른 글
| 섹션 8. DFS, BFS 활용 10. 미로탐색(DFS) (2) | 2022.12.30 |
|---|---|
| 섹션 8. DFS, BFS 활용 8. 수열 추측하기 (0) | 2022.12.28 |
| 섹션 8. DFS, BFS 활용 6. 순열 구하기 (0) | 2022.12.21 |
| 섹션 8. DFS, BFS 활용 5. 동전교환 (0) | 2022.12.18 |
| 섹션 8. DFS, BFS 활용 3. 최대점수 구하기 (2) | 2022.12.03 |
