--- id: "lessons/heuristic-beam-search" title: "설치 일정과 Beam Search: 남길 후보와 실행할 답" description: "분기 후보와 경로 후보를 따로 줄이고, 탐색 평가값과 실제 점수를 구분합니다." kind: "record" published: "2026-10-04T00:00:00.000Z" tags: ["알고리즘","C++","휴리스틱"] url: "https://www.readiz.com/records/heuristic-beam-search/" markdownUrl: "https://www.readiz.com/records/heuristic-beam-search/index.md" --- # 설치 일정과 Beam Search: 남길 후보와 실행할 답 Beam Search는 부분 일정 여러 개를 남기고, 각각을 한 방문씩 늘린 뒤 다시 좋은 후보만 추리는 탐색입니다. 이 사례에서는 다음 주택 후보와 여러 방문으로 이루어진 경로 후보를 서로 다른 기준으로 줄입니다. ![폭 2인 Beam Search에서 첫 단계 key 91과 88을 남깁니다. 이 둘을 확장해 얻은 107, 103, 94, 81 중 전체 상위 두 개인 107과 103을 남깁니다. 탈락한 72는 확장하지 않습니다.](https://www.readiz.com/assets/lessons/heuristic-planning/beam-search.svg) 그림은 폭 `K = 2`인 설명용 예시입니다. 숫자는 실제 채점 점수 `score`가 아니라 후보 유지용 평가값 `key`이며, 모든 부모에서 나온 다음 상태를 모아 상위 K개를 선택합니다. 두 후보가 같은 부모에서 나와도 됩니다. ## 문제 계약부터 상태로 옮기기 제출 코드가 받거나 호출하는 인터페이스는 다음과 같습니다. > **코드 환경: h-contest 설계 조각.** 표준 헤더·STL 없이 상태와 탐색 일부를 설명합니다. 문제의 공개 API와 전체 상태 관리에 연결하여 사용합니다. ```cpp #define MAP_SIZE 100 extern void move(int y, int x); extern void nextDay(void); void process(int mapInfo[][MAP_SIZE], int posY, int posX); ``` | 항목 | 계약 | | ----- | ------------------------------------- | | 지도 | `100 × 100`, 각 칸은 빈 칸 또는 타입 `1..6` 주택 | | 이동 | 두 좌표의 맨해튼 거리만큼 시간 사용 | | 설치 | 타입에 따라 60분부터 210분까지 사용 | | 하루 | 최대 720분 | | 일정 | 31일, `nextDay()`는 최대 30번 | | 날짜 변경 | 사용 시간만 0으로 만들고 현재 위치는 유지 | | 수익 | 주택별 기본 수익과 480분 이후 분당 200점 수당 | | 방문 상태 | 설치한 주택은 사라지지만 전달받은 `mapInfo`는 바뀌지 않음 | 마지막 항목 때문에 제출 코드는 실제 설치한 주택을 따로 기록해야 합니다. Beam Search 안에서 가상으로 선택한 주택과 실제로 `move`를 호출해 설치한 주택도 구분해야 합니다. ```cpp struct House { int y, x, type; int used; // 이전 날짜까지 실제로 설치했는가? }; ``` ## 하루 경로의 정확한 깊이 상한 가장 짧은 타입 1 설치도 60분이 걸립니다. 이동 시간이 0이어도 하루 최대 방문 수는 다음과 같습니다. ```text 720 / 60 = 12 ``` 따라서 하루 경로는 최대 12칸의 고정 배열로 충분합니다. ```cpp const int MAX_PATH = 12; struct State { int pos; int minute; int score; int key; int count; short path[MAX_PATH]; }; ``` 여기서 `score`와 `key`는 같은 값이 아닙니다. - `score`: 이 가상 경로를 실제 실행했을 때 받는 채점 점수 - `key`: 아직 완성되지 않은 경로를 탐색 중에 살려 둘지 정하는 값 현재 점수가 조금 낮아도 시간을 적게 쓴 경로는 다음 주택을 하나 더 설치할 수 있습니다. 이런 상태를 `score`만으로 너무 일찍 버리지 않으려면 별도 `key`가 필요합니다. ## 왜 한 단계 탐욕으로 끝내지 않는가 현재 위치에서 가장 효율적인 주택 하나만 반복해서 고르면 가까운 주택은 잘 찾습니다. 하지만 첫 선택이 이후 모든 이동 거리를 바꾸므로, 주택이 밀집한 지역으로 들어가는 경로의 가치를 놓칠 수 있습니다. ```text 당장 좋아 보이는 경로: 현재 -> 가까운 A 첫 이동은 조금 길지만 뒤가 좋은 경로: 현재 -> B1 -> B2 -> B3 ``` `B1` 하나만 보면 A보다 나빠도, `B1`, `B2`, `B3`가 가까이 모여 있으면 하루 전체 수익은 두 번째 경로가 더 높을 수 있습니다. 그렇다고 모든 경로를 만들 수는 없습니다. 주택이 약 400개라면 첫 두 단계만 보아도 후보 수가 크게 늘어납니다. 따라서 이 풀이에서는 한 경로만 남기는 탐욕과 모든 경로를 보는 완전 탐색 사이의 중간 지점으로 Beam Search를 사용합니다. ## 첫 번째 가지치기: 다음 주택 8개 각 상태에서 미방문 주택을 전부 검사하되, 실제 다음 상태로 만드는 주택은 평가값 상위 8개뿐입니다. ```text cost = travel + service[type] candidateKey = price[type] - candidateRate × cost candidateRate = 1200 ``` 후보 단계의 목적은 최종 경로를 평가하는 것이 아니라, 다음 분기 수를 줄이는 것입니다. `candidateRate`가 너무 크면 멀고 비싼 주택이 후보 목록에 들어오지도 못합니다. 너무 작으면 이동 시간이 긴 주택이 목록을 차지합니다. ```cpp const int BRANCH_COUNT = 8; void keepCandidate( int ids[], int keys[], int &count, int id, int key ) { if (count == BRANCH_COUNT && key <= keys[count - 1]) return; int pos = count < BRANCH_COUNT ? count++ : count - 1; while (pos > 0 && keys[pos - 1] < key) { ids[pos] = ids[pos - 1]; keys[pos] = keys[pos - 1]; --pos; } ids[pos] = id; keys[pos] = key; } ``` 8개짜리 배열에서는 일반 정렬이나 힙보다 이 삽입 코드가 단순합니다. 배열은 항상 평가값 내림차순이고, 이미 8개가 찼을 때 새 후보가 꼴찌보다 나쁘면 즉시 버립니다. ## 두 번째 가지치기: 경로 상태 32개 각 빔 상태에서 최대 8개를 확장하면 깊이 하나에서 최대 `32 × 8 = 256`개의 다음 상태가 생깁니다. 이 중 다음 깊이로 넘길 상위 32개를 고릅니다. ```text beamKey = actualScore - beamRate × usedMinute beamRate = 1550 ``` 예를 들어 두 상태가 다음과 같다고 하겠습니다. | 상태 | 사용 시간 | 실제 점수 | `score - 1550 × minute` | | -- | ----: | ------: | ----------------------: | | A | 400분 | 700,000 | 80,000 | | B | 500분 | 800,000 | 25,000 | B의 실제 점수가 더 높지만, A는 100분을 덜 썼습니다. 그 시간에 다른 주택을 붙일 가능성을 남기기 위해 탐색 중에는 A를 더 높게 평가합니다. ```cpp const int BEAM_WIDTH = 32; void keepState(State states[], int &count, const State &next) { if (count == BEAM_WIDTH && next.key <= states[count - 1].key) return; int pos = count < BEAM_WIDTH ? count++ : count - 1; while (pos > 0 && states[pos - 1].key < next.key) { states[pos] = states[pos - 1]; --pos; } states[pos] = next; } ``` 첫 번째 가지치기가 **한 상태 안의 다음 행동**을 줄였다면, 두 번째 가지치기는 **서로 다른 경로 전체**를 비교합니다. 두 단계의 기준과 폭은 서로 다른 파라미터입니다. ## 왜 1200과 1550을 따로 쓰는가 후보 평가와 상태 평가에 같은 시간 패널티를 써야 할 이유는 없습니다. | 파라미터 | 역할 | 이 풀이의 값 | | --------------- | -------------------------- | ------: | | `candidateRate` | 다음 행동이 분기 목록에 들어올지 결정 | 1200 | | `beamRate` | 확장된 전체 경로가 다음 깊이에 살아남을지 결정 | 1550 | 후보 단계는 폭넓게 보고, 상태 단계는 전체 시간 효율을 더 엄격하게 보는 설계입니다. 이를 하나의 식으로 합치면 긴 작업을 너무 일찍 제외하거나, 반대로 시간이 많이 든 경로가 빔을 지나치게 차지할 수 있습니다. 480분 이후에는 실제 점수에 분당 200점이 추가됩니다. 실제 수당을 `score`에 정확히 넣으면 그 구간의 실질 시간 패널티는 다음처럼 자동으로 낮아집니다. ```text 1550 - 200 = 1350점/분 ``` 별도의 “야간 모드” 분기를 만들지 않아도 하루 후반에 남은 시간을 더 적극적으로 쓰게 됩니다. ## 실제 점수 시뮬레이션 후보를 붙일 때는 채점기와 같은 순서로 시간을 계산합니다. ```cpp State next = state; if (state.minute + travel + service[type] > 720) continue; int startMinute = state.minute; next.minute += travel + service[type]; next.score += price[type]; if (next.minute > 480) { int bonusStart = startMinute > 480 ? startMinute : 480; next.score += (next.minute - bonusStart) * 200; } ``` `startMinute`은 이동을 시작하기 전 시각입니다. 현재 시각이 450분이고 이동과 설치가 100분이면 480분 이후 70분만 수당 대상입니다. 현재 시각이 500분이면 같은 100분 전체가 수당 대상입니다. 한 가상 경로 안의 방문 목록과 실제 설치 완료 목록을 함께 검사해 중복 선택을 막습니다. ## 생존 기준과 실행 기준을 분리한다 탐색 중 상태를 살리는 기준은 `key`지만, 하루에 실제로 실행할 경로는 `score`가 가장 높은 상태입니다. ```cpp if (next.score > best.score) { best = next; } ``` `best`는 깊이 1부터 깊이 12까지 계속 갱신합니다. 그러면 좋은 경로가 반드시 방문 12개를 채우지 않아도 됩니다. 더 이상 효율적인 주택을 붙일 수 없는 짧은 경로도 최종 답이 될 수 있습니다. ## 계산량을 단계별로 줄이기 주택 수를 `H`라고 하면 주택 평가 횟수의 중심은 다음과 같습니다. ```text 31일 × 깊이 12 × 빔 32 × H ``` `H <= 399`이므로 약 476만 번입니다. 각 상태에서 실제로 만드는 분기는 최대 8개라 한 깊이의 상태 생성 수는 최대 256개입니다. ## 파라미터 실험 순서 한 번에 여러 값을 바꾸면 어떤 변경이 효과가 있었는지 알기 어렵습니다. 먼저 기준선을 고정하고 한 축씩 비교합니다. | 실험 | 바꿀 값 | 기록할 값 | | -: | ----------------------- | -------------------- | | 0 | `32 / 8 / 1200 / 1550` | TC별 점수, 총점, 실행 시간 | | 1 | `BEAM_WIDTH` 24, 32, 40 | 경로 다양성의 효과와 시간 증가 | | 2 | `BRANCH_COUNT` 6, 8, 10 | 후보 누락과 상태 생성 비용 | | 3 | `candidateRate` 주변 값 | 고가 주택과 가까운 주택의 선택 비율 | | 4 | `beamRate` 주변 값 | 일일 사용 시간과 실제 점수 | 총점만 기록하지 말고 TC별 점수도 남겨야 합니다. 평균이 올라도 특정 지도 밀도에서 크게 무너지는 파라미터가 있을 수 있습니다. 날짜별로는 아래 값이 유용합니다. - 720분 중 실제 사용 시간 - 이동 시간과 설치 시간의 비율 - 주택별 기본 수익과 480분 이후 수당 - 하루 방문 수 - 첫 방문 위치와 마지막 위치 시각화에서는 점수만 보지 말고, 낮은 점수의 날짜가 긴 첫 이동 때문인지, 시간이 남았는데 후보를 못 붙인 것인지, 저효율 타입을 많이 고른 것인지 확인합니다. 전체 규칙과 기준 구현은 [에어컨 설치 기사 해설](https://h.readiz.com/practice/AIRCONTECH/editorial)에 있습니다. ## 작은 하루 일정으로 직접 실행하기 [빔 폭과 시간 패널티 실험](https://www.readiz.com/learn/explore/?demo=beam) · [C++17 전체 예제 내려받기](https://www.readiz.com/assets/lessons/heuristic-planning/beam-day.cpp) 위의 원문 코드는 h-contest 풀이의 설계 조각입니다. 아래 실행 예제는 같은 원리를 분리해 살펴보는 **하루짜리 축소 모델**입니다. 31일 진행, 타입별 설치 시간, 야간 수당, 공개 API 호출은 포함하지 않습니다. 시작 위치는 `(0, 0)`, 이동은 맨해튼 거리, 실제 점수는 방문한 작업의 보상 합입니다. 종료 위치에서 출발점으로 돌아오지 않습니다. 이 모델은 상태마다 가능한 다음 작업을 모두 확장합니다. 따라서 원문의 ‘상태별 상위 8개’ 가지치기는 생략하고, 모든 부모가 만든 후보를 합쳐 `key = score - timePenalty × minute` 순으로 빔 폭만큼 남깁니다. 동점이면 실제 점수가 큰 경로, 시간이 짧은 경로, 작업 번호가 사전순으로 작은 경로를 택합니다. 최종 `best`는 모든 깊이에서 **가지치기 전에 생성한 후보**의 실제 점수로 갱신합니다. | 작업 | 위치 `(x, y)` | 설치 시간 | 보상 | | ----- | ----------- | ----: | -: | | A (0) | (0, 0) | 6 | 9 | | B (1) | (1, 0) | 2 | 7 | | C (2) | (2, 0) | 2 | 7 | 시간 예산 7, 패널티 0일 때 빔 폭 1은 A를 남기고 점수 9로 끝납니다. 폭 2는 B도 남겨 B→C를 발견합니다. 이동·설치 시간은 `1 + 2 + 1 + 2 = 6`, 점수는 14입니다. 이 예제에서 폭을 늘리면 개선되지만, 휴리스틱 탐색에서 폭을 늘릴 때마다 항상 점수가 오른다는 일반 보장은 없습니다. **입력:** 첫 줄 `N budget beamWidth timePenalty`, 다음 N줄은 `x y service reward`입니다. `1 ≤ N ≤ 12`, `1 ≤ budget ≤ 1000`, `1 ≤ beamWidth ≤ 256`, `0 ≤ timePenalty ≤ 100`, `0 ≤ x,y ≤ 100`, `1 ≤ service ≤ 100`, `0 ≤ reward ≤ 1000`입니다. ```text 3 7 2 0 0 0 6 9 1 0 2 7 2 0 2 7 ``` ```sh c++ -std=c++17 -O2 beam-day.cpp -o beam-demo ./beam-demo < input.txt ``` 출력 첫 줄은 `score minute`, 다음 줄은 0-based 작업 번호 경로입니다. 이 입력의 결과는 `14 6`과 `1 2`입니다. 가능한 작업이 없으면 `0 0`과 빈 경로가 나옵니다. 패널티를 바꾸면 생존 순서는 달라져도, 표시하는 최종 점수에서 시간 패널티를 빼지는 않습니다.