개발공부/알고리즘 이론7 분할정복 divide & conquer (알고리즘) +(백준 1780) 알고리즘 문제에서 분할정복 문제를 만나면 어떻게 접근해야 하는지 정리하는 글이다. 이 문제를 찾는 인사이트는 문제를 보고 이 문제를 작은 문제로 쪼갤 수 있을까?를 보는 것이다.그리고 고민거리가 몇가지 있다. 1. 어떻게 나눌 것인가?2. 어디까지 나눌 것인가? degenerate case의 크기?3. 대칭적으로 나눌 것인가? 합병 VS 쾌속 정렬4. combine 단계가 필요한가? ( 대부분 쪼개긴 해야 하는데 합병 단계는 크게 필요 없는 경우가 많다.) 수시적으로 살펴보자 아래의 사진은 분할 정복을 표현하는 식이다. 이를 점화식으로 표현하면 아래와 같다.점화식의 해법은 아래와 같다. 1. 특성 방정식2. 텔레스코핑3. 마스터 정리 1번 2번은 머리 아프니 3번만 알아도 크게 상관 없다고 생각한다.ht.. 2024. 10. 7. 이전 1 2 다음
