티스토리 뷰
부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크
부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크
2-3. 순환(Recursion)의 개념과 기본 예제 3
Designing Recursion - 순환 알고리즘의 설계
순환적 알고리즘 설계
적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함
모든 case는 결국 base case로 수렴해야 함
ex - 가장 단순한 경우
if ( ... ) {
//basecase
} else {
//recursion
}암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라!!
순차탐색
이 함수의 미션은 data[0]에서 data[n-1] 사이에서 target을 검색하는 것이다. 하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉 0은 암시적 매개변수이다.
int search(int[] data, int n, int targert) {
for (int i = 0; i < n; i++)
if (data[i] == targer)
return i;
return -1;
}
매개변수의 명시화: 순차 탐색
이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다. 즉, 검색구간의 시작점을 명시적(explicit)으로 지정한다.
이 함수를 search(data, 0, n-1, target)으로 호출한다면 위에 있는 순차탐색 함수와 완전히 동일한 일을 한다.
int search(int[] data, int begin, int end, int targer) {
if (begin > end)
return -1;
else if (target == data[begin])
return begin;
else
return search(data, begin+1, end, target)
}
순차 탐색: 다른 버전
이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다. 즉, 검색구간의 시작점을 명시적(explicit)으로 지정한다.
int search(int[] data, int begin, int end, int targer) {
if (begin > end)
return -1;
else if (target == data[begin])
return begin;
else
return search(data, begin, end-1, target)
}
순차 탐색: 다른 버전
Binary search와는 다름
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라고 가정한다.
여기서 최대값을 찾는 법은 첫번째 인덱스에 해당하는 값과, 첫번째 인덱스를 제외한 나머지 범위에서의 값을 비교한 것들 중에 순환적으로 최대값을 찾는다.
Base case는 begin == end, 즉 데이터의 갯수가 1개인 경우이다.
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
items[begin]에서 items[end] 사이에서 target을 검색한다.
해당 메소드에 매개변수를 명시적으로 표시하지 않는다면, recursion으로 구현할 때 내부에서 resursive하게 호출되는 함수를 표현할 수 있는 방법이 없어진다.
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);
}
}
따라서, 순환 알고리즘을 설계하는데에 있어서 가장 중요한 것은
적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함
모든 case는 결국 base case로 수렴해야 함
'ICT Eng > Algorithm' 카테고리의 다른 글
[Algorithm] 2-5. Recursion 응용 2 - Counting Cells in a Blob (0) | 2018.01.11 |
---|---|
[Algorithm] 2-4. Recursion 응용 1 - 미로찾기 Java 구현 (0) | 2018.01.11 |
[Algorithm] 2-2. 순환의 개념과 기본 2 - Recursive Thinking (0) | 2018.01.09 |
[Algorithm] 2-1. 순환의 개념과 기본 1 - Recursion (0) | 2018.01.09 |
[Algorithm] 1. 알고리즘의 분석 (0) | 2018.01.09 |
- Total
- Today
- Yesterday
- springboot
- Spring
- 젠킨스
- 라즈베리파이
- AWS
- 레드블랙트리
- RBT
- vuex
- Java
- JPA
- 한밭이글스
- 알고리즘
- Recursion
- 순환
- 시간복잡도
- 인프런
- ORM
- Vue.js
- Spring Boot
- 한밭대학교
- Algorithm
- Raspberry Pi
- github
- IT융합인력양성사업단
- vuejs
- 스프링부트
- Wisoft
- 정렬
- 무선통신소프트웨어연구실
- 자바
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |