ㅇㅅㅎ

👀 약수 : 어떤 수를 나누어떨어지게 하는 수. 예) 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) : 빈 슬롯을 찾을 때까지 계속 ..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 테이블 더블링 ⁉️ 해시 테이블의 크기는 얼마나 커야 하나? 해시 테이블(지난 강의 참조)의 경우 m과 n이 비슷할 경우가 가장 좋지만 n을 알 수가 없습니다. m이 너무 작으면 느리고 m이 너무 크면 낭비가 됩니다. 그리고 항상 m = Θ(n) 이길 원합니다. ⁉️ 발상 : 작은 상수로 시작해 필요에 따라 늘리거나 줄입니다. ⁉️ 다시 해싱하기 : 해시 테이블을 늘리거나 줄이기 위해서는 해시 함수의 (m, r)도 바뀌어야 합니다. ⭐ m → m'로 테이블 사이즈를 변경할 경우 m' 사이즈 테이블을 생성 h'라는 새로운 해시 함수 생성 다시 해싱하기 for 항목 in 기존 테이블: 새로운테이블.inser..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 딕셔너리 : 추상 자료형(ADT)으로 일반적으로 딕셔너리는 각각의 항목에 키가 존재하는 집합이라 합니다. 균형 이진 탐색 트리는 연산 하나당 O(lg n) 시간이 소요되었는데 딕셔너리는 연산 하나 당 O(1) 시간이 목표입니다. insert(item): 집합에 항목 추가(존재하는 키는 덮어씀) delete(item): 집합에서 항목 제거 search(key): 존재할 경우 키와 항목 반환(존재하지 않을 경우 key error 발생) ⁉️ 파이썬의 딕셔너리 : 항목은 (키, 값) 쌍으로 이루어져 있습니다. 파이썬 집합은 항목이 곧 키가 되는 진짜 dict(사전)에 가깝습니다.(값이 없음을 의미합니다.) ⁉..