탐색
글 12개
음수가 있거나 모든 쌍이 필요할 때
비용이 가장 적은 후보부터 확정하는 방식이 안 통하는 두 경우입니다. 음수 간선을 다루는 벨만-포드(Bellman-Ford)와 모든 쌍의 거리를 한 번에 구하는 플로이드-워셜(Floyd-Warshall), 그리고 셋 중 무엇을 고를지.
남은 거리를 짐작하면 덜 헤맨다
목표가 하나일 때 탐색을 그쪽으로 기울이는 A 스타(A*) 알고리즘입니다. 휴리스틱이 지켜야 하는 조건, 과대평가하면 무엇이 깨지는지, 격자에서 무엇을 쓰고 동점은 어떻게 처리하는지.
꺼내는 순서를 큐가 아니라 비용이 정한다
칸마다 이동 비용이 다른 맵에서 최단 경로를 찾는 다익스트라 알고리즘(Dijkstra's algorithm)입니다. 왜 한 번 확정한 것을 다시 안 봐도 되는지, 음수 간선에서 왜 무너지는지, 게임에서 가중치를 어디서 얻는지.
채우기는 어디서 멈출지를 색으로 정한다
매치3의 같은 색 묶기, 페인트 통, 지뢰찾기의 빈 칸 열기가 전부 플러드 필(flood fill) 하나입니다. 이웃을 색으로 정하는 탐색이 어디서 터지고, 네 방향과 여덟 방향이 무엇을 바꾸는지 봅니다.
가까운 곳부터 한 겹씩 퍼지면 그게 곧 최단 거리다
너비 우선 탐색은 꺼내는 자리를 스택에서 큐로 바꾼 것이 전부입니다. 그 하나가 왜 최단 거리를 보장하는지, 거리와 부모를 어떻게 기록해 경로를 되짚는지, 그리고 칸마다 비용이 달라지면 왜 무너지는지.
한 갈래를 끝까지 가 보고 막히면 되돌아온다
깊이 우선 탐색이 실제로 어떻게 도는지 봅니다. 재귀와 스택이 왜 같은 코드인지, 방문 표시를 어디서 찍어야 하는지, 그리고 던전 연결 검사와 미로 생성에서 이 순서가 왜 필요한지.
꼭짓점은 양 끝이 아니라 두 점을 비교해서 찾는다
올라갔다 내려오는 곡선의 최고점을 찾는 문제입니다. 크다 작다로는 방향을 알 수 없어서, 가운데 두 점을 견줘 삼분의 일씩 버립니다. 그 전제가 깨지는 자리까지.
한 바퀴 돌아간 배열에서도 반쪽은 정렬돼 있다
링 버퍼처럼 어느 지점에서 끊긴 정렬 배열에서 값을 찾습니다. 가운데를 보면 두 반쪽 중 하나는 반드시 정렬돼 있고, 그 사실 하나로 절반을 버릴 수 있습니다.
배열이 아니라 답을 이분 탐색한다
찾는 대상이 배열의 값이 아니라 설정값일 때도 반으로 자를 수 있습니다. 판정이 단조롭기만 하면 됩니다. 그 전제가 깨지는 자리와 실수 범위를 다루는 법까지.
끝이 어딘지 모르는 배열에서 찾기
길이를 알려주지 않는 정렬된 데이터에서 값을 찾는 지수 탐색(exponential search)입니다. 경계를 두 배씩 넓혀 구간부터 만든 다음 이진 탐색으로 넘기는 방법과, 그 비용이 왜 전체 크기와 무관한지.
찾았는데 멈추면 안 되는 이유
정렬된 배열에 같은 값이 여러 개일 때 첫 자리를 찾는 문제입니다. 일반 이진 탐색이 왜 모자란지, 찾은 뒤 왼쪽으로 훑으면 왜 선형이 되는지, 그리고 한 줄만 바꾸면 그게 어떻게 사라지는지.
반으로 자르면 백만 칸이 스무 번에 끝난다
이진 탐색의 기본형입니다. 구간을 닫힌 것으로 잡을지 열린 것으로 잡을지, 언제 멈출지, 그리고 무한 루프와 오버플로가 나는 자리를 봅니다.