-
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} +...
-
Effective Modern C++ (3)
저번시간에 이어서 오늘은 예전에 Effective Modern C++ 을 공부하며 정리했던 내용들을 포스팅해볼까 합니다~ C++11/14 에서의 best practice 에 관한 내용으로서 최근 C++20 이 나오는 시점에서 이 또한 최신 내용은 아니긴 하지만 여전히 많은 부분들이 유효합니다. Chapter 6. 람다 표현식 항목 31. 기본 갈무리 모드를 피하라. 참고로, 갈무리는 ‘capture’를 의미한다. (첨엔 어색했으나 나도 이제 완전히 이 번역에 익숙해져버렸다.) 기본 갈무리 모드 (default capture mode)는 ‘참조 갈무리 모드’와 ‘값 갈무리 모드’가 있다. 기본 갈무리 모드를 피해야 하는...