-
시간 복잡도를 고려한 코드 설계 전략
개요 알고리즘 문제에는 여러 가지 제한이 주어집니다. 여기에는 입력으로 주어지는 값의 범위, 그 값들이 가지는 성질 등의 조건도 있지만, 대부분의 경우 메모리 제한과 시간 제한이 같이 주어집니다. 많은 문제들에서는 이 제한을 크게 고려하지 않고도 답을 찾아내는 로직만을 생각하여 코드로 구현하면 통과할 수 있지만, 일부 문제에서는 시간 제한 때문에 직관적인 해결책으로는 통과할 수 없는 경우도 존재합니다. 따라서 알고리즘 문제를 풀 때에는 코드를 작성하기 전후로 로직과 코드의 시간 복잡도를 계산하는 것이 중요합니다. 시간 복잡도는 알고리즘을 공부할 때...
-
GNN의 시간 복잡도와 공간 복잡도
Introduction 우리가 흔히 알고 있는 인공 신경망에는 가장 기본적인 Fully-connected network 그리고 Convolutional Neural network (CNN)나 Recurrent Neural network (RNN) 등이 있습니다. 이러한 인공 신경망들은 보통 벡터나 행렬 형태로 input이 주어집니다. 하지만 input이 그래프인 경우에는 벡터나 행렬 형태로 나타내는 대신에 Graph Neural Network (GNN)를 사용할 수 있습니다. 지난 글에서 이미 GNN의 기본 원리와 간단한 예시에 대해서 알아보았기 때문에, 이번에는 조금 다른 주제에 대해서 다뤄보려고 합니다. (만약 읽지 않으셨다면, 위의 ‘지난 글’을 클릭하여 읽고 오시는 것을...