[Inflearn] 영리한 프로그래밍을 위한 알고리즘 - 순환 (Recursion) 의 개념과 기본 예제 3

암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라

암시적 매개변수 : 코드 상에서 숨어 있는, 보이지 않는 변수

명시적 매개변수 : 코드 상에서 나타나 있는, 보이는 변수

 

 

 

1. 순차 탐색

1) 암시적 매개변수를 사용한 경우

검색할 구간의 시작 위치가 주어지지 않고, 배열의 시작 인덱스가 0이니까 암묵적으로 시작 위치는 0 끝 위치는 n-1이라는 것이다.

그래서 0부터 n-1까지 n개의 인덱스를 돌며 찾고자 하는 값(target)을 찾는 코드이다.

하지만 0은 매개변수로 받지 않고 있기 때문에 암시적 매개변수이고 이는 지양해야 한다.

 

 

2) 명시적 매개변수를 사용한 경우 - 순방향 탐색

 

begin ~ end로 검색할 구간의 시작 위치와 마지막 위치가 매개변수로 주어지고 있어 명시적 매개변수이다.

배열 0부터 확인하는 것이 아니라, begin 위치의 값만 확인하고 함수의 인자 값을 바꿔 함수를 재호출한다.

함수를 호출할수록 begin 값을 +1 시켜 배열 끝까지 탐색하게 한다는 것이다.

 

이런 함수를 구현할 때에는 맨 처음 함수가 호출될 때의 상황만 생각하고 매개변수를 설계해서는 안되고

자기 자신을 재호출할 때 필요한 매개변수들까지 표현할 수 있는, 좀 더 일반적인 형태를 가지게 해야 한다.

순환의 원리가 순차 탐색에서 이렇게 쓰인다는 것을 보여주는 좋은 예시인 것 같다.

 

 

3) 명시적 매개변수를 사용한 경우 - 역방향 탐색

두 번째 코드는 배열 앞에서부터 확인하는 코드였지만 세 번째 코드는 배열 뒤에서부터 확인하는 코드이다.

begin은 값을 증가해줘야 다음 배열 값으로 넘어갔지만, end는 값을 감소해줘야 이전 배열 값으로 넘어올 수 있다.

 

 

4) 명시적 매개변수를 사용한 경우 - 중간 기준 양쪽 탐색

begin과 end 사이의 중간 값 middle을 찾고 middle을 기준으로 시작~중간, 중간~끝의 두 부분으로 나눠서 탐색하는 방법이다.

먼저 시작~중간을 탐색해서 찾으면 index 값을 반환하고, 찾지 못했다면 중간~끝 부분을 탐색해서 결과 값을 반환한다.

 

 

 

 

 

2. 최대값 찾기

1) 명시적 매개변수를 사용한 경우 - 순방향 탐색

 

 

2) 명시적 매개변수를 사용한 경우 - 중간 기준 양쪽 탐색

 

 

 

 

 

3. 이진 검색 (Binary Search)

가정 - 데이터들은 크기 순으로 정렬되어 배열에 저장되어 있다