2202-07-19 자기 계발 일지

 아 훈련도 그렇고 24시간도 그렇고 정말 쉽지 않다. 특히 지난주? 생각하고 싶지도 않다. 아무리 자도 자도 피로 회복이 되지 않아서 죽는 줄 알았다. 어제도 도대체 무슨 정신으로 PS한거지? (어쩌면 한별 포스터 때문일지도.) 암튼 해야할 일을 그래도 해야지... 원래는 지난주가 PS하는 날이었는데 한게 실질적으로 거의 없으므로 그냥 이번주 다시 PS주간으로 하기로 했다. 제일 중요한 건 진로 공부니까. 근데 이게 도움이 되려나...

 

여태까지 푼 문제들은 대부분 그래프 이론 문제인 것 같다. 최근에 queue가 아니라 deque(덱)을 이용한 0_1_bfs 관련 문제를 한번 풀어보았다. (아니, 정확히는 매우 오랬동안 못푼 문제를 솔루션 봐서 겨우 이해해서 풀었다.) 숨바꼭질 3 https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

이 문제의 특징은 간선의 가중치가 0 혹은 1이라는 건데, 신기하게도 0인 가중치의 정점을 앞에(push_front), 1을 queue에다 하는 것처럼 뒤에(push_back)다가 넣고 기존의 bfs처럼 돌리면 문제가 풀린다는 점이다. 물론 is_visited 같은 배열에 ture / false를 저장하지 않고 INF 혹은 0~ 의 가중치를 넣는다는 차이점이 있겠지만... 이 문제가 유달리 다른 것 보다도 관심이 갔던건 이 코드를 확장해서 데이크스트라 알고리즘을 적용할 수 있지 않나? 라는 생각을 하였기 때문이다. 그러니까 queue에서 deque를 이용해서 일종의 우선순위를 구현했는데, 아예 priority_queue를 이용해서 depth별로 정리를 해두면, 가중치가 0과 1이 아니라 다른 것이더라도 충분히 제일 짧은 길이를 구할 수 있을 것이라 생각이 들었다. 확실히 위키백과에도 pq를 써서 구현한게 있는 걸 보면 그렇게 해도 되는 것 같다. 다만 문제가 있다면... pq를 구현하는 것 자체가 상당히 비싸다는 것이다. 전에도 우선순위 큐 문제를 한번 풀어보았는데 다른 백준문제에서 찾아보기도 힘든 6초!라는 엄청난 시간제한이 있었다. 데이크스트라를 이렇게 구현하지 않는 이유가 이것 때문이가 싶다.

 

 군대에서 몸상태를 제외한 별다른 걱정거리는 없지만... 아니 솔직히 있다. 동아리원들이 날 떼놓고 슈퍼시크릿앱을 만들고 있다. 글을 적고 잇는 지금도 디스코드에 뭔가 올라오고 있는 것을 보아 작당모의를 하는 것이 틀림 없다... 나중에 슈퍼시크릿앱이 만들어질 때 쯤 깃헙에 쳐들어 가서 수많은 이슈들로 혼내주고 싶다. (그게 되려나)

 

 오늘 인간적으로 호감있는 선임의 MBTI가 정반대라는 것을 알았다. ㅋㅋㅋ 뭔가 신기하다