- 분할 정복 - 주어진 문제를 더이상 나눌 수 없을 때까지 나누고, 나누어진 문제를 각각 풀어 답을 얻는 알고리즘
- 규칙은 정해져있지 않고 개발자의 창의력, 독창성, 경험에 달려있다
- 분할 정복 알고리즘을 설계하는 요령
- 분할 - 2개이상의 하위문제로 나눈다
- 정복 - 하위문제가 여전히 분할 가능하다면 하위집합에 대해 분할을 다시 수행, 아니라면 하위 문제를 푼다.
- 결합 - 위 두 과정에서 정복된 답을 취합한다.
- 부분문제 - 분할된 입력에 대한 문제
- 부분해 - 부분 문제의 해
- 문제해 - 부분해를 취합
- 합병 정렬 Merge Sort
- n개의 숫자들을 n/2개씩 2개의 부분 문제로 분할
- 각각의 부분문제를 재귀적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬(정복)
- 합병 정렬의 시간 복잡도
- (층수)xO(n) = log2nxO(n) = O(nlogn)
- 선택Selection 문제 : n개의 숫자들중에서 k번째로 작은 숫자를 찾는 문제
- 이진탐색 - 2분의 1로 나눈 두부분중에서 한부분만 탐색
- 선택문제
- 정렬되어있지않는 값들 중 피봇(기준)을 선택 -> 피봇을 기준으로 Small그룹 Large그룹으로 나눈다.
- good/bad 분할
- bad 분할 : 4분의 3보다 크다
good 분할 : 4분의 3보다 작다
반응형
'휴지통' 카테고리의 다른 글
2021년 10월 26일 화요일 기록 (0) | 2021.10.26 |
---|---|
네트워크 5주차 강의 - WAN 기술 (0) | 2021.10.13 |
알고리즘 강의 3주차 - 그리디 알고리즘 (0) | 2021.10.12 |
2021-10-08 프로그래머스 - SQL 고득점 KIT (0) | 2021.10.08 |
알고리즘 강의 1주차 (0) | 2021.10.08 |