구사과

추석에 BOJ에서 13문제 연습 셋을 만들고 풀기로 결심했다. 아직은 그렇다 ㅋㅋ! 문제 A. Bridge Park B. Kangaroos C. Hotline D. Justice for All E. Farm and Factory F. Longest Rivers G. Conquer The World H. Uncrossed Knight's Tour I. Hashigo Sama J. 빛의 왕과 거울의 미로 1 K. 빛의 왕과 거울의 미로 2 L. Celtic Knots M. Farm Village 9월 9일 K. 빛의 왕과 거울의 미로 2 비트 DP와 비슷한 식으로 한 줄에 대한 상태를 저장하는데, 단순한 불리언 변수로는 부족하니까 연결 상태에 대한 union-find를 메모이제이션하는 느낌으로 해결할 수 있..

IOI 2019 Day 2 대회가 종료되었다. 한국 학생들의 성적은 다음과 같다. 김세빈, 100 / 100 / 40 / 72.30 / 66 / 57, 435.30점, Day2 27등, 전체 18등, 금메달. 윤교준, 72 / 100 / 40 / 90.97 / 66 / 57, 425.97점, Day2 16등, 전체 22등, 금메달. 임유진, 72 / 100 / 40 / 61.41 / 66 / 57, 396.41점, Day2 40등, 전체 37등, 은메달. 이온조, 38 / 100 / 64 / 50.61 / 52 / 24, 328.61점, Day2 120등, 전체 83등, 동메달. 미국의 Benjamin Qi는 작년과 같이 이번에도 Day 2에서 조금 노는 (?) 모습을 보였고 1등 성적을 받지 못하였으나..

IOI 2019 Day 1 대회가 종료되었다. 한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라. 김세빈, 100 / 100 / 40, 240점, 8등 - 25등 윤교준, 72 / 100 / 40, 212점, 26등 - 59등 임유진, 72 / 100 / 40, 212점, 26등 - 59등 이온조, 38 / 100 / 64, 202점, 60등 올해도 미국의 Benjamin Qi가 만점인 300점을 3시간 30분만에 얻었다. 문제가 쉽지 않았음에도 불구하고 빠른 시간 안에 300점을 얻은 것이 놀라울 따름이다. 단순히 Day1에서 큰 점수차를 보여줬을 뿐만 아니라 실질적으로 다른 학생들과 실력 격차가 크다는 것을 증명했다고 생각한다. 2019년 2연속 우..

고등부 1번. 타일 타일 문제는 복잡한 알고리즘을 요구하지 않아서 풀이로 적을 내용은 길지 않으나, 구현 면에서 까다로운 점이 있는 문제이다. 고등부 1번을 풀지 못하였을 경우 다음과 같은 공부법을 추천한다. 고등부 1번 뿐만 아니라 어떠한 문제를 해결하더라도 이러한 방식으로 접근하는 것이 좋다. 먼저 컴퓨터를 일절 사용하지 않고 펜과 종이만을 사용하여 적절한 수도코드(pseudo-code)로 코딩을 완료해 놓은 후, 종이에 적힌 내용을 구현하고 정답 결과를 확인한 후, 틀렸을 경우 1번으로 반복 맞았을 경우 다른 좋은 구현을 보고 차이점 분석 Subtask 1/2 (45점) 타일을 교체하는 선택지가 없기 때문에, 문제에서 주어진 입력 하에 차량이 도착점으로 움직일 수 있는 지를 판별하면 된다. 이는 시..

중등부 1번. 신기한 수 Subtask 2 (100점) 숫자 $N$ 이 주어지면, 해당 수의 일의 자리에 적힌 수는 $N \mod 10$ 이 된다. 이후 숫자를 10으로 나눠주면, 십의 자리, 백의 자리… 에 있던 수들이 모두 일의 자리, 십의 자리로 움직인다. 고로, 이를 반복하면 $O(\log N)$ (입력에서는 최대 8번) 의 단순 연산으로 $N$의 자릿수 합을 알 수 있다. 어떠한 수 $A$ 가 어떠한 수 $B$ 로 나누어 떨어지는 것은, $A$ 를 $B$ 로 나눈 나머지가 0이라는 뜻이니, C++ 나머지 연산자를 사용하여 판별할 수 있다. 중등부 2번. 개구리 점프 Subtask 1 (19점) 어떠한 두 선분 $p, q$ 사이를 오갈 수 있다는 것은, 특정한 좌표 $x$ 가 존재해서, $p, q..

