[알고리즘] 순환(Recursion)의 개념과 기본 예제 3

인프런 무료 강의 권오흠교수님 '영리한 프로그래밍을 위한 알고리즘 강좌' 보면서 공부한 내용입니다.
부족한 내용이나 잘못된 내용은 댓글남겨주시면 감사하겠습니다!

출처 : https://inf.run/iezc

지난 시간에 이어 순환함수를 공부하였다.

2023.06.08 - [알고리즘] - [알고리즘] 순환(Recursion)의 개념과 기본 예제 1

2023.06.08 - [알고리즘] - [알고리즘] 순환(Recursion)의 개념과 기본 예제 2

 

오늘은 크게 순차 탐색, 최대 값 찾기, 이진 검색을 공부 하였다.

먼저 기초적인 순차 탐색이다.

/*
 * 순환(Recursion)의 개념과 기본 예제 3-01
 * 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸기!
 * 
 * 순차 탐색 : find에 넣은 값이 있으면 해당하는 인덱스 리턴, 없을 경우 -1 리턴
 * -> 2
 */
package edu.recursion;

public class Recursion03_01 {
	public static void main(String[] args) {
		int find = 3;
		int[] arr = {1, 2, 3, 4, 5, 6};
		int result = search(arr, arr.length, find);
		System.out.println(result);
	}

	// data[0]에서 data[n-1] 사이에서 target을 검색
	// 검색 구간의 시작 인덱스 0은 보통 생략 -> 즉, 암시적 매개변수
	public static int search(int[] data, int n, int target){
		for(int i=0; i<n; i++)
			if(data[i] == target)
				return i;
		return -1;
	}
}

다음과 같이 우리는 for문을 작성할 때 주로 int i=0을 자주 쓴다. 하지만 이 변수 i는 암시적 매개변수이다. 

암시적 매개변수가 있을 경우 썩 좋은 코드는 아니므로 이 변수를 명시적으로 바꿔볼거다.

 

똑같은 코드이지만 아까와는 다르게 시작점을 명시적으로 주었다.

/*
 * 순환(Recursion)의 개념과 기본 예제 3-02
 * 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸기!
 * 
 * [매개변수 명시화] 순차 탐색 
 * -> 2
 */
package edu.recursion;

public class Recursion03_02 {
	public static void main(String[] args) {
		int find = 3;
		int start = 1;
		int[] arr = {1, 2, 3, 4, 5, 6};
		
		// search(data, 0, n-1, target)으로 호출하면 03-01과 동일한 기능
		int result = search(arr, start, arr.length-1, find); // 인덱스는 0부터 시작하므로 length-1을 해줘야 함
		System.out.println(result);
	}

	// data[begin]에서 data[end] 사이에서 target을 검색
	// 검색 구간의 시작점을 명시적으로 지정
	public static int search(int[] data, int begin, int end, int target){
		if(begin > end) // 검색할 데이터의 갯수가 0일 경우
			return -1;
		else if(target == data[begin]) // 찾으려고 시작하는 위치가 찾는 값일 경우 바로 그 지점을 반환
			return begin;
		else
			return search(data, begin+1, end, target); // 그게 아니라면 찾는 시점을 +1 해줘서 다음 인덱스의 값과 비교
	}
}

 

이번 코드도 아까와 유사하지만 아까는 시작점에서 값을 비교했다면 지금 코드는 마지막 지점부터 값을 비교하는 것을 알 수 있다.

/*
 * 순환(Recursion)의 개념과 기본 예제 3-03
 * 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸기!
 * 
 * [매개변수 명시화] 순차 탐색 다른 버전
 * -> 2
 */
package edu.recursion;

public class Recursion03_03 {
	public static void main(String[] args) {
		int find = 3;
		int start = 1;
		int[] arr = {1, 2, 3, 4, 5, 6};
		
		int result = search(arr, start, arr.length-1, find); // 인덱스는 0부터 시작하므로 length-1을 해줘야 함
		System.out.println(result);
	}

	// data[begin]에서 data[end] 사이에서 target을 검색
	// 검색 구간의 시작점을 명시적으로 지정
	public static int search(int[] data, int begin, int end, int target){
		if(begin > end) // 검색할 데이터의 갯수가 0일 경우
			return -1;
		else if(target == data[end]) // 찾으려고 마지막하는 위치가 찾는 값일 경우 바로 그 지점을 반환
			return end;
		else
			return search(data, begin, end-1, target); // 그게 아니라면 찾는 시점을 -1 해줘서 이전 인덱스의 값과 비교
	}
}

 

