재귀함수

재귀함수를 디자인 하기 위한 3 단계

1) 함수의 정의를 명확히 한다
2) 기저 조건에서 함수가 제대로 동작하게 작성한다
3) 함수가 제대로 동작한다고 가정하고 함수를 완성한다.

어떤 문제든 제일 첫 번째로 시도해야 할 방법은 무조건 완전탐색이다.

그러나 완전탐색의 경우, 탐색범위가 커질수록 불리하다는 단점을 가지고있다.

데이터가 이미 정렬된 상태라면 이진탐색을 활용할 수 있다.

• 중간값을 기준으로 찾고자 하는 값과의 크기 비교를 한다.
  찾는 값을 탐색할 때 까지 범위를 지수로그 만큼 줄여나가므로 최악의 시간 복잡도는 O(logN)이다.

분할정복법

문제를 소문제로 분할하여 각각의 소문제를 해결하는 방식이며, 소문제의 해결 결과를 이용해 전체 문제를 해결하는 방법이다.

분할정복법에서는 수학적 문제 해결 능력이 가장 중요하고, 잠시 키보드에서 손을 치우고 노트와 펜을 잡아야 한다.

합병 정렬

분할정복법으로 해결할 수 있는 대표적인 문제 예시이다.

정렬되지 않은 배열 arr이 있다고 하자

arr = [3,5,7,2,5,9,13,11,24,11,24,11,23,1,4,5,3,2]

먼저 이 리스트를 2 분할한다.

arr1 = [2,3,5,5,7,9,11,13]
arr2 = [1,2,3,4,5,11,23,24]
#왼쪽과 오른쪽으로 나눈 리스트는 정렬되어 있다.

이 두 배열을 다시 합치면 정렬된 전체 배열을 만들 수 있을 것이다.
합치기 위해서는 각 리스트의 0번째 인덱스를 비교한다.

두 인덱스 값을 비교하여 더 작은 값을 빼서 새로 만든 빈 전체 배열에 넣어준다.

합병정렬의 시간복잡도

n개의 요소를 정렬하는 데 드는 시간은 = T(n)이다.
여기서 T(n)은 둘로 나눈 두 배열 T(N/2) + T(N/2) 를 정렬하는 총 시간이다.

여기에 왼쪽 배열과 오른쪽 배열의 요소를 하나하나 전부 비교하기 때문에
T(N) = T(N/2) + T(N/2) + O(N) 이다. N이 1이 될때까지 2로 나누는 시간은 logN이다.

이것을 다시 합치는 데에 O(N)의 시간이 소요되고, 해당 작업을 logN 번 수행하기 때문에 총 정렬시간은 O(NlogN)이 된다.

arr = [2,1,-2,5,-10,3,2,5,-3,7,9,-10]

리스트를 둘로 나눠서 연속부분 최대합을 찾아보면, [2,1,-2,5] = 6, [2,5,-3,7,9] = 20이 나온다. 또한 전체 배열에서의 연속최대합을 찾아보면, [3,2,5] = 10이다.

여기서 자른 지점을 포함하는 연속부분최대합은, 자른 지점을 기준으로 왼쪽과 오른쪽을 독립적으로 생각하는 것이다. 위의 배열에서 자른 지점의 기준이 되는 요소는 3(왼쪽) 2(오른쪽)이다.

이제 각 요소를 포함하는 기준으로 각 연속부분 최대합을 구하면,
왼쪽 배열 기준 [3] = 3 이 가장 크고, 오른쪽 배열 기준 [2,5,-3,7,9] = 20으로 가장 크다.

탐욕법 (Greedy)

순간의 최적의 선택이 궁극적으로 최적의 선택이다. 단순한 방법도 문제 풀이에는 충분하다.

완전탐색을 사용하면, 범위가 커질수록 경우의 수가 어마어마하게 커지기 때문에 시간효율성을 보장하기 힘들다. 따라서, 이와 같은 경우 탐욕법을 이용하며 효과적으로 문제를 해결할 수 있다.

요약

그러나, 탐욕법은 순간의 최선의 선택을 하는 가설을 파악하기 어려우며, 문제를 해결한 다는 것을 증명하기 어렵기 때문이다.

분할정복 알고리즘 요약

분할정복법은 어렵다.

분할정복법으로 해결할 수 있는 대표적인 예제로는:
합병정렬, 퀵정렬, 거듭제곱 구하기, 연속 부분 최대합, 가장 가까운 두 점 찾기, 히스토그램등이 있었다.

이 문제에서 발견할 수 있었던 점은, 문제를 어떻게 나누고, 작은 문제를 어떻게 해결해야 하며, 해결한 작은 문제를 또 어떻게 합쳐서 결과를 남길 것인가에 대한 문제였다.

이를 훈련하기 위해서는 관련 문제들을 많이 풀어보는 것이 중요하다.

코딩 능력과 문제 해결 능력은 다르다

코딩과 문제 해결 능력은 구별되어야 하며, 알고리즘 문제를 풀 때에는 키보드가 아닌 스스로의 논리를 가지고 노트와 펜으로 풀이를 떠올려야 할 것이다.