ㅇㅅㅎ

요즘 독서량을 늘리기 위해서 도서관에서 2주에 1권 빌리는 것을 한가지 규칙으로 정했습니다. 이번주에 읽게된 책은 청소년용 과학도서였는데 그 책에서 새롭고 신기한 동물들에 대해서 넓고 얕게 알게 되었지만 그 중에서 '매화날개딱새'라는 새의 소리가 재밌고 신기하여 오래 기억에 남겨두고 싶어서 블로그에 글을 쓰게 되었습니다. '매화날개딱새'는 안데스산맥 근처 콜롬비아와 에콰도르에 사는 새로 수컷이 깃털로 소리를 내어 구애합니다. 책에서는 이 소리를 바이올린 소리라고 하였는데 제가 느끼기에는 부저음(삐---)같은 소리로 처음에는 '이게 설마... 그 소린가?'라며 의문을 가졌습니다. 하지만 날개를 수직으로 쭉 뻗으면서 소리를 내는데 정말 신기합니다. 이 새는 날개를 1초에 100번 이상 앞뒤로 흔들면서 소리를..

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 테이블을 상향식으로 만들기 ⇒ 시간 = 하위 문제당 시간·하위 문제의 개수 하위 문제가 비순환적인지/위상학적 순서인지 확인하기 원래 문제 풀이 ⇒ 추가 시간 필요 : 하위 문제의 풀이 또는 하위 문제들로 조합하여 풀기 ✔ 2종류의 추측 2&3단계에서 어떤 하위 문제를 사용할지 추측 (피보나치를 제외하고 모든 동적 프로그래밍에서 사용) 1단계에서 정답 구조에 대해 더 많은걸 기억하거나 추측하기 위해 ..

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

👀 약수 : 어떤 수를 나누어떨어지게 하는 수. 예) 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