[알고리즘] 분할 정복 알고리즘
분할 정복 알고리즘 (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
- 메모리
- 명령어
- 포인터
- 컴파일
- 레지스터
- dynamic_cast
- 스레드
- CPU
- 수학
- 할당
- 멀티스레드
- 입출력
- 백준
- 초기화
- 크기
- 운영체제
- New
- 클래스
- 구조
- malloc
- const
- 함수
- 인터럽트
- c++
- 프로세스
- 알고리즘
- 상속
- 게임수학
- thread
- static_cast
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함