[알고리즘] 문제 해결 패턴 (4) 분할 정복 패턴

분할 정복 패턴

주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리한다.

(연결리스트나 트리가 될 수 있다.)

 

값을 찾기 위해 배열의 왼쪽에서 시작하여 오른쪽 끝까지 이동하는 것보다는

배열을 작은 조각으로 세분화하여 각 조각들을 어디로 이동시킬지 결정하는 작업을 하겠다.

즉! 큰 데이터 덩어리를 작은 조각으로 나누는것

 

예시

탐색 알고리즘의 대표적인 예로, 정렬된 숫자 배열을 이용하는 방법이 있다.

배열은 반드시 정렬된 상태여야 한다. 주어진 search 함수는 특정 값을 입력으로 받아, 그 값이 배열에서 위치한 인덱스를 반환한다.

search([1,2,3,4,5,6],4) // 3

 

function search(arr, val) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] == val) {
      return i;
    }
  }
  return -1;
}

 

o(n)의 시간복잡도이다. 이 구조를 선형 탐색이라고 한다. 

전체 배열을 한 번 훑어보고 찾거나 못 찾거나 둘 중하나이다.

배열은 정려되어야 함을 염두해둬야한다. 

이진 탐색 알고리즘

function search(array, val) {
  let min = 0;
  let max = array.length - 1;

  while (min <= max) {
    let middle = Math.floor((min + max) / 2);
    let currentElement = array[middle];

    if (array[middle] < val) {
      min = middle + 1;
    } else if (array[middle] > val) {
      max = middle - 1;
    } else {
      return middle;
    }
  }
  return -1;
}

 

시간 복잡도는 log(n)이다. 이진탐색이다. 

 

프로그래머스

쿼드압축 후 개수 세기

전력망을 둘로 나누기

이진 변환 반복하기

하노이의 탑