고속 푸리에 변환 (FFT)
DFT의 정규화부터 radix-2 버터플라이와 다항식 합성곱까지 살펴보고, 부동소수점 정수 계산의 한계를 설명합니다.
주제
컴퓨터 과학
컴퓨터 과학 주제로 명시적으로 분류된 검토 완료 글입니다. 한국어로 공개된 글만 표시합니다.
Floyd-Warshall Algorithm - 플로이드 워셜 알고리즘
플로이드–워셜의 모든 쌍 최단 경로 점화식을 유도하고, 안전한 C++ 구현과 도달 불가·음수 사이클의 의미를 살펴봅니다.
Max-flow min-cut theorem - 최대 유량 최소 컷 정리
잔여 네트워크의 도달 가능성을 이용해 최대 유량 최소 컷 정리를 증명하고, 작은 예제로 최적성을 확인합니다.
유클리드 알고리즘: 최대공약수 구하기
유클리드 알고리즘의 불변식과 계산 예를 증명하고, 비음수 입력을 전제로 한 C++ 구현 및 로그 단계 수를 설명합니다.
Flow network - 네트워크 플로우
실현 가능한 유량부터 잔여 간선의 증가와 취소, 컷의 상한, 포드–풀커슨 알고리즘의 종료 조건까지 살펴봅니다.
그래프 이론: 강한 연결 요소들(SCC)
강한 연결 요소의 의미와 타잔 알고리즘의 발견 번호·low-link·활성 스택 불변식을 예제와 구현으로 설명합니다.