exgs
commented
2 years ago 할 일
- Hello Coding 그림으로 개념을 이해하는 알고리즘 - 아디트야 바르가바 / (원서: grokking-algorithms) 다익스트라 알고리즘(Chapter 7), 동적 프로그래밍(Chapter 9) 부분 읽고 정리하기
(개인적인 사정상 집에서 하도록 하겠습니다~!)
정리
동적 프로그래밍
내 생각에 Dynamic programming에서 Dynamic의 의미는 런타임에 값을 저장하는 방식(메모제이션)을 취하기 때문인 것 같다.
- 동적 프로그래밍 알고리즘은 하위의 작은 문제들을 풀고, 이를 이용해서 더 큰 문제를 풀어나가는 방법입니다.
- 동적 프로그래밍은 하위 문제가 서로 의존하지 않는 경우에만 사용할 수 있습니다.
- 모든 동적 프로그래밍의 답안에는 격자가 있습니다. 격자의 각 칸에는 최적화하고자하는 값을 적습니다.
- 막대기 자르기, 최장 공통 부분 수열 문제, 0/1 배낭 문제 가 가장 유명하다.
다익스트라 알고리즘
- 그래프의 간선에 가중치를 준 가중 그래프(weighted graph)
- 가중 그래프에서 X까지의 최단 경로를 구하는 다익스트라 알고리즘 가중치의 합이 가장 작은 경로를 찾는다.
-
다익스트라 알고리즘은 방향성 비순환 그래프(DAG(=Directed Acyclic Graph))에 적용 할 수 있다. 또는 사이클을 가진 경우는 가중치가 양수일 때만 적용할 수 있다. (음수일때는 벨만-포드 알고리즘)
가중치가 음수일 때 문제가 발생하는 이유는 “일단 어떤 정점을 처리하면 그 정점에 도달하는 더 싼 경로는 존재하지 않아야 하는데, 포스터에 도달하는 더 싼 길이 발견되기 때문이다.” 다익스트라 알고리즘을 수기로 풀어봄
soo-bak
wisdom08
JSY8869
jongfeel
https://meet.google.com/jyx-mxnq-kpk
참여 방법:
Assignees에 자신의 github 계정을 self로 추가 2시간 분량의 할 내용에 대해 댓글 작성 (최소 모임 시작 전까지) 빛의 속도 혹은 (주말, 휴일 포함) 최소 3일 내에 구글 캘린더 등록 메일 확인 모임 시간에 각자 개발 관련된 공부 진행
모임 끝난 후 공부한 내용 정리 & 링크 추가 => 최소 다음 모각코 전까지 확인 가능해야 함.
주의: 회사일 혹은 마감 기한 임박한 일 처리의 경우는 최대한 자제해 주세요. 주말 아침에 일하면 우울하니까요. ㅜㅜ