#알고리즘

버블·선택·삽입·퀵·병합 다섯 정렬 알고리즘을 시간복잡도와 안정성 기준으로 비교하고, 정처기 필기에서 자주 나오는 함정을 정리한다.

같은 부분 문제를 반복 계산하는 낭비를 없애는 것이 동적 계획법이다. 피보나치 재귀가 왜 느린지에서 출발해 메모이제이션(top-down)과 타뷸레이션(bottom-up)의 차이, 상태 정의→점화식→초기값이라는 점화식 세우기 3단계, 코딩테스트에서 DP 문제를 알아보는 신호까지 실행 가능한 코드로 정리한다.

그래프 탐색의 두 축 BFS와 DFS는 큐냐 스택이냐로 갈린다. 같은 그래프에 두 탐색을 돌려 순서 차이를 확인하고, BFS는 최단 거리·DFS는 백트래킹이라는 용도 구분, 방문 체크 시점과 재귀 깊이라는 코딩테스트 단골 함정까지 실행 가능한 코드로 정리한다.

정렬된 배열에서 후보를 매번 절반씩 지워 O(log n)에 찾는 이진 탐색. 동작 원리와 자주 틀리는 경계·오버플로 함정, 값이 없어도 위치를 찾는 lower/upper bound, 그리고 답을 직접 못 세는 문제를 이진 탐색으로 바꾸는 매개변수 탐색까지 정리한다.

프로그램의 빠르기는 실행 시간이 아니라 입력이 커질 때 연산이 늘어나는 속도로 잰다. Big-O가 무엇을 버리고 무엇을 남기는지, 대표 복잡도의 감, 같은 문제를 O(n²)에서 O(n)으로 줄이는 예제, 그리고 코딩테스트에서 입력 크기로 허용 복잡도를 어림하는 법까지 정리한다.