KOI 고등부 풀기 (7년을 7일에) 결과 정리

생각보다 시간이 많이 빠듯했다. 할 것도 많았고, 오랜만에 하다보니까 하나하나 생각하는데 시간도 꽤나 오래 걸렸다. 사실 애초에 이 셋에 일주일동안 쓴 시간이 다 합쳐봤자 얼마 안되었다는게 가장 문제였다. 

18솔을 했다. 하지만 여왕벌은 거르더라도 실골 문제들을 풀자고 만들어 놓은 연습셋이 아니기 때문에 아쉬운 부분이 많다. 그래도 일단 쭉 정리를 해보려 한다

A - 사냥꾼
KOI 2013 고등부 1번
그냥 딱히 생각하는 것도 오래 안걸리고 구현도 딱히 안빡셌다. 무난한 문제
풀이 https://stonejjun.tistory.com/98

B - 막대기
KOI 2013 고등부 2번
문제를 잘 못봤다. 관찰 위주의 문제였고, 솔직히 오래 걸릴 문제도 아니었지만, 문제 조건을 잘못 봐서 오래 고생한것이 컸다. 자신감 있는 형식의 문제
풀이 https://stonejjun.tistory.com/98

C - 전봇대
KOI 2013 고등부 3번
이것도 그냥 문제를 보자마자 거의 바로 풀이가 생각났던 문제. 삼분탐색이 생각났는데, 삼분탐색은 말로만 들었었고 한번도 구현한 적이 없었다. 그런데 구현이 전혀 어렵지 않았다. 무난한 문제. 
풀이 https://stonejjun.tistory.com/98

D - 수족관 3
KOI 2013 고등부 4번
꽤 오랜 시간 투자를 했고, 다양한 방법으로 접근을 했다. 풀이가 느낌은 있는데 오류 없이 정확히 성립하는 풀이를 찾기가 어려웠다. DNC나 세그트리를 쓰면 될 것 같다. 정확히 말하자면 세그트리의 각 노드를 어떤식으로 구성해야 깔끔하게 합치는 과정이 이루어지고 답을 구할 수 있는지 대충 감은 잡히는데 완벽하게 나오지가 않는다. 아마도 가장 먼저 업솔빙을 할 문제.
풀이 https://stonejjun.tistory.com/98

E - 관중석
KOI 2014 고등부 1번
그냥 간단한 수학 문제. 기약분수라는 아이디어만 있으면 굉장히 간단하게 해결할 수 있다. 
풀이 (준비 중)

F - 버스 노선
KOI 2014 고등부 2번
쉬운문제임에도 불구하고 애를 먹었다. 일단 원형을 보는 순간 두배로 늘려서 일직선으로 늘리는 테크닉을 생각했다. 그리고서는 세그트리밖에 생각이 안났다. 많이 봤던 유형 같아서 세그트리를 쓰지 않기 위해서 계속 생각을 했고, 알고보니 정렬 한 번이면 끝나는 문제였다. 
풀이 (준비 중)

G - 동전 게임
KOI 2015 고등부 1번
승부차기를 알고 있다면 그냥 너무 쉬운 문제. 머리로만 푸려면 1차이로 헷갈릴 수 있으니 공책을 조금만 사용하면 뚝딱.
풀이 (준비 중)

H - 구간 성분
KOI 2015 고등부 2번
이번 셋을 돌기 전에 풀었었던 문제. 웰노운 해싱 문제. 
풀이 (준비 중)

I - 매트
KOI 2015 고등부 3번
일단 문제를 읽으면 이 문제가 DP문제라는 것은 바로 알 수가 있다. 그런데 제한이 많이 붙어있고, 관찰을 해야하는 부분도 생각보다 어렵다. 구현도 DP 치고 꽤나 까다로운 편. 
풀이 (준비 중)

 J - 여왕벌
KOI 2015 고등부 4번
악명 높은 문제. 보지도 않았고, 생각도 안해봤고, 업솔빙도 안할 문제.
풀이 (준비 중)

K - 리조트
KOI 2016 고등부 1번
이 문제도 딱 보자마자 DP가 바로 생각나는 문제. DP table 정의하기도 어렵지 않고, 점화식을 세우는 것도 그렇게 어렵지 않았다. 무난한 문제.
풀이 (준비 중)

L - 주유소
KOI 2016 고등부 2번
2년전에 풀었었던 문제. 그때 봤을때는 충격과 공포의 문제였다. 다익을 섞는다는 것을 아예 생각조차 해본적이 없고, n개의 노드에 대해서 각각 다익을 돌려본다는 것 조차 생각해 볼 수도 없었다. 지금봐도 금방 풀기는 힘들어 보이는 문제. 오랜만에 다익을 짜봤다. 
풀이 (준비 중)

M - 트리
KOI 2016 고등부 3번
최근에 배운 내용들 때문에 뇌절한 문제. 사실 내 풀이가 맞을수도 있다. HLD를 최근에 배운탓에 HLD+LCA밖에 풀이가 떠오르지 않아서 HLD 복습하는김에 짰는데 11트를 했다. 정말 미치는 줄 알았다, 알고보니 LCA에서 sparse table을 안 채우고 있었다. 진짜 대회에서 이런 실수를 할 걸 생각하니까 눈앞이 깜깜했다. 그래도 코드짜는 연습은 정말 여러번이 되었다. 
풀이 (준비 중)

