분할정복 알고리즘 / 이분탐색 알고리즘

분할 정복 알고리즘

• 분할정복 알고리즘
  • divide and conguer
  • 주어진 문제를 최소단위로 분할하여 문제를 분할하는 방법
  • 나폴레옹의 아우스터리스 전투에서 사용한 전략에서 유래
    • 분할 (문제를 하나 이상의 작은 단위로 나누기) → 정복 (하나씩 해결) → 통합

재귀방식	분할정복 알고리즘

 

• 이진탐색 (Binary Search)
  1. 이진탐색을 위하여 정렬된 자료를 배열에 저장한다
  2. 탐색하고자 하는 값을 변수에 저장한다
  3. 배열 내의 중간값을 찾는다
  4. 중간값과 변수에 저장된 특정 값을 비교한다
  5. 작으면 앞, 크면 뒤에서 값 비교
  6. 위 과정을 반복한다.

 

• 빠른 정렬 Quick Sort
  • 기준(pivot)을 정해 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하여 정렬을 반복하는 방식 (분할 정복 방식
  • 선택정렬보다 빠르며, 정렬 알고리즘 중 가장 많이 사용되는 방법 중 하나
  • 재귀적으로 정렬을 수행하며 평균 시간복잡도는 매우 우수하지만 최악의 경우(이미 정렬된 경우 등)에는 O(n^2) 시간 발생 가능

실행 과정	예시	8 4 7 3 5
***기준값(pivot)을 설정 → 이미 정렬된 배열 부분의 내용과 자신의 값을 비교 → 자신의 위치 찾아 삽입 = 재귀적으로 정렬 완료 될 때까지 반복	1) 기준값(pivot) 설정	8 4 7 3 5
	2) 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할	4 3 (5 기준) 8 7
	3) 왼쪽 그룹에 대해 다시 퀵정렬	[3] 4  (3기준)
	4) 오른쪽 그룹에 대해 다시 퀵정렬	[7] 8  (7기준)
	5) 전체 정렬 결과 병합	3 4 5 7 8

***기준값(pivot)을 설정 방법 (첫번째 요소(0), 마지막 요소(n-1), 중간요소(n/2), 무작위, 처음-중간-끝 중 중앙값)

 

이분탐색 알고리즘

• 분할정복 알고리즘

정렬 단계	탐색 단계	단순 설계 단계	분할 적용 알고리즘	그리디 설계절차	문제해결 단계
기준 ↓ 비교 ↓ 이동	기준 ↓ 비교 ↓ 찾기	구조화 ↓ 모든 경우 적용 ↓ 해결책 선택	분할 ↓ 정복 ↓ 통합	선정과정 ↓ 적정성 점검 ↓ 해답점검	나누기 ↓ 답구하기 ↓ 답 이용 (상위 → 전체)

 

• 파이썬 코드 예시

def binary_search(lst, target):
    first = 0
    last = len(lst) - 1
    found = -1

    while first <= last and found == -1:
        mid = (first + last) // 2
        if list[mid] == target:
            found = mid
        elif list[mid] > target:
            last = mid - 1
        else:
            first = mid + 1

    if found == -1:
        print(f"이분탐색 실패: {target} 없음")
        return False
    else:
        print(f"{mid} 인덱스에서 {target} 찾음!")
        return True


# 테스트
list = [6, 13, 14, 25, 37]
print(binary_search(lst, 33))

 

• C++ 코드 예시항목 설명

#include <iostream>
#include <vector>
using namespace std;

bool binary_search(const vector<int>& lst, int target) {
    int first = 0;
    int last = lst.size() - 1;
    int found = -1;

    while (first <= last && found == -1) {
        int mid = (first + last) / 2;
        if (lst[mid] == target) {
            found = mid;
        } else if (lst[mid] > target) {
            last = mid - 1;
        } else {
            first = mid + 1;
        }
    }

    if (found == -1) {
        cout << "이분탐색 실패: " << target << " 없음" << endl;
        return false;
    } else {
        cout << found << " 인덱스에서 " << target << " 찾음!" << endl;
        return true;
    }
}

int main() {
    vector<int> lst = {6, 13, 14, 25, 37};
    binary_search(lst, 33);
    return 0;
}

 

목적	정렬된 리스트에서 원하는 값을 빠르게 찾기
시간복잡도	O(log n)
전제 조건	리스트가 정렬되어 있어야 함
동작 방식	중간 값을 기준으로 반씩 범위를 줄이며 탐색