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

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

1. 탐욕법 문자들을 합쳐 문자열을 만드는데 드는 비용이 최소가 되게 선택하려면 일단 가장 작은 문자 두개를 선택해 합쳐나가야 할 것 같다. 합쳐진 문자열에 또 합치게 되면 이전에 합치게한 문자열이 중복으로 또 다시 카운트 되기 때문이다. 2. 증명 탐욕적 선택 속성을 증명하기 위해 먼저 가장 작은 두 문자가 서로 합쳐지지 않은 최적해가 있다고 해보자 a와 b가 가장 작은 두 수 일때 먼저 다른 문자열과 합친것을 다음과 같이 표현했다. X = b + B Y = a + C 거리가 같은경우 : X + Y 일 경우 a 와 B를 바꾸어도 비용은 일정하므로 답은 변하지 않는다 거리가 다른 경우: X + a 일경우 a와 B를 바꾸게 될경우 B가 병합되는 횟수가 적어져 비용이 줄어들게 된다. 그러므로 작은 두 문자열..

1. 탐욕법 이 문제는 전자레인지를 데우는 시간의 총 합은 변하지 않는다 이 총합과 어떤 음식하나를 다 먹는 시간 의 합의 최소값이 문제에서 구하라는 해이다. 점심시간을 최소화하기 위해서 일단 음식하나에의해 좌우 되니 음식 먹는 속도가 느린 사람이 제일 먼저 전자레인지를 돌릴꺼 같다. 2. 증명 만약 음식 먹는 속도가 느린사람이 첫번째로 안오는 최적해를 생각해보자 맨 처음 사람과 속도가 제일 느린 사람의 순서를 바꿔보자 순서를 바꿔도 최적해인것에는 변함이 없다. 그러므로 속도가 느린 사람부터 선택하는 방법은 최적해에 포함된다. 부분문제 또한 자명하다. 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..

1. 탐욕법 가장 직관적인 알고리즘 설계 패러다임 중 하나임 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없음. 그러나 모든 선택지를 고려해 보고 , 그중 전체 답이 가장 좋은 것을 찾는 두 방법과 다르게 각 단계마다 '지금' 당장 가장 좋은 방법만을 선택함 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않음 탐욕적 알고리즘은 많은 경우 최적해를 찾지 못하고 다음과 같은 경우에만 쓸 수 있음. 1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동젹 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용 2. 시간이나 공간적 게약으로 인해 다른 방법으..

1. 완전 탐색 이 문제는 다음으로 재생될 곡은 바로 이전 곡에만 영향 받기때문에 마르코프 모델이라고 할 수 있다. 이 문제는 주어진 k분 30초에 좋아하는 노래들이 각각 나올 확률을 구하는 문제이다. 좋아하는 곡들의 번호들과 i다음으로 j가 재생될 확률을 담고있는 행렬 T가 주어지고 각 곡의 길이가 주어진다 number 음악이 min분에 재생될 확률을 구하려면 일단 0 ~min 에 number 음악이 시작되는 확률을 먼저 구해야한다. 해당 음악이 min분에 재생될 확률은 해당 음악이 min - number.len + 1에서부터 min까지 시작되는 확률을 전부 더한것과 같기때문이다. play(min, number) = min에서 number가 재생될 확률 play(min, number) = Σ ( pla..