tag · 8 posts

#algorithm

완전탐색을 출발점으로 두고, 탐색 공간을 줄이는 네 가지 근거를 축으로 알고리즘 시리즈의 지도를 그립니다. 그래프 탐색부터 정수론까지 여섯 편의 구성과 서로의 의존 관계를 정리합니다.

read →

그래프 표현 두 가지의 선택 기준을 정리하고, 격자와 상태 공간을 그래프로 읽는 방법을 다룹니다. 깊이 우선 탐색과 너비 우선 탐색이 각각 어떤 질문에 답하는지, 너비 우선이 최단 거리를 보장하는 근거는 무엇인지 확인합니다.

read →

이분탐색의 전제를 정렬이 아니라 단조성으로 다시 정의하고, 답 자체를 이분탐색하는 파라메트릭 서치로 확장합니다. 경계 조건을 안정적으로 처리하는 템플릿과 투 포인터, 백트래킹의 가지치기, 비트마스킹을 같은 관점으로 묶습니다.

read →

그리디가 성립하는 두 가지 조건을 정리하고, 증명 대신 반례를 찾는 실용적인 판별법을 다룹니다. 그리디가 깨질 때 동적 계획법으로 넘어가는 과정과 점화식을 세우는 절차, 배낭 문제의 두 변형을 확인합니다.

read →

가중치가 있는 그래프의 최단 경로를 다익스트라로 풀고, 음수 간선과 전체 쌍 최단 거리라는 변형을 확인합니다. 연결 여부만 필요할 때의 유니온 파인드, 최소 비용 연결을 만드는 최소 신장 트리, 순서 제약을 처리하는 위상정렬까지 신호별로 정리합니다.

read →

나이브 문자열 매칭이 버리는 정보가 무엇인지 짚고, KMP의 실패 함수가 그 정보를 어떻게 저장하는지 다룹니다. 해시로 비교하는 라빈카프와 접두사를 공유하는 트라이까지 문자열 전용 구조를 정리합니다.

read →

유클리드 호제법과 에라토스테네스의 체를 원리부터 정리하고, 모듈러 연산이 어떤 성질 위에서 안전한지 확인합니다. 자바스크립트에서 정수 정밀도가 깨지는 경계와 BigInt로 넘어가는 기준까지 다루며 두 시리즈를 마칩니다.

read →

자료구조와 알고리즘을 두 개의 시리즈로 나눠 다룹니다. 자료구조 시리즈는 데이터를 담고 정리하는 구조를, 알고리즘 시리즈는 그 안에서 찾고 결정하는 방법을 봅니다. 각 편이 독립적으로 읽히도록 구성했고, 이 편은 전체 지도 역할을 합니다.

read →