꿈 꾸는 누렁이

지난 포스팅 때, 재귀는 믿음이 졸라 중요하다고 했다. 이번에도 마찬가지다.

그 전에 재귀를 공부할 때, 써야하는 경우에 대한 추가적인 기록이 필요할 것 같아서 먼저 기록한다.

재귀가 필요한 경우

재귀가 필요한 경우는 다음과 같다.

탈출 조건이 명확하고, 같은 작업이 계속해서 반복되는 경우.

피보나찌 수열에서는 n-2항과 n-1 항이 더해지는 부분이 반복된다.

Fibonacci(5) 이면 Fibonacci(4) + Fibonacci(3) 인데 Fibonacci(4)에도 Fibonacci(3)에도 n-2항과 n-1항이 더해지는 부분이 필요하기 때문에 반복이 되고, 이를 재귀로 구현했던 것이다.

이번 포스팅에서 구현해 볼 이진 탐색에서 또한 마찬가지다. 

가운데 값을 구한 후 비교 -> 범위 재설정 

이 작업이 반복되기 때문이다. 탈출 조건의 명확성은 말할 것도 없고 말이다.

이진 탐색에서도 믿음이 필요한가?

물론이다. 필요하다. 위에서 제시한 재귀가 필요한 경우와 믿음이 존재한다면 재귀 함수를 마음 놓고 신경도 안 쓰고 사용해도 된다.

재귀란 무엇인가?

피보나찌 수열 구하기이다. 재귀로 구해볼 것이다. 재귀는 매우 특이한 방법이 아닐 수 없다.

A라는 함수가 있을 때, A를 열심히 실행하는 도중에! 그것도 A가 미처 다 끝나지도 않은 채로 다시 A를 실행한다. 

이렇게 되면 와 진짜 너무 복잡한데, 또 두 번째 실행된 A안에서 또 A가 호출하면 와 진짜 머리 터진다.

윤성우 선생님? 강사님? 교수님? 의 자료 구조에서 공부한 파트를 정리하게 되었다.

그냥 재귀를 하면 심심하니까 피보나찌 수열을 통해서 재귀 함수를 작성해보았다. 복잡할 수 있으므로 시간의 흐름에 따라 스텝을 밟을 것이다.

피보나찌 수열의 재귀적 구현

먼저, 다음은 피보나찌 수열이다.

0,   1,   1,   2,   3,   5,   8,   13,   ...

0번째 항과 1번째 항은 무조건, 지구가 멸망하지 않는 이상 0과 1로 각각 주어진다.(멸망하면 수학을 풀 필요가 없다) 그렇다면 2번째 항부터는 어떻구 구하는가?

• 2번째 항을 구하는 방법 : 0번째 항의 값과 1번째 항의 값을 더한다.
• 3번째 항을 구하는 방법 : 1번째 항의 값과 2번째 항의 값을 더한다.
• 4번째 항을 구하는 방법 : 2번째 항의 값과 3번째 항의 값을 더한다. (ㄱ)
• n번째 항을 구하는 방법 : n-2 번째 항의 값과 n-1 번째 항의 값을 더한다. ( 일반화 ) (ㄴ)

일단, (ㄱ) 까지의 상황을 코드로 정리해보겠다.

그렇다. 무식하다. 근데 이게 좀 쩌는 것이 무어냐면 ㅋㅋ,

• Fibonacci(4); 의 결과 : 3
• Fibonacci(3); 의 결과 : 2 
• Fibonacci(2); 의 결과 : 1

함수의 결과가 중요하지 않다. Fibonacci 함수의 본질을 알려준다. Fibonacci 함수의 본질은 다음과 같다.

Fibonacci 함수에 원하는 항의 인덱스 값을 넣으면 해당 인덱스 항의 값을 구해줘요!

이게 진짜 개중요하다. 우리는 앞으로 만들 우리의 Fibonacci 함수를 믿어야 한다. 우리는 Fibonacci 함수의 인자로 원하는 항의 인덱스 값을 넣으면 해당 인덱스 항의 값을 내어준다는 사실을 믿어야한다. 믿음이다. 재귀 함수 루틴이 들어간다고 해서 이러한 사실이 부정인가? 아니다. 

위의 믿음을 가지고 특정 항을 생각해보자. 특정 항은 예를 들어 5번째 항의 값을 구한다고 생각하자.

