[TIL] 방의 개수 / 이분 탐색과 탐욕법

프로그래머스 방의 개수

오늘은 그래프를 활용하는 프로그래머스 방의 개수 문제를 풀었습니다.

이동한 좌표를 정점, 좌표 사이를 이동한 경로를 간선으로 생각하면 방이 생성되는 순간을 그래프의 사이클로 판단할 수 있습니다.

이미 방문한 정점에 도착하더라도 기존 간선을 다시 지나가는 경우에는 새로운 방이 생기지 않습니다. 따라서 정점의 방문 여부뿐만 아니라 간선의 방문 여부도 함께 관리해야 했습니다.

또한 대각선이 교차하는 경우에는 교차점이 정수 좌표로 기록되지 않는 문제가 있었습니다. 이를 해결하기 위해 한 번의 이동을 두 번으로 나누어 좌표계를 확대했고, 대각선 교차점도 일반 정점과 동일하게 처리할 수 있었습니다.

이번 문제를 통해 복잡한 영역을 직접 계산하기보다, 그래프의 정점과 간선 관계로 문제를 단순화하는 방법을 배웠습니다.

이분 탐색

이분 탐색은 정렬된 데이터나 단조성을 가진 범위에서 탐색 구간을 절반씩 줄여 나가는 알고리즘입니다.

특정 값을 찾는 기본적인 형태뿐만 아니라, 조건을 만족하는 첫 위치나 마지막 위치를 찾을 때도 사용할 수 있습니다.

또한 최댓값이나 최솟값을 직접 구하기 어려운 문제를 “이 값이 가능한가?”라는 결정 문제로 바꾸고, 판정 결과의 단조성을 이용해 답을 찾는 파라메트릭 서치 방식도 정리했습니다.

이분 탐색에서는 left, right, mid의 의미와 탐색 구간을 일관되게 유지하는 것이 중요하다는 점을 학습했습니다.

탐욕법

탐욕법은 매 단계에서 현재 가장 좋아 보이는 선택을 확정하며 답을 구하는 알고리즘입니다.

다만 단순히 가장 크거나 작은 값을 선택한다고 해서 항상 정답이 되는 것은 아닙니다. 현재 선택이 이후의 최적해를 해치지 않는다는 근거가 필요합니다.

회의실 배정 문제처럼 탐욕적인 선택으로 기존 최적해의 선택을 교체해도 결과가 나빠지지 않는다는 것을 보이는 교환 논증도 함께 학습했습니다.

탐욕법 문제에서는 구현보다 어떤 기준으로 선택할 것인지, 그리고 그 선택이 왜 안전한지를 설명하는 과정이 중요하다는 점을 알게 되었습니다.