이번에는 중간 지점 값을 구해 중간~시작점을 비교하고, 없을 경우 중간지점~끝을 비교하는 버전이다.

/*
 * 순환(Recursion)의 개념과 기본 예제 3-04
 * 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸기!
 * 
 * [매개변수 명시화] 순차 탐색 다른 버전
 * -> 2
 */
package edu.recursion;

public class Recursion03_04 {
	public static void main(String[] args) {
		int find = 3;
		int start = 1;
		int[] arr = {1, 2, 3, 4, 5, 6};
		
		int result = search(arr, start, arr.length-1, find); // 인덱스는 0부터 시작하므로 length-1을 해줘야 함
		System.out.println(result);
	}

	public static int search(int[] data, int begin, int end, int target){
		if(begin > end) // 검색할 데이터의 갯수가 0일 경우
			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) // 만약 인덱스를 다 돌아서 -1이 될 경우 없는 값이므로 index 리턴
				return index;
			else
				// 중간지점~시작점 다 돌았는데 없으면 중간지점에 인덱스를 하나 더 추가하여 다시 함수 실행
				return search(data, middle+1, end, target); 
			 
		}
	}
}

 

매개변수를 명시화하여 최대 값을 찾는 함수이다.

/*
 * 순환(Recursion)의 개념과 기본 예제 3-05
 * 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸기!
 * 
 * [매개변수 명시화] 최대값 찾기
 * -> 6
 */
package edu.recursion;

public class Recursion03_05 {
	public static void main(String[] args) {
		int start = 1;
		int[] arr = {1, 2, 3, 4, 5, 6};
		
		int result = findMax(arr, start, arr.length-1);
		System.out.println(result);
	}

	// data[begin]에서 data[end] 사이에서 최대값 찾아서 반환. begin <= end라고 가정
	public static int findMax(int[] data, int begin, int end){
		if(begin == end) // 시작점과 끝점이 같을 경우 배열의 값은 하나이므로 그 값을 최대 값으로 리턴
			return data[begin];
		else
			// findMax(data, begin+1, end) 여기 안에서 최대 값을 찾은 후
			// 그 값과 data[begin] 이 값을 비교
			return Math.max(data[begin], findMax(data, begin+1, end));
	}
}

 

순차 탐색과 유사하게 중간 지점에서부터 최대 값을 찾는 버전이다.

/*
 * 순환(Recursion)의 개념과 기본 예제 3-06
 * 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸기!
 * 
 * [매개변수 명시화] 최대값 찾기 다른 버전
 * -> 6
 */
package edu.recursion;

public class Recursion03_06 {
	public static void main(String[] args) {
		int start = 1;
		int[] arr = {1, 2, 3, 4, 5, 6};
		
		int result = findMax(arr, start, arr.length-1);
		System.out.println(result);
	}

	// data[begin]에서 data[end] 사이에서 최대값 찾아서 반환. begin <= end라고 가정
	public static 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); // 그 두 값을 비교
		}
	}
}

 

마지막으로 알고리즘에서 유명한 이진 검색을 하는 함수를 구현해보았다.

이전과 유사하게 중간 지점에서부터 값을 비교하였다.

/*
 * 순환(Recursion)의 개념과 기본 예제 3-07
 * 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸기!
 * 
 * Binary Search - 이진 검색 : 데이터가 정렬되어 있는 배열에서 특정한 값을 찾기
 * -> 1
 */
package edu.recursion;

public class Recursion03_07 {
	public static void main(String[] args) {
		int start = 1;
		String[] arr = {"찰리", "스누피", "우드스탁"};
		String find = "스누피";
		int result = binarysearch(arr, find, start, arr.length-1);
		System.out.println(result);
	}

	// items[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]); // compareTo : 문자열 비교 - 작으면 음수, 같으면 0, 크면 양수
			if(compResult == 0)
				return middle;
			else if (compResult < 0)
				return binarysearch(items, target, begin, middle-1);
			else
				return binarysearch(items, target, middle+1, end);
		}
	}
}