돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/5542 문제 풀이 이 문제에서 쿼리 q개를 제거해보자. 그러면 어떻게 풀 수 있을까? 이 형태의 문제를 해결하기 위해서 생각해야 하는 핵심 아이디어는 바로 결정 문제로 바꾸어서 해결하는 것이다. 목적지까지 이동하는 도중 축제랑 가장 멀리 떨어질 수 있는 거리 x 를 구하는 것은, 축제랑 거리 x이상 떨어진 노드들만 사용해서 목적지까지 이동이 가능한지를 묻는 결정 문제로 바꿔서 생각할 수 있다. 결정 문제는 어떻게 해결할까? 일단 각 노드들이 축제로부터 거리가 얼마나 떨어져 있는지를 알아야 하기 때문에 다익스트라를 먼저 실시해야 한다. 모든 축제 정점은 거리 0으로 해놓고 pq에 넣은 후에 시작하면 모든 노드에 대해서 가장 가까운 축..

NYPC 2022가 어느덧 코 앞으로 다가왔다. 많은 사람이 이미 알고 있을 테지만, 혹시 참가 신청을 안하려고 하거나 모르고 있는 사람들을 위해서 설명을 하려고 한다. Chap 1. 대회의 의미 사람들은 프로그래밍 대회에 참여한다. 정확히는 프로그래밍 대회에 참여하는 사람들이 있다.공부를 왜 하는가라는 물음에 시험에 통과하고 싶기 때문이라고 하는 사람도 있고, 자기 만족이라고 하는 사람도 있지만, 대회에 나가서 수상을 목표로 하는 사람도 적지 않다. 하지만 목표로서의 대회가 아닌 조금 다른 시선으로 바라보자. 대회는 굉장히 좋은 자기 검증 수단이자 공부 방법이다. 대회를 참가함으로써 자신이 얼마나 잘하는지, 무엇을 잘하고 무엇을 못하는지릉 알 수 있다. 또한, 정해진 시간에 동일한 문제를 같이 고민하는..

문제 링크 : https://www.acmicpc.net/problem/25351 문제 풀이 part 1 이후로 f(p)는 구간 p에 대한 중간 원소 인덱스 합을 의미한다. 또한 (a,b) 는 닫힌 구간 [a,b] 를 의미한다. 선공과 후공이 고를 수 에 대해서 생각해보자. T번째 판은 [a,b] 에서 진행된다. 두 개의 구간 p와 q에 대해서 p가 q에 속한다면 f(p)

문제 링크 : https://www.acmicpc.net/problem/10350 문제 풀이 맨처음에 문제를 딱 보고서 떠오른 생각은 가장 작은 값에서 "행동" 을 실행하는 것을 반복하면 될 것이라고 생각했다. exchange argument에 의해서 가장 작은 값의 위치에서 실행하는 것이 더 손해를 볼 일은 없다고 생각했다. 그래서 좀 더 고민을 해보다가 다른 생각이 떠오르지 않아 구현을 시작했고, 결과는 pq에 담으니 mle가 뜨게 되었다. 이를 보고서 절댓값의 감소량을 추적해보니 얼마 되지 않는다는 것을 알 수 있었다. 따라서 답은 굉장히 크다는 것을 알 수 있었고, 어떻게 해도 직접 "행동"을 한 번씩 해가면서 변화를 보는 것은 답이 될 수 없겠다고 판단하였다. 이 상황에서 내가 나아갈 수 있는 ..

요즘 codeforces 에서 문제를 푸느라고 한동안 블로그 글을 쓰지 않았다... 다시 백준에서 문제를 조금 풀게 된 만큼 한 번씩 글을 써야겠다. 문제 링크 : https://www.acmicpc.net/problem/9208 문제 풀이 (의식의 흐름) ※ 제 풀이는 intended solution에서 좀 벗어난 풀이입니다. 관련 개념 및 의도 된 풀이를 보고 싶으시면 https://qwerasdfzxcl.tistory.com/11 를 참고해주세요. 문제의 첫 방향성을 잡는 것이 힘들었다. 관찰의 실마리도 별로 보이지 않았으며, 무엇을 사용해야겠다는 감도 잡히지 않았다. 그렇기 때문에 일단 문제를 직선에서 풀기로 생각하였다. 원형 문제는 보통 길이를 두 배로 하여 직선으로 바꿀 수 있기 때문에, 그리..

대회 1주일전 팀연습. 이번에는 NWERC 2018을 골랐다. KCG BEJ AHI ABCD를 류트, EFG를 클리멕, HIJK을 내가 보기 시작했다... H가 해석도 다 안되었는데 I가 빠르게 풀리고 있어서 I를 보기 시작했다. 그런데 해석하는데 너무 오랜시간이 걸렸다. 예제가 없었으면 진짜로 해석을 제대로 하지 못했을 수도 있었다. 그래도 결국 해석을 끝마쳤고, 굉장히 쉬운 I를 짜서 바로 맞았다. 그다음으로 많이 풀린 문제는 H 였고, 코포 앞쪽에 나올법한 간단한 아이디어 문제였다. 바로 뚝딱. 그 사이에 그다음으로 많이 풀린 K를 류트가 잡고 있었고, 내 코딩이 끝나자 바로 이어서 코딩을 하고 뚝딱. 순조로운 출발 I : AC (00:14) H : AC (00:22) K : AC (00:30) 그..

처음으로 1컴으로 연습을 해보기로 하였다. 선정한 대회는 SWERC 2016. 복기글을 너무 늦게 써서 한 행동들만 기억나고 그 순서가 기억이 나지 않는다. ABCD를 류트, EFG를 클리멕, HIJK을 내가 보기 시작했다. 초반 부분은 잘 기억이 나지 않는다. 가장 크게 느꼈던 점은 영어 실력의 부재. 코포에서 아래의 힌트 부분과 번역기가 얼마나 큰 역할을 했었는지 새삼 깨달을 수 있었던 시간이었다.문제를 해석하는 것이 어질어질 했고, 문제들이 하나 같이 해석하고나서도 막막했다. C와 F가 가장 많이 풀리고 있었고, 류트와 클리멕이 C와 F를 같이 의견을 나누면서 하나씩 풀어내었다. 아마 류트가 C, 클리멕이 F를 했던것으로 기억한다. 나는 그 사이에 그 다음 많이 풀린 K를 류트에게 소개하였다. 문제..

나는 검수자로서, 대회 주최자로서 언젠가는 boj 22847 - 루미너스와 모험 중 마주친 퍼즐게임을 풀겠다는 의지를 잡고 있었다. 하지만, 엄두는 나지 않았다. 그와중에 주위에서 몇몇 분들이 풀겠다는 의지를 비쳤고, 그에 힘입어 나도 도전을 하였다. 이 글을 루미너스의 공식 풀이를 본 분들에게 바칩니다... 공식 풀이에서 사용된 용어와 파트를 가지고 설명합니다. 수도 없는 시간의 고민 끝에 나온 공식 풀이지만, 이를 구현하는 것은 너무나도 힘들 것 같았다. 특히 c 구역에 경우에 따라서 나누는 부분 앞에서 나는 구현할 의지를 잃었고, 그 경우를 하나로 통합하는 방법을 고민했다. 결론을 말하자면 C 구역에 D가 있는 모든 경우를 굉장히 비슷한 두 경우로 나누는 것에 성공했다. 이제부터 이에 대해 설명하려..

문제 링크 : https://www.acmicpc.net/problem/1591 문제 풀이 맨 처음에 같은 숫자의 가능성을 생각하지 못하고, 배열에서 인접한 두 값을 통해서 순서 관계를 얻을 수 있기 때문에 이를 조합하여 위상정렬을 하면 될 것이라고 생각했다. 그래서 코딩을 바로 했고, 틀린 후에 같은 숫자의 가능성을 생각해냈다. 일정 시간동안 생각을 했음에도 풀이를 생각해 낼 수 없었고, 태그를 열어봤더니 오일러 경로가 있었다... 몰랐던 내용이었기 때문에 풀이를 보았다. 길이 m-1 개의 배열로 잘라서 생각한다. 그 m-1 길이의 배열간의 배치 순서를 모두 알 수 있다면 문제를 해결할 수 있다. 문제에서 주어지는 길이 m의 배열은 길이 m-1 배열 두 개의 인접한 순서 관계를 알려준다. 정확히는 맨 ..

문제 링크 : https://www.acmicpc.net/problem/16056 문제 풀이 문제에서 주어진 정보를 그래프처럼 생각하면 정점을 가구와 콘센트 두 종류로 분류할 수 있다. 그리고 모든 간선은 가구와 콘센트 사이만을 잇는다. 즉, 이분그래프가 나오게 된다는 것이다. 그리고 최대 매칭값을 비슷하게 구하는 문제이기 때문에 이분 매칭을 떠올릴 수 있다. 이 문제의 가장 큰 특징은 하나의 콘센트에만 멀티탭을 꽃아서 3개의 가구와 연결을 시킬 수 있다는 것이다. 생각을 해보자. 한번 이분매칭 했을 때 추가로 이을 가구가 존재하지 않는다면 그대로 답이 될 것이며, 연결이 되지 않은 두 개의 가구가 같은 콘센트에 매칭이 될 수 있으면 그 콘센트에 플러그를 꽃아 2개의 추가매칭을 만들 수 있다. 그렇지 않..