ㅇㅅㅎ

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 단일 시작 단일 도착 다익스트라 : s에서 t까지의 최단 경로만 필요하다면 Q에서 제거되었을 때 알고리즘을 멈춥니다. u=t일 때 종료합니다. ✔ 양방향 탐색 : 여기에서 다루는 속도를 가속화시키는 방법은 최악의 경우 복잡도를 바꾸지 않지만 실제에 적용되었을 때 방문하는 정점의 개수를 줄입니다. s에서 시작하는 기존의 다익스트라 알고리즘의 첫 번째 단계를 실행해서 순방향으로 경로를 찾습니다. 그리고 t에서부터의 역방향 탐색(간선을 반대로 따라가는 것)을 시작합니다. df[u] : 전방향 탐색에서의 거리를 저장 db[u] : 역방향 탐색에서의 거리를 저장 Qf : 전방향 탐색에 이용 Qb : 역방향 탐색에..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 복습 정점 u에서 v까지의 최단 경로의 가중치를 δ(u, v)로 둡니다. 정점 u에서 정점 v가 도달 불가능하면 δ(u, v)의 값은 무한대(∞)입니다. 정점 u와 v사이에 음의 순환이 있으면 최단 경로는 정의되지 않습니다. ✔ 일반적 최단 경로 알고리즘 ⁉️ 문제점 양의 가중치를 가지고 있는 간선도 지수 시간 복잡도를 가집니다. → 다익스트라 알고리즘을 이용하여 해결 가능합니다. 음의 가중치를 가진 순환이 시작점으로부터 도달이 가능하다면 알고리즘이 아예 끝나지 않을 수도 있습니다. ✔ 벨만-포드 알고리즘 : 음의 순환이 없다면 알고리즘의 마지막엔 d[v] = δ(s, v)입니다. 다익스트라 알고리즘은 ..

