Jacob's Coding Playground

[문제 출처 : Codechef] 이번에 살펴볼 문제는 우리가 이미 다뤘던 최대공약수 구하기를 활용하여 풀 수 있는 예제입니다. 그럼 어떤 문제인지 살펴봅시다.

이번에 살펴볼 개념은 Validation Set Approach라는 것입니다. 흔히 machine learning에서는 단순히 현재 training data에 대해서만 최적화 하는 것이 아니기 때문에 반드시 test data에 대한 성능이 중요한데요, 우리에게 test data가 주어진 것이 아니기 때문에 현재 가지고 있는 데이터의 일부를 쪼개서 test data로 활용하는 방법을 Cross-validation이라고 합니다. Cross-validation에도 여러가지 방법들이 있는데요, 그 중에서 가장 간단하게 활용되곤 하는 방법이 validation set approach입니다.

[문제 출처 : Codechef] 이번에 살펴볼 문제는 다음과 같습니다.

지갑에 다양한 지폐들이 있습니다. 지갑에 있는 지폐들의 조합으로 정확히 $m$원을 낼 수 있을까요? 거스름돈이 생겨서도 안됩니다.

예를 들면, 지갑에 [1, 5, 5]원의 지폐들이 있다고 가정해 봅시다. 그러면 1, 6, 10, 11원을 조합할 수 있습니다. 7원은 만들 수 없겠죠? 결국엔 하나하나씩 조합해 보면서 원하는 조합이 나오는지를 찾아야 합니다. A의 모든 부분집합 출력하기를 참고하시면 좋을 것 같네요 :)

이번에 살펴볼 자료구조는 Counter라는 dictionary의 일종인 자료구조입니다. 이름에서 알 수 있듯이, 이 Counter는 특히나 어떤 item을 count하는 데에 특화되어 있습니다. 이것은 collections라는 라이브러리 안에 존재하는 자료구조이므로 반드시 import해 주셔야 합니다.

from collections import Counter
from operator import itemgetter

그럼 먼저 3, 8, 10이 각각 5개씩 들어있는 A라는 리스트를 가정해 보겠습니다. Counter의 강력한 생성자 덕분에 이 리스트의 원소들을 각각 count하여 원소들을 key로, 등장하는 횟수를 value로 하여 dictionary를 만들 수 있습니다. 또한 Counter는 key가 정의되지 않는 상태에서 숫자 연산을 하더라도, default값을 0으로 지니고 있기 때문에 keyError가 나지 않습니다. 이런 면에서 기본 dictionary보다 편리하죠 :)

이번에 알아볼 예제는 $a, b, c\ge 0$일때, $a+b+c=n$을 만족하는 $a,b,c$의 조합의 개수를 구하는 것입니다. 가장 컴퓨터스럽게 구하는 방법은, 일일이 숫자를 대입하면서 가능한 조합의 수를 count하는 것입니다. 먼저, $a+b+c=2$의 해를 구한다고 가정해 봅시다. 그러면 이를 그림으로 나타내면, 아래와 같습니다.