인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.
순환 알고리즘의 설계
무한 루프를 피하기 위해서는
-
적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다.
-
모든 case는 결국 base case로 수렴해야 한다.
가능하면 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라
순차 탐색(segumtical search)
이 함수의 미션은 data[0]에서 data[n-1] 사이에서 target을 검색하는 것이다. 하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉 암시적 매개변수이다.
int search(int[] data, int n, int target){
for(int i=0; i<n; i++){
if(data[i] == target){
return i;
}
}
return -1;
}
순차 탐색: Recursion 버전
이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다. 즉, 검색구간의 시작점을 명시적(explicit)으로 지정한다.
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);
}
}
이 함수를 search(data, 0, n-1, target)으로 호출한다면 앞 페이지의 함수와 완전히 동일한 일을 한다.
리커전 함수의 매개변수는 맨처음 호출 될 때만을 생각해서 설계하면 안되고 자기 자신을 호출할때 필요한 매개변수까지 고려해서 설계해야 한다.
순차 탐색: 다른 버전
int search(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);
}
}
}
최대값 찾기: 매개변수의 명시화
이 함수의 미션은 data[begin]에서 data[end] 사이에서 최대값을 찾아 반환한다. begin <= end라고 가정한다.
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));
}
}
최대값 찾기: 다른 버전
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
item[begin]에서 items[end] 사이에서 target을 검색한다.
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(compResult < 0){
return binarySearch(items, target, begin, middle-1);
} else{
return binarySearch(items, target, middle+1, end);
}
}
}
반복문을 사용한다면 begin = 0, end = n으로 두고 짜면 된다.