충북 동명초등학교 문동국 선생님께서 작성하신 내용입니다.
<전국정보올림피아드 2012~2016년 5년간의 문제 분석 및 경향>
1) 올림피아드 특성상 고등부 문제1,2,3번 문제는 초,중등부 2,3,4번 문제와 겹치는 문제가 많아 따로 기술하지 않았습니다. (그 이외 문제들은 제가 시간부족 및 능력부족으로 시도하지 못한 문제는 빼놓았습니다)
2) 대체적으로 최근 2014~2016년 3년 간의 문제는 이전의 문제보다 다소 쉬워진 경향이 있습니다. 전형화 된 알고리즘을 요구하기 보다는 수학적 능력을 요구하는 문제들로 구성되어 있습니다.
3) 의외로 그래프의 깊이탐색이나 너비탐색의 문제는 거의 나오지 않았습니다. 전형화 된 문제와 풀이이기 때문일 것이라는 생각됩니다.(2016년 초등부4번 문제 제외-너비탐색)
4) 동적계획법 문제 항상 나오며 초등부는 3번, 중등부는 2번,3번 문제로 나옵니다. 특히 중등부 3번 문제로 나온 동적계획법은 상당히 난이도가 높습니다. 초,중등부는 여기서 은상과 금상이 갈라진다고 보시면 될 것 같습니다.
5) 그리디(Greedy) 문제의 출제빈도가 매우 높습니다. 거의 매년 빠짐없이 나온다고 봐도 됩니다. 아이들에게 필수적으로 지도해야 할 영역입니다. 특히 3번 이상에서 나오는 그리디 문제는 대체로 까다롭습니다.
6) 최근 2년 연속으로 중등부 문제로 트리가 나왔습니다. 트리가 자료구조 중에서는 종류도 많고 난이도도 가장 높지 않나 생각합니다. 자료구조의 중요성이 강조되는 듯합니다.
6) 아래 문제들은 제가 직접 풀어보면서 쉬웠던 것, 어려웠던 것은 저의 기준으로 정하고 기술한 것으로 개인의 능력 및 특성차에 따라 크게 다를 수 있음을 알려드립니다.
7) 이후 업무일정은 그동안 지역본선, 전국본선에서 제가 푼 문제를 정리하여 알고리즘별로 분류 후, 같은 알고리즘 내에서 수준을 나누어 아이들이 순차적으로 학습할 수 있는 기출문제 중심 알고리즘 코스를 만들 예정입니다.
[2016년도 문제분석]
[2015년도 문제분석]
1.초등1번 사과 - 단순반복문+조건문
2. 초등2번 벨트- 수학문제
3. 초등3번 카드게임- 동적계획법 초
- 하향식 동적계획법으로도 충분히 풀 수 있다.
- 상향식으로 바꿀 수 있기에 지도하기 좋은 문제
4. 중등1번 동전게임 - 배열과 조건문을 활용한 문제- (중상)
5. 중등2번 =초등3번과 같음
6. 중등3번
- 이 문제 전에 트리의 기본문제가 필요함 (상)
- 어려운 이유는 노드 수가 10^5, 이진트리형태가 아님, 따라서 배열의 인덱스를 활용하지 못함
[2014년도 문제분석]
1. 초등1번 전자레인지-초기 그리디 연습문제로 단순하게 풀 수 있다. (하)
2. 초등2번 색종이문제- 2차원 배열 연습문제 기초문제(하)
3. 초등3번 격자상의 경로- 재귀함수를 활용한 미로탐색방법+경우의 수 문제(중하)
- 이 문제 전에 미로탐색 문제가 있으면 좋을 듯 하다.
- 수학의 확률과 통계단원의 조합의 공식을 안다면 쉽게 풀 수 있다.
4. 초등4번 버스노선- 그리디 문제+각 노선의 포함관계를 묻는 문제 (상)
5. 중등 1번 =초등3번과 같음
6. 중등 2번 관중석- 기약분수, 공약수와 관련된 수학문제 (중)
7. 중등 3번 버스노선=초등 4번과 같음
[2013년도 문제분석]
1. 초등1번 올림픽- sort 함수를 활용하여 정렬하는 방법을 묻는 문제(중하)+조건,반복문
2. 초등2번 택배- 그리디 문제 (중상)
3. 초등 3번 입력 숫자 - 단순히 표에 숫자를 채우는 문제 (중)
4. 중등1번 -사냥꾼문제 (중상), 영역 안의 포함과 관련된 문제, 영역과 다른 영역의 관계까지 확인할 수 있어야 풀 수 있는 문제
5. 중등2번-초등 3번과 같음
6. 중등3번 막대기-동적계획법문제, 일단 막막했던 문제, 두 기준선을 가지고 각각 점화식을 만들어 구해야 하는 문제(상)
[2012년도 문제분석]
1. 초등1번 문제-풀지 않았습니다. 귀차니즘
2. 초등2번 예산문제-중, 수학문제
3. 초등3번 통학버스문제- 중, 전형적인 그리디문제
4. 중등1번=초등2번과 같음
5. 중등2번 전시장-동적계획법 문제로 하향식으로 풀 수 없으며, 까다로움, 상향식으로 풀어도 O(n^2)->O(n)으로 고쳐야 함
6. 중등3번 원숭이-그래프 문제로 dfs, bfs의 문제라기 보다는 조건에 맞지 않는 정점을 옮기는 문제(중상)
