돌이 코딩하는 방

나는 검수자로서, 대회 주최자로서 언젠가는 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개의 추가매칭을 만들 수 있다. 그렇지 않..

문제 링크 : https://www.acmicpc.net/problem/2802 문제 풀이 K개를 골랐을 때 최솟값을 구하는 문제... 문제를 딱 보면 최솟값을 구하는것이 아니라 특정 x값 이내가 되도록 k개를 고를 수 있는지에 대한 결정 문제로 변화시켜야 된다는 감을 잡을 수 있다. 즉, 파라메트릭 서치를 사용하면 될 것이라는 것이다. 파라매트릭 서치를 사용한다고 치자. 어떤 m*m*m 범위가 존재하여 그 안에 k개가 있는 그러한 범위가 있는지를 빠르게 판별해야 한다. 위치가 바뀌지 않으니까, prefix sum을 이용하면 된다. 3차원 이기 때문에 포함과 배제의 원리와 prefix sum을 잘 이용하면 m*m*m 큐브 범위내의 수를 셀 수 있다. 구현이 살짝 까다롭다. 1차이 관리가 살짝 까다로우며 ..

0. NYPC란? 코딩에 대한 청소년들의 관심 제고와 역량 증진을 목적으로 2016년 부터 넥슨에서 매년 개최하고 있는 청소년 코딩 대회이다. 전국의 12-19세 청소년을 대상으로 열리는 대회이다. (참가비無) 넥슨 게임 IP를 활용한 문제, 직접 코딩한 결과를 볼 수있는 시뮬레이션 문제 등재미있는 프로그래밍 문제를 통해 코딩에 대한 인식 변화와, 즐거운 경험 및 도전의 장을 제공하고자 만든 대회이다. 한 줄 요약 : 재미있는 프로그래밍 문제로 이루어진 청소년 코딩 대회! 1. WHY NYPC? NYPC를 3년 동안 참가해본 입장에서 NYPC를 참가해야하는 3가지 이유를 말해보려고 한다. 그 3가지는 크게 경험, 보상, 가능성이라고 말할 수 있을 것 같다. 경험! NYPC에 참가하는 것은 정말 좋은 경험..

예선 대회에 대한 이야기는 https://stonejjun.tistory.com/185에서 찾아볼 수 있다. 시점은 SCPC가 끝나고 조언을 받고, 랜플디를 시작하면서 내가 딱 바뀌려고 시작하는 시점이다. 즉, 내 능력치와 자신감이 바닥에 떨어져 있는 시점에서 대회가 진행되게 되었다. 오히려 그만큼 편한 마음을 가졌을지도 모른다. 이번에는 모여서 대회를 하기로 했기 때문에 미리 모여서 Ryute와 든든~~한 국밥 한그릇 하고 스터디 카페 룸으로 모였다. 대회가 시작되었고, 나는 IJKL을 읽었다. I를 읽자마자 메모리 크기를 보고 머리가 어질어질했고, J는 보고 N범위를 보고 머리가 어질어질 해졌으며, L은 고개가 갸웃했고, K는 웃음밖에 안나왔다. 내가 K를 보자마자 떠오른 생각은 Combination..

나는 klimmek55와 Ryute와 함께 참여하였다. 팀명에 관해서는 아무도 의견을 내지 않았다. 그래서 팀명으로 0.001의 이득이라도 보자는 마인드로 팀명을 "신경 쓰이는 팀명"으로 지었다. 각각 닉네임은 '코가 간지럽다, 들숨 내뱉는다, 눈을 깜빡인다.' 라는 악질적인 닉네임으로 다른 팀들의 시간을 1초라도 뺏자는 생각이었다. 이 외적으로 따로 준비를 하지는 않았다. 예선은 온라인으로 치기로 했기 때문에 디스코드 방을 만든 정도. 팀 대회 경험이 좀 있는 Ryute가 시작전에 여러가지 사항들을 알려주었다. Ryute가 ABC를 보고 klimmek이 DEF를 보고 내가 GHIJ를 보는 전략이었다. 맨 처음에 스코어보드에서 가장 빠르게 많이 풀린 문제는 ABC였다. 그래서 Ryute가 A를 빠르게 풀..

문제 링크 : https://www.acmicpc.net/problem/22883 의도된 풀이 주최측에서 의도한 풀이는 관찰을 통해서 주어진 임의의 게임판을 1*a 혹은 b*1 게임판으로 바꾸는 것이었다. 그렇게 되면 특정 게임판은 가로로만 이동이 가능하거나, 세로로만 이동이 가능하기 때문에 바로 둘이 각각 최대 몇턴 동안 살아남을 수 있는지가 구해진다. 따라서 직관적으로 누가 이길지를 계산할 수 있다. Stonejjun의 풀이 Part 1. 기본 지식과 유리도의 이해. 이 게임은 기본 상태보다 자신이 플레이 한 후의 상태가 자신에게 더 불리해지는 게임이다. 즉, 자신이 선공으로 이기면 후공으로 해도 이기며, 후공으로 지면 선공으로 해도 지고, 자신이 3번 행동을 하고 시작하면 훨씬 불리한 상태로 시작하..

문제 링크 : https://www.acmicpc.net/problem/1989 문제 풀이 수열에 있는 각 수 별로 그 수가 최솟값인 최대 배열을 잡을 수 있으면 문제를 풀 수 있다. 옛날에 풀었던 문제가 생각났고, 풀이가 바로 생각났다. 어떠한 수열 조각에 대해서 최솟값을 잡는다. 그럼 그 때 그 최솟값에 대한 값은 그 값 * 수열 조각의 구간합이다. 이때 다른 임의의 값은 그 최솟값을 포함하면 그 값이 최솟값이 될 수 없다. 따라서 수열 조각에서 최솟값 부분을 빼면서 수열을 쪼갤 수 있다. 이런식으로 수열을 계속 쪼개나가면서 값을 구하면 된다. 구간 최솟값과 구간 합은 둘다 segment tree를 이용하여 구할 수 있다. 그리고 구현이 더 쉬운 다른 풀이가 생각났다. 결국 수열의 모든 값에 대해서 ..

일시 : 8.13 문제 : 1989 부분배열 고르기 2 난이도 : P5 태그 : 미확인 풀이 : 미확인 풀이 시간 :