---
id: "lessons/heuristic-destroy-repair"
title: "광고판 배치와 destroy/repair: 지우고 다시 채우기"
description: "작은 이동의 한계를 여러 광고의 제거와 재배치로 넘고, 실패한 시도를 정확히 복구합니다."
kind: "record"
published: "2026-10-04T00:00:00.000Z"
tags: ["알고리즘","C++","휴리스틱"]
url: "https://www.readiz.com/records/heuristic-destroy-repair/"
markdownUrl: "https://www.readiz.com/records/heuristic-destroy-repair/index.md"
---

# 광고판 배치와 destroy/repair: 지우고 다시 채우기

## 문제 구조 요약

[광고판 도시 배치](https://h.readiz.com/practice/BILLCITY)는 `process(buildings, ads)` 안에서 `place_ad(adId, buildingId, top, left)`를 호출해 광고판을 놓는 문제입니다.

문제 구조는 다음과 같습니다.

| 항목    | 내용                                               |
| ----- | ------------------------------------------------ |
| 건물 수  | 20개                                              |
| 광고 수  | 132개                                             |
| 건물 타입 | `WAREHOUSE`, `STORE`                             |
| 점수    | `WAREHOUSE`는 `ad.score`, `STORE`는 `ad.score * 2` |
| 금지 조건 | 건물 밖, 창문 칸, 다른 광고와 겹치기, 같은 광고 재사용                |
| 회전    | 광고는 회전하지 않는다                                     |
| 출력    | 각 TC의 `SCORE`, 마지막 합산 `SCORE`                    |

이 문제는 단순히 광고를 많이 넣는 문제가 아닙니다. 좋은 광고를 골라야 하고, `STORE` 보너스를 활용해야 하며, 남은 빈 공간이 나쁘게 쪼개지지 않도록 좌표를 골라야 합니다.

## 0점에서 first-fit까지

아무것도 하지 않는 `process`의 점수는 0입니다.

그다음은 가장 단순한 first-fit입니다.

```text
for ad in input_order:
    for building in input_order:
        for top, left in row_major_order:
            if place_ad(ad, building, top, left):
                다음 광고로 넘어간다 // 좌표·건물 반복을 모두 종료
```

first-fit은 빠르고 구현이 쉽습니다. 하지만 좋은 좌표를 고르지 않습니다. 처음 들어가는 위치에 바로 놓기 때문에 큰 광고가 들어갈 수 있는 공간을 작은 광고가 먼저 잘라 버릴 수 있습니다.

로컬 `canPlace`를 작성했다면, 같은 위치에 대한 `place_ad`의 성공·실패 결과와 먼저 대조합니다.

## 정렬 greedy: 무엇을 먼저 놓을 것인가

first-fit 다음에는 "무엇을 먼저 볼 것인가"를 고칩니다.

이 문제에서는 광고마다 `score`, `h`, `w`가 다르고 `STORE`는 점수가 2배입니다. 그래서 입력 순서보다 아래 기준이 자연스럽습니다.

```text
광고 순서:
- score가 높은 광고
- score / area가 높은 광고
- 큰 광고를 먼저 넣어야 빈 공간이 덜 망가지는 경우

건물 순서:
- STORE 먼저
- 유효 빈칸이 큰 건물 먼저
- 창문 때문에 모양이 까다로운 건물은 별도 평가
```

정렬 greedy는 "좋은 물건을 먼저 본다"는 의미입니다. 하지만 이것만으로는 아직 부족합니다. 같은 광고를 같은 건물에 넣더라도 좌표에 따라 이후 공간이 달라지기 때문입니다.

## 위치 평가식: 어디에 놓을 것인가

이 문제의 분기점은 "놓을 수 있는 첫 위치"와 "나중에도 좋은 위치"를 구분하는 데 있습니다.

건물 폭이 작기 때문에 각 행을 bitmask로 들면 배치 가능 여부를 빠르게 검사할 수 있습니다.

> **코드 환경: h-contest 설계 조각.** 표준 헤더·STL 없이 상태와 탐색 일부를 설명합니다. 문제의 공개 API와 전체 상태 관리에 연결하여 사용합니다.

```cpp
// 호출 전: 건물 내부 좌표, 1 <= w < 32, x + w <= 32, y + h <= 24 확인
unsigned int occ[20][24];

int canPlaceLocal(int bid, int y, int x, int h, int w) {
    unsigned int mask = ((1u << w) - 1u) << x;

    for (int r = 0; r < h; ++r) {
        if (occ[bid][y + r] & mask) return 0;
    }
    return 1;
}
```

창문도 처음부터 `occ`에 넣어 두면, 이후 배치 검사는 "이미 막힌 칸과 겹치는가" 하나로 단순해집니다. 단, 광고를 제거해야 하므로 창문 mask와 광고 mask를 분리해서 복구할 수 있게 해야 합니다.

좌표를 평가할 때는 실제 점수만 보면 부족합니다.

```text
placement value =
    건물 배율을 반영한 실제 점수
  + 벽, 창문, 기존 광고와 붙는 contact 보너스
  - 빈 공간을 얇게 쪼개는 penalty
```

contact가 높으면 광고가 구석이나 기존 물체에 붙어 빈 공간을 덜 조각내는 경우가 많습니다. 단, contact만 크게 주면 큰 광고가 들어갈 중앙 공간을 잃을 수 있으므로 실제 점수와 같이 봐야 합니다.

탐색 중 제거·복구는 풀이가 가진 로컬 배치에서만 수행합니다. 최종 배치를 고른 뒤 `place_ad`를 호출합니다. 이미 공개 API로 배치한 광고를 로컬 배열에서 지워도 채점기 상태가 되돌아가지는 않습니다.

## 작은 local search의 한계

정렬 greedy 이후에는 이미 놓은 광고 하나를 빼고 다른 광고를 넣어 보는 작은 local search를 시도할 수 있습니다.

```text
1. 점수 대비 효율이 낮은 광고 하나를 제거한다.
2. 미배치 광고 중 좋은 후보를 몇 개 넣어 본다.
3. 점수가 오르면 유지하고, 아니면 rollback한다.
```

광고 하나만 빼서는 빈 공간 구조가 크게 바뀌지 않습니다. 이미 나쁘게 쪼개진 공간은 작은 이동만으로 회복하기 어렵습니다.

![2행 4열 보드에서 A와 B가 가운데 두 열을 차지합니다. A만 제거하면 빈 폭이 2라서 폭 3인 C가 B와 겹칩니다. A와 B를 함께 제거하고 C를 넣으면 점수가 6에서 10으로 개선됩니다.](https://www.readiz.com/assets/lessons/heuristic-planning/destroy-repair.svg)

[그림 크게 보기](https://www.readiz.com/assets/lessons/heuristic-planning/destroy-repair.svg)

배치 원리만 떼어 낸 작은 예시입니다. 건물 배율은 1로 두고, A·B는 각각 `2×1`, C는 `2×3`입니다. A 또는 B만 제거하면 연속 빈 폭은 2라서 C가 들어가지 않습니다. 둘을 함께 제거해야 폭 3을 확보합니다.

## 큰 destroy/repair

배치 구조를 바꾸려면 한 번에 여러 광고를 지우고 다시 채우는 편이 강합니다.

```text
best = contact-aware greedy 결과

repeat:
    current = best 복사
    광고 여러 개를 제거한다
    제거된 광고와 미배치 광고를 다시 후보로 만든다
    contact-aware greedy로 다시 채운다

    current가 좋아졌으면 best로 채택한다
```

여기서 중요한 것은 destroy보다 repair입니다. repair가 first-fit이면 큰 destroy를 해도 낮은 품질의 배치로 돌아가기 쉽습니다. 반대로 repair가 위치 평가식을 잘 쓰면, 같은 공간을 더 좋은 모양으로 다시 채울 수 있습니다.

제거 대상을 완전히 무작위로만 고를 필요도 없습니다.

```text
- 최근에 배치한 광고
- 점수 대비 면적 효율이 낮은 광고
- 특정 건물 하나에 놓인 광고 전체
- 창문 주변에서 공간을 많이 막는 광고
- 무작위 제거와 목적 제거를 섞은 후보
```

remove count는 실험값입니다. 너무 작으면 지역 최적을 벗어나지 못하고, 너무 크면 매번 거의 새로 만드는 것과 비슷해집니다.

## 예산을 제한한 건물 단위 재탐색

전체 문제를 정확히 푸는 것은 어렵습니다. 하지만 건물 하나만 떼어 내면 후보 수가 줄어듭니다.

```text
for each building:
    현재 building에 놓인 광고를 모두 제거한다
    미배치 광고 중 이 building에 넣어 볼 후보를 고른다
    DFS로 이 building만 다시 채워 본다
    좋아졌으면 채택하고, 아니면 rollback한다
```

전체는 greedy와 destroy/repair로 넓게 찾고, 작은 부분은 DFS나 DP로 다시 봅니다. 후보를 제한한 부분 문제를 끝까지 풀었다면 **그 후보 집합 안에서만** 최적성을 말할 수 있습니다. 시간이나 node 방문 수를 소진해 중단했다면 부분 문제의 최적해도 보장하지 않습니다.

DFS의 비용을 줄이는 방법은 보장 범위가 서로 다릅니다.

| 방법                        | 무엇이 달라지는가                            |
| ------------------------- | ------------------------------------ |
| 후보·건물·구역 제한               | 정확히 풀 대상인 부분 문제 자체를 줄임               |
| 남은 후보 점수의 안전한 upper bound | best를 넘을 수 없는 가지를 버리며 부분 문제의 최적성은 유지 |
| 시간·node 방문 수 제한           | 아직 가능한 가지를 남기고 중단하므로 최적성 보장이 사라짐     |

느슨한 upper bound라도 효과가 있습니다. 남은 후보를 모두 넣는다고 가정해도 현재 best를 넘지 못하면 더 내려갈 필요가 없습니다.

## Beam Search보다 repair가 먼저일 수 있다

Beam Search는 부분 상태의 평가식이 좋을 때 강합니다. 그런데 이 문제에서는 미완성 배치의 점수를 평가하기 어렵습니다.

초반에 높은 점수 광고를 많이 넣은 후보가 좋아 보여도, 실제로는 큰 광고가 들어갈 공간을 망쳐 최종 점수가 낮을 수 있습니다. 이럴 때는 미완성 후보를 오래 들고 가는 것보다 완성된 답을 많이 만들고 실제 점수로 비교하는 편이 안정적입니다.

```text
완성된 greedy 답 생성
-> destroy/repair로 완성 답끼리 비교
-> 작은 구역 재탐색과 실제 점수 비교
```

repair가 계속 같은 나쁜 배치를 만들면 반복 횟수나 빔 폭을 늘려도 개선 폭이 작습니다. 제거 개수와 repair 평가식을 따로 바꾸어 비교합니다.

## 다른 배치 문제

[상자 쌓기](https://h.readiz.com/practice/STACKING)에서도 작은 이동으로 해소되지 않는 빈 공간이 생깁니다. 일부 배치를 제거한 뒤 다시 채우는 destroy/repair를 비교해 볼 수 있습니다.

## 성공과 실패를 모두 실행해 보기

[제거·재배치·원상복구 실험](https://www.readiz.com/learn/explore/?demo=repair) · [C++17 전체 예제 내려받기](https://www.readiz.com/assets/lessons/heuristic-planning/destroy-repair.cpp)

원문의 `canPlaceLocal`은 전체 제출 코드가 아닌 설계 조각입니다. 새 실행 파일은 위 그림의 **2행 4열 보드에서 한 번의 교체 시도**만 구현합니다. 건물 배율은 1이고 창문은 없습니다. A와 B는 가운데 두 열을 차지하며 각각 3점입니다. C는 2행 3열입니다. 이 실험의 repair 후보는 C 하나로 제한하며, 제거한 A·B를 다시 넣는 전체 탐색은 수행하지 않습니다.

1. 원래 보드와 점수 6을 보관하고 별도 후보를 복사합니다.
2. A만 또는 A·B를 함께 제거합니다.
3. C를 놓을 수 있는 첫 좌표를 찾습니다. 회전은 허용하지 않습니다.
4. C를 놓았고 점수가 엄격하게 올랐을 때만 채택합니다. 그 외에는 원래 보드 전체를 유지합니다.

**입력:** `removeMask replacementScore` 한 줄입니다. `removeMask`는 A만 제거하는 1 또는 A·B를 제거하는 3, C의 점수는 0부터 1000까지입니다.

| 입력     | 시도 결과                     | 최종 점수 |
| ------ | ------------------------- | ----: |
| `1 10` | B가 가로막아 C를 놓을 수 없음 → 복구   |     6 |
| `3 10` | C 배치 성공, 6에서 10으로 개선 → 채택 |    10 |
| `3 4`  | C 배치 성공, 점수 하락 → 복구       |     6 |

```sh
c++ -std=c++17 -O2 destroy-repair.cpp -o repair-demo
echo '3 10' | ./repair-demo
```

출력 첫 줄은 `배치성공여부 채택여부 후보점수 최종점수`입니다. 이어서 최종 보드를 두 줄로 출력합니다. 위 입력은 `1 1 10 10`, `CCC.`, `CCC.`입니다. 거절된 시도에서는 점수뿐 아니라 보드도 정확히 `.AB.`, `.AB.`로 돌아옵니다. 공개 `place_ad`를 호출한 뒤 되돌리는 예제가 아니라, **로컬 후보만 수정하고 마지막에 채택하는 구조**입니다.