Koala 알고리즘 학회 7주차 후기(2/13~2/19)

📍 주제

7주차의 주제는 Dijkstra이었다.
늘 해보고싶은 주제였기에, 재밌을 것같아 기대감을 갖고 시작했다.

💡 What Did You Learn?

해당 알고리즘 자체가 최단거리 , 달라봐야 최소비용을 구하기 위한 알고리즘이기에 문제들도 설명만 다르지 결국 구현 내용은 동일했다.
가끔 정점의 방문 순서를 기억해야하는 문제들도 있는데, 단순히 priority_queue에 방문 순서를 순서대로 push해준 vector또한 삽입해줌으로써 해결했다.
처음에 이론은 구글링해서 공부했는데, 선형 탐색으로 탐색하는 $O(N^2)$의 방식과 인접 리스트를 활용한 $O(NlogN)$의 방식이 주로 소개된다.
당연히 후자를 익혀서 공부했고, 전자 구현 방식을 알고있어야할 필요성은 느끼지 못했다.
주관적이긴 하지만, 다른 많은 사람들도 DFS BFS Dijkstra 등의 그래프 알고리즘 문제는 코드를 통째로 외워놓고 문제에서 응용된 부분만 수정하는 유형이라, 처음 공부하는 사람도 코드를 여러 번 따라치면서 외운 후에 여러 문제를 풀어보면서 이해하는 것도 괜찮은 방식인 것같다. 실제로 내가 하는 방식이기도 하다.

📝 푼 문제

• 최소비용 구하기
• 최소비용 구하기 2
• 특정한 최단 경로
• 녹색 옷 입은 애가 젤다지?
• 미확인 도착지
• 서강그라운드
• 택배
• 발전소 설치
  
  총 8문제

🥇 후기

벌써 7주차가 끝나고 마지막 한 주 남았다.
Platinum도 달성한만큼.. 어느정도 실력은 올라왔다고 생각해서(물론 코딩테스트 수준 기준으로..^_^) 이후에 자신없는 알고리즘(DP , Greedy)만 며칠간 집중공략을 마치고나면 감만 유지해나갈 예정이다.
8주차는 일정이 있어 많은 문제를 풀지는 못 하지만, 학회에서도 사실상 7주차가 마지막 커리큘럼인 것같아 성공적으로 아주 만족스럽게 마무리한 것같다.
자세한 전체 후기는 8주차까지 끝마치고 적어보겠다.

아 이번주에 가장 뼈저리게 반성한 것은... 문제 좀 제발 꼼꼼히 읽자.
나의 정말 악질적이고 추잡한 습관은, 문제를 읽다보면 '어느정도 어떤 조건에서 어떤 것을 구현해라' 라는 게 추측이 된다. 그때 나는 바로 예제 입출력을 보고, 나의 예상과 맞아떨어지면 바로 머릿속으로 알고리즘을 설계한다.
문제를 안 읽었으니까, 당연히 빠뜨린 조건이 있고 이는 오답을 초래했다.
정말 예전부터 한두번이 아니다. 중요한 건 앞으로 반복하지 않는 것..!
문 제 는 읽 으 라 고 있 는 것