신나서 시작하는 velog

동기

사실 개발 블로그를 작성하는 사람들을 보면 새로운 지식을 배우는 것도 버거운데 굳이 저렇게 정리까지 해서 올리는데 시간을 투자해야하나??... 라는 생각을 가지고 있었다.

그런데 최근에 PS를 시작하면서 문득 내가 막혔을 때 다른 사람의 글을 보고 도움을 받은 것 처럼, 나도 누군가에게 도움이 되고 싶다는 생각이 들었다. 그리고 결정적으로 어제 나에게 여러모로 의미있는 문제를 깔끔한 코드로 풀었는데 기분이 너무 좋아서 누군가에게 자랑하고 싶었다.

"그" 문제

TSP(Traveling Salesman Problem)라고도 불리는 외판원 순회 문제는 컴퓨터 공학을 전공한 사람이라면 한번쯤은 들어봤을 아주 유명한 NP-hard 문제 중 하나이다. 이 문제가 낯설다면 여러 고수들이 잘 정리한 글이 많으니 찾아보기 바란다.

나는 이 문제를 OS시간에 multiprocessing과 multithreading 개념을 연습하는 과제로 처음 접했다. 과제의 요구사항은 여러개의 process/thread 이용해 완전탐색하는데 걸리는 시간을 측정하는 것이었는데, 당시 코알못이었던 process/thread로 역할을 분배하는건 둘째치고, 모든 경로를 탐색하는 코드부터 막혀서 엄청 고생했던 기억이 있다.

당시 제출했던 과제의 output. 13개의 도시를 7개의 프로세스로 순회하는데 약 2분이 걸린 모습이다.

재회

그리고 어제 비트마스크를 공부하면서 이 문제를 다시 만나게 되었는데, dp와 비트마스킹을 이용하면 기존의 $O(n!)$이 아닌 $O(n^2*2^n)$의 시간복잡도로 해결할 수 있고, 무려 16개의 도시에 대한 최소값을 1초도 안걸리는 시간으로 해결한다!!!!

코드도 나름 깔끔하게 적었고, 내가 과거에 며칠 삽질했던 문제를 잡기술까지 동원해 혼내주면서 엄청난 코르가즘을 느꼈다.
맞다. 자랑하려고 적었다.

향후

어제의 성취감을 넘어서는 날은 흔하지 않겠지만, 앞으로도 종종 나의 배움을 공유하거나 기록용으로 velog에 글을 작성하려고 한다. 나의 velog가 미래의 내가 과거의 나를 점검하는 기록이자, 가끔식 하기 싫을 때 나를 이끌어주는 동기가 되었으면 좋겠다.