회고
오늘은 눈이 빨리 떠졌다. 오전 8시 30분. 바로 헬스장으로 가서 등 운동 후 씻고 10시에 강의실에 출석했다. 하루를 빨리 시작하니 여유로워서 좋다. 매일 아침 8시에 운동하고 10시에 출석하면 베스트일텐데, 참 힘들다. 잠을 일찍 자는 수 밖에 없다.
3주차 과제에서 남은 문제는 4개. 오늘은 남은 문제를 해결할 생각이었다. 우선 '2617번: 구슬 찾기' 문제를 풀었다. DFS로 해결할 수 있었지만, 카테고리에 플로이트 워샬 알고리즘이 적혀있었기에 배워서 써먹어볼 생각으로 플로이드 워샬을 공부했다. 로직은 간단하다. 시간복잡도는 O(N^3)이다. 모든 노드에서 다른 모든 노드까지의 최단 거리를 갱신하는 알고리즘이다. 다익스트라 알고리즘과는 사용처가 달라서, 배워두면 좋을 듯하다. 로직도 딱히 별게 없고 그냥 3중 for문 돌면서 최단거리 갱신하면 된다. 대신 3중 for문이다 보니 속도가 빠르지는 않다. '구슬 찾기' 문제에서 DFS 로직과 비교하면 속도가 3배 정도 차이가 난다. DFS 풀이도 제대로 봐야겠다.
그 뒤로 남은 문제 3개가 '위상 정렬' 문제인데, 정말 하기가 싫더라. 개념 자체도 어렵고 이걸 각기 다른 문제에 적용하는 것도 머리가 아프다. 아직 목요일까지는 시간이 있으므로 문제 풀이는 다음으로 미룬다. 코치님들도 딱히 모든 문제를 기한 내에 풀 것을 강요하지는 않으셨고.. 괜찮겠지..?
python의 heapq 모듈을 뜯어보았다. 내가 직접 구현한 힙 클래스와 파이썬 내장 모듈인 heapq에 무슨 차이가 있길래 속도가 차이가 심하게 나는지 궁금해서, 파이썬의 공식 구현체인 cpython의 heapq.py를 보고 구현 힙과 차이를 분석해보았다. 자세한 사항은 [[파이썬의 heapq 모듈은 왜 빠를까]] 글을 참고하기 바란다.
오후 6시에는 반찬거리를 사러 시내로 향했다. 자전거로 10분컷. 전에 갔던 반찬가게가 꽤 괜찮았어서 또 들렀다. 오늘 산 것은 매운오뎅볶음, 숙주나물, 무생채로, 총합 7500원이다. 싸고 맛있다. 정글 합숙에서 유일하게 즐길 수 있는 시간이 밥 타임이라, 이럴 때라도 즐겨야한다. 객실 TV모니터로 신서유기 유튜브 재방송을 보며 저녁식사를 한다. 식사 후에는 오랜만에 책을 읽었다. 정글에 들어오기 직전에 읽었던 김승호 님의 "돈의 속성"이라는 경제 관련 도서이다. 한동안 바쁘고 손이 안가서 내버려두다가, 며칠전에 리디셀렉트 정기구독료 결제 알림이 와서 다시 읽기 시작했다. 방에서 혼자 독서의 시간을 가지는 것도 꽤나 마음에 여유를 가질 수 있다. 내일 중으로 완독할 수 있을 듯하다. 짧은 독서 후, 저녁 공부를 재개했다.
알고리즘 주차가 끝난 후에도 알고리즘 공부를 지속적으로 하기 위해, 블루반 내 알고리즘 스터디를 형성했다. 백준 온라인 저지 사이트의 그룹 시스템을 통해 "[크래프톤 정글 2기] 블루반 스터디" 그룹을 만들었다. 바로 내일 오후 3시부터 5시까지 연습용 코테를 칠 생각이다. 동료들 모두가 의욕만땅이라 꾸준히 할 수 있을 것 같다.
TIL
- 플로이트 워샬 알고리즘은 다익스트라 알고리즘과는 궤를 달리한다. 모든 노드에서 다른 모든 노드에의 최단 거리를 갱신하기 때문에 시간 복잡도는 O(N^3)이다. 로직도 쉽고 응용하기 좋을 것 같다.
- heapq 모듈이 빠른 이유는 다음과 같다. (1) 나누기 연산(//)을 시프트 연산(>>)으로 대체, (2) 불필요한 연산 제거. 생각보다 별게 없어서 놀랐다. 이것만으로 알고리즘 속도가 훨씬 빨라질 수 있다니. 그래도 모듈을 직접 뜯어봤으니 로직에 대한 이해도가 높아진 것 같다.
- 시프트 연산은 일반적으로 사칙연산보다 빠르다고 한다. 그러나 파이썬에서는 조금 다른 것 같기도 하다. 이것도 조만간 정리해볼 생각이다.
