-
Problem Solving과 생성함수
간혹 조합론 문제를 해결하다가 점화식이 안 나와서 좌절하고 있을 때, 이 문제는 생성함수를 이용하면 기계적으로 만들어낼 수 있다는 충격적인 코멘트를 받아 언젠가 공부해야지 마음먹고 있습니다. 아쉽게도 정규 교육과정에 포함되어있지 않아서인지 problem solving와 관련된 자료가 드물었습니다. 때문에 이 포스트를 작성하시로 하였습니다. 이 포스트는 생성함수는 무엇이고, problem solving에 적용할 수 있는 방법을 다룹니다. 생성함수란? 일반적으로, 어떤 수열 ${a_i} = (a_0, a_1, a_2, \cdots)$에 대하여, \[f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots...
-
Segment Tree Beats
안녕하세요. rdd6584로 활동하고 있는 권일우입니다. 이 글에서는 요즘 유행하는 segment tree beats(이하 세그비츠)에 대해서 소개하겠습니다. 이를 위해서는, segment tree with lazy propagation에 대한 지식이 선행되어야 하지만 여기서는 소개하지 않겠습니다. Segment Tree Beats segment tree beats의 beats는 일본 애니메이션 “angel beats”에서 따온 것으로 특별한 의미를 가지고 있지 않습니다. 그러면 세그비츠가 뭘까요? 세그비츠는 lazy propagation의 활용형으로 중단조건과 갱신조건을 적절히 조절하여 까다로운 구간 쿼리를 해결하는 방법 중 하나입니다. 아래와 같은 문제가 있습니다. 길이 $N$의 배열 $A$, 아래와 같은...
-
제곱수의 합
서론 숫자를 제곱수의 합으로 표현하는 문제는 매우 유명한 문제이다. 예를 들면, $11339 = 1^2+27^2+103^2$ 으로 표현 가능 하고, 11339는 세 제곱수의 합으로 표현 가능하다. 우리는 이 글에서, 어떤 자연수를 최소 갯수의 제곱수의 합으로 표현하는 방법에 대해 알아본다. 제곱수의 최소 갯수 우리는 어떤 자연수가 최소 갯수의 제곱수의 합으로 표현되려면, 제곱수의 합으로 어떤 자연수를 표현하려면, 제곱수가 몇 개 필요한지를 알아 볼 필요가 있다. 이를 위해서 다음의 세 정리들이 필요하다. Lagrange의 네 제곱수 정리 Lagrange는 1770년에, 모든 자연수는...
-
더 빠른 문제 풀이 코드를 위한 상수 줄이기
개요 알고리즘을 공부하면 언제나 등장하고, 항상 신경써야 하는 요소가 있습니다. 바로 시간 복잡도 입니다. 공간 복잡도도 중요한 요소이기는 하지만, 메모리 사용량만큼의 시간이 걸리는 알고리즘은 효율적이지 않은 경우가 많기 때문에 상대적으로 덜 언급되곤 합니다. 하지만 어느 분야나 그렇듯이 이론과 현실에는 거리가 있기 마련입니다. 정확히는 알고리즘을 공부할 때 배우는 요소들은 문제를 푸는 수학적인 방법만을 고려한 것이지만, 문제 풀이를 할 때는 그 알고리즘을 프로그래밍 언어로 구현해내야 하고, 실제로 컴퓨터를 통해 실행시켜야 하기 때문에 시간 복잡도를 계산해서 예측한 속도와는...
-
2019 아주대학교 프로그래밍 경시대회(APC) 풀이
2019 아주대학교 프로그래밍 경시대회 (APC) 2019년 5월 26일 제9회 아주대학교 프로그래밍 경시대회(APC, Ajou, Programming Contest)가 열렸습니다. APC는 아주대학교 학생들을 위한 교내대회로, 경인지역 6개대학 연합 프로그래밍 경시대회 shake!에 출전할 10명의 대표학생을 선발하는 선발전을 겸하고 있습니다. 추가로 2019 APC는 성균관대학교와 한국항공대학교의 2019 shake! 학교 대표 선발전 역시 겸하였습니다. 2019 APC는 정보통신대학 학생을 위한 Divison1과 비전공생 및 복수전공생 학생을 위한 Division2로 나누어 진행되었습니다. Division1의 경우 2019 APC는 Division1 8문제와 Division2 6문제로 구성되었으며 그중 4문제가 공통문제라 총 10문제로 이루어져...