[12주차] 분할정복법과 탐욕적기법

4월 9일 자 학습 내용 정리입니다.

 

 

✅ 분할정복법

분할정복법은 아래와 같다.

1.  문제를 소문제로 분할한다.
2.  각각의 소문제를 해결한다.
3.  소문제의 해결 결과를 이용해 전체 문제를 해결한다.

 

분할정복법의 대표적인 예로는 합병정렬과 이분탐색이 있다.

 

✔️ 합병정렬

합병정렬(Merge Sort)은 흔히 하향식 2-way 방법으로 쓰이는데 이는 다음과 같이 작동한다.

1.  리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 아래 과정을 거친다.
2.  분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3.  정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4.  결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로합병 한다. 이때 정렬 결과가 임시배열에 저장된다.
5.  복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.

 

출처 : https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

 

def mergeSort(data):
  if len(data) < 2:
      return data
      
  mid = len(data) // 2
  left = mergeSort(data[:mid])
  right = mergeSort(data[mid:])
  
  mergedArr = []
  p1 = p2 = 0
  
  while p1 < len(left) and p2 < len(right):
    if left[p1] < right[p2]:
      mergedArr.append(left[p1])
      p1 += 1
    else:
      mergedArr.append(right[p2])
      p2 += 1
  
  mergedArr += left[p1:]
  mergedArr += right[p2:]
  
  return mergedArr

 

✔️ 이분탐색

이분탐색(또는 이진탐색, Binary Search)은 배열 내부의 데이터가 정렬되어있을 때 사용할 수 있는 알고리즘이다.

데이터가 무작위로 되어있을 때에는 사용할 수 없지만 정렬되어진 채로 주어진다면 매우 빠르게 데이터를 찾을 수 있다.

 

이분탐색은 탐색의 범위를 절반씩 좁혀나가며 데이터를 탐색한다.

이때 위치를 나타내는 변수를 3개 사용하는데 바로 탐색하고자 하는 범위의 시작점, 끝점, 중간점이다.

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이분탐색의 과정이다.

 

출처 : https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

 

def binarySearch(arr, target, start, end):
  if start > end:
    return None
    
  mid = (start + end) // 2
  
  if arr[mid] == target:
    return mid
  elif arr[mid] > target:
    return binarySearch(arr, target, start, mid-1)
  else:
    return binarySearch(arr, target, mid+1, end)

 

 

✅ 탐욕적기법

탐욕적기법 또는 그리디(Greedy) 알고리즘은 탐욕적으로 문제를 푸는 알고리즘이다.

즉, 순간의 최적의 선택이 궁극적으로는 최적의 선택이다.

이를 다시 말하자면 현재 상황에서 지금 당장 좋은 것만 고르는 것이다.

그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

 

🔍 참조

이것이 취업을 위한 코딩테스트다 with 파이썬 (한빛미디어, 나동빈)

합병정렬 https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC