2020. 5. 1. 15:41ㆍPS/도전
서론
안녕하세요! 비키라입니다.
저는 2020/03/29부터 KOI 전국본선 고등부 1,2번 문제들을 본격적으로 풀었습니다. (도전 내용)
도전을 시작할 때 채점이 가능한 1,2번 문제들을 전부 풀자는 목표를 세웠고, 먼저 백준 온라인저지에
있는 모든 KOI 고등 1,2번 문제를 문제집에 정리하였습니다.
2019년 최신 문제부터 1997년 문제까지 차례대로 나열되어 있으며 편한 순서대로 풀면 됩니다.
오래된 문제들은 대부분 인터넷에서 풀이를 찾을 수 없었는데 이 경우 오랜 시간 풀이를 찾아 헤멨고, 그러다가 KOI 공식 풀이를 찾아, 이를 참고하여 공부했습니다.
한국정보올림피아드 전국본선 문제들을 공부하시는 분들을 위해 고등부 1,2번 문제의 풀이를 정리합니다.
구성은 아래와 같습니다.
1. 날짜
2. 문제
3. 핵심 아이디어와 풀이 링크
KOI 고등부 1,2번 정리
(※ 2020년 5월 31일 기준 백준 온라인 저지에서 채점 가능한 문제들입니다.)
- 제 블로그에 풀이가 없는 문제의 경우 다른 분의 블로그 풀이 링크를 걸었습니다
경고
어떤 문제이든 문제에 대한 충분한 고민을 하는 것이 먼저입니다.
맹목적으로 풀이를 먼저 읽고 공부하는 것은 문제 해결력에 거의 도움되지 않을 뿐더러, 스스로 생각하는 힘에 부정적 영향을 끼칠 가능성이 큽니다.
이 글을 보시는 여러분이 KOI 문제에서 최대한 많은 것을 얻어가길 기원합니다.
사용법
1. 문제 이름을 누르면 문제 사이트로 연결됩니다. 문제를 읽고 충분히 이해합니다.
2. 풀 수 있을 때까지 풉니다. 너무 오랜 시간 동안 안 풀리면 이 글로 돌아와 풀이를 참고합니다.
3. 풀이의 핵심만 읽고 스스로 구현을 시도합니다.
4. 구현도 어렵다면 풀이의 소스코드를 모티브로 스스로 구현해봅니다..
5. 다른 사람의 소스코드를 참고하여 AC를 받았다면 반드시 풀이를 덮고 처음부터 끝까지 다시 구현해봅니다.
CTRL + F 누르고 원하는 연도/문제이름을 입력하시면 쉽게 찾을 수 있습니다.
2019년 1차대회
1번: 쇼핑몰
2번: 점프
구간을 똑똑하게 쪼개어 DP를 해줍니다.
JusticeHui님 : https://justicehui.github.io/koi/2019/06/30/KOI19_1_H2/
2018년
1번: 화살표 그리기
2번: XCorr
누적합 배열과 lower_bound를 이용해 해결할 수 있습니다.
IOI KOREA : https://www.youtube.com/watch?v=hQs9jVQUYBY
2017년
1번: 물통
BFS 문제인데, 한 물통은 무조건 꽉 차 있거나 비어 있을 수 밖에 없다는 것에서 착안한 풀이입니다.
IOI KOREA : https://www.youtube.com/watch?v=I_k8FDR0uiM&t=34s
2번: 문명
Union-Find로 BFS보다 빠르게 처리할 수 있습니다.
IOI KOREA : https://www.youtube.com/watch?v=0OjHIQvwR9M
2016년
1번: 리조트
DP 문제입니다. 재귀함수로 매우 직관적으로 풀 수 있습니다.
JusticeHui님 : https://justicehui.github.io/koi/2018/10/30/BOJ13302/
2번: 주유소
다익스트라의 변형입니다. 다익스트라 알고리즘을 모른다면 먼저 공부하고 푸는 것이 훨씬 이해에 도움이 됩니다.
JusticeHui님 : https://justicehui.github.io/koi/2018/12/15/BOJ13308/
2015년
1번: 동전 게임
이런 종류의 문제가 낯설다면 KOI 초등부 문제를 먼저 풀고 오는 것이 좋습니다.
시뮬레이션 문제입니다. 재귀/수식으로 해결 가능합니다.
마이구미님 : https://mygumi.tistory.com/305
2번: 구간 성분
vector 전체를 std::set에 넣거나, 해싱으로 해결 가능합니다.
2014년
1번: 관중석
최대공약수 알고리즘을 이용해 서로소인지 탐색해주며 가능한 경우를 전부 탐색해도 되고, 조금 더 최적화 시킬 수도 있습니다.
sgc109님 : https://sgc109.tistory.com/108
2번: 버스 노선
라인 스위핑 문제인데 적절한 정렬과 케이스 분류가 중요합니다.
2013년
1번: 사냥꾼
적절한 정렬 후 DP를 수행하면 됩니다.
이때 투 포인터로 O(n)에도 가능하고, 이분탐색으로 O(nlogn)에도 가능합니다.
JusticeHui님 : https://justicehui.github.io/koi/2018/07/23/BOJ8983/
2번: 막대기
꽤 복잡한 다이나믹 프로그래밍 문제입니다. DT의 정의와 채우는 방법을 잘 정하는 것이 중요합니다.
2012년
1번: 예산
대표적인 이분탐색 문제입니다. 예산의 합을 기준으로 이분탐색을 수행하는 것이 핵심입니다.
occidere님 : https://blog.naver.com/occidere/221364545507
2번: 달리기
세그먼트 트리/펜윅 트리의 개념이 꼭 선행되어야 합니다. 문제해결을 위한 창의적 알고리즘 고급편에 자세한 풀이가 나와 있습니다.
JusticeHui님 : https://justicehui.github.io/koi/2019/03/03/BOJ2517/
2011년
1번: 공약수
최대공약수 알고리즘(유클리드 호제법)을 안다면 쉽게 해결할 수 있습니다.
travelbeeee님 : https://travelbeeee.tistory.com/250
2번: 부서 배치
이분매칭 및 Knapsack문제와 유사한 DP를 사용해야 합니다.
2010년
1번: 세 용액
대표적인 투포인터 문제입니다.
2번: 체인점
다익스트라 + 펜윅트리/세그트리 로 해결하는 문제입니다. 펜윅트리로 최대값/최소값 트리를 구성할 수 있는 특수한 조건이 특징입니다.
2009년
1번: 섞기 수열
간단한 수학 + 사이클 찾기 문제입니다. DFS연습용으로 좋습니다.
2번: 줄다리기
살짝 복잡한 라인 스위핑 문제입니다. 로직을 받아드리려면 문제를 확실하게 이해해야 합니다.
2008년
1번: 채점
어떤 방법이 가능한지 묻는 DP 문제입니다. long long 배열의 원소 하나를 64bit bool 배열로 활용하므로써 최적화를 진행합니다.
2번: 달팽이
기하 문제입니다.
IOI KOREA : https://www.youtube.com/watch?v=xAQCAGqmc18
2007년
1번: 점
수학적 관찰력이 중요한 문제입니다.
채점, 체인점에 이은 원조 '점' 문제이죠.
2번: 초고속철도
Lower_bound를 이용하여 정말 창의적으로 DP를 수행해야 합니다.
2006년
1번: 기지국
문제는 무섭게 생겼지만 막상 보면 간단한 DP 문제입니다.
시간복잡도가 O(n^2)가 나오고 n이 10000까지 가능하기 때문에 쫄기 쉬운데 실제로는 넉넉하게 작동합니다.
2번: 두부 모판 자르기
복잡한 DP 문제입니다. 문제 해결을 위한 창의적 알고리즘 고급편에 자세한 설명이 있습니다.
JusticeHui님 : https://justicehui.github.io/koi/2019/01/06/BOJ10937/
2005년
1번: 양팔 저울
탐색 공간의 배제가 적절하게 해서 구현하면 됩니다.
제 풀이는 980ms 대로 매우 빠듯하게 동작하기 때문에 가능하다면 다른 분의 풀이를 참고하시기 바랍니다.
2번: 경비행기
매우 재밌는 이분탐색 + BFS 문제입니다. 위에서 '예산' 문제를 푸셨다면 이분탐색을 적용하기 쉬울 것입니다.
2004년
1번: 돌다리 건너기
2번: 고속버스 노선
2003년
1번: 트리의 높이와 너비
규칙을 찾으면 중위 순회라는 것을 파악할 수 있습니다. 이후 중위 순회를 구현하면 됩니다.
2번: 숫자 박스
개인적으로 꽤나 어려운 DP 문제였습니다.
DP 정의를 얼마나 꼼꼼하게 세우느냐가 향후 체감 난이도를 결정합니다.
2002년
1번: 로봇 조종하기
무조건 DP 식을 스스로 세워보는 것이 좋습니다.
2번: 헬기착륙장
2001년
1번: 두 배열의 합
문제가 매우 간단합니다. 이분탐색, 해싱, 투 포인터.. 어떤 것을 활용해도 좋습니다.
2번: 로봇
구현이 자칫하면 루즈해질 수 있는 BFS 문제입니다. 화이팅입니다!
2000년
1번: 수열 축소
BOJ에 있는 문제는 한국정보올림피아드 원문제와 조건은 비슷하지만 풀이가 전혀 다릅니다.
모두 DP문제입니다.
KOI 버전 : https://howtoliveworldnice.tistory.com/112?category=831934
BOJ 버전 : https://howtoliveworldnice.tistory.com/110?category=831934
1999년
1번: 검은점과 하얀점 연결
최대값과 함께 답을 복원해내야 하는 DP 문제입니다. 역추적 과정이 꽤나 흥미롭습니다.
1998년
2번: 통나무 옮기기
통나무를 어떻게 구조화할 것이냐가 쟁점인 BFS 문제입니다.
1997년
1번: 다각형의 확장
푸신 분이 있다면 댓글로 힌트를 남겨주세요! 풀이를 쓰셨다면 링크를 달도록 하겠습니다.
2번: 미로만들기
0-1BFS 문제인데, 다익스트라 및 BFS 변형으로도 풀립니다.
3번: 벽장문의 이동 (3번이지만 난이도가 1번보다 낮아 넣었습니다.)
간단한 재귀 문제입니다. 입력크기가 작아 적당한 탐색 공간 배제로 메모이제이션 없이 0ms를 받을 수 있습니다.
1996년
1번: 잠수함식별
매우 신선했던 오토마타 이론을 활용하는 문제입니다. 이것이 정규표현식이라고도 하는데, 이미 구현된 함수를 사용하는 것보다 오토마타 이론을 공부하여 푸는 것이 훨씬 재밌습니다.
DP의 정의를 잘 세우는 것이 중요합니다.
마무리
총 46개의 문제중 16문제가 DP문제입니다. 1,2번 만점을 위해 DP문제를 확실히 익히는 것도 좋은 전략입니다.
스스로 알고리즘 문제 푸는 것을 즐기기에 다른 분들도 함께 즐길 수 있길 바랍니다.
여러분의 댓글 하나, 하트 하나가 글쓴이에게 큰 힘이 됩니다.
'PS > 도전' 카테고리의 다른 글
| #1 2SUM #2 No Division Multiplying (0) | 2020.08.07 |
|---|---|
| KOI 2019 2차 대회 2번 '괄호' 풀이 (0) | 2020.07.11 |
| [도전 30일차] 다각형의 확장 (도전중) (0) | 2020.04.30 |
| [도전 29일차] 헬기 착륙장 - KOI 고등부 풀이 (0) | 2020.04.29 |
| [도전 27일차] 검은점과 하얀점 연결 풀이 (0) | 2020.04.27 |