ㅇㅅㅎ

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 프로세서 구조 컴퓨터 구조의 발전 인텔 8086 (1981): 5 MHz (IBM PC에 처음 사용됨) 인텔 80486 (1989): 25 MHz (숫자를 상표로 사용할 수 없다는 법원 판결 때문에 i486이 됨) 펜티엄 (1993): 66 MHz 펜티엄 4 (2000): 1.5 GHz (약 30단계의 깊은 파이프라인) 펜티엄 D (2005): 3.2 GHz (이후 클럭 속도의 증가가 멈춤) 쿼드코어 제온 (2008): 3 GHz (하나의 칩의 코어 수가 성능의 주요 요소) 병렬 알고리즘의 문제점 프로세서는 계산할 데이터를 필요로 하나 SRAM은 4개보다 많은 메모리 요청을 병렬적으로 처리 불가합니다. ..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 정의 P : 다항 시간에 풀 수 있는 모든 문제들의 집합 예시) 음수 가중치 사이클 탐지 ∈ P EXP : 지수 시간에 풀 수 있는 모든 문제들의 집합. 예시) n×n 체스 ∈ EXP 그러나 ∈/(속하지 않음) P → n×n 체스 주어진 보드 배열에서 누가 이기는가? R : 유한 시간에 풀 수 있는 모든 문제들의 집합 예시) 테트리스 ∈ EXP 그러나 ∈ P 인지는 모름 → 주어진 보드와 조각들에서 살아남기 정지 문제 : 컴퓨터 프로그램이 주어졌을 때, 그것이 한 번이라도 정지하는가? 계산 불가능 (∈ / R):이것을 푸는 알고리즘은 없다 (모든 입력값에 대해 유한 시간에 맞게 푸는 것) 결정 문제: 답..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 복습 ⁉️ 동적 프로그래밍의 5단계 하위 문제 정의하기 ⇒ 하위 문제의 개수 세기 (해법의 일부분을) 추측하기 ⇒ 선택지의 개수 세기 하위 문제의 풀이 연관짓기 ⇒ 하위 문제당 시간 계산 재귀+기억 또는 DP 테이블을 상향식으로 만들기 ⇒ 시간 = 하위 문제당 시간·하위 문제의 개수 하위 문제가 비순환적인지/위상학적 순서인지 확인하기 원래 문제 풀이 ⇒ 추가 시간 필요 : 하위 문제의 풀이 또는 하위 문제들로 조합하여 풀기 ⁉️ 텍스트 정렬, 블랙잭은 시퀀스와 관련있습니다.(단어, 카드의 시퀀스) ⁉️ 문자열/시퀀스 x에 대해 유용한 문제들 ✔ 괄호 묶기 : A[0] · A[1]···A[n − 1]를 계..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 동적 프로그래밍 * DP ≈ “세심한 무차별 대입법” * DP ≈ 추측 + 재귀 + 메모이제이션 * DP ≈ 문제를 합리적인 개수의 하위 문제로 나누고 해를 비순환적으로 연관 짓습니다. 보통 해의 일부를 추측합니다. * time = #subproblems x time/subproblem → 근본적으로 분할 상환합니다. 각 하위 문제를 한 번만 셉니다. → 메모이제이션을 통해 처음 이후에는 O(1) 시간이 걸립니다. * DP ≈ DAG에서의 최단 경로 ⁉️ 동적 프로그래밍의 "간단한" 5단계 * 반드시 순차적인 것은 아닙니다. 하위 문제를 정의합니다. ⇒ 하위 문제의 개수를 셉니다.(#subprobs) 해..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 동적 프로그래밍(DP) 강력한 알고리즘 디자인 기법 보기에는 지수 시간이 걸리는 많은 문제도 DP를 사용하면 (사용해야지만) 다항 시간에 풀 수 있음 특히 최적화 문제(최소화/최대화)에 쓰임(최단 경로 문제) * DP ≈ “세심한 무차별 대입법” * DP ≈ 재귀+ 재사용 ✔ 피보나치 수 ⁉️ 목표 : n번째 피보나치 수를 계산하는 것 ⁉️ 단순 알고리즘(재귀 정의) def fib(n): if n

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)입니다. 다익스트라 알고리즘은 ..

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..