순환 recursion
- 자기 자신을 호출하는 함수를 의미함
1
2
3
4
5
void func() {
...
func()
...
}
순환 알고리즘의 설계
- 적어도 하나의 base case가 있어서, 순환되지 않고 종료될 수 있어야 한다.
- 모든 case는 최종적으로 base case로 수렴해야한다.
- recursion으로 설계를 할 때는 암시적
implicit매개변수를 명시적explicit매개변수로 바꾸어야 한다.
순차탐색 예제
암시적으로 매개변수를 표현한다면
시작 인덱스는 0이다.
1
2
3
4
5
6
int search (int [] data, int n, int target) {
for (int i = 0; i < n; i++)
if (data[i] == target)
return i;
return -1;
}
매개변수를 명시하기
이 함수는 data[begin]에서부터 data[end] 사이에서 target을 검색하는데, 검색구간의 시작점을 begin으로 명시적으로 표현했다.
1
2
3
4
5
6
7
8
int searcdh(int [] data, int begin, int end, int target) {
if (begin > end)
return -1;
else if (target == items[begin])
return begin;
else
return search(data, begin+1, end, target);
}
명시적 매개변수를 사용한 순차탐색의 다른 버전
참고 - 이진 탐색과는 다르다!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int searcdh(int [] data, int begin, int end, int target) {
if (begin > end)
return -1;
else
int middle = (begin + end) / 2;
if (data[middle] == target){
return middle;
}
int index = search(data, begin, middle-1, target);
if (index != 1) {
return index;
} else {
return search(data, middle+1, end, target);
}
}
최대값 찾기 예제
매개변수를 명시해서 최대값 찾기
1
2
3
4
5
6
7
8
int findMax(int[] data, int begin, int end) {
if (begin == end) {
//데이터 갯수가 하나인 경우
return data[begin];
} else {
return Math.max(data[begin], findMax(data, begin+1, end));
}
}
최댓값 찾기 다른 버전
1
2
3
4
5
6
7
8
9
10
int findMax(int[] data, int begin, int end) {
if (begin == end) {
return data[begin];
} else {
int middle = (begin + end) / 2;
int max1 = findMax(data, begin, middle);
int max2 = findMax(data, middle + 1, end);
return Math.max(max1, max2);
}
}
이진검색 Binary Search
- 이진검색은 데이터가 오름차순으로 정렬되어있을 때 사용가능한 알고리즘이다.
- items[begin]과 items[end]사이에서 target을 검색하는 이진탐색법
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int binarySearch(String[] items, String target, int begin, int end) {
if (begin > end) {
return -1;
} else {
int middle = (begin + end) / 2;
int compResult = target.compareTo(items[middle]);
if (compResult == 0) {
return middle;
} else if (coompResult < 0) {
return binarySearch(items, target, begin, middle - 1);
} else {
return binarySearch(items, target, middle + 1, end);
}
}
}
미로찾기 예제
답이 Y/N인 문제
현재 위치에서 출구까지 가는 경로가 있으려면
- 현재 위치가 출구이거나 혹은
- 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나이다.
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
public class Maze {
private static int N = 8;
private static int [][] maze = {
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 1, 1, 0, 1, 1, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1},
{0, 1, 0, 0, 1, 1, 0, 0},
{0, 1, 0, 0, 0, 0, 1, 1},
{0, 1, 1, 1, 0, 0, 1, 1},
{0, 1, 0, 0, 0, 1, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1},
{0, 1, 1, 1, 0, 0, 0, 1}
};
private static final int PATHWAY = 0;
private static final int WALL = 1;
private static final int BLOCKED = 2;
private static final int PATH = 3;
public static boolean findMazePath(int x, int y) {
if (x < 0 || y < 0 || x >= N || y >= N) {
return false;
} else if (maze[x][y] != PATHWAY) {
return false;
} else if (x == N-1 && y == N-1) {
maze[x][y] = PATH;
return true;
} else {
maze[x][y] = PATH;
if (findMazePath(x-1, y) || findMazePath(x, y+1) || findMazePath(x+1, y) || findMazePath(x, y-1)) {
return true;
}
maze[x][y] = BLOCKED;
return false;
}
}
public static void main(String[] args) {
findMazePath(0,0);
}
}
멱집합 powerset예제
- 문제 : 임의의 집합 data의 모든 부분집합을 출력하라
- 예) data = {a, b, c, d} -> 2^4 = 16개
- 기반 로직
- {a, b, c, d, e, f}의 모든 부분집합을 나열하려면
- a를 제외한 {b, c, d, e, f}의 모든 부분집합들을 나열하고
- {b, c, d, e, f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다.
- {b, c, d, e, f}의 모든 부분집합에 {a}를 추가한 집합들을 나열하려면
- {c, d, e, f}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고
- {c, d, e, f}의 모든 부분 집합에 {a, b}를 추가한 집합들을 나열한다
- Psuedo code
1
2
3
4
5
6
7
8
9
10
11
powerSet(P, S) {
// S의 멱집합을 구한 후 각각의 집합에 집합 P를 합집화하여 출력하기
if (S is an empty set) {
print P;
}
else {
let t be the first element of S;
powerSet(P, S-{t});
powerSet(P U {t}, S-{t});
}
}
- 미션
- data[k], …, data[n-1]의 멱집합을 구한 후 각각에 include[i]=true, i=0, …, k-1인 원소를 추가하여 출력하기
- 처음 이 함수를 호출할 때는 powerSet(0)으로 호출한다. 즉 P는 공집합이고 S는 전체집합이다.
Reference
- 인프런
<영리한 프로그래밍을 위한 알고리즘 강좌>
