[알고리즘] 분할 정복 알고리즘
분할 정복 알고리즘 (Divide-and-Conquer Algorithm) 주어진 문제의 입력을 분할하여 부분문제(subproblem)로 만들어 해결하는 방식 대부분 분할 정복 알고리즘은 단순 분할이 아닌, 분할된 부분문제들로 부분해를 찾아야 한다. 예시 문제로 크기가 n인 입력값이 있다고 가정하고 n을 3개로 분할한다 할때 각 부분문제의 크기가 $$n/2$$라고 하면 각 입력 크기의 반은 n/2라고 할수있다. 이제 입력 크기가 1이 되어 더 이상 분할할 수 없는 k번째까지 분할을 한다면, $$n$$$$n/2$$$$n/2^2 (n/4)$$$$n/2^3 (n/8)$$$$n/n^4 (n/16)$$$$...$$$$n/2^k$$ 위와 같은 순서가 성립된다. 이때, 입력크기가 1이되는 총 횟수를 k는 $$n/2^..
Computer/Algorithm
2021. 3. 20. 22:09
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 상속
- 수학
- 멀티스레드
- 운영체제
- static_cast
- c++
- 메모리
- 컴파일
- 클래스
- 초기화
- dynamic_cast
- 할당
- malloc
- CPU
- 함수
- 크기
- New
- 구조
- 명령어
- 스레드
- 알고리즘
- 인터럽트
- 입출력
- 포인터
- thread
- 게임수학
- const
- 레지스터
- 백준
- 프로세스
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함