보자마자 풀이가 보이는 경우가 있다. 수학적 배경이 있으면 프로그래밍을 하는 데 하등 불편함이 없다는 말은 사실인 듯 하다. 이게 웰노운이 아니라서 다이나믹 프로그래밍으로 문제를 풀었다는 다른 사람의 기여를 보고 놀랐다. 하기사 다이나믹 프로그래밍이 점화식을 프로그램으로 푸는 제법 수월한 방법이기는 하지만... 여기서는 머리를 좀 써 보자. 그럼 본격적으로 풀이에 돌입해 보자. 문제 여러 개의 소국가로 나뉘어져 있었던 A국을 다시 하나의 국가로 합치기 위해 각 소국가의 대표 N명이 원탁에 모였다. 각 대표는 미리 원탁의 자리를 배정받았다. 회의를 시작하기 전에 일단 서로 악수를 하려고 한다. 각 대표는 한 사람과만 악수할수 있고, 모든 악수는 동시에 일어난다. 이때, 어떤 사람의 팔도 교차하지 않았을 때..

조합론에 관련된 문제를 풀다 보면 라는 수열을 생각보다 많이 접할 수 있다. 정확하게 카탈란 수라는 이름을 주지는 않는 경우가 많지만 0번째 항부터 시작하는 첫 몇 개의 항이 1, 1, 2, 5, 14... 인 수열이라거나, 아니면 다음 점화식으로 이루어진 수열을 이용해야 하는 문제는 제법 보았을 것이다. $$ C_{n+1} = \sum_{i+j=n}C_iC_j = \sum_{i=0}^{n} C_iC_{n-i} $$ 그런데 이걸 매번 다이나믹 프로그래밍이나 재귀 함수로 풀다 보면, n이 충분히 커졌을 때 시간 초과를 받는 경우가 종종 생긴다. 그런 불상사를 시작 전에 회피하고자 한다. 그래서 이 포스트에서는 카탈란 수의 일반항을 구하는 방법을 다룰 것이다. 분명히 쓸모가 많을 것이다. 장담하건대. 우선 ..

이 문제는 2022 Goricon A번 문제 되시겠다. 처음으로 참가한 대회에서 처음으로 푼 문제라 여러모로 감명이 깊다. 비록 브론즈 3의 쉬운 난이도라고 해도 말이다. 파이썬의 기본을 종합 테스트하는 문제라고 개인적으로 생각한다. 반복문과 사칙연산을 잊지 않았는가, 어떻게 현상을 코드로 옮길 것인가... 등등. 그럼 본격적으로 풀이에 돌입해 보자. 문제 리그오브전설 스트리머 순범이는 트위치 플랫폼으로 시청자를 끌어모으고 있다. 순범이는 '트윕' 음성 도네이션을 통해 시청자들과 소통하고는 한다. 순범이는 트윕에 '미션' 기능이 있다는 것을 알고, 자신의 리그오브전설 실력을 활용해 매 게임마다 미션 기능으로 돈을 끌어모으려고 한다. 미션 기능을 이용하는 시청자가 너무 많을 때도 있어서 순범이는 게임이 끝..

오랜만에 골드 문제의 풀이와 함께 돌아왔다. 분할 정복이라는 새로운 개념을 배우고 나서 하루에만 열 개 가까이 골드 문제를 처리했다. 한 방법을 새로이 알게 되면 아무래도 그 방법을 이용해 풀 수 있는 문제는 전부 도전해 보는 편이라. 그럼 본격적으로 풀이에 돌입해 보자. 문제 비요뜨는 지금 강 앞에 서 있다. 강 위에는 징검다리가 놓여 있다. 징검다리는 비요뜨가 있는 방향에서부터 반대 방향까지 차례로 1번, 2번, ..., N번의 번호를 가지고 있다. 비요뜨는 1번 징검다리 위에 올라갔다. 그리고 아래 두 가지 규칙을 지키며 징검다리를 건너려고 한다. 1 ≤ X ≤ N 인 임의의 정수 X에 대해, 현재 있는 징검다리의 번호를 i번이라고 할 때 i+X번 징검다리로 뛸 수 있다. N번째 징검다리를 지나쳐선..

수학적으로 접근할 수 있는 문제는 먼저 수학으로 접근해 보아야 한다. 런타임 전의 전처리를 뇌로 하는 것이다. 인간의 뇌라고 특별할 게 있겠는가. 돌발상황에 아주 잘 대처하는 거대한 생체 컴퓨터인 것을. 머리로 계산하고 코드를 단순히 짜는 게 오히려 더 낫다(고 한다). 주석만 적당히 달려 있다면. 물론 기본기가 어느 정도 되어 있다는 전제 하에 말이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 춘향이는 편의점 카운터에서 일한다. 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오. 예를 들어, 거스름돈이 1..

lambda 형식으로 되어 있는 함수는 한 줄로 아주 간단한 연산을 하게 만들어주는 함수이다. 아주 간단한 연산이라고 해 봤자 어떤 경우에는 lambda를 굳이 안 써도 될 정도로 간단하겠지만, 가끔씩 쓸 만한 경우가 있다. 그런 경우의 대표적 예시 중 하나가 바로 이 문제. 그럼 본격적으로 풀이에 돌입해 보자. 문제 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며..