[항해99 취업 리부트 코스 학습일지] 4주차 TIL(3)

오늘은 그리디, 다익스트라 알고리즘 문제를 풀었다. 역시 완전탐색, 구현, 시뮬레이션 이런 건 나랑 안 맞아 ... 구현 능력이 부족하다는 말이겠지 ...? 엉엉 그래도 오늘은 어제보다 훨씬 빠르게 풀었다. 재밌기도 했고 역시 난 뭔가 패턴을 찾거나 최적의 경로? 그런 거 구하는 알고리즘이 재밌는 거 같다. 엄청 잘하는 건 아니지만~ 그래도 구현 문제보단 훨씬 재밌다...ㅎ

 

- 오늘 진행된 강의에서 학습한 내용은 무엇인가요?

그리디 & 다익스트라 알고리즘

- 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요

 

<기술 매니저님 피드백>

 

• 다익스트라 - bfs 코드와 비슷 템플릿 외워두는 게 좋다.
• 우선순위 큐 사용하는 거, 최소 비용 갱신하는 로직 차이만 있다.
• 목적지 노드에 방문하면 바로 출력할 수 있도록 구현하기
• 다익스트라
  • 한 노드에서 다른 노드로 가는 모든 최단 거리 (최소 비용) 구하는 것 -> 결과 배열에 넣어두고 마지막에 출력하는 방식
  • 한 지점에서 다른 지점까지의 최단 거리
  • 목표하는 곳까지 가는 동안 최소 비용을 계산해서 갔으니까 더이상 검사하지 않고 끝내도 된다. 
  • 예를 들어 0 -> a 최단 거리
  • 우선순위 큐에서  poll하니까 a가 나왔다. 우선순위 큐 중에 최소인 a가 나온 거
  • 이때 큐에는 a보다 큰 값이 들어있음
  • a가 아니니까 다른 지점을 경유해서 가야한다.
  • 그러니까 절대 최단 거리가 될 수 없다.
• 다익스트라 ->  visited 배열을 사용한 경우와 사용 안 한 경우 차이
  • 대부분 문제에서 visited 사용 안 해도 풀린다
  • 오히려 쓰면 안되는 문제들이 있다.
  • 우선순위 큐에서 먼저 나오는 걸로 따라서 가는 게 끝인데 굳이 방문했다고 표시할 필요가 없다. 이미 최소 비용을 구했던 곳으로는 다시 갈 일이 없을 것이다.
  • 이미 어떤 경로를 지나왔으면 최소 비용을 구한 건데 다시 갈 이유가 없다.

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다. 

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지