알고리즘/이론 (52) 썸네일형 리스트형 04. 탐욕법 [1. 개요] 탐욕법은 가장 직관적인 알고리즘 설계 패러다임 중 하나이다. 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없으나, 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다는 것이 다르다. 그래서, 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다. 탐욕법으로 최적해를 찾을 수 있는 많은 문제들은 동적 계획법으로도 풀 수 있다. => 모든 단계를 고려하는 동적 계획법이 틀릴 이유가 없기 때문 그럼에도, 탐욕법을 사용하는 이유는 동적 계획법에 필요한 메모리나 시간이 너무 크기 때문이다. 탐욕적 알고리즘을 설계하는 좋은 방법은 간단한 입력을 몇 개 손으로 풀어 보면서 패턴을 찾는 것 [2. 사용되는 경우] A. 탐욕법을 사용.. 03. 동적계획법 - 예제4 [1. 문제 설명] 2xN 크기의 직사각형을 2x1 크기의 타일로 채울 때 좌우 대칭으로 채우지 않는 경우의 수를 구한다. 비대칭 타일링 방법의 수를 1,000,000,007 로 나눈 나머지 (1e9 + 7) [2. 풀이 접근] A. 여사건 방식 전체 타일링 방법에서 대칭 타일링 방법의 수를 빼서 구한다. 대칭 타일링 수는 n 이 짝수인 경우와 홀수인 경우를 나누어서 생각한다. n 이 짝수인 경우 => 가운데를 가로 타일링으로 채우고, 한쪽을 채운 뒤, 나머지 한쪽을 동일하게 채우는 방식 => 절반 한쪽을 채우고, 나머지 한쪽을 마찬가지로 동일하게 채우는 방식 n 이 홀수인 경우 => 가운데러르 세로 타일링을 채우고, 한쪽을 채운 뒤, 나머지 한쪽을 동일하게 채우는 방식 == 전체 계산 후 주의할 점 =.. 03. 동적계획법 - 예제3 [1. 문제 설명] 수열을 s 가지의 자연수만을 이용하여 양자화 하였을 때, 각 숫자별 오차 제곱의 합을 최소 값을 출력한다. 양자화 => 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현 [161, 164, 178, 184] => 160, 170, 180 으로 표현.. [2. 풀이 접근] A. 잘못된 접근 주어진 수열 A 이 첫번째 수자를 어떤 숫자로 표현할 것인지 결정하고 나머지 수열에 대해 재귀 호출하는 방식 => 양자화에 사용 할 숫자에 제한이 있어서, 현재 까지의 결정이 앞으로의 결정에 영향을 준다 => 최적 부분 조건이 성립하지 않는다. => 메모이제이션에 필요한 메모리 확보도 어려울 것. ==> 입력 상, 1000 이하의 숫자 중 10 개의 숫자를 선택하는 경우를 고려해보면... 03. 동적 계획법 - 예제1 [예제1 => 합친 LIS] [예제2 => 원주열 외우기] 03. 동적 계획법 [1. 개요] 큰 의미에서 분할 정복과 같은 접근 방식 그러나 하나의 문제의 답을 여러번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함 두 번 이상 계산되는 부분 문제를 중복되는 부분문제라고 한다. 계산의 중복 횟수는 분할의 깊이가 깊어질 수록 지수적을 증가한다. (같은 값을 두번 이상 계산할 일이 빈번해질 수 있다.) 한 번 계산한 값을 저장해두었다가 재활용하는 최적화 기법을 메모이제이션이라 한다. 보통 동적 계획법 알고리즘 구현은 아래와 같은 두 단계로 구성 문제를 완전 탐색을 이용해 해결 중복되는 부분 문제를 한번만 계산하도록 메모이제이션을 적용 [2. 메모이제이션] 수학의 함수와 프로그래밍에서 함수는 사실 서로 다르다 프로그래밍을 할 때는 함수의 불변성이 성립하지 않을 수 있기 때문이다. .. 02. 분할 정복 예제 - 2 [1. 예제 => 팬미팅] 02. 분할 정복 예제 - 1 [1. 예제 => QUADTREE] 02. 분할 정복 [1. 개요] 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤, 각 문제에 대한 답을 재귀호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산 여기서 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 것이 아니라 거의 같은 크기의 부분 문제로 나누는 것 (=> 보통 절반씩 나눔 => O(logn)) 적용을 위해서는 문제에 몇 가지 특성이 성립해야 한다. 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 한다. => 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다. 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다. 보통 같은 작업을 더 빠르게 처리해 준다. [2. 구성 요소] Divide => 문제를 더 작은 문제로 .. 01 완전 탐색 예제 - 3 [예제 => CLOCKSYNC] 01. 완전 탐색 예제 - 2 [예제 => BOARDCOVER] 이전 1 2 3 4 5 6 다음