알고리즘/이론 (46) 썸네일형 리스트형 02. 분할 정복 예제 - 1 [1. 예제 => QUADTREE] 02. 분할 정복 [1. 개요] 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤, 각 문제에 대한 답을 재귀호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산 여기서 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 것이 아니라 거의 같은 크기의 부분 문제로 나누는 것 (=> 보통 절반씩 나눔 => O(logn)) 적용을 위해서는 문제에 몇 가지 특성이 성립해야 한다. 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 한다. => 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다. 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다. 보통 같은 작업을 더 빠르게 처리해 준다. [2. 구성 요소] Divide => 문제를 더 작은 문제로 .. 01 완전 탐색 예제 - 3 [예제 => CLOCKSYNC] 01. 완전 탐색 예제 - 2 [예제 => BOARDCOVER] 01. 완전 탐색 예제 - 1 [예제 1 => PICNIC] 01. 완전 탐색 [1. 개요] 완전탐색이란 가능한 경우의 수를 일일히 나열하면서 답을 찾는 방법 컴퓨터가 충분히 빠르기 때문에 가능한 방법 [2. 재귀호출] 완전히 같은 코드를 반복해서 실행 및 다양한 알고리즘을 구현하는데 매우 유용한 도구 재귀 호출 작성 시 유의 할 점 => 더 이상 쪼개지지 않는 최소한의 작업에 도달한 경우, 답을 곧장 반환하는 조건문을 반드시(?) 포함하도록 한다. => 일명 기저 사례(base case) 에 대한 처리가 필요하다. 중첩 for 문 등을 아주 유용하게 대체 할 수 있다. 완전 탐색 구현 시 아주 유용한 도구 [3. 문제와 부분 문제] 문제 => 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합 부분 문제 (원래 문제의 부분 문제) => 원래 문제에서 한 조각을 떼어냈을 뿐, .. 이전 1 2 3 4 5 다음