1. 문제 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2. 풀이 입력으로 제공된 카드들의 누적합을 최소로 만드는 경우의 수를 만들라는 문제다. 이는 Greedy로 접근이 가능한데 이유는 아래와 같다. a, b, c, d 총 네 개의 카드 묶음(a < b < c < d)이 있다고 가정해보자. 이 때, 먼저 만든 묶음은 또 다른 카드 묶음과 합쳐져야 하므로 한 번 더 더해져야 함을 의미한다. 즉, 더 큰 카드 묶음을 이용하여 새로운 묶음을 만들수록 큰 수가 중복해서 더해진다는 것을 의미한다. ..

앞선 알고리즘 소개 포스트를 통해 완전 탐색을 알아보았는데, 완전 탐색(brute force)의 핵심은 큰 문제를 작은 문제로 분할하여 모든 경우를 탐색해보는 것이었으며 그 중, 작은 문제로의 분할이 가장 핵심이라고 볼 수 있다. 이는 비단 완전 탐색에 국한되는 것이 아니라 향후 다룰 동적 계획법(Dynamic Programming)이든, 지금 다룰 욕심쟁이 알고리즘이든 모든 알고리즘 문제의 가장 기본이 된다고 볼 수 있다. 완전 탐색이 모든 경우에 대해 체크한 후 최적의 해를 골라내는 것이었다면, 욕심쟁이 혹은 탐욕법(Greedy)의 경우 각 단계마다 현재 최선의 방법만을 선택하는 것을 의미한다. 다만 늘 현재의 최선의 해답만을 선택하므로, 앞으로 남은 선택지들에 대한 사항은 고려하지 않게 되는데 이로..