문제
- 주어진 배열 요소중 몇번째 요소가 가장 큰 수인지 확인하기
-
해결방법 두가지
- 첫번재 : recursion
- 두번째 : binary search와 비슷한 방법
해결 방법1
- POINT1: 배열의 시작점(begin)과 나머지것들과의 Math.max 비교를 진행한다.
- POINT2: 3번째 인자값이 arr.length-1이어야 한다.
이유는 재귀 호출할때 begin+1이기 때문이다.
만일 arr.length를 하게 되면 배열의 길이보다 +1 요소 더 검사 하기 때문이다.
중요
-
매개변수를 명시화 하자 !
- recursion 함수 매개변수 선언할때 처음 호출하는 상황말고 자기 자신을 호출하는 상황에서의 매개변수를 생각해야 한다 .
- 그래서 아래와 같은 예제에서 begin, end가 추가가 된것이다.
- 예를 들어 permutation(순열-모든문자열의 조합) 알고리즘을 확인해보자
stack
- Math.max(arr[4], findMax(arr, 4, 4) = '5') => Math.max(5, 5) = 5
- Math.max(arr[3], findMax(arr, 3, 4)) => Math.max(3, 5) = 5
- Math.max(arr[2], findMax(arr, 2, 4)) => Math.max(2, 5) = 5
- Math.max(arr[1], findMax(arr, 1, 4)) => Math.max(1, 5) = 5
CODE1
function findMax(arr, begin, end) {
if (begin === end) {
return arr[begin]
} else {
// POINT1
return Math.max(arr[begin], findMax(arr, begin + 1, end))
}
}
var arr = [1, 2, 3, 4, 5, 100, 30, 50]
/*
# POINT: 3번째 인자값이 arr.length-1이어야 한다.
이유는 재귀 호출할때 begin+1이기 때문이다.
만일 arr.length를 하게 되면
배열의 길이보다 +1 요소 더 검사 하기 때문이다.
*/
console.log(findMax(arr, 0, arr.length-1))해결 방법2
- 반을 나눠 분할뒤 비교하는 방식을 사용했다.
CODE2
function findMax(arr, begin, end) {
if (begin === end) {
return arr[begin]
} else {
var middle = Math.floor((begin + end) / 2)
var max1 = findMax(arr, begin, middle)
var max2 = findMax(arr, middle + 1, end)
return Math.max(max1, max2)
}
}
var arr = [1, 2, 3, 4, 5]
console.log(findMax(arr, 0, arr.length-1))