돌이 코딩하는 방

내 인생 처음이자 마지막 KOI 본선... 준비를 좀 덜 했다고 하더라도, 실력이 좀 줄었다고 하더라도 안할 수는 없었다. 나름 역대 koi 2차 문제들을 3개 빼고 다 풀기도 하는 등, 열심히 준비를 했다. 긴장되는 마음가짐을 최대한 억누르려고 했고, 나에게 크게 중요한 대회는 아니라는 마인드 컨트롤을 하였다. 사전 준비 대회는 1시 30분에 시작이었고, 1시부터 준비할 수 있는 시간을 가졌다. 그런데 키보드가 너무 불편했다. 내 노트북 키보드가 굉장히 특이한 형태인데, 그 키보드에 익숙해져버려서, 다른 키보드에 손이 잘 안익게 되었다. 앞으로는 항상 키보드를 들고 다닐까 생각을 하고 있다. 아무튼 스페이스바가 아예 안되는 컴퓨터가 있어 옆 컴퓨터에서 시험을 보게 되었다. 연습 문제는 예선 2교시 1번..

후기 글을 쓰던 도중에 결과가 떠서 급하게 바로 이어서 쓰는 글이다. 결과는 이렇다. 총 시험인원은 654명 정도였고, 내가 7등을 기록하였다. 6등은 441점이고, 5등은 443점이다. 결국 마지막에 못긁은 17번 테케 4점이 너무 아쉽게 작용하게 된 것이다. 왜냐하면 금컷이 1%. 즉 6등이기 때문이다. 만약 그냥 은상이라고 알려주었으면 진짜 너무 억울했을텐데, 내가 전국 7등이라는 것을 입증할만한 수치가 같이 딸려와서 다행이다... 흠.... 휴.... 사실 이렇게 말은 하지만 지금 미친듯이 기쁘다. 지난 2년동안 메이저 대회에서의 나를 생각하면 정말 끔찍했다. 사실 코딩에서의 디테일이 많이 부족했다고 할 수 있다. 어쩌면 최근에 실력이 많이 상승했다고 할 수 도 있는 것 같다. 아무튼 정말정말 행..

문제 링크 : https://www.acmicpc.net/problem/13310 문제 태그 더보기 삼분 탐색, 로테이팅 켈리퍼스, 볼록 껍질 문제 풀이 가장 멀리 떨어진 두 별의 거리가 최소인 날을 구해야 한다. 다시 생각하면 임의의 두 별에 대해서 거리를 구한 후, 그 중 최댓값이 그 날에 대한 수치가 되는 것이다. 문제에서는 각 날별로 두 별의 거리를 구하는 것이지만 일단 관점을 바꿔서 두 별의 거리를 각 날별로 관찰해보자. V자. 이런식으로 나올것이다. 즉, 일정 시점까지는 두 별이 계속 가까워 졌다가, 일정 시점 이후부터는 계속 멀어질 것이다. 혹은 시간 구간 내에서는 계속 감소하거나 계속 증가할 수도 있다. 두 별에 대한 모든 거리 그래프를 겹친 후에 그 중 최댓값을 뽑아낸 그래프 G'를 생각..

BOJ 13302 고등부 1번 리조트 문제 링크 : https://www.acmicpc.net/problem/13302 문제 태그 더보기 DP 문제 풀이 각 주어진 상황에서 여러가지 조건 중 하나를 선택할 수 있으며, 선택을 통해서 최적의 결과를 얻어내야 하는 문제. -> 아무리 봐도 DP. 각 상태는 DP table에 저장하고, 선택할 수 있는 조건들은 DP 관계식으로써 표현할 수 있다. dp[i][j]를 i번째날 쿠폰을 j개 들고 있을 때, 사용한 돈의 최솟값 이라고 설정하면, 1일권을 산 경우, 3일권을 산 경우, 5일 권을 산 경우, 쿠폰을 쓴 경우에 대해서 각각 일수와 쿠폰 수의 변화를 생각하여 DP식 들을 여러개 만들어 주면 된다. 자세한 것은 아래의 코드를 참고하자. 평가 : 난이도는 확실히..

문제 링크 : https://www.acmicpc.net/problem/17613 문제 풀이 일단 문제를 한 번 보자. "만일 점프간격을 2배씩 계속 증가시켜 마지막 점프에서 목표 수 x를 지나칠 것 같으면, 필요한 경우 언제든지 점프 간격을 다시 처음 상태인 간격 1로 되돌아 갈 수 있다. 이것을 재시작이라고 부른다." 라는 문구가 굉장히 중요한 부분이다. 굳이 이 문구를 통해서 유추를 할 필요는 없지만, 풀이를 생각하는 과정에서 이 문장은 풀이의 일부에 확신을 주게 된다. Phase 1 현재 개구리가 $2^i$ 까지 한 번에 뛰었다. 그리고 $2^{i+1}$을 뛸 수 있는 상황이다. 그런데 안 뛸 이유가 있을까? $2^{i+1}$은 1부터 $2^i$까지의 합보다 크다. 1번의 점프로 i번의 점프의 효..

