0. 다양한 집합류 모임
집합이란, 수학적으로 정의하기 대단히 힘든 요소이다. 국립국어원에서는 특정 조건에 맞는 원소의 모임이라고 이야기한다. ZFC 위에서는 수학적으로 다룰 수 있는 모든 대상을 집합이라고 하고, 단지 0개 이상의 원소를 가질 뿐이다.
이처럼 집합이란 수학적으로 정의하기 대단히 힘든 요소라고 할 수 있는데, 국립국어원에서 말하는 나이브한 집합의 정의 "특정 조건에 맞는 원소의 모임"으로 생각해보자.
{0,1,2}는 통상적으로 집합이라고 생각된다. 그러나 {0,0,1}을 집합이라고 생각하는 경우는 거의 없다. {0,0,0,1}도 마찬가지로 집합이라고 여겨지는 경우는 매우 드물다. 하지만, 잘 생각해보면 나이브한 집합의 정의 "특정 조건에 맞는 원소의 모임"이라는 정의를 위배하지 않는다고 보기에 부족해 보이지는 않는다. 이는 일반적으로 중복집합이라고 하는 집합이 아닌 다른 집합류의 일종으로 분류해볼 수 있다. "특정 조건에 맞는 원소의 모임"을 집합류로 분류하고, 그 세부 분류로 집합, 중복집합 등을 분류해볼 수 있다.
집합류에는 집합, 중복집합, 수열, 함수 등이 있을 수 있다. 집합은 중복을 허락하지 않는 모임, 중복집합은 중복을 허락하는 넓은 모임, 수열은 가산의 순서가 있는 중복을 허락하는 모임, 함수는 비가산의 순서가 있는 중복을 허락하는 모임이라고 할 수 있다.
튜링 기계의 메모리는 수열을 구현할 수 있다. 애초에 각 슬롯의 나열은 하나의 수열을 이룬다. 이때 순서를 무시하면 중복집합을 구현하는 것은 대단히 쉽다.
1. 자료구조와 push/pop
기계위에 잘 구현된 중복집합이 있다고 가정하자. 우리는 다음 두 쿼리를 생각할 수 있다.
- push k : k를 중복집합에 집어넣는다.
- pop : 중복집합의 각 원소에 대해 함수 T에 대한 함수값이 가장 작은 원소를 중복집합에서 제거하고 그 값을 출력버퍼에 기록한다.
이때 함수 T는 "치역이 실수이고, 이 기계로 계산가능하며, 온전히 원소의 값에만 의존할 필요 없다"는 조건을 만족한다. 온전히 원소의 값에만 의존할 필요 없다는 의미는, 중복집합 {2,2,2,2}에 대해서 모든 함수값이 같을 필요는 없다는 것이다. 포인터주소, 메모리, 시간 등에 의존해도 좋다는 의미이다. 함수 T를 탈출함수라고 한다.
이때 이 기계를 자료구조라고 한다. 알기 쉬운 모양으로 모식화하면, 어떤 중복집합 안에 원소들을 넣을 수도, 뺄 수도 있고, 원하는 원소를 넣을 수 있으나 뺄 때는 조건에 따라 뺄 수 있다고 이해할 수 있다.
2. 큐와 스택
큐와 스택은 탈출함수가 push 쿼리를 수행한 시간에만 의존하는 순서 의존적 자료구조이다.
큐는 push 쿼리가 수행된 시간이 작을수록, 스택은 반대로 push 쿼리가 수행된 시간이 클 수록 탈출함수의 함수값이 작아진다. 즉, 큐는 먼저 push된 원소가, 스택은 나중에 push된 원소가 먼저 pop에서 반환된다. 이런 구조를 FIFO(First In First Out/선입선출), LIFO(Last in First Out/후입선출)이라고 한다.
큐, 스택은 데이터를 관리하는 데 주로 사용되는데, 예를 들어 그래프 탐색의 깊이우선탐색/너비우선탐색을 할 때 튜링 기계 위에서의 방문 시작 시간과 방문 종료 시간이 다르기 때문에 방문 시작 시간이 지났지만 방문 종료 시간이 지나지 않은, 방문 중인 노드를 관리하는 데 등의 여러 방면에서 사용된다.
3. 우선순위 큐
우선순위 큐는 탈출함수가 push 쿼리를 수행한 시간에 의존하지 않는 비 순서 의존적 자료구조이다. 전순서 위상정렬 등 다양한 알고리즘에 사용된다.
4. 메서드
메서드란, 여러 개의 쿼리를 묶어 하나의 쿼리처럼 수행할 수 있게 만들어 둔 복합 쿼리 단위이다.
예를 들어 쿼리 P, Q, R과 쿼리에 사용되는 인자 a, b, c, d가 있다고 하고, 수행해야 할 쿼리가 아래와 같다고 하자.
- Pab Qbc Rcca Pdc Qca Raad
이때 P x y, Q y z, R z z x를 수행하는 쿼리 F x y z를 생각하자. 그러면 위 쿼리는 두 개의 쿼리로 표현할 수 있다.
- Fabc Fdca
이런 방식으로 여러 번 실행하거나, 다시 사용할 것을 목적으로 여러 쿼리를 연결해 하나의 쿼리로 이용할 때 유용하게 사용할 수 있는 쿼리의 모음을 메서드라고 한다.
메서드를 구성하는 쿼리는 메서드를 포함할 수 있다. 예를 들어, 수행해야 할 쿼리가 아래와 같다고 하자.
- Pab Qbc Pbc Qcd Pcd Qde Pff Paf Qfa
이때 메서드를 아래와 같이 정의하자.
* Fxyzwu : Pxy Qyz Pyz Qzw Pzw Qwu
그러면 수행해야 할 쿼리는 메서드를 이용해 아래와 같이 표현할 수 있다.
- Fabcde Pff Paf Qfa
하나의 쿼리를 더 생각하자.
* Gxyz : Pxy Qyz
그러면 수행해야 할 쿼리는 메서드를 이용해 아래와 같이 표현할 수 있다.
- Gabc Gbcd Gcde Pff Gafa
한편, Fxyzwu의 정의식을 다시 보면, Fxyzwu는 Gxyz Gyzw Gzwu와 같은 쿼리를 수행함을 알 수 있고, F는 메서드 G를 세 번 수행하는 메서드와 동일함을 알 수 있다. 메서드를 하나의 수행가능한 쿼리 단위로 볼 수도 있지만, 프로그램의 쿼리 나열의 어떤 구간을 재심볼화한 표기라고 생각할 수도 있다.
5. 마무리
자료구조에 대해 설명하려고 했는데 중복집합이랑 메서드에 대한 설명이 주가 되어서 아쉽게 생각합니다. 물리학에 시공간이 있듯이 컴퓨터에도 시공간적인 요소가 있습니다. 다음 화에서는 우선적으로 시간에 대한 설명을 먼저 하도록 하겠습니다. 많이 늦었습니다. 다음 화는 빨리 올라갈 수 있도록 하겠습니다.