계산 이론은 전산학의 근간을 이루며, 컴퓨터를 사용하는 모든 학문의 수학적 분석에 있어서 중요한 역할을 한다. 계산 이론 분야의 $P = NP$ 난제는 컴퓨터 과학의 거의 모든 분야를 관통하는 중요한 문제이고. $P = NP$ 난제의 여러 중요한 실용적 의미와 그 악명높음은 이미 대중적으로도 잘 알려져 있다. 계산 이론의 내용은 전산학의 어떠한 부분을 다루더라도 만나게 되는 경우가 많지만, 대부분의 내용은 튜링 머신과 같은 복잡한 개념을 바탕으로 정의된다. 이러한 특징 때문에, 계산 이론의 많은 내용은 잘 알려져 있으면서도 제대로 알고 있는 사람은 그렇게 많지 않은 경우가 많다. NP 시간 복잡도가 Non-Polynomial의 줄임말이라는 유명한 오해가 대표적인 사례이다. 튜링 머신과 같은 개념은 매우 ..

A. Strange DeviceSubtask 1 (10점)문제에 적힌 대로 모든 순서쌍을 나열한 후, 정렬하여 서로 다른 순서쌍의 개수를 세자.Subtask 4/5 (20점)고정된 $0 \le y 각각의 구간 $[L_i, R_i]$ 에 대해서, 가능한 $q$ 의 구간을 계산할 수 있다. 가능한 $q$ 의 구간을 계산했다면, 가능한 $q \mod T$ 의 구간 역시 알 수 있다. (원형으로 넘어가는 것을 주의하도록 하자.) 결국 각 $y$ 에 대해서 가능한 $x$ 의 개수는 가능한 $q \mod T$ 의 개수랑 동일하니, 이러한 구간을 전부 추린 후, 구간 합집합을 $O(N \log N)$ 시간에 계산하면 $O(BN \log N)$ 에 문제를 해결할 수 있다.$N$ 개의 구간의 합집합을 구하는 것은, $[..

Berlekamp-Massey 알고리즘은 특정한 DP의 점화식을 찾아주는 알고리즘이다. $10^{18}$ 번째 피보나치 수를 찾기 위해서 행렬 곱셈을 짜고, 타일 채우기 문제를 풀기 위해서 수많은 점화식과 씨름하던 옛 시간은 이젠 안녕. 이제는 백트래킹 짜고 하드 코딩해서 넣으면 끝난다. 이 글은 알고리즘의 구현법, 동작 원리나 증명에 대해서 거의 설명하지 않는다. 그 이유는 내가 구현법과 동작 원리, 증명을 모르기 때문이다. 알고리즘 구현은 여기에서 복붙해서 사용하면 된다. 이론적 배경지식이 상당히 깊지만, 그 활용도가 매우 높기 때문에, 일단 이해하지 말고 작동법부터 제대로 깨우친 후, 나중에 다시 돌아와서 방법을 이해하는 것을 추천한다. 1967년 이 알고리즘을 개발한 수학자 Elwyn Berlek..

(So, 1986)가사

뭐 했는지만 대충 알 수 있는 수준의 짧은 요약글로 정리하려고 한다. 다 쓰면 너무 길다.Day1 A: NEERC 2018 B랑 매우 비슷한 General Matching. D: 특수한 그래프에서 weighted bipartite matching을 빠르게 계산하는 문제. weighted bipartite matching은 가중치가 큰 순서대로 에지를 추가하면서, 최대 매칭을 증가시키는 것만 넣어주는 식으로 계산할 수 있다. 이렇게 가중치를 없에고 최대 매칭 문제로 환원하면, ARC076F / POI Ice Skates 에 나온 유형처럼, 홀의 결혼 정리 + Segment Tree 로 해결 가능. 사실 생략한 아이디어들이 이것저것 있는데 다 적으면 너무 길어지니 생략. E: planar graph에서 ra..