문제 링크 : https://www.acmicpc.net/problem/17612 문제 풀이 딱히 사고의 흐름이라고 할 게 없다. 상황의 형태와 여러가지 조건들을 주어지고 이를 시뮬레이팅 할 수 있는 코드를 짜는 구현 문제이기 때문이다. 고객들이 어떤 순서로 나갈지를 알아내야 한다. 고객들은 번호 순으로 입장하고, 빈 구역이 있으면 바로 입장하며, 각 고객별로 주어진 시간만큼 있다가 퇴장한다. 이때 입장할 구역이 여러군데면 가장 작은 번호로 가며, 나갈 때는 동시에 끝나면 번호가 큰 순서대로 나간다. 정리하면 나가는 순서는 일련의 규칙을 따른다. 일련의 규칙에 따른 정렬 -> 우선순위 큐. 솔직히 따지고 보면 우선순위 큐 연습문제라고 봐도 무방하다. 동시에 자리가 나면 무조건 작은 번호의 구역으로 이동하..

문제 링크 : https://www.acmicpc.net/problem/14870 문제 태그 DP, Two pointer, Segment Tree 문제 풀이 일단 기존 상태의 상황을 구하는 것은 매우 쉬울 것이다. 당연히 DP로 구할 수 있고, 이때의 식은 다음과 같다. $DP[i][j]=max(DP[i-1][j],DP[i][j-1])+arr[i][j]$ 여기서 특정위치의 arr값을 1을 올리거나 내리는 값을 했을 때 DP 테이블이 어떤식으로 바뀌는지 구해야 하는 문제이다. 만약 $DP[i-1][j]$와 $DP[i][j-1]$이 둘 다 바뀌었으면 $DP[i][j]$도 바뀌었을 것이다. 혹은 둘 중에 더 큰 값, 즉 영향을 받는 값이 바뀌면 바뀔 것이다. 여기서 한가지 관찰을 해야한다. 한 가로줄에 대해서..

문제 링크 : https://www.acmicpc.net/problem/14869 문제 태그 DP, deque, Segment Tree 문제 풀이 (의식의 흐름) 기본적으로 난이도가 있는문제이다. 일단 이 문제를 보자마자 이 문제가 DP라는 사실을 깨닫지 못했다면, 앞으로의 관찰은 거의 불가능한 난이도라고 생각해도 좋다. 그럼 DP 테이블을 정의해보려고 해보자. 일단 몇번째 강좌인지가 중요할 것이고, 어느 학원에서 듣는지가 중요할 것이다. 그렇게 $DP[i][j]$를 i번째 강좌를 j번 학원에서 수강할 때, 이때까지의 비용의 최솟값이라고 설정하자. 이러면 문제는 문제의 조건인, 한 학원에서 s~e 개를 연속해서 듣기를 만족할 수 없다. 그렇다고 $DP[i][j][k]$를 설정해서 k를 j번째 학원에서 현..

BOJ 8983 고등부 1번 사냥꾼 문제 링크 : https://www.acmicpc.net/problem/8983 문제 태그 스위핑 문제 풀이 N개의 x축에 붙은 지점중 임의의 어떤 지점에 대해서 택시거리가 L이하만큼 떨어져 있는지 판별하는 문제. 당연히 하나를 관찰하면 지점은 다 x축에 있으므로 모든 지점에 대해서 떨어진 y거리는 고정이다. 가장 중요한 관찰을 하자면 어떤 점에 대해서 가장 x값이 비슷한 지점과 거리가 가장 짧을 것이고 그 지점과 거리가 L보다 크면 당연히 나머지 지점에 대해서도 거리가 L보다 클 것이다. 따라서 그냥 가장 비슷한 x값을 찾는 문제. 배열에서 가장 비슷한 값을 찾는 것은 그냥 정렬을 해놓고 lower_bound를 돌려도 되고, 혹은 정렬을 해놓고 sweeping을 해서..

생각보다 시간이 많이 빠듯했다. 할 것도 많았고, 오랜만에 하다보니까 하나하나 생각하는데 시간도 꽤나 오래 걸렸다. 사실 애초에 이 셋에 일주일동안 쓴 시간이 다 합쳐봤자 얼마 안되었다는게 가장 문제였다. 18솔을 했다. 하지만 여왕벌은 거르더라도 실골 문제들을 풀자고 만들어 놓은 연습셋이 아니기 때문에 아쉬운 부분이 많다. 그래도 일단 쭉 정리를 해보려 한다 A - 사냥꾼 KOI 2013 고등부 1번 그냥 딱히 생각하는 것도 오래 안걸리고 구현도 딱히 안빡셌다. 무난한 문제 풀이 https://stonejjun.tistory.com/98 B - 막대기 KOI 2013 고등부 2번 문제를 잘 못봤다. 관찰 위주의 문제였고, 솔직히 오래 걸릴 문제도 아니었지만, 문제 조건을 잘못 봐서 오래 고생한것이 컸다..