👀 약수 : 어떤 수를 나누어떨어지게 하는 수. 예) 4의 약수는 1, 2, 4입니다. ✔️ 약수를 구하는 함수 def divisor(n): result = [] for i in range(1, int(n**0.5)+1): if n%i == 0: result.append(i) result.append(n//i) return result

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 복습 d[v]는 출발점 s에서의 현재까지 구한 최단 경로의 길이입니다. 완화 과정을 통해 d[v]는 최종적으로 s부터 v까지의 최단 경로의 길이인 δ(s, v)가 됩니다. Π[v]는 s부터 v까지의 최단 경로에서 v의 선행자를 의미합니다. 최단 경로 계산에서의 기본 연산은 완화 연산이라고 할 수 있습니다. 👀 완화 연산 Relax(u, v, w) if d[v] > d[u] + w(u, v): d[v] = d[u] + w(u, v) ∏[v] = u ⁉️ 완화의 안전성 귀납법을 이용한 간단한 보조정리 : 완화 알고리즘은 불변 조건인 모든 v∈V에서 d[v]≥ δ(s, v) 임을 항상 만족합니다. 증명 : 과..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 최단 거리 : 가중치가 최소인 경로 p를 찾으려고 하는 것 ⁉️ 동기 : A에서 B로 가는 가장 짧은 거리 구글 지도의 "길 찾기". 가중 그래프 G(V, E, W), W = E → R의 문제 V = 정점(도로의 교차점) E = 간선(거리, 도로); 방향 간선(일반통행 도로) W(U, V) = 간선 (u, v)의 가중치 함수(거리, 통행료) ⁉️ 알고리즘 다익스트라 O(VlgV + E) : 음이 아닌 가중치를 가정. E=O(V^2) 벨만-포드 O(VE) : 일반적인 알고리즘 ✔ 가중 그래프 ⁉️ 표기 : v0에서 vk까지의 경로 p를 의미합니다. (v0)는 v0에서 v0까지의 가중치 0인 경로를 의미합니..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 복습 그래프 탐색 : 그래프를 탐험하는 것 예) 시작점 s에서 원하는 정점까지 가는 경로를 찾는 것 인접 리스트 : |V|연결 리스트의 배열 Adj 각 정점 u∈V에 대해, Adj[u]는 u의 이웃들을 저장 예) {v∈V | (u, v)∈E}(방향 그래프에서 (u, v)는 나가는 간선입니다.) 너비 우선 탐색(BFS) : s에서 레벨별로 그래프를 탐색합니다. - 최단 경로를 찾습니다. ✔ 깊이 우선 탐색(DFS) : 그래프를 재귀적으로 탐색하고 필요에 따라 역추적하여 미로를 해결하려는 것과 같습니다. 깊이 우선 탐색에서 주의할 점은 정점을 반복하지 않는 것입니다. ⁉️ 깊이 우선 탐색 알고리즘 parne..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 그래프 탐색 그래프 탐색은 "그래프를 탐험하다"는 것이라고 할 수 있습니다. 그래프를 탐색하는데 여러 가지 개념들이 있습니다. 시작 점 s에서 원하는 정점으로의 경로를 찾는 것 그래프의 또는 s에서 도달할 수 있는 모든 정점과 간선을 방문하는 것 ⁉️ 그래프 : G = (V, E) V = 정점의 집합(임의의 레이블) E = 간선의 집합, 정점의 쌍(v, w) - 순서쌍 ⇒ 그래프의 방향이 있는 간선 - 비순서쌍 ⇒ 무방향 ⁉️ 응용 웹크롤링(구글이 페이지를 찾는 방법) 소셜 네트워킹(페이스북이 친구 찾기를 사용하는 법) 네트워크 브로드캐스트 라우팅 가비지 컬렉션 모델 검사(무한 상태 기계) 수학적 추측 ..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 복습 √2 를 백만 자릿수까지 계산 |√a|를 뉴튼 방법을 이용하여 계산 위의 결과들이 실제로 이차적 수렴의 성질인지 알아보기 위하여 뉴턴법의 오차를 살펴보겠습니다. ✔ 뉴턴법의 오차 분석 전체적으로 보았을 때 알 수 있는 것은 오차에 대한 아래의 식입니다. 분모 부분의 (1+εn)에서 n이 계속해서 커질수록 εn은 예상했던 대로 0에 가까워집니다. 그래서 (1+εn) 값은 1이라고 할 수 있고 결국 오차값이 이차적 수렴의 성질을 가진다고 할 수 있는 것입니다. 굉장히 작은 값이지만 매 반복마다 제곱값으로 작아지는 것입니다. 만약 0.01이 가장 처음의 εn 값이라고 한다면 (εn)^2은 0.0001이 ..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 무리수 : 피타고라스는 정사각형의 대각선의 길이와 한 변의 길이의 비율은 정수비로 표현할 수 없다는 것을 발견했습니다. 따라서 그 비율을 정수로 이루어진 비인 유리수로 표현할 수 없습니다. 그는 이것을 '설명 불가'라고 칭했습니다. 무리수를 위협으로 생각했기 때문에 무리수의 패턴을 찾으려고 시도했습니다. 하지만 결국 패턴을 찾아내지 못했습니다. → 고정밀 계산이 필요한 또 하나의 이유가 됩니다. 👀 무리수에 숨겨진 특정한 패턴이 있을까요? ⁉️ 카탈란 수 : 올바른 괄호 구조 문자열로 이루어진 집합 P는 아래와 같이 귀납적으로 정의합니다. λ ∈ P (λ: 빈 문자열) 만약 α, β ∈ P이면, (α)β..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 개방 주소법 ⁉️ 충돌을 대처하는 또 다른 방법 체이닝 없이 모든 항목이 테이블에 저장됩니다. 한 슬롯당 하나의 항목입니다. ⇒ m(해시 테이블의 슬롯 크기) ≥ n(항목 수) ⁉️ 조사 해시 함수는 키 삽입/탐색/삭제를 위한 키의 슬롯의 탐색 순서를 정합니다. 해시 함수는 하나의 슬롯만 보는 게 아닙니다. 소학적으로 표현하면 다음과 같습니다.(모든 k ∈ μ인 특성을 가진 해시 함수 h를 만들고 싶을 때) 는 0, 1, … , m − 1의 순열입니다. 즉, i를 하나씩 늘려가며 h(k, i)를 다 돌면, 표에 있는 모든 슬롯을 돌게 됩니다. ⁉️ Insert(k, v) : 빈 슬롯을 찾을 때까지 계속 ..