이 글을 쓰게 된건 주변에서 많은 사람들이 자료구조에 관한 기초적인 문제를 잘 풀 지 못하는 것을 보고 주제를 떠올렸다.

만약 누구에게 자료구조를 어떻게 공부해야할 지에 대해 질문을 받거나, 혹은 조언을 해준다면 어떻게 해야 할까? 라는 점이 떠오른 주제이다. 그래서 일단 자료구조가 정확히 무엇이고, 왜 공부해야하는 지 조금 더 피부에 와닿게 설명하면 좋겠다고 생각해서 그러한 내용들을 정리하려고 한다.

1. 정의

일단 자료구조가 무엇인지 설명하는 것이 중요할 것 같다.

자료구조는 {데이터의 집합과 관계, 데이터를 저장하는 방법, 데이터의 연산에 대한 정의} 이 세가지 요소로 이루어져 있다. (일반적인 정의는 사실 모른다)
https://en.wikipedia.org/wiki/File:Directed.svg

예를 들어 그래프는, 수학적으로 표기할 때 그래프 \(G = \{V,E\}\) 로 나타낼 수 있다. 이때 \(V\)는 정점, \(E\)는 간선의 집합을 뜻한다. 정점은 그림의 파란색 원이고, 간선은 각 정점을 잇는 선이다. 간선의 방향성이니 뭐니는 이 글에선 설명하지 않는다.
그래프는 많은 것을 추상화할 수 있지만 전형적인 예시로는 정점을 도시로, 간선을 도로로 나타낼 수 있을 것이다. 아무튼 그래프 \(G\)의 각 정점에 숫자를 매겨서 각각 \(1,2,3\) 이라고 하고, 간선 세개를 \((1,2),(2,3),(3,1)\) 이라고 하자.
\(E\) 가 이미 \(V\) 사이의 관계를 정의해 주고 있으므로, 데이터의 집합과 관계 가 얼추 정의되어 있는 것으로 보인다.
그러면 저 자료들을 어떻게 컴퓨테 저장 할 것인지가 중요할 것이다. 예를들어, 2차원 배열을 만들고 배열의 한 원소 arr[x][y]가 1일 경우, (x,y) 가 \(E\) 에 속해있다고 정의할 수 있을 것이다. \(V\) 에 속하는 원소들은 배열 하나에 전부 저장하는 식으로 \(V\) 를 컴퓨터에 저장할 수 있을 것이다.
그럼 이제 데이터의 연산은 어떤 것을 정의할까? 이는 해당 데이터를 어떻게 이용할 지에 따라서 달라질 수 있지만. 정점을 추가/삭제 하는 연산, 간선을 추가/삭제 하는 데이터를 관리할 기본 연산들을 정의할 수 있고, 자료구조를 활용하기 위해 한 정점에서 어떤 정점으로 도달가능한 지를 반환하는 연산, 어떤 정점에서 인접한 정점이 무엇인지 (간선으로 직접 연결되어있는 정점이 무엇인지) 반환하는 연산 등을 정의할 수 있다. 어떤 문제를 푸느냐에 따라 다를 것이다.

2. 활용

이제 자료구조를 어떻게 각자 응용할 수 있을까에 대한 설명이다. 이는 알고리즘과 직접적인 연관이 있다.
우선 예시로 간단한 문제 하나를 생각해보자.

\(N\) 개의 정수로 이루어진 수열 \(S\) 가 주어질때, 최댓값을 구하여라.

쉬운 문제라고 생각했을 수 있는데, 쉬운 문제가 맞다. 단순히 모든 원소를 돌면서 가장 큰 값이 무엇인지 계속 갱신하면 된다.

1
2
3
max = -inf
for i in S:
  max = i > max ? i : max 

그런데 문제를 바꿔서, \(S\) 에서 최댓값을 가지는 원소를 \(Q\) 번 제거하고, 제거할 때 마다 최댓값을 구해야 한다고 보자.
역시 아직까지는 자료구조를 활용하지 않아도 된다. 일단 한 번 \(S\)를 정렬하는 것만으로 해결되기 때문이다.

1
2
3
S.sort()
for (i = 0; i < Q; i++):
  answer = S[N - i]

한 번 더 문제를 바꾸자. 이제 최댓값을 제거하는 쿼리 사이에 주어지는 임의의 정수 \(a\)를 \(S\) 에 삽입해야 한다. 삽입 연산은 총 \(M\) 번 주어진다. 이제 문제는 어려워졌을 수 있다. 바로 위의 방법대로 하면 정렬을 \(M\) 번 수행해야한다. 즉 시간복잡도는 \(O(MNlogN)\) 이다. 이는 자료구조를 활용하여 개선될 수 있다.

