반응형
- 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다.
- 모든 case는 결국 base case로 수렴해야 한다.
암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라.
0 ~ n-1 -> 암시적
begin ~ end -> 명시적
순차탐색
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public int search(int[] data, int n, int target) {
for(int i = 0; i < n; i ++){
if(data[i] == target){
return 1;
}
}
return -1;
}
public int search(int[] data, int begin, int end, int target) {
if(begin>end)
return -1;
else if(target == data[begin])
return begin;
else
return search(data, begin+1, end, target);
}
|
cs |
최대값 찾기
1
2
3
4
5
6
7
8
|
public 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));
}
}
|
cs |
1
2
3
4
5
6
7
8
9
10
11
|
public 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);
}
}
|
cs |
반응형
'알고리즘 > Algorithm' 카테고리의 다른 글
Recursion의 응용 - 미로찾기 (0) | 2021.01.19 |
---|---|
2진검색 알고리즘 (0) | 2021.01.19 |
Recursion(순환)-2 (0) | 2020.07.05 |
선형 시간 알고리즘 (0) | 2020.07.05 |
Recursion(순환)-1 (0) | 2020.06.27 |