ACM - 습격자 초라기

[2017-06-11]

링크: https://www.acmicpc.net/problem/1006

1층과 2층에 각각 N개의 적들이 있다. 이 문제는 dynamic programming을 위해서 memoization을 해야하는데 그 과정을 직관적으로 표현하기에는 까다로웠다. 직관적으로 memoization을 구현하기에는 N이 최대 10,000이므로 1층과 2층 모두 사용하려면 10,000 x 10,000 필요하고 N이 최대 10,000이므로 최소 short 자료형을 사용해야 하므로 대략 200MB이상의 메모리 공간이 필요하다. 배열을 사용하기에는 메모리 제한이 걸린다. 따라서 STL에서 제공하는 associative array인 map을 사용함으로써 메모리 제한 문제를 해결했다.

한 위치를 기준으로 0~2만큼 이동하기에 10,000 x 10,000만큼의 배열은 필요없다. 10,000 x 5만큼 필요할 것이다. 위의 방식을 적용하기 위해서는 배열이 아닌 map이 적당하다고 생각했다. map을 이용하면 직관적으로 memoization을 구현할 수 있기에 쉽게 풀 수 있다.

단, 환형이기 때문에 index가 0과 N-1인 부분을 고려해야한다.

※ 더 최적화 할 수 있는 방법
memoization을 사용했음에도 시간제한을 아슬아슬하게 통과했다. map은 balanced tree로 구현되어 있고 search 시간이 log(N)이기 때문에 생각보다 많이 나온 것 같다. 이를 줄이기 위해서는 직관적으로 memoization을 구현하지 않고 두 개의 층을 10,000개의 배열로 사용한다. map의 경우, N이 최대가 10,000이니 밑이 2인 log로 본다면 14번의 탐색이 필요하다. 하지만 배열은 direct access로 1번만에 검색이 가능하다. map이 아닌 배열을 사용하고 dynamic programming에 맞게 규칙을 만들 수 있다면 지금보다 시간을 1/14 (120ms) 정도로 줄일 수 있을 것으로 본다.


[2017-07-12]

unordered_map을 보는 순간 초라기 문제가 다시 생각나서 글을 추가하게 되었다. map은 탐색시간이 log(N)이 걸리기 때문에 unordered_map 즉, hash_table 방식을 이용하여 탐색시간을 O(1)으로 속도를 최적화 할 수 있다. 하지만 hash 값을 만드는 과정에서 오버헤드가 발생하며 hash값이 충돌될 경우에도 그에 따른 탐색 시간이 더 걸린다. hash값을 이용하기때문에 key값으로 pair객체를 사용하던 것을 int로 바꿈으로써 객체가 생성되는 오버헤드도 줄일 수 있었다. hash값을 만드는 함수는 key 값 그대로를 반환하게 구현하여 서로 collision되지 않게 하였다. 그래도 이상적인 시간보다는 4배정도 더 걸린다.