recursive 재귀적
접근법
- 부분문제(subproblem)에 대한 해법을 통해 완성된다.
- 단순히 f(n-1)에 대한 해답에 무언가를 더하거나, 제거하거나, 그 해답을 변경하여 f(n)을 계산해낸다.
- 데이터를 반으로 나눠 각각에 대해서 문제를 푼 뒤 이 둘을 merge하기도 한다.
접근법
상향식 접근법
- 우선 간단한 경우들에 대한 풀이법을 발견하는 것으로부터 시작.
- 이전에 풀었던 사례를 확장하여 다음 풀이를 찾는다.
하향식 접근법
- 어떻게 하면 N에 대한 문제를 부분 문제로 나눌 수 있을지 생각해봐야한다.
- 나뉜 부분문제의 경우가 서로 겹치지 않도록 주의한다.
반반 접근법
- 데이터를 절반으로 나누는 방법
- 병합정렬
merge sort가 반반접근법을 이용한 정렬 방법 : 배열 절반을 각각 정렬한 뒤 이들을 하나로 병합
재귀적 문제의 패턴
- “n번째 ~~를 계산하는 알고리즘을 설계하라”
- “첫 n개를 나열하는 코드를 작성하라”
- “모든 ~~를 계산하는 메서드를 구현하라”
재귀 vs 순환
- 재귀적 알고리즘 사용시 공간 효율성이 나빠질 수 있다.
- 재귀 호출이 한 번 발생할 때마다 스택에 새로운 layer를 추가해야 한다.
- 재귀의 깊이가 n일 때 O(n)만큼 메모리를 사용하게 된다는 것을 의미한다.
재귀적 알고리즘을 순환적 알고리즘으로 구현하는 것이 더 나을 수도 있다.
- 모든 재귀적 알고리즘은 순환적으로 구현될 수 있지만, 순환적으로 구현된 코드는 때로 훨씬 더 복잡하다. 순환적으로 작성하면 얼마나 더 어려울 지 자문해보라.
재귀함수의 기본 포멧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param at 현재 위치 = 어디서부터 시작하는지
* @param depth 재귀가 깊어질 때마다 depth를 1씩 증가시켜 M과 같아지면 더이상 재귀를 호출하지 않고 return 하고 끝남
*/
public static void rec (int at, int depth) {
if (depth == M) {
// 깊이가 M이랑 같을 경우에 출력
}
// 재귀하면서 백트래킹 할 반복문 구현
for () {
// 반복문 내용
}
}
재귀를 위해 필요한 것
- N 크기의 boolean 배열 - 이미 방문한 노드라면 다음 노드를 탐색하도록 하기 위해서
- 탐색 과정에서 값을 담을 int 배열
구체적인 dfs 포멧
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
boolean[] visit = new boolean [N];
int[] arr = new int [M];
public static void dfs(int N, int M, int depth) {
// 재귀 깊이가 M과 같아지면 탐색과정에서 담았던 배열을 출력
if (depth == M) {
for (int val : arr) {
System.out.print(val + " ");
}
System.out.println();
return;
}
for (int i = 0; i < N; i++) {
// 만약 해당 노드를 방문하지 않았다면
if (visit[i] == false) {
// 1. 해당 노드를 방문 상태로 변경함
visit[i] = true;
// 2. 해당 깊이를 index로 하여 i+1값을 저장
arr[depth] = i+1;
// 3. 다음 자식 노드 방문을 위해 depth를 1씩 증가시키면서 재귀 호출
// depth + 1 과 depth++ 은 똑같이 1은 증가시켜주지만 작동원리는 다르다.
// depth++ 은 depth 변수의 값 자체가 1 증가하기 때문에 재귀에서 빠져나와도 증가된 값은 그대로 유지된다.
dfs(N, M, depth+1);
// 4. 자식 노드 방문이 끝나고 돌아오면 방문 노드를 방문하지 않은 상태로 변경
visit[i] = false;
}
}
return;
}
reference
코딩인터뷰 완적분석 189가지 프로그래밍 문제와 해법 dfs 코드 포멧
