SW 문제해결 - 분할 정복

About this offer

분할 정복 기법 문제를 작은 하위 문제로 나누고(분할) 각각을 해결(정복)한 뒤, 그 결과를 결합(통합)하여 원래 문제를 해결하는 알고리즘 기법 분할 정복 기법 적용된 대표적 정렬 알고리즘 : 퀵 정렬, 병합 정렬 분할 정복 기법 유래 1805 년 12월 2일 아우스터리츠 전투에서 나폴레옹이 사용한 전략 전력이 우세한 연합군을 공격하기 위해 나폴레옹은 연합군의 중앙부로 쳐들어가 연합군을 둘로 나눔 둘로 나뉜 연합군을 한 부분씩 격파함 분할 정복 기법의 설계 전략 분할(Divice) : 해결할 문제를 여러 개의 작은 부분으로 나눔 정복(Conquer) : 나눈 작은 문제를 각각 해결 통합(Combine) : (필요하다면) 해결된 해답을 모음 분할 정복 기법의 구조 Top-down approach 예시 분할 정복 기법의 예시 가짜 동전 찾기 n 개의 동전들 중에 가짜 동전이 하나 포함되어 있다. 가짜 동전은 진짜 동전에 비해 아주 조금 가볍다. 진짜 동전들의 무게가 동일하다고 할 때 양팔 저울을 이용해서 가짜 동전을 찾아보자. * 양팔 저울을 최소로 사용해서 가짜 동전을 찾는 방법은 무엇인가? * 예를 들어 동전이 24(진짜 23, 가짜 1)개 있다면? 거듭 제곱 분할 정복 기법을 이해하기 위해, 자연수 C의 n 제곱 값을 구하는 함수를 구현해봅시다 반복(Iterative) 알고리즘 : O(n) Iterative_Power(x, n) result <- ` FOR i in 1 -> n result <- result * x RETURN result 분할 정복 기반의 알고리즘 : O(log2n) Recursive_Power(x, n) IF n == 1: RETURN x IF n is even y <- Recursive_power(x, n/2) RETURN y * y ELSE y <- Recursive_Power(x, (n-1)/2) RETURN y * y * x 병합 정렬(Merge Sort) 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식 병합 정렬 과정 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄 top-down 방식 시간 복잡도 O(n lon n) 병합 정렬 과정 예시 {69, 10, 30, 2, 16, 8, 31, 22}를 병합 정렬하는 과정 분할 단계 : 전체 자료 집합에 대하여, 최소 크기의 부분집합이 될 때까지 분할 작업을 계속한다. 병합 단계 : 2개의 부분 집합을 정렬하면서 하나의 집합으로 병합한다. 8개의 부분집합이 1개로 병합될 때까지 반복 병합 정렬 알고리즘 분할 과정 merge_sort(LIST m) IF length(m) == 1 : RETURN m LIST left, rigth middle <- length(m) / 2 퀵 정렬 (Quick Sort) 이진 검색

Offer details

Provider

velog

Source

velog-rss

Score

54.4

Confidence

49%