Fibonacci(5) = Fibonacci(4) + Fibonacci(3);

재귀를 생각하지 말라. 믿음이 있어야한다.
Fibonacci(4)는 4번째 항의 값을 리턴할 것이라는 믿음.
Fibonacci(3)은 3번째 항의 값을 리턴할 것이라는 믿음.

이런 믿음을 바탕으로 (ㄴ)까지의 상황으로 아래와 같이 구현해보았다.

그렇다면, 실제로 어떻게 동작을 해보는지 재귀의 경우를 그려볼까?

피보나치 수열의 재귀적 구현의 동작 원리

그만 알아보자

이진 탐색을 구현해보았다.

이진 탐색에 대해 간단하게 기록하기 전에 이진 탐색의 전제 조건에 대해서 기록을 먼저 해보겠다.

이진 탐색의 전제 조건

• 이진 탐색은 오름차순이든 내림차순이든 관계없이 '정렬'이 되어있는 연속된 배열 자료구조에서 적용된다.

이러한 전제를 갖는 자료구조를 대상으로 탐색을 진행하는 것이 이진 탐색이다. 그렇다면 왜 이진 탐색은 저런 전제를 갖나?
그 해답은 이진 탐색의 정의에 있다.

이진 탐색이란?

타겟을 탐색할 때, 전체 자료구조의 (1)최대한 가운데 위치하는 값과 타겟을 (2)비교하여 탐색의 범위를 비교한 가운데 값을 기준으로 왼쪽과 오른쪽 중 하나로 탐색의 (3)범위를 좁히고 다시 좁혀진 범위에서 최대한 가운데 값을 다시 비교하고 탐색의 범위 결정을 반복하여 타겟을 탐색하는 알고리즘이다.

이진 탐색은 반복이 들어간다. (4)반복이 들어간다는 의미는 탈출 조건이 필요하다는 뜻이다.

이 탈출 조건은 매우 당연하고 자연스럽다.

허나, 이 이유를 알기 전에 범위를 잡는다는 개념을 알아야 한다. 범위를 잡는 것은 여러 케이스들이 있을테지만 선형(배열) 자료 구조에서의 범위를 잡는다는 행위에 대해서 적어보겠다.

탐색할 범위를 잡는다는 것은 시작 인덱스와 끝 인덱스를 잡는 것이다. 쉽게 말해서 시작과 끝을 잡아야한다. 배열에서 시작과 끝을 잡는다는 의미는 시작 인덱스 값과 끝 인덱스 값을 잡는다는 것이다.

자, 그러면 세 가지의 경우가 있다.

• 시작 인덱스 < 끝 인덱스
  : 정말 당연한 것이다. 탐색할 범위의 양 시작과 끝을 잡고 있다고 보면 된다.
• 시작 인덱스 == 끝 인덱스
  : 이런 경우가 나올 수 있을까? 나올 수 있다. 시작 인덱스이자 끝 인덱스에 위치한 값이 타겟인 경우다. 운이 안 좋은 가장 최악의 경우인 것이다. 어떻게 이렇게 제일 끝에 나올 수 있어? 재수 없단 말이지! 이런 뉘앙스의 최악의 경우를 뜻하고, 이런 경우까지 고려하여 알고리즘의 성능 평가를 시행한다 실제로.
• 시작 인덱스 > 끝 인덱스
  : 이런 경우가 가능할까? 알고리즘이고 말고를 떠나서 글자 자체만 보더라도 불가능하다. 고로, 탈출 조건이 된다. 이 경우는 해당 배열 자료구조에 타겟에 해당하는 값이 없기 때문에 발생하는 경우이다. 시작 인덱스와 끝 인덱스가 같은 바로 위의 경우에도 타겟이 검출되지 않으면 발생하는 경우이고, 이 경우에는 조건 제어를 통해 반복을 탈출해야한다. 왜냐고? 배열에 타겟이 없으니까!

자 그렇다면 구현하는데에 생각하는 순서를 좀 정리해본 것이 위 본문에서의 괄호 안의 숫자들이다.

• (1)최대한 가운데 위치하는 값(을 구한다)
• (2)비교
• (3)범위를 좁힌다(결정한다)
• (4) 탈출 조건

위 순서에 해당하는 부분들을 주석으로 표시해봤다.