N - 먼 별
KOI 2016 고등부 4번
대충 생각해 봤는데 감이 살짝밖에 안잡히는 문제. 이 문제에 쓰는 테크닉을 알고 있는데 그 테크닉을 쓰면 왜 되는지 전혀 이해가 안된다. 시간을 좀 더 가지고 나중에 풀어볼만한 문제. 
풀이 (준비 중)

O - 물통
KOI 2017 고등부 1번
대회에서 생각이 안나면 생각보다 크게 말릴것 같은 형식의 문제. 관찰을 하나만 하거나 STL을 좀 잘 다룰줄 알면 정말 쉽게 풀 수 있다. STL모르면 구현을 좀 돌아가는 과정에서 뇌절할 요소가 꽤 있다고 생각한다. 
풀이 https://stonejjun.tistory.com/99

P - 문명
KOI 2017 고등부 2번
이것도 2년전쯤에 풀어봤었다. 굉장히 좋은 문제라고 생각한다. 그때 구현해놓은 거 보니까 말이 안나왔다... 다시짜면 길이가 1/3 정도로 줄 것 같았다. 아무튼 무난하게 좋은 문제. 
풀이 https://stonejjun.tistory.com/99

Q - 요리 강좌
KOI 2017 고등부 3번
이번 셋 최대 아웃풋. 사실 1차적으로 생각하는데 얼마 안걸렸다. 기본적으로 DP라고 생각했고, 3개만 추려낸다는 관찰은 오래 걸리지 않았다. DP table 정의도 잘 되었고, DP 식도 잘 세워놨는데 시간복잡도가 이상했다. DP 문제는 정말 많이 풀어봤다고 생각했는데 좀 쉬다보니까 간단한 테크닉도 기억을 하지 못했던 것 같다. 그래도 풀이 전체를 완성하는 데 그렇게 많은 시간을 쏟아붓지는 않았다. 문제는 구현이었다. 무엇이 문제였는지 구현 20틀을 꼬라박고 결국 코드를 아예 처음부터 새로 짜서 맞았다...
풀이 https://stonejjun.tistory.com/100

R - 조개 줍기
KOI 2017 고등부 4번
DP느낌의 문제이고 DNC나 세그먼트 트리를 써야될 것 같은 문제 업데이트 되는 구간이 특이하다는 사실을 발견했는데 이를 DNC를 이용해야 하는지 세그를 이용해야하는지 아직 고민을 못했다. 
풀이 https://stonejjun.tistory.com/101

S - 화살표 그리기
KOI 2018 고등부 1번
그냥 간단한 문제. 딱히 할 말이 없다. 
풀이 (준비 중)

T - XCorr
KOI 2018 고등부 2번
그냥 간단한 문제. 딱히 할 말이 없다. 
풀이 (준비 중)

U - 조화로운 행렬
KOI 2018 고등부 3번
풀겠다고 다짐한지가 굉장히 오래 지난것 같고, 풀이도 어느정도 알고있는 문제. 내가 다른 포스팅에서 언급했던 3-elements 느낌의 문제이다. DNC로 해결하거나 2D 세그를 잘쓰면 해결되는 문제. 사실 2D세그를 짤 줄 몰라서 묵혀두고 있었던게 크다. 
풀이 (준비 중)

V - 족보
KOI 2018 고등부 4번
작년에 풀이를 보고 풀어봤던 문제. 이걸 대회중에 어떻게 생각할 수 있나 싶다. 풀이 자체도 굉장히 관찰과 함께 신박하고 특히 구현 난이도가 굉장히 높은 문제였다. 
풀이 (준비 중)

W - 괄호
KOI 2019 고등부 2번
생각하는게 은근 까다로울 수 있는 DP문제. 잘못하면 뇌절하기 쉽다. 특히 구현 단계에서 string와 dp라는 좀 색다른 조합으로, 생각을 조금만 한다면 굉장히 간단하게 구현할 수 있지만, 그걸 캐치하지 못하면 빙빙 돌아가면서 굉장히 어렵게 구현을 해야하는 요소가 많다. 
풀이 (준비 중)

X - 검은 돌
KOI 2019 고등부 3번
풀이의 일부만 알고 있는 문제. 내가 풀이를 말했더니 친구가 그 풀이가 맞았다고 했다. 하지만 난 아무리 생각해봐도 시간복잡도가 흘러 넘칠 것 같은 문제. 사실 고민할 시간이 있었다면 이 문제를 잡고 짜보았을 것 같다. 문제에 대해서 말을 좀 하자면 DP 테이블에서 조개줍기와 같이 구간이 되게 특이하다는 성질을 이용하면 된다. 구간의 단조성이라고 해야할지, 아무튼 이를 이용해서 dnc를 해야할 것 같은데, 굳이 필요가 없는 것 같기도 하다. 확실히 트리에서 진행되는 거라 안 익숙해서 생각이 잘 안되는 것 같다. 
풀이 (준비 중)

Y - 고압선
KOI 2019 고등부 4번
풀이를 알고 있는 문제. 하지만 내가 못하는 파트에다가 말도 안될 것 같은 구현이라고 생각한다. 애초에 이 풀이 자체를 생각할 수 있을지도 잘 모르겠지만, 생각해 냈다고 하더라도 이 테크닉을 현장에서 직접 구현하기는 힘들 것 같다. 그래도 조만간 한번쯤은 무조건 풀어봐야 하는 문제.  
풀이 (준비 중)