-
동적 계획법을 최적화하는 9가지 방법 (Chapter 3)
동적 계획법을 최적화하는 9가지 방법 (Chapter 3) 이 글은 Chapter 2에서 계속된다. 8. Circular LCS 두 문자열 $S, T$ 가 주어질 때 둘의 LCS를 구하는 문제는 잘 알려져 있고, $n = S, m = T$ 일 때 $O(nm)$ 보다 빨리 하기 힘든 것으로도 유명하다. Circular LCS 문제는 $S$ 를 Cyclic shift 할 수 있을 때, 각 cyclic shift에 대해서 LCS를 계산하는 문제이다. 기호로 표현하면, 모든 $0 \le i \le S - 1$ 에 대해, $LCS(S[i:]...
-
GNN의 시간 복잡도와 공간 복잡도
Introduction 우리가 흔히 알고 있는 인공 신경망에는 가장 기본적인 Fully-connected network 그리고 Convolutional Neural network (CNN)나 Recurrent Neural network (RNN) 등이 있습니다. 이러한 인공 신경망들은 보통 벡터나 행렬 형태로 input이 주어집니다. 하지만 input이 그래프인 경우에는 벡터나 행렬 형태로 나타내는 대신에 Graph Neural Network (GNN)를 사용할 수 있습니다. 지난 글에서 이미 GNN의 기본 원리와 간단한 예시에 대해서 알아보았기 때문에, 이번에는 조금 다른 주제에 대해서 다뤄보려고 합니다. (만약 읽지 않으셨다면, 위의 ‘지난 글’을 클릭하여 읽고 오시는 것을...
-
Codeforces Round #620 개최 후기
개요 Codeforces Round #620 (Div. 2) Announcement Editorial Codeforces Round #578 개최 후기 작년 여름, nong (전 hyunuk) 님과 함께 개최한 Codeforces Round #578 (Div. 2)은 저의 문제 풀이 경력에서 가장 멋진 경험이었다고 해도 과언이 아닙니다. 항상 문제를 푸는 입장에서 참여하고 비교적 소규모의 대회 몇 개에만 부분 출제 및 검수를 해본 것이 전부였던 저에게 만 천 명이 넘게 등록한 대회의 문제 반을 출제하여 성공적으로 개최한 것은 굉장한 일임이 분명했습니다. 하지만 후기글에 남겼던 것과 같이 문제마다...
-
Deep Q-learning으로 뱀 게임 인공지능 만들기
소개 강화학습 알고리즘을 테스트하기 위해 다양한 라이브러리를 사용할 수 있지만 원하는 환경이 없는 경우가 종종 있습니다. 이런 경우 간단한 환경은 pygame, opencv 같은 라이브러리를 가지고 직접 만들어서 테스트해볼 수 있습니다. 이번 포스트에서는 뱀 게임 환경을 직접 구현하고 강화학습 알고리즘을 적용하는 과정을 살펴볼 것입니다. 이를 위해 pygame으로 뱀 게임을 만들고 Keras로 딥마인드의 “Playing Atari with Deep Reinforcement Learning”에서 소개되었던 DQN(Deep Q-Networks)을 구현 해보겠습니다. 본 포스트에서 다루는 뱀 게임 인공지능 전체 코드는 여기에서 확인할 수 있습니다. DQN으로...
-
Rabin fingerprint for problem solving
Rabin fingerprint란? Rabin fingerprint는 길이 $n$의 배열 $m$, 임의의 값 $\space x$에 대해 아래와 같은 수식을 가지는 일종의 해시 함수입니다. $f(x)=m_{0}+m_{1}x+\ldots +m_{n-1}x^{n-1}$ 주로, 라빈카프 알고리즘에서 사용되기 때문에 해당 알고리즘을 공부하신 분께는 친숙할텐데요. 위 해시함수를 응용하여 문제를 해결하는 방법에 대해서 소개하고자 합니다. 모든 설명에서 $x$가 $max(m_i)$보다 큰 상황을 가정합니다. 가장 긴 문자열(링크) $m_0$ ~ $m_i$를 $g(x,\space 0,\space i) = m_0 + m_1x + … + m_{i}x^{i}$와 같이 $m_j$ ~ $m_{j+i}$를 $g(x,\space j,\space j+i) = (m_jx^{j} +...