Daddy's Journey to Platinum

출처: https://cses.fi/problemset/task/1745

문제 설명

입력 

출력

입력 예

출력 예

제약조건

문제 풀이

프로그램 내용

vector<bool> dp(n*1000+1);
...
for (int c : coins) 
{
	for (int i = dp.size() - 1; i > 0; i--) 
	{
            if (dp[i]) 
                dp[i + c] = 1; 
            d[c] = 1; 
	}
}
...

Dynamic Programming ( link )

출처: https://cses.fi/problemset/1744

문제 설명

입력 

출력

입력 예

출력 예

제약조건

문제 풀이

프로그램 내용

...   
for(int i=1; i<=a; ++i) {
	for(int j=1; j<=b; ++j) {
		if(i^j)
			dp[i][j]= INT_MAX;
		for(int k=1; k<i; ++k) // 가로로 자르는 경우
			dp[i][j]=min(dp[i][j], dp[k][j]+dp[i-k][j]+1);
		for(int k=1; k<j; ++k) // 세로로 자르는 경우
			dp[i][j]=min(dp[i][j], dp[i][k]+dp[i][j-k]+1);
	}
}
...

Dynamic Programming ( link )

Competitive Programming (CP) 혹은 USACO 공부방법은 외국어를 배우거나, 운동을 배우고 훈련하는 것에 더 가깝다. 머리속에 지식(knowledge)을 쌓는 것보다 직접 작성할 수 있는 기술(skill)을 습득하는 과정이다.

여러가지 Blog나 참고 문서들이 있다.

1. USACO Resource page ( link )
2. Crash Course Coding Companion ( link )
3. General Resources for Competitive Programming ( link )
4. Beginner (Bronze/Silver) December Contest Prep ( link )
5. A Way to Practice Competitive Programming : From rating 1000 to 2000 ( link )

먼저, 확인해야 할 것은 CP 는 Coding Competition이 아니라 Problem Solving Competition이라는 것이다. 실제로 문제 해결과정에서 implementation이 필요 없는 것은 아니지만, 전체 문제 풀이를 10이라고 할때 구현이 차지하는 부분은 2~3 정도가 된다고 생각한다. 정확한 문제의 이해가 전체의 1/3은 차지한다. 정확한 문제의 이해는 입력과 출력의 경계를 명확하게 하고, 알고리즘 구현과정에서 주의해야 하는 부분들을 찾을 수 있게 해준다. 예를 들어 문제 풀이 과정중에 덧셈이 있고 그 덧셈값을 어떤 변수에 저장하는 알고리즘을 생각해보자. 이때, 더하는 값들의 범위와 더한 결과 값을 기록하는 변수의 범위는 달라 질 수 있다는 것을 구현하기 전에 정리하는 것이 문제의 이해 과정에 얻어지는 것이라고 할 수 있다. 그 문제 이해를 기반으로 알고 있는 알고리즘에서 구현할 수 있는 것을 문제의 답안으로 할 수  있다. 대부분의 프로그래머들처럼 문제가 생겼을때 검색을 하거나 관련 자료를 찾아서 살펴볼 수 없다. 물론, 그정도의 자료조사나 연구가 필요한 문제는 일반적인 CP의 범위 바깥에 있다. 혹은 배경지식의 부족함으로 더 준비해야 하는 부분이 된다.

