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