[MIT] 파이썬을 이용한 알고리즘의 이해 - 알고리즘적 사고: 극댓값 찾기

 

 

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다.

 

 

 

✔ 극댓값이란?

 주위의 모든 값들이 현재의 값보다 작은 값입니다. 즉, 주위의 모든 값보다 현재의 값이 큰 값입니다. 극댓값을 최댓값으로 생각할 수도 있지만, 극댓값이 항상 최댓값인 건 아니지만 최댓값은 항상 극댓값입니다.

 

 이번 강의에서는 1차원과 2차원으로 나누어서 각 차원에서 극댓값을 구합니다. 그리고 그 과정에서 사용한 알고리즘과 사용한 알고리즘의 시간복잡도에 대해서 알아봅니다. 시간복잡도와 배열에 대해서 미리 알고 계시면 이해하기 편합니다.

 

 

 

✔ 1차원의 경우

 위와 같은 알파벳 1차원의 배열이 존재한다고 할 때 b≥a이고 b≥c이면 2번 위치가 극댓값입니다. 혹은 i≥h이면 9번 위치가 극댓값입니다.

👀 1차원 배열의 경우 0부터 시작하지만 강의에서 1부터 위치를 시작하므로 위와 같이 표기했습니다.

 

알고리즘

⁉ 한쪽 끝에서부터 시작하는 경우

 평균적으로 한쪽에서 가운데 쪽으로 증가하다가 중간 어딘가에 극댓값이 존재할 것입니다.

* 왼쪽 끝 혹은 오른쪽 끝에서도 극댓값이 존재할 수도 있습니다.

 

⏱시간 복잡도 : Θ(n)

 n/2에서 극댓값을 찾게 된다면 n/2개의 원소를 확인하면 됩니다. 하지만 최악의 경우 전체 다 확인해야 합니다.(왼쪽에서 시작하는데 오른쪽 끝에 극댓값이 존재할 경우)

👀 강의에서는 n/2에서 극댓값을 찾게 된다면 n/2개의 원소를 확인하면 된다고 나와있지만 극댓값을 확인하기 위해서는 n/2+1개의 원소를 확인해야 되지 않을까라는 의문이 생깁니다.

 

 

⁉ 분할 정복 알고리즘

 분할 정복 알고리즘을 이용하여 이 1차원 배열을 여러 개의 작은 배열들로 재귀적으로 쪼개는 것입니다. 이것을 반복하면 복잡도를 낮출 수 있습니다. 아래의 예제의 경우 1차원 배열을 a라고 가정하고 알고리즘을 적용해 보면 다음과 같습니다.

    1) a[n/2] < a[n/2-1] 이면 왼쪽 절반인 1~n/2-1까지 보고 극댓값을 찾습니다.

    2) a[n2]<a[n/2+1]이면 오른쪽 절반인 n/2+1~n까지 보고 극댓값을 찾습니다.

    3) 위의 두 가지의 경우가 다 아닐 경우 n/2 위치가 극댓값입니다. ( a[n/1] ≥ a[n/2-1],  a[n/2] ≥ a[n/2+1] )

 👀 1번과 2번의 경우 각 부분에서 극댓값을 찾는 것보다 영역에서 계속하여 분할 정복 알고리즘을 적용하여 극댓값을 찾는 것이 더 좋지 않을까 싶습니다.

 

⏱시간 복잡도 : Θ(log2(n))

 

---

 

✔ 2차원의 경우

 위와 같은 알파벳 2차원의 배열이 존재한다고 할 때 a≥b, a≥d, a≥c, a≥e 이면 a는 2차원 배열의 극댓값입니다.

 

알고리즘

⁉ 탐욕 알고리즘

 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달합니다.

 위의 오른쪽 이미지와 같이 12에서 시작하여 극댓값을 탐욕 알고리즘으로 찾게 되면 12 → 13 → 14 → 15 → 16 → 17 → 19 → 20 순서로 20을 극댓값으로 찾게 됩니다. 하지만 최악의 경우 처음부터 끝까지 다 봐야 합니다.

 

⏱시간 복잡도 : Θ(nm)

 

 

⁉ 분할 정복 알고리즘 변형

 1차원에서 사용한 분할 정복 알고리즘을 조금 변형하여 극댓값을 찾는 방법입니다. 방법은 아래와 같습니다. 

    1) 중앙 열 j=m/2를 선택한다.

    2) (i, j)에서 j열의 최댓값을 찾는다.

.

    3-1) (i, j-1)>(i, j)이면 왼쪽 열을 선택하고 (i, j+1)>(i, j)이면 오른쪽 열을 선택한다.

(i, j) < (i, j+1)이기 때문에 오른쪽 열 선택

 

    3-2) 두 조건 모두 만족하면 남은 열이 작은 쪽을 선택한다.

(i, j-1)>(i,j)와 (i, j+1)>(i, j)를 만족하기 때문에 왼쪽든 오른쪽든 상관 없지만 남은 열이 작은 왼쪽 선택

    3-3) 두 조건 모두 만족하지 않으면, (i, j)가 2차원 극댓값이다.

    4) 열 개수가 절반으로 줄어든 새로운 문제를 푼다.(열이 1개가 남을 때까지 2~3번 반복)

    5) 열이 1개 남으면 최댓값을 찾고 끝난다.

⏱시간복잡도 : Θ(nlog(m))