원소를 추가해도 정렬된 상태를 유지한 채로 있을 수 있으면서, 그러한 삽입 연산이 빠른 자료구조가 없을까?
이진탐색트리 라는 자료구조는, 데이터를 정렬하여 보관하면서도, 삽입/삭제가 \(O(logN)\) 으로 빠르다. 삽입/삭제/탐색 이 모두 \(O(logN)\) 인 것이다. (정확히는 균형잡힌 이진탐색트리에서이다)
이러한 자료구조를 도입한다면, 일단 최댓값을 탐색하는 데에는 \(O(logN)\) 으로, 기존에는 배열의 마지막에 접근한 것과 달리 느려졌다. 하지만 삽입 연산이 \(O(N)\) 에서 \(O(logN)\) 으로 개선되었다. 따라서 총 시간 복잡도는 대략 \(O((Q+M)logN)\) 이다.

1
2
3
4
5
6
7
bst = make_bst(S) // 이진탐색트리에 S를 저장
for i in inputs:
  if i == 삭제 쿼리:
    bst.delete(bst에서 최댓값)
    answer = bst.최댓값()
  elif i == 삽입 쿼리:
    bst.insert(i)

실제로는 힙 이라는 자료구조가 정확히 위와 같은 연산을 가진 자료구조이다. 수열 \(S\) 에서 최댓값만 관리하여, O(1) 만에 최댓값을 알 수 있는 자료구조이다. 삽입/삭제 시간복잡도는 동일하다.

즉 자료구조의 활용 방법은, 우리가 어떤 데이터를 원하는 연산을 빠르게 수행하고 싶을 때 기존에 있는 자료구조를 직접 쓰거나 변형하여 쉽게 해결하는 데에 있다.
“쉽게” 해결한다는 뜻은, 알고리즘을 설계할 때 더욱 추상화하여 다른 부분에 집중할 수 있다는 뜻이다.

알고리즘 표현 1

1
2
3
4
5
6
7
8
9
10
11
1. 주어진 수열 S의 각 값으로 for-each 문을 돈다. 각 값을 i라 하자. 그리고 비어있는 배열 T를 생각하자.
  1. idx = 1으로 시작하자.
  2. T[idx] 와 i를 비교하자. 
    1. T[idx] 가 비어있다면 T[idx] = i, 그리고 다음 i값을 가지고 1-1로 돌아가자. 
    2. T[idx] 가 크다면 idx = idx * 2, 그리고 1-2로 돌아가자.
    ...
2. 만약 삭제 연산이 들어오면,
  1. idx = 0 으로 시작하여 T[idx] 가 존재할 때 동안 idx = idx * 2 + 1 
  ...
3. 만약 삽입 연산이 들어오면,
... 

알고리즘 표현 2

1
2
3
1. 균형잡힌 이진탐색트리 bst에 수열 S의 값들을 삽입한다.
2. 삭제 연산이 들어오면, bst에서 최댓값을 제거한 다음 최댓값을 찾아 반환
3. 삽입 연산이 들어오면, bst에 해당 정수를 삽입

자료구조의 연산을 통해 알고리즘을 위와 같이 추상화하더라도, 알고리즘 표현1 과 동일하게 곧바로 구현이 가능할 정도로 구체적인 표현이 되었다.
문제에서 “균형잡힌 이진탐색트리” 라는 문제를 분리했다고도 볼 수 있다.

3. 자료구조의 구현

자료구조는 {데이터의 집합과 관계, 데이터를 저장하는 방법, 데이터의 연산에 대한 정의} 이 세가지 요소로 이루어져 있다.
위에서 이와 같이 말했는데, 보통 특정 자료구조를 구현하는 방법을 꼭 외울 필요는 없다. 자기만의 구현 방법이 있을 수 있다. 쉬운 구현 vs 성능 두 이점 사이에서 trade-off하면 된다.

예로 들어, 어떤 자료구조는 데이터를 계속 삽입/삭제 할 수 있는데, 삭제는 가장 최근에 삽입된 데이터만 가능하며 탐색또한 가장 최근에 삽입된 데이터만 찾을 수 있다.

위와 같은 성질과 연산을 가진 자료구조를 스택이라고 하고, 이러한 연산을 구현하려면 데이터가 삽입된 순서를 관리할 방법을 생각하면 된다. 이를 관리할 알고리즘은 자유롭게 생각할 수 있다. 알고리즘에 따른 장단점이 있을 뿐 정답은 없다. 물론 자료구조의 학습은 이러한 연산을 위한 효율적인 알고리즘을 이해하는 데에 있다. 추가로, 구현할 때에는 동작하는 예제 코드를 먼저 보지 않는 것이 좋다고 생각한다. 자신이 알고리즘에서 이해하지 못한 부분을 찾는 데에 방해가 된다고 생각되기 때문이다.