1. 최적화 문제 이 문제는 각 기지를 모두 연결할 수 있는 거리 중에서 최대 거리를 최소화 하는 문제로 모든 경우의 수를 만들어서 최대거리가 최소인 경우를 찾으면 된다. 하지만 이 최적화 문제는 경우의 수가 너무 많다. 2. 결정 문제 결정 문제로 문제를 변형해보자 모든 기지를 통신반경 D인 무전기로 연결할 수 있는지? 이 문제를 이진탐색으로 여러번 수행하면 최적해에 아주 가까운 근사값을 얻을 수 있을 것이다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 ..

1. 결정 문제(decision problem) 결정 문제란 예 아니오 현태의 답만이 나오는 문제들을 가리킴. 최적화 문제의 반환 값은 답의 경우의 수가 무한한 데 반해, 결정 문제는 두가지 답만 있음. 그러므로 결정 문제가 최적화 문제보다 더 어렵거나 시간 복잡도가 더 클 일도 없다. 2. 결정 문제로 바꾸기 어떤 문제에서 최대가 되는 x를 구하자고 하자 이를 결정 문제로 바꾸는 것은 다음과 같다. y이상일때 문제가 해결되는지? 이 결정 문제를 이분법을 사용하여 10번 100번 반복하면 결국 원래 문제인 x를 구할 수 있다. 3. 이분법의 함정 답이 가질 수 있는 가지수가 유한일 때 이분법은 수치적 안정성을 잃어버리게 된다. 최적화 문제는 아주 미세한 차이가 나더라도 답과 가까운 값을 반환하지만 결정 ..

1. 완전 탐색(시간초과, 잘못된 구현) 이 문제는 각 친구들이 먹을 수 있는 음식이 하나라도 먹을 수 있게 하는 최소한의 메뉴를 선정하는 문제이다. 이 문제는 다음과 같이 완전 탐색할 수 있다. - 친구들을 기준으로 탐색 - 음식들을 기준으로 탐색 모든 친구들이 먹을 수 있는게 하나라도 있어야하므로 친구들을 기준으로 탐색하는게 더욱 구현이 직관적일 것이다. 코드는 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 6..

1. 완전 탐색 주어진 블록으로 빈 공간에 넣을 수 있는 최대 개수를 구하는 문제이다. 이 문제를 풀기 위해서는 일단 다음과 같은 함수가 필요할 것 같다. - 블록들을 회전 시키는 함수. - 왼쪽위에서부터 오른쪽아래까지 블록을 넣는지 않넣는지 , 블록을 넣을때 회전하는 케이스 까지 모든 경우를 세는 함수. 이 완전 탐색으로는 시간안에 못풀것 같다. 10*10 의 빈 공간이 있으면 최대 5^100번 함수가 실행 될것 같기 때문이다. (5가지 경우 수 선택 x 0 90 180 270에 100개의 칸) 물론 이것이 실제 돌아가면 훨씬 더 빨리 수행될것이다. 하지만 그래도 엄청나게 큰 수행시간 일 것이다. 2. 조합탐색 - 가지치기 단순 휴리스틱 함수를 구현하면 더욱 빨리 수행될 것 같다. 이 함수는 남은 칸의..

1. 조합 탐색 동적 계획법이나 분할 정복 등의 디자인 패러다임은 적절히 적용 될 때는 매우 유용하나 모든 문제에 적용할 수 없다. 이럴 경우 결국 완전 탐색으로 풀어야 한다. 완전 탐색은 탐색 공간의 크기에 직접적으로 비례한다. 따라서 문제의 규모가 클 경우 사용하기 어렵다는 문제가 발생한다. 이런 완전 탐색을 포함해, 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘들을 알고리즘 문제해결 전략에서는 조합탐색이라고 부른다. 조합 탐색에는 다양한 최적화 기법이 있으며 모두 기본적으로 모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어 봐야 할 답의 수를 줄이는 것을 목표로 한다. 조합 탐색을 최적화하기 위해 어떤 방법을 사용해야 할지 찾아내는 것은 문제 자체에 대한 깊은 식견을..

1. 문제의 데이터를 변형해야한다. 초소의 실수 좌표들이 주어지고, 반지름이 주어진다. 이 데이터들을 가공하여 문제를 바로 푸는 것은 까다롭다. 그러므로 책에서는 이 데이터들을 중심각 구간으로 표현하였다. 중심각 이외에 원과 원이 만나는 X축 구간으로도 풀 수 있을것 같다. 2. 탐욕법 각 초소들의 구간으로 나타내면 이것은 활동 선택문제와 매우 유사하다. 하지만 이 문제는 처음 구간을 고르는게 중요하다. 원은 순환하기 때문에 처음 구간은 맨 마지막 구간과 이어지기 때문이다. 전체 구간이 0~2π 라고 할때 0 을 포함하는 구간들은 항상 두개 이하 선택 해야한다. 맨 오른쪽, 맨 왼쪽에 해당하는 구간 두개가 있으면 항상 다른 구간들은 그 구간에 포함되기 때문이다. 그리고 0 을 포함하는 구간들을 지금 선택..