#recursion
노트 7개
Algorithm › Math
선형 점화식의 일반항상수 계수 선형 점화식의 일반항을 생성함수, 특성방정식, 행렬 대각화 세 가지로 구하고, 세 방법이 같은 고유값을 찾는 일임을 야콥스탈 수열로 보인다.
Algorithm › Paradigm
동적 계획법 (DP)겹치는 하위 문제의 답을 한 번만 계산해 저장하고 재사용하여 큰 문제를 효율적으로 푸는 기법. 하위 문제를 찾는 연습(타일링)과 구간 DP(연쇄 행렬 곱셈)를 함께 다룬다.
Algorithm › Paradigm
분할 정복문제를 서로 독립적인 작은 하위 문제로 나누어 재귀적으로 풀고, 그 결과를 합쳐 원래 문제를 해결하는 기법과, 실행 시간을 점화식(반복 대입·추정 후 증명·마스터 정리)으로 구하는 법.
Algorithm › Paradigm
재귀 함수자기 자신을 다시 호출해 문제를 더 작은 같은 문제로 줄여 가는 함수와 그 종료 조건. 예제로 팩토리얼과 유클리드 호제법(최대공약수·최소공배수)을 다룬다.
Algorithm › Search
깊이 우선 탐색 (DFS)한 갈래를 갈 수 있는 데까지 파고든 뒤 되돌아오는 그래프 탐색으로, 스택이나 재귀로 구현한다.
Algorithm › Sorting
병합 삽입 정렬 (Ford-Johnson)비교 횟수를 최소화하도록 설계된 Ford-Johnson 알고리즘. 짝짓기로 큰 원소를 재귀 정렬하고, 작은 원소를 야콥스탈 수 순서로 이진 삽입해 이진 탐색 비용을 낭비하지 않는다.
Algorithm
파싱 알고리즘과 프랫 파서토큰열을 구문 트리로 만드는 파싱 알고리즘의 흐름. BNF 규칙을 함수로 옮기는 재귀 하향 파서(JSON 예제), 연산자 우선순위로 그리디하게 묶는 플로이드의 상향식 파서, 바인딩 파워로 둘의 장점을 합친 프랫 파서를 셸 문법 예제로 정리한다.