일단 논의에 쓰기 위해 다음과 같은 게임을 생각해 봅시다.
NxN 개의 칸으로 이루어진 정사각형 판이 있고 각 칸에 돌을 여러개 놓을 수 있습니다. 유저는 다음과 같은 query들을 요청할 수 있게 됩니다
PUT x y k ( (x, y)에 k개의 돌을 더 놓아라) )
SAVE (현재 바둑판의 상태를 저장하라)
LOAD n (n번째로 저장했던 SAVE를 불러오기)
그리고 query는 M개 들어온다고 합시다. query를 모두 처리한 후 당신의 프로그램은 지금의 판의 상태를 출력하고 끝내야 합니다....
우선 N과 M의 크기는 신경쓰지 말고 가장 단순하게 위의 프로그램을 구현할 방법을 생각해봅시다.
판을 BOARD 라는 자료구조로 표현했다고 할 때 다음과 같은 방법을 생각할 수 있습니다.
CurrentBoard = 현재 다루고 있는 판.
SAVELIST = BOARD들의 list. (C++에서는 vector, Python에서는 list 쯤으로 구현할 수 있겠군요)
PUT => CurrentBoard 에 작업한다
SAVE => CurrentBoard의 Copy를 만들어서 SAVELIST 뒤에 삽입한다.
LOAD n => SAVELIST[n] 을 CurrentBoard 으로 copy assign 한다.
마지막엔 CurrentBoard를 출력
CurrentBoard의 Copy를 SAVE해야만 하는 이유는 CurrentBoard를 가리키는 포인터 따위를 저장했다가는 CurrentBoard가 바뀌면 SAVE된 것도 바뀌기 때문이겠죠.. 현재가 바뀐다고 과거가 바뀌면 당연히 안될겁니다.
아주 직관적이고 단순한 방법으로써 위의 프로그램을 구현하는데 하등 문제가 없습니다. 다만 메모리가 폭발하고 시간이 폭발하고 사회가 무너지고 가정이 무너지고... N이 1000쯤 되면 Copy던 Copy Assign이던 시간을 너무 잡아먹겠군요. 메모리도 물론 부족할겁니다.
위의 방법의 SAVELIST 라는 구조는 생각해보면 1차원적인 구조라는 것을 쉽게 알 수 있습니다. 시간여행의 관점에서 본다면 Time Line 이 단 하나만 존재하는 세계가 되겠군요. 과거를 볼 수 있을 뿐 과거를 가져와서 바꾼다고 해도 그것은 오직 현재의 물체가 될 뿐이죠. 새로운 timeline이 생성되지는 않습니다. 단 하나의 우주만 존재하는거죠.
그와 비해 이번에 생각해볼 방법은 다중우주가 될겁니다. 과거로 가서 과거를 변경한다면 그 과거를 시점으로 해서 또다른 timeline이 생겨납니다. 여기서 우리의 자료구조가 Tree가 될것임을 느낄 수 있죠 (정말 Tree는 매번 불쑥 튀어나오네요)
(네 그렇습니다 전 그림을 아주 못그립니다)
판의 상태에 집중하지 말고 판에 가하는 변경(modification)에 집중해봅시다. 우리의 게임에서 변경을 위한 query는 PUT하나 밖에 없네요.
알아야 할 사실은 판의 상태는 사실 그 것에 가해진 변경들의 집합과 똑같다는 것입니다. 변경들을 판에 차례로 적용하기만 하면 언제든 의도된 상태를 만들어 낼 수 있으니까요. 그렇다면 변경들을 다루어 보죠.
변경을 MOD라는 자료구조로 표현한다고 합시다. 변경들의 집합을 원소로 갖는 Tree Node 를 생각해봅시다.
현재 작업하는 Node를 CurrentNode라고 합시다. 그럼 query 들을 다음과 같이 처리할 수 있습니다.
PUT => CurrentNode의 MOD리스트에 추가한다.
SAVE => 새로운 Node를 만들어서 CurrentNode의 자식으로 만들고 CurrentNode를 새로운 Node로 한다
LOAD => CurrentNodes는 그냥 삭제해버리고 k 번째 Node로 가서 새로운 Node를 만들어서 자식으로 만들고 CurrentNode를 새로운 Node로 한다.
(트리와 더불어 LOAD를 위해 k번째 Node가 어딨는지 저장해 놓을 필요가 있겠죠).
마지막에 출력하기 위해 판의 상태를 알고 싶다면 다음과 같이 하면 되겠죠.
(여기서 back은 자신의 부모를 가리키는 포인터입니다.)
void walkup(board& b, node* n) {
if(n==NULL) return;
walkup(b, n->back);
b.modify(n->q);
}
walkup(b, CurrentNode);
1번 노드로 부터 현재 노드 까지의 경로를 밟으며 그 노드가 가지고 있는 변경들을 다 판에 가해주는 걸 하는 코드입니다.
우리의 게임만 봐도 알겠지만 변경의 정보를 저장하는게 훨씬 메모리 소모가 적습니다. (10만x10만 개의 정수랑 x, y, k 세개의 정수를 비교해 봅시다)
이제 공간적인 측면은 문제가 안되고 시간적인 측면만 해결하면 될텐데 저는 거기서 막혔네요.
궁금한 사람들을 위해 원래 문제의 링크를 남김니다.
1번쨰 방법을 적용했을 경우 30%의 데이터를 빠르게 처리했지만
2번째 방법을 적용해도 놀랍게도 50%의 데이터 밖에 처리하지 못하네요.
전 치과가봐야해서 이만 글을 줄입니다.
글쓰기