IT/알고리즘&자료구조 정리
[알고리즘] 분할정복
아래 글은 'Introduction to Algorithms(한빛아카데미)'와 분할 정복 블로그 를 보고 정리한 것이다. 대표 문제 백준 6549번: 히스토그램에서 가장 큰 직사각형 분할 정복 분할 정복(Divide and Conquer)은 (1) 분할과 (2) 정복, (3) 결합의 세 가지 단계를 거치면서 재귀적으로 문제를 해결한다. 분할: 현재의 문제와 동일하되 입력의 크기가 크기, 또는 문제의 크기를 더 작은 부분 문제로 분할한다. 정복: 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 충분히 작으면 직접적인 방법으로 푼다. 결합: 부분 문제의 해를 결합해 원래 문제의 해가 되도록 만든다. 부분 문제가 재귀적으로 풀 수 있을 만큼 충분히 클 때, 재귀 대상이라고 한다. 부분 문제가 충분..
