알고리즘/이론 (48) 썸네일형 리스트형 06. 결정 문제 - 예제1 [1. 문제 설명] n 개의 탐사기지와 무전기가 존재 모든 무전기의 통신 반경은 d 따라서, 두 탐사 기지 사이의 거리가 d 이하이어야만 연락 가능 항상 모든 기지 간에 서로 연락 가능하다록 하는 무전기의 최소 통신 반경을 계산 [2. 풀이 접근] printf / scanf 서식문자 https://testkernelv2.tistory.com/57?category=513498 [3. 코드] 05. 조합 탐색 - 예제2 [1. 문제 설명] m가지의 음식을 준비할 수 있고, n명의 친구를 초대하려고 한다. 각 친구가 먹을 수 있는 음식, 먹을 수 없는 음식이 주어질 때, 각 친구가 먹을 수 있는 음식이 최소한 하나씩 있게 하려면 최소 몇가지의 음식을 해야하는가? [2. 풀이 접근] NP 완비 문제 중 하나로, 다항 시간에 푸는 방법은 아직 없다. 탐욕적 접근 방법으로 가장 많은 사람들이 먹을 수 있는 음식을 만들어 보는 방식으로 접근 할 수 있지만, 모든 입력에 대해 최적해를 찾아낼 수는 없다. 예제) ??? 완전 탐색으로 접근 해서, 간단한 가지치기를 하면 답을 구할 수 는 있지만, 시간 내에 동작하지 않는다. 이 문제를 푸는 간단한 방법은 탐색의 형태를 바꾸는 것 이다. 매 재귀 호출마다 아직 먹을 음식이 없는 친구를.. 05. 조합 탐색 [1. 개요] 동적 계획법이나 분할 정복 등의 문제 해결 방법을 모든 문제에 적용 할 수 없다. 캐시를 위한 메모리를 너무 많이 사용하거나 적절한 분할 방법이 없는 경우가 존재하기 때문이다. 이 경우 완전 탐색에서 다시 돌아와 생각 해야 한다. 부분 답과 완성된 답의 집합을 탐색공간이라 부른다. 완전 탐새의 수행 시간은 탐색 공간의 크기에 비례한다. 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘을 조합 탐색이라 부르기로 한다. 기본적으로 최적해가 될 가능성이 없는 답들을 탐색하지 않는다. [2. 가지치기 기법] pruning 기법은 현재 상태에서 답의 나머지를 완성했을 때 얻을 수 있는 가장 좋은 답이 지금까지 우리가 구한 최적해보다 나쁘면 탐색을 더 하지 않는다. 똑똑한 가지치기 기법들은 .. 04. 탐욕법 - 예제3 [1. 문제 설명] [2. 풀이 접근] 적당한 사람을 배정 해야 할 때 vector 를 정렬해서 사용했을 시 문제점 탐색은 O(logn) 이 가능하나, 배정했으므로 vector 에서 제거해야 한다. 이 때, vector 특성 상 제거하는데, O(n) 시간이 소요된다. 이진검색트리인 set 혹은 multiset 을 사용한 경우 탐색과 제거 모두 O(logn) 에 할 수 있다. 그런데 set 은 중복 값을 저장 할 수 없으나 multiset 은 중복 값을 저장 할 수 있다. [3. 코드] 04. 탐욕법 - 예제2 [1. 문제 설명] n 개의 문자열들의 길이가 주어질 때, n 개의 문자열들을 순서와 상관없이 합쳐서 한개의 문자열로 만들 때 필요한 비용의 최소 값 ex) {al, go, spot} 을 합칠 때 {al+go}+spot => al+go 비용: 4, algo+spot 비용 8 => 총 비용 12 [2. 풀이 접근] 한 문자열이 전체 비용에 미치는 영향에 대해서 생각해보면 병합되는 문자열들의 총 길이가 전체 비용에 더해진다. 병합의 대상이 되는 문자열의 길이가 매번 전체 비용에 누적된다고 볼 수 있다. 위 예제에서 "al" 은 "al" + "go" 에서 전체 비용에 더해지고 "algo" + "spot" 에서 전체 비용에 더해진다 볼 수 있다. 그래서, 항상 길이가 짧은 두 문자열이 병합의 대상이 되게 하는 .. 04. 탐욕법 - 예제1 [1. 문제 설명] n 개의 도시락이 있고, i번째 도시락을 데우는데 m[i] 초, 먹는데는 e[i] 초가 걸린다. 도시락을 먹기 위해서는 도시락을 먼저 데워야 한다. 도시락을 여러번에 나누어 데울수는 없다. 모든 사람이 도시락을 다 먹을 때 까지 걸리는 최소 시간 [2. 풀이 접근] 스케줄링 문제는 보통 탐욕법으로 풀 수 있다. (모든 경우는 아님) 전체 시간 = n-1 개의 도시락을 데우는 시간 + 마지막 도시락을 먹는데 걸리는 시간 먹는데 오래 걸리는 도시락부터 데우면 된다. 먹는데 오래 걸리는 도시락을 먼저 데우면, 다른 도시락을 데우는 시간 동안 이 도시락을 먹을 수 있기 때문이다. === 탐욕적 선택 속성 증명 먹는데 가장 오래 걸리는 샤브샤브 도시락을 먼저 데우는 최적해가 반드시 하나 있음을.. 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 => 원주열 외우기] 이전 1 2 3 4 5 다음