순환 알고리즘의 설계
조건
적어도 1개의 base case 가 존재해야한다. 즉, 순환되지 않고 종료되는 케이스가 있어야 한다.
모든 케이스는 결국 base case 로 수렴해야한다.
기억하기
암시적 매개변수를 명시적 매개변수로 바꾸어라!
1. 순차탐색
순차 탐색에서의 미션은 0부터 n-1 배열 사이에서 타겟을 찾는 것이다. 하지만 이 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉, 여기서 0이 암시적 매개변수가 된다.
이렇게 암시적으로 표현된 변수를 아래와 같이 명시화하는 것이 필요하다. 시작 인덱스를 명확하게 매개변수로 전달한다.
왜 필요할까?
맨 처음 재귀함수를 호출할 때에는 0부터 시작하겠지만, 그 다음번부터 호출할 때에는 시작점이 한칸씩 뒤로 밀리게 된다.
따라서 이 함수가 한번만 호출될때를 생각하지 말고, 계속 반복되어 호출될 것을 생각하고 매개변수를 디자인 해야한다.
일단 매개변수를 명확하게 만들고 나중에 필요 없을 때, 삭제해주는 방법이 좋다.
package practice.algorithm.recursion;
public class SearchFromBegin {
public static void main(String[] args) {
String s = "elephant";
char target = 'p';
System.out.println("search(s, 0, s.length(), target) = " + search(s, 0, s.length()-1, target));;
}
private static int search(String s, int begin, int end, char target) {
if (begin >= end) {
return -1;
}
if (s.charAt(begin) == target) {
return begin;
}
return search(s, begin+1, end, target);
}
/**
* search(s, 0, s.length(), target) = 3
* */
}
뒤에서부터 탐색하는 방법
package practice.algorithm.recursion;
public class SearchFromEnd {
public static void main(String[] args) {
String s = "elephant";
char target = 'p';
System.out.println("search(s, 0, s.length(), target) = " + search(s, 0, s.length()-1, target));
}
private static int search(String s, int begin, int end, char target) {
if (begin >= end) {
return -1;
}
if (s.charAt(end) == target) {
return end;
}
return search(s, begin, end-1, target);
}
/**
* search(s, 0, s.length(), target) = 3
* */
}
가운데부터 탐색하는 방법
package practice.algorithm.recursion;
public class SearchFromMiddle {
public static void main(String[] args) {
String s = "elephant";
char target = 't';
System.out.println("search(s, 0, s.length(), target) = " + search(s, 0, s.length(), target));
}
private static int search(String s, int begin, int end, char target) {
if (begin > end) {
return -1;
}
int middle = (begin + end) / 2;
if (s.charAt(middle) == target) {
return middle;
}
int index = search(s, begin, middle-1, target);
if (index != -1) {
return index;
}
return search(s, middle + 1, end, target);
}
/**
* search(s, 0, s.length(), target) = 7
* */
}
2. 최대값 찾기
처음부터 탐색하는 방법 - 일반적
package practice.algorithm.recursion;
public class SearchMaxFromBegin {
public static void main(String[] args) {
int[] arr = new int[]{1, 100, 55, 4, -100};
System.out.println("findMax(arr, 0, arr.length-1) = " + findMax(arr, 0, arr.length - 1));;
}
private static int findMax(int[] arr, int begin, int end) {
if (begin == end) {
return arr[begin];
}
return Math.max(arr[begin], findMax(arr, begin+1, end));
}
/**
* findMax(arr, 0, arr.length-1) = 100
* */
}
가운데부터 탐색하는 방법
package practice.algorithm.recursion;
public class SearchMaxFromMiddle {
public static void main(String[] args) {
int[] arr = new int[]{1, 100, 55, 4, -100};
System.out.println("findMax(arr, 0, arr.length-1) = " + findMax(arr, 0, arr.length - 1));;
}
private static int findMax(int[] arr, int begin, int end) {
if (begin == end) {
return arr[begin];
}
int middle = (begin + end) / 2;
int max1 = findMax(arr, begin, middle);
int max2 = findMax(arr, middle+1, end);
return Math.max(max1, max2);
}
/**
* findMax(arr, 0, arr.length-1) = 100
* */
}
3. 이진 탐색
package practice.algorithm.recursion;
public class BinarySearch {
public static void main(String[] args) {
String[] strings = new String[]{"a", "v", "e", "p", "w", "b"};
String target = "w";
System.out.println("binarySearch(strings, target, 0, strings.length-1) = " + binarySearch(strings, target, 0, strings.length - 1));;
}
private static int binarySearch(String[] strings, String target, int begin, int end) {
int middle = (begin + end) / 2;
int result = target.compareTo(strings[middle]);
if (result == 0) {
return middle;
}
if (result < 0) {
return binarySearch(strings, target, begin, middle-1);
}
return binarySearch(strings, target, middle+1, end);
}
}
Last updated