분할정복 (1) 썸네일형 리스트형 백준 알고리즘 중급 - 분할정복 분할 정복에 대해 간단하게 정리해보자. - * 분할 정복 (Divide & Conquer) : 문제를 2개 또는 그 이상의 작은 부분 문제로 나눠서 푸는 것. - '나눠서 푼다'는 점에서 DP와 같지만, DP는 문제가 겹쳐서 메모를 이용해야 하고, 분할 정복은 문제가 겹치지 않는다. * 이분 탐색 (Binary Search) : 정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘. 크기가 N일 때, O(logN). - 중간값과 비교해서 범위를 조금씩 좁혀 가면 된다. 예제를 한번 풀어보자. - 숫자 카드 (low) : 숫자 카드 중에 구하려는 값이 있는지 판별하는 문제다. 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 .. 이전 1 다음
