[항해99 취업 리부트 코스 학습일지] 24일차

이번 주 목표 

📢 이번주 목표는 백준 골드2까지 승급하는 것이다. 현재 골드3이다.
     마이크로서비스 구축 가이드 책 완독하기(274/697)

오늘 스케줄

09:00~09:20 모닝 스크럼
09:30~12:00 데일리 과제 문제 풀이
12:00~13:00 점심 식사
13:00~17:30 데일리 과제 문제 풀이
17:30~18:00 팀 코드 선정 회의
18:00~18:20 기술매니저님과 팀 코드 리뷰
18:20~19:20 저녁 식사
19:30~20:30 데일리 과제 못 풀었던 8번 풀기
20:40~휴식

오늘 목표

👉 데일리 과제 모두 풀기

👉 TIL 빠지지 않고 작성하기

👉 북 스터디 참여

👉 인프런 마이크로서비스 강의 수강하기

오늘 한 것

• TIL 빠지지 않고 작성하기
• 데일리 과제 모두 풀기
• 북 스터디 참여

오늘 못한 것

• 인프런 마이크로서비스 강의 수강하기

알게된 것

다익스트라

• 최단 경로를 구하는 알고리즘
• 가중치가 있는 그래프의 최단 경로를 구하는 문제는 대부분 다익스트라 알고리즘을 사용
• 가중치가 양수일 때 사용이 가능하다.

다익스트라 알고리즘 특징

다익스트라 알고리즘의 특징은 다음과 같습니다.

• 음수 가중치를 가진 간선이 존재하지 않는다.
• 탐욕 알고리즘(Greedy Algorithm)을 사용한다.
  • Greedy Algorithm의 설명은 이곳을 참조
• 미방문(non-visited) 정점(vertexes)들을 저장하기 위해 우선순위 큐 사용

 

다익스트라의 컨셉(The concept of Djkstra's)

여러 도시 중 A라는 도시에서 G라는 도시까지 간다고 가정합시다.

 

경로는 여러가지가 있을 것을 것입니다.

• A - B - G
• A - D - F - G
• ....

만약 한 경로마다 소모되는 시간은 다음 그림과 같다고 합시다.

그렇다면 이때 가장 최단 거리의 경로는 어떤 것일까요?

 

다익스트라 알고리즘은 이 문제를 다음과 같은 명제로 제시합니다.

"부분 경로에서 최단 거리의 집합"

 

 

아래 그림에 나오는 숫자들의 색깔은 다음을 의미합니다.

• 파란색 숫자: 예상 소요 시간
• 빨간색 숫자: 해당 노드까지 실제 소요한 시간

 

A 도시에서 출발

다음에 갈 수 있는 도시는 3개뿐 : B, C, D

다음 세 도시(B, C, D) 중 다음으로 갈 수 있는 경로 탐색합니다.

 

1. B도시에서 다음으로 갈 수 있는 경로는

• E 도시(A-B-E): 6시간 소모
• G 도시(A-B-G): 11시간 소모 (도착)

2. C도시에서 다음으로 갈 수 있는 경로는

• E 도시(A-C-E): 8시간 소모

위에서 B를 거쳐 E를 가는 것이 더 빠르기 때문에 이 경로는 제외합니다.

 

• F 도시(A-C-F): 4시간 소모

3. D도시에서 다음으로 갈 수 있는 경로는

• F 도시(A-D-F): 9시간 소모

 

위에서 C를 거쳐 F에 가는 것이 더 빠르기 때문에 이 경로는 제외합니다.

 

 

남은 두 도시(E, F)에서 다음으로 갈 수 있는 경로 탐색합니다.

1. E 도시에서 다음으로 갈 수 있는 경로는

• G 도시(A-B-E-G): 7시간 소모 (도착)

이전에 A에서 B를 거쳐 G에 도착했던 경로(11시간 소모)보다 시간 소모가 더 적기 때문에 해당 경로로 update합니다.

 

2. F도시에서 다음으로 갈 수 있는 경로는

• G도시(A-C-F-G): 6시간 소모(도착)

바로전에 A-B-E-G 경로에 비해 1시간이 더 적은 6시간이 소모되므로 이 경로로 다시 update합니다.

 

 

이를 통해 다익스트라는 전체 경로의 최단 경로를 찾기 위해서 중간중간 부분 노드에서의 최단 경로를 찾고 새로 탐색한 경로가 내가 이전에 찾았던 경로보다 더 짧은 거리라면 해당 거리로 계속해서 업데이트합니다.

이런 방식을 통해 최종적으로 목적지에 도착했을 때의 최단 거리를 찾아내는 방식인 것입니다.

 

출처: https://cdragon.tistory.com/entry/Algorithm-Dijkstra-Algorithm%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

🤔오늘의 반성

- TIL 늦게 씀
- 마이크로서비스 강의 못 들은 점

 

👍 오늘의 칭찬

1. 깃헙 1일 1커밋 달성
2. 북 스터디 참여
3. 데일리 과제 모두 품

❗ 항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.
https://hanghae99.spartacodingclub.kr/reboot