CP를 준비하는 과정은 Web 페이지를 만들거나 app을 만드는 것과는 방향이 아주 다르다. 이런 개발 과정은 중간중간 확인과 수정이 필요하기도 하고, 기능 구현을 외부에 의존하기도 한다. 실제 개발을 하는 프로그래머에게 제일 많이 하는 조언중 한가지는 이미 만들어져 있는 것을 다시 개발하려고 하지 말라는 것이다. ( Don't invent wheel again) 즉, 이미 기존에 사용할 수 있는 것들을 최대한 활용해서 문제해결에만 집중하라는 것이다. CP에서도 문제 해결에 집중해야 하지만, CP는 제한된 시간안에서 할 수 있는 것만을 대상으로 한다. 그리고, 외부에서 빌려오는 기능은 대부분이 제한되어 있다. Python이나 Java의 확장성이 대부분의 CP에서는 제약 조건이 되고, 언어에서 기본으로 제공하는 라이브러리 기능이외 추가적인 확장 기능은 없다. 

시간제한이 없다면, 거의 대부분의 문제는 단순한 Brute Force 를 통해서 답을 구할 수 있다. 시간 제한이 있기 때문에 조금은 효율적인 알고리즘을 적용하는 것이다. Brute force, simple implementation은 CP에서는 중요하고 잘 훈련해야 하는 부분이다. 잘 생각해야 하는 것이 CP는 black box 테스트이다. 어떻게 구현되어 있는가는 제한 조건만 만족한다면 문제가 되지 않는다. 즉, 지금 문제 해결을 위해 필요한 명확한 알고리즘과 그 구현을 익숙하게 구현하는 것을 목표로 공부를 하는 것이다. 너무 많은 자료조사나 공부가 항상 도움이 되는 것은 아니다. 새로운 아이디어, 어렵지만 잘 만들어진 알고리즘이 일반적인 문제해결에는 도움이 될것이다. 하지만, CP에서는 간단하게 할 수 있다면, 간단하게 해결하는 것이 좋다. 확장성을 생각해서 더 범용적이고 잘 정리된 알고리즘을 준비하기 위해서 필요한 시간동안 다음 문제를 고민하는 편이 훨씬 도움이 되고, 문제가 생겼을때 더 빨리 잘못된 부분을 찾아낼 수 있다.

그렇지만 CP 준비 과정에서는 알고리즘이나 자료구조에 대해서 공부하는 과정을 배제 할 수는 없다. 그래서, 공부를 한다면 문제 해결에 필요한 수준으로 구현하기 위해 필요한 것까지를 목표로 해야 한다. 많은 알고리즘을 학문적으로 증명하기 위해서는 복잡한 수준의 수학과 논리가 필요하고 그런 부분은 그것을 전공으로 공부하는 대학원에서나 필요한 일이다. CP에서 필요한 수준은 명확한 단계별 논리 흐름과 그때에 어떤 형태로 자료를 다루는가 하는 것이다. 끼워야 할 자리에 레고 모양이 맞으면 끼우면 된다. 레고공장에서 어떻게 블럭이 만들어지는지 알 필요는 없는 것이다.

동시에 이렇게 공부를 할 때 주의해야 할 부분도 있다. 즉, 알고리즘에 대한 메타인지와 함께 실제 알고리즘 구현에 대한 메타인지도 필요하다. 즉, I know vs I think I know 를 구분하는 것도 필요하지만, I can implement vs I think I can implement 도 구분히야 한다. 알고리즘이나 자료구조를 알고 있다고 실제로 구현하지 못하면 문제를 풀 수 없다. CP에 대한 훈련은 알고리즘에 대한 지식을 쌓는 것이 아니라, 알고리즘을 구현할 수 있는 능력을 훈련한다고 생각해야 한다.

남이 작성한 코드를 읽는 것은 도움이 되지만, 남의 코드를 단순히 외우는 것은 크게 도움이 되지 않는다. 프로그램은 외국어를 배워서 의사소통하는것과 결이 같다. 외국어가 부족해도 손짓이나 표정을 섞어서 의사소통을 할 수 있는 것은 실제로 같은 방법으로 의사소통의 경험이 있어야 가능하고, 동시에 같은 대상에 대해서 논의 할때 가능한 것이다. 또, 다른 사람의 프로그램 코드는 읽는 것을 목표로 해야 하지, 내용을 그냥 옮겨서 문제를 풀었다고 읽은 것이 아니다. 프로그램의 논리구조를 자기의 언어로 설명하는 것을 코드를 읽었다고 해야 한다. 다른 사람의 코드를 읽어서, 자기가 pseudo code로 프로그램을 작성할 수 있어야 코드를 읽고 이해했다고 할 수 있다. 

CP에서는 빠른 실패가 도움이 될 수도 있다. 경우에 따라 다르겠지만, 자기가 작성할때 생각하지 못했던 부분을 채점 프로그램이 찾아 줄 수도 있다. 생각하지 못한 입력의 범위나 출력의 범위를 알기 위해서는 빨리 실패하는 것도 좋다. 제출과 채점에 불이익이 없다면, 채점 시스템도 디버깅 툴로 이용할 수 있다. 훈련을 위해서 online judge 프로그램을 사용한다면, 당연히 활용할 수 있는 장점중의 하나이다.

2019년 미국 대표중 한명이었던 William Lin 이 CP 에 대해서 설명한 내용은 살펴볼 필요가 있다. ( link )  

CP를 훈련하고, USACO를 준비할때 참고하기 위한 리스트이다.  

1. I/O에 주의한다. 항상 특정한 입력과 출력을 할 수 있도록 준비해야 한다. 
2. 문제풀이는 종이에서도 충분히 가능하고 동시에 자기가 생각한 알고리즘의 소요시간이나 메모리에 대해서 분명히 이해하고 적용해야 한다.  
3. 하나의 문제에 일정 시간 이상 사용하지 않는다.  한문제에 1시간이 넘어간다면, 지금 풀 수 없는 문제로 표시하고 다른 문제를 보거나, 다른 사람의 답안을 읽어보는 것도 좋다.
4. 내 프로그램은 내가 검토하지 말자. online judge에서 검증 받을 수 있는 문제들로 연습해서, 시스템의 도움을 받자.
5. 대부분은 현재 내 수준에 합당한 문제들로 연습하지만, 쉬운 문제, 어려운 문제들에도 일정 부분을 배정하자.
6. 한번 풀었던 문제도 입력의 조건이나 출력의 조건이 달라지면 다른 문제가 된다. 문제를 풀고, 확장 가능성을 생각해보자.

미국에서 USAMO 준비는 다음 책들이 일종의 교과서처럼 사용된다.

For AMC10/AMC12 

Introduction-level

- Prealgebra
- Introduction to Algebra
- Introduction to Geometry
- Introduction to Number Theory
- Introduction to Counting & Probability

Intermediate-level 
- Intermediate Algebra
- Intermediate Counting & Probability

Intermediate 시리즈는 제외하고 Problem Solving V1 을 보는 경우도 많다.

For AIME

the Art of Problem Solving Volume 1: the Basics
the Art of Problem Solving Volume 2: and Beyond

For USAMO or higher

How to Solve It: A New Aspect of Mathematical Method by G. Polya (Author)   
The Art and Craft of Problem Solving by Paul Zeitz (Author) 
How to Solve It: Modern Heuristics by Zbigniew Michalewicz (Author), David B. Fogel  (Author) 
Problem-Solving Strategies by Arthur Engel  (Author) 

영역별 이론 참고 도서들 

102 Combinatorial Problems by Titu Andreescu  (Author), Zuming Feng  (Author)
103 Trigonometry Problems: From the Training of the USA IMO Team by Titu Andreescu  (Author), Zuming Feng  (Author)
104 Number Theory Problems: From the Training of the USA IMO Team by Titu Andreescu  (Author), Dorin Andrica  (Author, Contributor), Zuming Feng  (Author)  
105 Algebra Problems from the AwesomeMath Summer Program by Titu Andreescu 
106 Geometry Problems from the AwesomeMath Summer Program by Titu Andreescu  (Author), Michal Rolinek  (Author), Josef Tkadlec  (Author)

여기에 소개된 책들이외에도 많은 국제대회, 국가대회들의 문제들과 표준 답안들이 있으므로, 그런 문제들을 이용해서 공부를 하게된다. AoPS ( link ), AwesomeMath ( link)를 찾아보면 더 많은 정보들을 얻을 수 있다.

앞쪽에 나와있는 AoPS에서 나온 책들은 단원별로 간단한 이론 설명이 있고, 해당하는 문제들이 있다. 대부분의 문제는 이론의 이해수준을 평가하기 위한 문제들이고, 과거 competition에 나왔던 문제들이나, 변형 문제돌이다.  AoPS 의 온라인 수업도 있고, 이런 교재들이 이용해서 설명하는 After school 프로그램들도 있다. 

조기교육 혹은 선행학습이라는 형태로 요즘은 아주 빠른 나이에 준비를 시작해서, 학교에서 진행하는 수학과는 별개로 준비를 하는 경우가 많다. 빠른 경우는 초등학교 저학년부터 시작하기도 하지만, 보통은 5~6학년에 시작해서 9~10학년쯤 마무리하는 경우가 보통이다. 대략 소요시간은 introduction series - 1년6개월~2년, AIME-1년, 그 다음 단계는 할 수 있는 만큼이라고들 한다.  여기서 말하는 AIME 전까지의 기본적인 과정만 잘 끝내도 일반적인 고등학교 2학년 수준까지 마무리하기 때문에 많이 참가하는 지도 모른다. 대회 성적이 만족스럽지 않아도, 일반적인 수학 선행학습으로 생각하고 몇년간 진행하는 것이다.

시험을 위해서 준비하는 훈련의 난이도는 자기가 준비하는 한단계 앞정도까지만을 권장한다. 어려운 난이도의 문제들은 일정 수준의 이론배경이 없으면 답안을 읽고 이해하기도 힘들기 때문에, 충분한 이론 학습이 되기 전에는 진행이 불가능하다. 그러므로, 다른 여러가지 공부와 마찬가지로 자기의 현재 수준에 대한 정확한 인지가 필요하고, 자기의 수준에 맞는 문제들이나 그것보다 조금 어려운 내용을 가지고 지속적으로 훈련하도록 한다. 

혹시, 어려운 난이도의 문제가 궁금한 사람들을 위해서, 2018년 short list problem (link) 를 적는다. 이 문제들은 2018년 imo 대회를 위해서 참가국들에서 제출한 문제들을 모아둔 것이고, 다음해 imo 대회에서 공개된다.  관련된 자료로는 INFINITY (link) 가 있다.

5~6학년에 시작해서 일주일에 10시간정도의 시간을 지속적으로 투여할때 10학년 혹은 11학년에는 달성할 수 있는 정도가 관심이 있는 사람이 훈련으로 가능한 수준의 한계라고 생각한다. 그리고, 그 수준은 AIME qualified가 될것이다. 누구에게나 시간이라는 자원은 항상 부족한 것이고, 수학공부에서 요구하는 몰입 수준을 생각한다면, 적어도 4~5년동안 거의 매일 한시간 이상의 시간을 투여한다는 것은 누구에게나 가능은 하지만 누구나 할 수는 없는 일이다. 지속과 몰입을 양립시키면서, 긴 시간동안 학습을 계속 할 수 있다면, 그 과정 자체가 훌륭한 성취라고 믿는다.

충분한 몰입과 훈련이 있다면, 학교 교과과정에 있는 수학이론들은 충분히 빠른 시간에 살펴볼 수 있는 것은 사실이다. 자기 주도학습으로 속도를 빨리해서 일반적인 수학이론을 쌓는 방법으로 일반 교과과정을 마무리 한다면 좋은 방향이라고 생각한다. 하지만, 학원이나 개인 교습의 형태로 교재 학습 속도만을 빨리하고 일반적인 문제 풀이를 반복하는 방법으로 진행하는 것은 시험을 잘 보기 위해서 준비하는 방법이지, 생각하는 방법을 훈련하는 것과는 거리가 있다.

수학적인 감각이나 문제풀이 방법은 꼭 어려운 수학문제를 푸는 것으로만 가능한 것은 아니다. 생각하는 방법이기 때문에 쉽고 단순한 문제들도 그 문제를 충분히 이해했다면, 그 문제를 약간 확장하거나 다른 풀이 방법을 찾아 보는 것으로도 전혀 다른 방향으로 진행될 수 있다. 피타고라스 정리를 확장했을 때가 궁금해서 적었던 메모가, Fermat's Last Theorem이 된것은 너무 유명한 것인지도 모른다.  

개인적으로 거의 10년 이상 올림피아드의 경향이나 문제들에 대해서 살펴보지 않았기 때문에, 이 자료의 정확도에 대해서 확신하기는 힘들지만, 최근에 찾아본 자료들에서 나오는 얘기도 아주 달라지지는 않은 것 같다. 다만, USAMO 나 그 이상의 수준의 문제들에 적용되는 이론들이 과거보다 많이 심화되고 어려워진것은 확실하다.

공부의 방법은 여러가지가 있겠지만, 여기서 논의하는 것은 USAMO라는 대회에 초점을 맞추고 설명한다. 어떤 시험을 준비하기 위해서 제일 기초적이고 중요한 부분은 과거에 출제된 문제들에 대한 분석이다. 필요한 이론 공부는 당연한 준비과정의 일부가 되야한다. 이런 기본적인 내용은 제외하고, 몇가지를 정리해본다.

1. Validation of every step 

2. If you can't solve a problem now, you need to check a problem type.

   - Lack of knowledge or Don't get the main idea of a problem

3. Recognize current level

   - I know vs I think I know

4. If you feel burn-out, take enough rest. 

5. Time scheduling

  - If you can assign an hour per each day, only plan for 40 minutes not an hour and a half.

6. If you skip a certain topic, you should remember the gap to fill.  

7. Don't hold a hard problem longer than a certain amount of time.

  - the expected time (problem # / test period) * N, ex) 5 min -> not exceed 20 min, N = 3

Time assign

• Learning Theory : 1
• Problem Solving : 2
• Review Problem solving : 2
• Learning Other's idea : 1
• Review other's idea : 2 
  • analyze the tackling idea: agreeable, new, need to understand
  • Point to extend or another way to tackle

비슷한 두가지 시험에 참가하는 참가자들의 수가 많은 차이를 보이는지 생각해보기 위해서, 비슷한 점과 다른 점들을 살펴보겠다. 

먼저 두가지 시험을 준비하기 위해서는 자기주도 학습이 필요하다. 많은 영역들이 정규교과과정에서 다뤄지지 않거나, 약간의 언급만을 하기 때문에 실제적인 내용을 공부하기 위해서는 관련된 책을 기초로 공부해가는 과정이 필수적으로 요구된다. 물론, 학교외의 기관에서 제공하는 수업을 통해서 이런 과정을 준비할 수도 있지만, 모두에게 가능한 선택지가 아니므로 준비하는 개인의 자기주도 학습을 먼저 언급한다.  

자기주도 학습의 중요성과 함께 peer review도 중요한 부분을 차지한다. 올림피아드에 관심이 있어서 과거 기록들을 살펴보면 특정 그룹의 학생들이 지속적으로 상위권에 등장하는 것을 알 수 있다. 이것은 재능이 있는 사람들이 그 그룹에 모였기 때문에 나타난 현상이라는 설명은 쉽게 이해할 수 있다. 거기에 더해서 peer들과 상호작용의 영향도 이런 현상을 만든 동인중 하나로 생각해야 한다. 주변 peer들과의 경쟁에서 지속적인 자극을 받는것과  문제 해결 과정에서 fast feedback 을 주변 peer들에서 받는 것이 다른 한 부분이 된다. 수학의 증명이나 작성한 코드의 디버깅을 하는 경우, 자기의 논리를 자기가 검증하기 위해서는 먼저 자기 논리에서 충분한 거리만큼 빠져나와서 타인의 시선으로 분석을 할 수 있어야 더 쉽게 가능하다. 사람들은 자기가 원래 가지고 있던 논리의 편향성에서 자유롭지 못하고, 그래서 자기 논리의 문제점을 쉽게 발견하기는 어렵다. 글쓰기를 하는 경우에도, 작성한 글을 적어도 하루이상 지난뒤에 다시 살펴보라고 하는 것과 맥락을 같이 한다고 할 수 있다. 하지만, 주변에 비슷한 peer가 있는 경우는 자기의 논리나 프로그램을 타인의 시선에서 분석한 feedback 을 받을 수 있다.

또, 많은 다른 과목의 학습과 마찬가지로 이 두가지 영역에서는 analytical reasoning - 논리적 추론 과정이 아주 강조된다.  본질적으로 USACO, USAMO 모두 제한된 영역에서 논리적인 추론을 통한 문제해결이다. 다만, 그 문제 해결과정에서 수학적인 전개를 이용하느냐, 실제 동작하는 프로그램의 실행결과를 이용하는냐의 차이가 있을 뿐이다. 논리적 문제해결이 두가지에서 필요한 기본(Basic, not base)에 해당하는 영역이다. 여기에서 analytical reasoning을 언급하는 이유는 단기간에 발전할 수 없는 영역이기 때문이다. 특정한 방법을 암기하고 다시 그대로 재현하는 방법은 일반적인 시험준비에서 훌륭한 대비전략이다. 한데, 올림피아드라는 영역에서는 특정한 방법을 암기하고 재현해는 방법으로 준비하기는 암기해야 할 대상이 너무 많다. 암기할 수 있는 한계내에서 암기하고, 그것들을 어떤 방법으로 재현하고 연결하는가를 결정하는 과정이 이런 추론과정이고, 이것은 프로 바둑 기사들이 기보의 패턴을 인식하고 무의식적으로 복기하는 위해서 훈련하는 것처럼 상당한 기간동안의 훈련이 필요한 일이다. 즉, USAMO, USACO 모두 상당히 긴 시간동안 결과를 확신할 수 없는 상태에서 준비해야 하는 일이다.

두가지에서 서로 다른 부분들을 살펴보겠다. 

먼저, USAMO 의 과정은 다음과 같은 특징들에서 스케이트 보드나 스노보드의 half-pipe 와 비슷하다고 생각한다.  

• 지속적인 가속과 적절한 방향 선택을 하지 못하면, 특정한 위치까지 올라갈 수 없다. 
• 어떤 위치로 가는 경로가 알려져 있지만, 모르는 사람은 존재하는 경로를 읽을 수 없다.
• 문제 풀이의 과정을 잘 이해하고 숙달하지 못하면, 비슷한 문제에 같은 방법을 적용할 수 없다.

또, USACO 와 다른 몇가지 부분도 있다. 

• 문제의 영역이 잘 드러난다. ex) number theory, geometry, combinatorics, algebra
• 풀이 과정의 전체 과정에서 명확한 논리 전개를 확인하는 white box test이다.
• 문제 영역의 제한이 있지만, 훨씬 넓은 범위이다. (link)
  
  • 다른 곳에 출제된적이 없는 문제
  • 가능한 대학 수학 이전의 영역들

다음으로 USACO의 과정은 orienteering 과 비슷하다. 

• 입력을 받아서 기대되는 출력을 만들어 내면 된다.
• 마라톤처럼 정해진 경로로만 가야 하는 것이 아니라 지름길을 찾아서 이용하기를 권장한다.  
• 입력이 바뀌면 전에 있던 경로가 유효하지 않을 수 있다. ( 숲에서 길 찾는 방법을 평원에서 적용하기는 힘들다.)
  • 특정 입력에서만 유용한 경로도 존재할 수 있다.  

또한 USAMO 와는 이런 다른 점이 있다.  

• 구체적인 풀이 과정을 확인하지 않는 black box test 이다. 많은 경우 입력과 출력을 시스템에서 확인하고 평가한다.
• 특정한 알고리즘, 수학적 이론이 구체적으로 제시된다. (link)
• 알고리즘의 이론적인 이해가 부족해도, 알고리즘을 정확히 구현할수 있다면 문제 풀이에 사용할 수 있다. 

이렇게 두가지 시험에 대해서 비슷한 부분과 다른 부분들에 대해 정리해봤다. 이 내용들은 지극히 개인적인 조사와 분석에 의한 것이므로 실제와 다를 수 있다.  다음에는 이 분석을 기초로 어떻게 준비해야 효과적인 수 있을지에 대한 학습전략을 생각해 보겠다.

미국에서 고등학생들을 대상으로 하는 올림피아드 중에서 준비하는 사람들의 성격이 비슷할 것 같은 두가지에 대해서 확인한 몇가지 자료를 가지고 어떤 차이가 있고, 왜 그런 차이가 있을까 생각해봤다.

먼저, 2 가지 모두 몇번의 선발과정을 거쳐서 상위 득점자들이 모여서 다음 단계를 진행한다.

USAMO 는 다음과 같은 순서로 진행된다.

1. AMC10 / AMC12 : 누구나 참가 가능
2. AIME : 1의 시험에서 상위 득점자
3. USAMO / USAJMO : 1+2 시험의 상위 득점자 500 명
4. MOP : 3의 상위 득점자 60명 내외
5. IMO : 4 + @

USACO 의 경우

• Dec, Jan, Feb, Mar 4 회의 online test
• bronze - silver - gold - platinum 단계별 승급
• Summer camp : platinum 상위 득점자
• IOI : 4 + @

2019-2020 의 경우 자료가 다 나오지 않아서, 2018-2019 자료를 기준으로 분석했다.

USAMO 

미국내 참가자 만을 대상으로 한 결과이다.

USACO 

레벨에 따른 참가자 분포가 달라질 수 있지만, 단순히 전체 참가자 중에서 미국 참가자수를 기준으로 하면, 전체 참가자의 50%정도가 미국내 참가자 이다.

Bronze 레벨 참가자는 AMC10/AMC12 참가자와 비슷한 위치에 있다. 

AMC10/12 는 2번의 시험이고 중복 참가가 가능하므로 대략 70000명 정도가 참가한다고 할 수 있다. (AMC10A+AMC12A) Bronze 레벨 참가자의 1/2을 미국 참가자라고 하면, 1500 명정도라고 할 수 있겠다. 4번의 시험동안 추가 유입이 가능하지만, 실제로 참가자수는 매번 줄어든다. 이 줄어드는 참가자들은 다음 단계로 승급된 경우도 있지만, 그냥 포기한 경우도 있을 것이다.  `18 12월 bronze 참가자 중에 Pre-C는 3103명이며, 이중 50%가 미국내 참가자라고 하면, 이중에 1550명이고 이중 853명이 승급되었으므로 참가자는 700명남고 1월에 참가자는 1000명정도에 300명이 승급되면, 다시 700명정도가 남는다. 다음인 2월에는 850/139 ~ 700, 3월에는 480/88 정도라고 할 수 있다.

1500 명 vs. 70000 명. 40배 이상의 차이가 된다. 왜 이런 차이가 나타난 것일까? USACO가 USAMO보다 알려진 기간이 짧아서인것도 한가지 이유가 될 테고, 학교에서 기본으로 배우는 수학과 개인이 추가로 배워야 하는 프로그래밍이라는 차이도 한가지 이유가 될 것이다.

또다른 차이라고 생각한 것은 2가지 시험을 위해서 준비하는 방향성 혹은 방법의 차이가 있는 것 같다. USAMO를 준비하는 학생들은 대부분이 4~6학년 사이에 AMC8으로 시작해서 AMC10/AMC12를 준비한다. 이 과정에서 학생들은 거의 표준화된 교재들을 순서대로 공부하고, 필요에 따라서 개인적인 추가 수업을 받기도 하면서 준비한다. 하지만, USACO를 준비하기 위해서는 특별히 알려져 있는 준비과정이 없다. 또, 프로그래밍은 새로운 언어를 배우는 것과 닮아 있어서 개인의 역량에 크게 영향을 받는다. 어떤 사람은 단순히 입문 교재만을 읽어보고도 충분한 정보를 습득해서, 자기가 원하는 프로그램을 작성할 수 있지만, 어떤 사람은 모든 과정에 익숙해지기 전에는 작은 프로그램도 못 만드는 경우도 있다. 여기에 더해서, Competitive Programming 이라고 하는, 이런 대회를 준비하는 것은 일반 프로그래밍을 배우는 것과는 또 다른 방향으로 접근해야한다. 

이런 것이 참가자 수의 현격한 차이를 만든 이유라고 생각한다.  다음에는 USACO 와 USAMO 시험에 대해서 조금은 다른 방향으로 한번 생각해보려고 한다. 두 가지는 어떤 방향성을 가지고 준비해야 하는가? 혹은 어떤 것이 준비에 더 어려운가? 준비를 위해 더 효과적인 방법은 없을까? 여러가지 방향으로 생각들을 정리해서 적어보겠다.

출처: https://www.acmicpc.net/problem/15686

문제 설명

입력

출력

입력 예

출력 예

제약조건

문제 풀이

프로그램 내용

...
bitset<MAX_M> bsets;
int min_dist = INT_MAX;	
vector<pair<int, int>> t_shops;
	
for(int b = 0; b < (1<<(int)shops.size()); ++b)
{
	if (__builtin_popcount(b) == tM) 
    {
    	bsets = b;   /// 해당하는 치킨집 조합 결정
    	for(int id=0; id< (int)shops.size();++id)
        {
        	if(bsets[id]) 
        	{
        		t_shops.push_back(shops[id]);
	        }				
		}
        int t_dist = 0;
        for(int id = 0; id<(int)house.size(); ++id)
        {
        	int h_dist = INT_MAX;
            int ht_dist = INT_MAX;
            int x, y;
            tie(x, y) = house[id];								
            for(int idn = 0; idn < (int)t_shops.size(); ++idn)
            {
    	        int t_x, t_y;
        	    tie(t_x, t_y) = t_shops[idn];									
            	int hh_dist = abs(x - t_x) + abs(y - t_y);
            	if( ht_dist > hh_dist)
            		ht_dist = hh_dist;
			}
            if (h_dist > ht_dist)	/// 각 집의 치킨거리 최소값
            	h_dist = ht_dist;
			t_dist += h_dist;
		}
	t_shops.clear();
	if( min_dist > t_dist)	/// 도시 치킨 거리 최소값
        min_dist = t_dist;
	}
}

관련된 문제

• bitset :   USACO Trainging : 2.1.6 Healthy Holsteins ( link )

출처:  https://cses.fi/problemset/task/1639

문제 설명

입력 

출력

입력 예

출력 예

제약조건

문제 풀이

프로그램 내용

...
for(int i=0; i <= m; ++i)
{
	for (int j=0; j <= n ; ++j)
	{
		if ( i == 0)
        	dist[i][j] = j; /// init for desStr
		else if ( j == 0)
        	dist[i][j] = i; /// init for srcStr
		else if ( srcStr[i-1] == desStr[j-1])
        	dist[i][j] = dist[i-1][j-1];
		else
        	dist[i][j] = 1 + min({	dist[i-1][j],      /// insert
									dist[i][j-1],      /// remove
									dist[i-1][j-1]});   /// replace
	}
}
...

Dynamic Programming ( link )

출처: https://train.usaco.org/usacogate

문제 설명

입력

출력

입력 예

출력 예

문제 풀이

프로그램 내용

...    
    for(int idx=0; idx < (1<<numG) ; ++idx)
    {
        vector <int> feeds(numV, 0);
        bitset<16> check(idx);

        for (int idx2=0; idx2 < numG ; ++idx2)
        {
            if( check[idx2] )
            {
                for(int idx3=0; idx3 < numV; ++idx3)
                {
                    feeds[idx3] += Feed_list[idx2][idx3];
                }
            }
        }

        /// check health : feeds vs V_req
        bool healthy = true;
        for(int idx2=0; idx2 < numV; ++idx2)
        {
            if ( feeds[idx2] < V_req[idx2])
            {
                healthy = false;
                break;
            }
        }

        if ( healthy 
        			&& check.count() < feed_count 
        			&& check.to_ulong() > feed_bit.to_ulong())
        {
            feed_count = check.count();
            feed_bit = check;
        }
    }
...

Chapter 2. Bigger Challenges (link)

출처: https://www.acmicpc.net/problem/2903

문제 설명

입력

출력

입력 예

출력 예

제약조건

문제 풀이

프로그램 내용

...
vector<int> dots(16,0);
vector<int> edges(16, 0);
vector<int> faces(16,0);
    
dots[0] = 4;
faces[0] = 1;
edges[0] = 4;
    
for(int id=1; id<=15 ; ++id)
{
	faces[id] = faces[id-1]*4;
	edges[id] = edges[id-1]*2 + faces[id-1]*4;
	dots[id] = dots[id-1] + faces[id-1] + edges[id-1];
}
...

관련된 문제