Jacob's Coding Playground

어떤 자연수들의 list A가 주어진다고 가정해 봅시다. 이 list에는 어떤 수들이 존재하는지 확인하려면 어떻게 해야 할까요? 즉, 중복되는 것들을 제외하고 distinct한 원소들은 몇 개가 있을까요?

이번에 살펴볼 개념은 k-fold Cross-validation입니다. 앞서 다뤘던 Validation Set Approach과 Leave-One-Out Cross-Validation에 이어 마지막 validation 방법입니다. 사실 개념은 LOOCV와 크게 다르지 않으니 쉽게 이해하실 수 있을 것입니다. 먼저 아래의 그림을 보시죠.

이번에 살펴볼 개념은 앞서 Validation Set Approach에서 살펴봤듯이, machine learning에서 필수적인 validation의 한 방법입니다. Validation set approach 방식은 간단하고 빠르게 동작할 수 있지만, 가장 큰 단점으로 매번 다른 random set을 뽑을 때마다 그 결과가 달라질 수 있다는 점을 들었습니다. 이번에 살펴볼 Leave-One-Out CV(LOOCV) 방식은 총 $N$(샘플 수 만큼)번의 model을 만들고, 각 모델을 만들 때에 하나의 샘플만 제외하면서 그 제외한 샘플로 test set performance를 계산하여 N개의 performance에 대해서 평균을 내는 방법입니다.

[문제 출처 : Codechef] 기나긴 연회가 끝나고, 이제 장소를 청소하고 정리하는 일만 남았습니다.
주방에는 쉐프와 보조 두 명만 남았습니다.
총 치워야 할 n개의 일 중에 m개는 이미 나머지 종업원들이 마쳤습니다.
쉐프와 보조는 다음과 같은 규칙으로 나머지 하지 않은 일들을 분담하려고 합니다.

쉐프가 가장 빠른 index의 일을 맡습니다.

보조가 그 다음으로 빠른 index의 일을 맡습니다.

이런식으로 계속 반복해서 남은 일들을 할당합니다.

이 경우에 결국 쉐프와 보조가 받게 되는 일들은 각각 어떤 것들일까요?

[문제 출처 : Codechef] 이번에 살펴볼 문제는 꽤나 흥미로운 문제입니다. 이번 문제에서는 Recursive 함수, Dynamic Programming, 수학적인 해까지 종합 선물세트로 다뤄볼 수 있습니다. 아마 a+b+c=n의 해의 수 구하기와 같이 좋은 예제가 될 것 같습니다. 먼저 어떤 문제인지 살펴보겠습니다.