강의자료로

기말 공개 코딩 15문제

기말고사 범위는 6~10장입니다. 기존 9장 NP완전 문제는 수업과 기말 범위에서 제외하고, 근사 알고리즘을 9장, 휴리스틱 알고리즘을 10장으로 옮겼습니다. 6~10장 각 3문제, 총 15문제 중 10문제를 코딩테스트로 출제합니다. 8-4·9-4·10-4와 추가 연습용 7-5~7-7은 기말 범위에 포함하지 않습니다. 각 함수의 입력·반환값·조건과 예제를 아래에서 확인하세요.

6장 동적 계획법

계단 오르기와 연속 부분합을 먼저 연습합니다. 두 문제의 설명과 Python/C 코드는 강의 PPTX에서 확인할 수 있습니다. 6-4는 두 문제를 푼 뒤 응용해 보는 도전문제입니다.

메모이제이션에 쓰는 해시맵과 Python 사전

해시맵은 키와 값을 짝지어 저장합니다. 계단 높이를 키로, 그 높이까지 오르는 방법 수를 값으로 두면 높이 4에 답 5를 연결할 수 있습니다. Python에서는 dict, 즉 사전을 사용합니다.

memo = {1: 1, 2: 2}  # 1칸은 1가지, 2칸은 2가지
memo[3] = 3             # 높이 3의 답 3을 저장
3 in memo               # True: 키 3이 있음
memo[3]                 # 3: 키 3의 값을 읽음
4 in memo               # False: 아직 키 4는 없음

in으로 키가 있는지 확인한 뒤 값을 읽습니다. 없는 키를 바로 읽으면 KeyError가 발생합니다. 배열의 dp[4]는 번호 4인 칸을 읽고, 사전의 memo[4]는 키 4에 연결한 값을 찾습니다. 아래 문제의 제출 코드는 배열과 변수로 구현할 수 있습니다.

6-2 계단 오르기 · 쉬움

작성 방식: 바텀업(반복문)
작은 높이부터 차례로 표를 채우는 바텀업 방식으로 작성한다. 1칸의 답은 1, 2칸의 답은 2이다. n=1이면 1을 바로 반환하고, 그 외에는 dp[1]=1, dp[2]=2를 넣은 뒤 3부터 n까지 반복문으로 계산한다.

높이가 n칸인 계단을 바닥에서 꼭대기까지 오른다. 한 번에 1칸 또는 2칸을 오를 수 있다. 오르는 순서가 다르면 서로 다른 방법으로 센다.

꼭대기까지 오르는 서로 다른 방법의 수를 반환하시오.

climb_stairs(n)

입력

n
계단 높이. 1 이상 90 이하의 정수

반환값과 조건

오르는 방법의 개수를 정수 하나로 반환한다. 이동 횟수나 이동 순서 목록을 반환하지 않는다.

  • 1칸 뒤 2칸을 오르는 방법과 2칸 뒤 1칸을 오르는 방법은 서로 다르다.
  • 계단을 내려가거나 꼭대기를 넘는 이동은 허용하지 않는다.
  • C에서는 큰 결과를 저장하도록 long long을 사용한다.

예제

한 칸
n=1

반환값: 1

1칸을 한 번 오르는 방법 하나다.

두 칸
n=2

반환값: 2

1+1과 2의 두 가지다.

세 칸
n=3

반환값: 3

1+1+1, 1+2, 2+1의 세 가지다.

네 칸
n=4

반환값: 5

1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2의 다섯 가지다.

일곱 칸
n=7

반환값: 21

5칸의 8가지와 6칸의 13가지를 더해 21가지다.

풀이 설명

마지막 이동이 1칸이면 n-1칸까지 오르는 방법에 1칸을 붙이고, 마지막 이동이 2칸이면 n-2칸까지 오르는 방법에 2칸을 붙인다. 두 경우의 방법 수를 더한다. dp[1]=1, dp[2]=2에서 시작하고, 3칸부터 앞의 두 답을 더한다. n=1이면 1을 바로 반환한다.

C 함수와 자료형
long long climb_stairs(int n)

n은 계단 높이이므로 int로 받는다. 방법 수는 크게 늘어나므로 반환값과 dp 배열의 각 칸에 long long을 쓴다.

이 문제 연습하기

6-3 연속 부분합 · 기본

정수 배열 a에서 하나 이상의 원소가 연속해서 이어진 구간 하나를 고른다. 구간 중간의 원소를 건너뛸 수 없다.

고른 구간의 원소 합 중 가장 큰 값을 반환하시오.

max_subarray(a)

입력

a
길이 1~10,000인 정수 배열. 각 값은 -1,000,000~1,000,000

반환값과 조건

연속 구간 합의 최댓값을 정수 하나로 반환한다. 구간의 위치나 원소 목록을 반환하지 않는다.

  • 구간에는 원소가 반드시 하나 이상 있어야 한다. 빈 선택은 허용하지 않는다.
  • 배열의 원래 순서와 이웃 관계를 유지한다.
  • 모든 값이 음수이면 그중 가장 큰 값 하나를 고른다.
  • C에서는 합이 int 범위를 넘을 수 있으므로 long long을 사용한다.

예제

중간부터 끝까지
a=[4,-6,3,2,-1,4]

반환값: 8

3+2-1+4=8인 연속 구간을 고른다.

모두 음수
a=[-8,-3,-5]

반환값: -3

하나는 골라야 하므로 가장 큰 -3을 고른다.

원소 한 개
a=[-7]

반환값: -7

유일한 구간 [-7]의 합 -7을 반환한다.

모두 양수
a=[2,4,1]

반환값: 7

배열 전체를 골라 합 7을 얻는다.

0을 고르는 경우
a=[-2,0,-1]

반환값: 0

원소 0 하나로 이루어진 구간을 고른다.

풀이 설명

ending에는 현재 위치에서 반드시 끝나는 구간의 최대 합을 둔다. 이번 수만으로 새로 시작하거나, 이전 ending에 이번 수를 붙이는 두 후보를 비교한다. best에는 지금까지 본 모든 위치의 최대 합을 따로 남긴다. 두 값은 첫 원소로 시작한다.

C 함수와 자료형
long long max_subarray(const int a[], int n)

a는 원소 배열, n은 원소 수이다. a는 읽기만 한다. n은 1 이상이므로 a[0]으로 시작할 수 있다. 원소의 합은 long long으로 저장한다.

이 문제 연습하기

6-4 1로 만드는 최소 연산 횟수 · 도전문제

정수 n을 아래 연산으로 바꾸어 1을 만든다. 한 번의 연산에서는 1을 빼거나, 2·3·5 중 하나로 나눈다. 나눗셈은 나누어떨어질 때만 할 수 있다.

n을 1로 만드는 데 필요한 연산 횟수의 최솟값을 반환하시오.

make_one(n)

입력

n
1 이상 10,000 이하의 정수

반환값과 조건

최소 연산 횟수를 정수로 반환한다. 중간에 거친 수의 개수가 아니라 연산한 횟수를 센다.

  • 처음부터 n=1이면 연산하지 않으므로 답은 0이다.
  • 정수 나눗셈으로 나머지를 버리는 연산은 허용하지 않는다. 예를 들어 7을 2로 나누어 3으로 바꿀 수 없다.

바로 나누는 경우와 먼저 1을 빼는 경우

이미 도착
n=1

반환값: 0

이미 1이므로 연산은 0회이다.

한 번에 도착
n=5

반환값: 1

5÷5=1이다.

두 번 나누기
n=10

반환값: 2

10÷2=5, 5÷5=1로 두 번이다.

먼저 1 빼기
n=26

반환값: 3

26−1=25, 25÷5=5, 5÷5=1로 세 번이다.

처음에 나눌 수 없음
n=7

반환값: 3

7−1=6, 6÷3=2, 2÷2=1로 세 번이다.

나누어떨어지는 후보만 비교한다

10에서는 9, 5, 2로 갈 수 있다. 9에서 1까지는 최소 두 번, 5와 2에서는 각각 한 번이 필요하다. 여기에 첫 이동 한 번을 더하면 후보는 3,2,2회이고 답은 2회이다. 3으로 나누는 경우는 10이 3의 배수가 아니므로 후보에 넣지 않는다.

C 함수의 인자
int make_one(int n, int dp[])

dp는 길이가 n+1인 작업 배열이다. 함수가 dp[1]부터 채운다.

이 문제 연습하기

7장 백트래킹 기법

강의에서는 전화 문자 도입 예제를 손으로 풀고, 7-2 목표 합과 7-3 그래프 색칠을 배웁니다. 7-4 N-퀸은 기본 두 문제를 푼 뒤 도전하는 사이트 연습문제입니다.

7-2 합이 목표가 되는 선택의 수 · 쉬움

양의 정수 배열 a에서 원소를 몇 개 골라 합을 만든다. 각 위치의 원소는 한 번만 고를 수 있다. 고른 원소의 합이 target과 같은 선택이 몇 개인지 센다.

합이 target인 선택의 수를 정수로 반환하시오.

subset_sum_count(a, target)

입력

a
길이 0~20의 배열. 각 값은 1~50인 정수
target
목표 합. 0~1000의 정수

반환값과 조건

조건을 만족하는 선택의 개수를 반환한다. 가능한지 여부나 선택한 원소의 개수를 반환하지 않는다.

  • 같은 값이라도 위치가 다르면 다른 원소이다.
  • 선택한 원소를 나열하는 순서는 구분하지 않는다. 1과 2를 고른 것과 2와 1을 고른 것은 같은 선택이다.
  • 아무것도 고르지 않은 선택도 포함하며, 그 합은 0이다.

같은 값과 같은 선택을 구분하는 기준

서로 다른 두 선택
a=[1,2,3], target=3

반환값: 2

1과 2를 고르거나, 3만 고르는 두 방법이다.

값이 같은 두 원소
a=[1,1], target=1

반환값: 2

첫 번째 1을 고르는 것과 두 번째 1을 고르는 것은 다르다.

순서는 세지 않음
a=[1,2], target=3

반환값: 1

두 원소를 모두 고르는 한 방법이다. 1+2와 2+1로 두 번 세지 않는다.

빈 선택
a=[], target=0

반환값: 1

아무것도 고르지 않은 한 방법의 합이 0이다.

만들 수 없는 합
a=[2,4], target=3

반환값: 0

가능한 합은 0,2,4,6이다. 3은 없다.

원소 하나마다 두 갈래로 나뉜다

첫 원소 1을 보는 순간에는 고르거나 건너뛰는 두 선택이 있다. 1을 골랐다면 다음 원소 2를 볼 때 합은 1이고, 건너뛰었다면 합은 0이다. 이 과정을 마지막 원소까지 반복하고, 마지막 합이 target인 갈래에서만 1을 더한다.

C 함수의 인자
int subset_sum_count(const int a[], int n, int target)

n은 배열 a의 원소 수이다.

이 문제 연습하기

7-3 이웃한 점을 다른 색으로 칠하기 · 기본

무방향 그래프의 각 점에 색 하나를 칠한다. 선으로 연결된 두 점은 서로 다른 색이어야 한다. 사용할 수 있는 색은 1번부터 k번까지이며, 모든 색을 반드시 사용할 필요는 없다.

이 조건으로 모든 점을 칠할 수 있으면 1, 없으면 0을 반환하시오.

can_color(graph, k)

입력

graph
점 1~8개의 0/1 연결 표. graph[i][j]=1이면 i와 j가 연결됨
k
쓸 수 있는 색 수. 1~3의 정수

반환값과 조건

가능하면 정수 1, 불가능하면 정수 0이다. 색 배치나 배치의 개수를 반환하지 않는다.

  • graph는 정사각 표이고 대칭이다. 자기 자신과의 연결은 없어 대각선은 0이다.
  • 연결되지 않은 두 점은 같은 색이어도 된다.
  • 점이 여러 덩어리로 나뉘어 있어도 모든 점을 칠한다.

삼각형에 두 색과 세 색을 쓸 때

삼각형, 두 색
세 점이 모두 서로 연결된 삼각형, k=2

반환값: 0

마지막 점은 앞의 두 점 모두와 이웃하므로 남는 색이 없다.

삼각형, 세 색
같은 삼각형, k=3

반환값: 1

세 점에 서로 다른 색을 칠하면 된다.

떨어진 점도 있음
0–1만 연결되고 2는 혼자인 그래프, k=2

반환값: 1

0과 1만 다르게 칠하면 된다. 2는 어느 색이나 가능하다.

색을 모두 쓸 필요 없음
점 하나, k=3

반환값: 1

한 색만 사용해도 조건을 만족한다.

연결된 두 점, 한 색
선 하나로 연결된 두 점, k=1

반환값: 0

양 끝의 색을 다르게 할 수 없다.

색을 정하기 전에 이미 칠한 이웃을 본다

삼각형에서 0번을 빨강으로 칠했다면 1번은 빨강을 쓸 수 없다. 1번을 파랑으로 칠한 뒤에는 2번에서 빨강과 파랑이 모두 막힌다. 세 번째 색이 있으면 성공하고, 없으면 앞의 선택으로 돌아간다. 코드의 color[v]=0은 방금 칠한 색을 지우는 줄이다.

C 함수의 인자
int can_color(const int graph[][8], int n, int k)

graph는 연결 표, n은 정점 수이다. 실제로는 앞의 n행·n열을 사용한다.

이 문제 연습하기

7-4 서로 공격하지 않는 퀸의 배치 수 · 도전문제

n×n 체스판에 퀸 n개를 놓는다. 퀸은 같은 행, 같은 열, 같은 대각선에 있는 다른 퀸을 공격한다. 어느 두 퀸도 서로 공격하지 않도록 놓아야 한다.

조건을 만족하는 배치의 수를 정수로 반환하시오.

nqueen_count(n)

입력

n
체스판의 한 변 길이이자 퀸 수. 1~8의 정수

반환값과 조건

가능한 배치 수를 반환한다. 가능한 배치가 없으면 0이다.

  • 한 칸에는 퀸 하나만 놓는다.
  • 회전하거나 뒤집은 모양도 퀸이 놓인 칸이 다르면 다른 배치로 센다.
  • 퀸 n개를 n개의 행에 서로 공격하지 않게 놓으면 각 행과 열에 하나씩 놓이게 된다.

작은 체스판에서 답이 없는 경우

한 칸
n=1

반환값: 1

유일한 칸에 퀸 하나를 놓는다.

두 줄
n=2

반환값: 0

행과 열을 다르게 놓아도 같은 대각선에 놓이게 된다.

세 줄
n=3

반환값: 0

세 퀸을 모두 충돌 없이 놓는 배치가 없다.

네 줄
n=4

반환값: 2

위에서부터 2,4,1,3열인 배치와 그 좌우 대칭 배치를 각각 센다.

다섯 줄
n=5

반환값: 10

조건을 만족하는 서로 다른 열 선택이 열 가지이다.

행 차이와 열 차이가 같으면 대각선이다

(1행,2열)과 (2행,3열)은 행과 열이 모두 한 칸 차이이므로 같은 대각선이다. 코드는 퀸을 한 행에 하나씩 놓아 같은 행 검사를 생략한다. 앞 행의 퀸과 열이 같은지, 행 차이와 열 차이의 절댓값이 같은지를 검사한다.

C 함수의 인자
int nqueen_count(int n)

n은 한 변의 칸 수이면서 놓을 퀸 수이다.

이 문제 연습하기

8장 분기한정 기법

기말 범위는 8-1, 8-2, 8-3입니다. 8-4는 추가 연습이며 출제하지 않습니다.

수업 PPTX와 같은 입력과 숫자로 연습합니다. 각 문제의 첫 번째 예제는 PPTX 예제입니다.

8-1 주어진 방문 순서의 왕복 비용 · 아주 쉬움

구할 값

route에 적힌 순서대로 도시를 방문하고, 출발한 0번 도시로 돌아올 때까지 드는 비용의 합을 구하세요.

도시는 0번부터 n−1번까지 있습니다. dist는 도시 사이의 이동 비용을 적은 표이고, route는 방문할 순서입니다.

route_cost(dist, route)

입력

dist
n행 n열의 비용 표입니다. n은 도시 수이며 1~9입니다. 행은 출발 도시, 열은 도착 도시입니다. 예를 들어 dist[0][1]은 0번에서 1번으로 가는 비용입니다.
route
도시 번호를 방문 순서대로 적은 길이 n의 배열입니다. 첫 값은 0이고, 모든 도시 번호가 한 번씩 들어 있습니다. [0,1,2]이면 0번, 1번, 2번 순서입니다.

반환값

마지막 도시에서 0번으로 돌아오는 비용까지 포함한 총비용을 정수 하나로 반환합니다.

계산 규칙

  • 각 이동 비용은 0~100인 정수이고, 같은 도시로 가는 대각선 값은 0입니다. 모든 도시 사이를 이동할 수 있습니다.
  • dist의 행 번호와 열 번호는 모두 0번부터 셉니다. 반대 방향의 비용은 다를 수 있으므로 각각 표에서 읽습니다.
  • 방문 순서는 입력받은 route를 따릅니다. 마지막 원소 다음에는 route의 첫 원소인 0번으로 돌아옵니다.
  • 도시가 하나이면 dist=[[0]], route=[0]이고 반환값은 0입니다.
예제 1 · PPTX 예제 · 0번 → 1번 → 2번 → 0번
dist = [
  [0, 2, 8],
  [1, 0, 3],
  [4, 6, 0]
]
route = [0, 1, 2]

반환값 9

0→1은 2, 1→2는 3, 2→0은 4입니다. 2+3+4=9를 반환합니다.

예제 2 · 방문 순서가 0번 → 2번 → 1번일 때
dist = [
  [0, 2, 8],
  [1, 0, 3],
  [4, 6, 0]
]
route = [0, 2, 1]

반환값 15

0→2는 8, 2→1은 6, 1→0은 1입니다. 8+6+1=15를 반환합니다.

예제 3 · 두 도시의 왕복
dist = [
  [0, 5],
  [8, 0]
]
route = [0, 1]

반환값 13

0→1의 비용 5와 1→0의 비용 8을 더합니다. 5+8=13입니다.

예제 4 · 도시가 하나일 때
dist = [
  [0]
]
route = [0]

반환값 0

0번 도시에서 시작해 그대로 끝납니다. dist[0][0]=0이므로 반환값은 0입니다.

풀이 힌트

route=[0,1,2]이면 dist[0][1], dist[1][2], dist[2][0]을 더합니다. i는 route에서 읽을 위치입니다. 현재 도시는 route[i], 다음 도시는 route[(i+1)%n]입니다. 마지막 위치의 다음 위치는 0이 됩니다.

C 함수의 입력
int route_cost(const int dist[][9], int n, const int route[])

dist는 비용 표이고 n은 실제 도시 수입니다. dist[][9]의 9는 한 행의 저장 공간이며, 앞 n행·n열을 사용합니다. route의 앞 n개 값이 방문 순서입니다.

이 문제 연습하기

8-2 남은 작업 비용의 하한 계산 · 쉬움

구할 값

아직 작업을 맡기지 않은 사람마다, 남은 작업 중 가장 싼 비용을 하나씩 찾아 더하세요.

사람 n명과 작업 n개가 있고 번호는 각각 0번부터 n−1번까지입니다. 앞의 몇 사람에게는 작업을 이미 맡겼습니다. 이 함수는 앞으로 드는 비용을 낮게 잡아 보는 계산입니다. 이렇게 실제 비용보다 작거나 같게 잡은 값을 하한이라고 합니다.

assignment_bound(cost, used, next_row)

입력

cost
n행 n열의 비용 표이며 n은 1~8입니다. cost[r][c]는 사람 r에게 작업 c를 맡길 때 드는 비용입니다. 행은 사람, 열은 작업이며 번호는 0번부터 셉니다.
used
길이 n의 작업 사용 표시입니다. used[c]=1이면 작업 c를 이미 맡겼고, 0이면 남아 있습니다. [0,1,0]이면 작업 1만 사용한 상태입니다.
next_row
다음에 작업을 맡길 사람 번호입니다. 0번부터 next_row−1번 사람은 배정이 끝났으며, next_row번부터 마지막 사람까지 계산합니다.

반환값

남은 각 사람의 최소 비용을 더한 값을 정수 하나로 반환합니다. 이미 배정한 사람에게 든 비용은 이 합에 넣지 않습니다.

계산 규칙

  • 각 비용은 0~100인 정수입니다. next_row는 0~n이며, used에서 값이 1인 칸의 개수와 같습니다.
  • 각 사람의 행에서 used가 0인 작업 열만 살펴보고, 그중 가장 작은 비용을 고릅니다.
  • 이 하한 계산에서는 서로 다른 사람이 같은 작업 열의 값을 골라도 됩니다. 한 행을 계산한 뒤에도 used는 그대로 둡니다.
  • next_row=0이면 모든 사람을 계산하고, next_row=n이면 남은 사람이 없으므로 0을 반환합니다.
예제 1 · PPTX 예제 · 작업 1을 이미 맡긴 상태
cost = [
  [9, 2, 7],
  [6, 4, 3],
  [5, 8, 1]
]
used = [0, 1, 0]
next_row = 1

반환값 4

사람 0의 배정은 끝났으므로 사람 1과 2만 봅니다. 작업 1의 열은 제외합니다. 사람 1은 min(6,3)=3, 사람 2는 min(5,1)=1이므로 3+1=4입니다. 두 값 모두 작업 2의 비용이어도 허용합니다. 사람 0에게 이미 든 비용 2는 더하지 않습니다.

예제 2 · 아무 작업도 맡기지 않은 상태
cost = [
  [9, 2, 7],
  [6, 4, 3],
  [5, 8, 1]
]
used = [0, 0, 0]
next_row = 0

반환값 6

세 사람을 모두 봅니다. 각 행의 최소 비용은 2, 3, 1이므로 2+3+1=6입니다. 사람 1과 2가 같은 작업 2의 값을 골라도 이 계산에서는 허용합니다.

예제 3 · 모든 사람의 배정이 끝난 상태
cost = [
  [9, 2, 7],
  [6, 4, 3],
  [5, 8, 1]
]
used = [1, 1, 1]
next_row = 3

반환값 0

n=3이고 next_row=3이므로 남은 사람이 없습니다. 더할 비용이 없어 0을 반환합니다.

예제 4 · 남은 사람이 한 명인 상태
cost = [
  [7]
]
used = [0]
next_row = 0

반환값 7

사람 0에게 남은 작업은 작업 0 하나입니다. 그 비용 7을 반환합니다.

풀이 힌트

PPTX의 used=[0,1,0], next_row=1에서는 작업 1의 열을 제외합니다. 사람 1은 min(6,3)=3, 사람 2는 min(5,1)=1이므로 하한은 4입니다. 실제로 서로 다른 작업을 맡기면 남은 비용은 7 또는 8입니다. 4는 이 실제 비용보다 낮게 잡은 값입니다.

C 함수의 입력
int assignment_bound(const int cost[][8], int n, const int used[], int next_row)

cost는 비용 표이고 n은 실제 사람 수이자 작업 수입니다. cost[][8]의 앞 n행·n열을 사용합니다. used[c]는 작업 c의 사용 표시이며, next_row는 계산을 시작할 사람 번호입니다.

이 문제 연습하기

8-3 작업을 중복 없이 배정하는 최소 비용 · 기본

구할 값

모든 사람에게 서로 다른 작업을 하나씩 맡겼을 때, 총비용을 가장 작게 만드는 배정의 비용을 구하세요.

사람 n명과 작업 n개가 있고 번호는 각각 0번부터 n−1번까지입니다. 모든 사람이 작업 하나씩을 맡아야 하며, 각 작업도 정확히 한 사람이 맡아야 합니다.

assignment_min(cost)

입력

cost
n행 n열의 비용 표이며 n은 1~8입니다. cost[r][c]는 사람 r에게 작업 c를 맡길 때 드는 비용입니다. 행은 사람, 열은 작업이고 번호는 0번부터 셉니다.

반환값

규칙을 지키는 모든 배정 중에서 총비용의 최솟값을 정수 하나로 반환합니다.

계산 규칙

  • 각 비용은 0~100인 정수입니다. 비용이 0인 작업도 정상적으로 맡길 수 있습니다.
  • 사람마다 작업 하나를 맡기고, 같은 작업을 두 사람에게 맡기지 않습니다.
  • 선택한 사람·작업 칸들의 비용을 모두 더해 총비용을 구합니다. 반환할 것은 최소 비용입니다.
  • 사람이 한 명이면 유일한 작업의 비용을 반환합니다.
예제 1 · PPTX 예제 · 세 사람의 최소 배정 비용
cost = [
  [9, 2, 7],
  [6, 4, 3],
  [5, 8, 1]
]

반환값 9

사람 0→작업 1의 비용은 2, 사람 1→작업 0의 비용은 6, 사람 2→작업 2의 비용은 1입니다. 서로 다른 작업을 사용했고 합은 9입니다. 가능한 여섯 배정의 총비용은 14, 20, 9, 10, 21, 16이므로 최솟값은 9입니다.

예제 2 · 두 사람의 배정을 비교하기
cost = [
  [4, 1],
  [2, 3]
]

반환값 3

사람 0→작업 0, 사람 1→작업 1이면 4+3=7입니다. 반대로 맡기면 1+2=3입니다. 더 작은 3을 반환합니다.

예제 3 · 두 사람의 가장 싼 작업이 겹칠 때
cost = [
  [1, 8],
  [2, 9]
]

반환값 10

1과 2는 둘 다 작업 0의 비용이어서 함께 고를 수 없습니다. 가능한 배정은 1+9=10 또는 8+2=10입니다. 최소 비용은 10입니다.

예제 4 · 모든 비용이 0일 때
cost = [
  [0, 0],
  [0, 0]
]

반환값 0

서로 다른 작업을 하나씩 맡기면 두 비용의 합이 0입니다.

예제 5 · 사람과 작업이 하나씩일 때
cost = [
  [7]
]

반환값 7

사람 0이 작업 0을 맡는 한 가지 배정만 가능합니다. 비용 7을 반환합니다.

풀이 힌트

사람 0부터 차례로 작업을 고르고, 고른 작업은 used에 표시합니다. 다음 사람의 탐색을 마치고 돌아오면 표시를 지워 다른 배정도 봅니다. 완성된 배정 중 가장 싼 비용을 best에 기억합니다. 현재 비용이 이미 best 이상이면 그 갈래를 멈출 수 있습니다. 남은 비용도 모두 0 이상이기 때문입니다.

C 함수의 입력
int assignment_min(const int cost[][8], int n)

cost는 비용 표이고 n은 실제 사람 수이자 작업 수입니다. cost[][8]의 앞 n행·n열을 사용합니다. 함수는 모든 사람의 작업을 고른 뒤 최소 총비용을 반환합니다.

이 문제 연습하기

8-4 모든 도시를 방문하는 최소 왕복 비용 · 추가 연습

이 문제는 기말고사 출제 범위에서 제외합니다. 원할 때 추가로 연습할 수 있습니다.

구할 값

0번 도시에서 출발해 모든 도시를 한 번씩 방문하고 0번으로 돌아오는 경로 중, 총비용이 가장 작은 경로의 비용을 구하세요.

도시는 0번부터 n−1번까지 있습니다. 다음에 방문할 도시의 순서도 직접 골라야 합니다. dist는 도시 사이의 이동 비용을 적은 표입니다.

tsp_min(dist)

입력

dist
n행 n열의 비용 표이며 n은 도시 수이고 1~9입니다. dist[i][j]는 i번 도시에서 j번 도시로 가는 비용입니다. 행은 출발 도시, 열은 도착 도시이고 번호는 0번부터 셉니다.

반환값

가능한 모든 방문 순서 중, 마지막에 0번 도시로 돌아오는 비용까지 더한 최솟값을 정수 하나로 반환합니다.

계산 규칙

  • 각 이동 비용은 0~100인 정수이고 대각선은 0입니다. 모든 도시 사이를 이동할 수 있습니다. 반대 방향의 비용은 다를 수 있습니다.
  • 출발점은 0번으로 고정합니다. 나머지 도시를 각각 한 번씩 방문하고 마지막에만 0번으로 돌아옵니다.
  • 방문 순서별 총비용을 비교해 가장 작은 비용을 반환합니다.
  • 도시가 하나이면 추가로 이동할 곳이 없으므로 0을 반환합니다.
예제 1 · PPTX 예제 · 두 방문 순서를 비교하기
dist = [
  [0, 2, 8],
  [1, 0, 3],
  [4, 6, 0]
]

반환값 9

0→1→2→0이면 2+3+4=9입니다. 0→2→1→0이면 8+6+1=15입니다. 세 도시의 방문 순서는 이 두 가지이므로 더 작은 9를 반환합니다.

예제 2 · 두 도시의 왕복
dist = [
  [0, 5],
  [8, 0]
]

반환값 13

가능한 왕복은 0→1→0입니다. 가는 비용 5와 돌아오는 비용 8을 더해 13을 반환합니다.

예제 3 · 모든 이동 비용이 0일 때
dist = [
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0]
]

반환값 0

어느 순서로 방문해도 모든 이동 비용이 0이므로 최소 총비용도 0입니다.

예제 4 · 도시가 하나일 때
dist = [
  [0]
]

반환값 0

출발점 0번에 그대로 있으므로 추가 이동 비용이 없습니다.

풀이 힌트

현재 도시, 지금까지 방문한 도시 수, 누적 비용을 기억합니다. 아직 방문하지 않은 다음 도시를 하나 골라 이동합니다. 모든 도시를 방문한 순간 마지막 도시에서 0번으로 돌아오는 비용을 더합니다. 이미 찾은 최소 비용보다 현재 비용이 크거나 같으면 그 갈래를 멈출 수 있습니다.

C 함수의 입력
int tsp_min(const int dist[][9], int n)

dist는 비용 표이고 n은 실제 도시 수입니다. dist[][9]의 앞 n행·n열을 사용합니다. 출발점은 0번이며, 모든 도시를 방문한 뒤 0번으로 돌아오는 최소 비용을 반환합니다.

이 문제 연습하기

9장 근사 알고리즘

먼저 최적해를 직접 찾아봅시다

프린터 두 대에 파일 다섯 개를 한 번씩 배정합니다. 숫자는 각 파일의 출력 시간입니다.
프린터 두 대에 파일 다섯 개를 한 번씩 배정합니다. 숫자는 각 파일의 출력 시간입니다.

같은 속도의 기계 두 대가 동시에 출발합니다. 8, 7, 6, 5, 4분짜리 작업을 한 번씩 나눠 맡겨 모든 일을 가장 빨리 끝내려면 어떻게 배정하면 될까요? 작업 하나를 쪼갤 수 없습니다. 각 기계는 맡은 일을 쉬지 않고 하나씩 처리합니다.

8,7,6,5,4분 작업을 두 기계에 직접 나누는 문제
직접 나눈 뒤 최적해 확인하기
위쪽은 8+7, 아래쪽은 6+5+4. 두 프린터가 15분에 함께 끝납니다.
위쪽은 8+7, 아래쪽은 6+5+4. 두 프린터가 15분에 함께 끝납니다.

8+7과 6+5+4로 나누면 양쪽 모두 15분입니다. 전체 작업량은 30분어치이므로 두 기계가 15분보다 빨리 끝낼 수 없습니다. 따라서 최적값은 15분입니다.

8+7과 6+5+4를 나눠 두 기계가 15분에 끝난다

왜 빠른 근사 방법도 배우나요?

작업마다 왼쪽·오른쪽을 모두 시도하면 40개에서는 단순 배정 후보가 2⁴⁰개입니다. 정확한 탐색이나 동적 계획법의 계산 비용이 커지는 입력에서는, 짧은 시간에 쓸 수 있는 배정이 필요합니다.

현재 덜 맡은 기계에 다음 작업을 보내는 규칙은 이 입력을 17분에 끝냅니다. 최적 15분보다 2분 늦지만 모든 작업을 처리하며, 작업 목록을 한 번 읽어 배정을 만듭니다.

최적 15분과 입력 순서로 만든 근사 배정 17분을 비교
빠른 규칙은 왼쪽 17분, 오른쪽 13분입니다. 모든 파일을 받으려면 17분까지 기다립니다.
빠른 규칙은 왼쪽 17분, 오른쪽 13분입니다. 모든 파일을 받으려면 17분까지 기다립니다.

근사 알고리즘은 조건을 지키는 답을 빠르게 만들고 최적값에 대한 품질 한도를 보장합니다. 이번 장에서는 원래 최적화 목표 → 직접 해 보기 → 빠른 규칙 → 최적과 비교 → 코드 순서로 공부합니다.

9장 PPTX · 151장 · 단계별 그림·발표 노트 포함 · PDF · 발표 대본 TXT

9-1 두 기계에 작업 나누기

각 작업은 한 번씩만 처리합니다. 작업 하나는 한 기계에 맡겨 끝까지 처리합니다. 예를 들어 8분짜리를 두 기계에 4분씩 나누는 배정은 허용하지 않습니다. 두 기계는 같은 속도이고, 처음부터 모든 작업이 준비되어 있습니다.

기계 한 대는 맡은 작업을 한 번에 하나씩 처리합니다. 그 기계에 8분과 6분을 맡기면 8분짜리를 끝낸 뒤 6분짜리를 처리해서 14분에 끝납니다. 다른 기계도 자신에게 맡겨진 일을 이어서 합니다. 작업이 전부 끝나는 시각은 두 기계 중 늦게 끝난 쪽의 시각입니다.

먼저 직접 배정하고 최적값을 확인합니다
14분과 16분이면 모두 끝나는 시각은 16분입니다
14분과 16분이면 모두 끝나는 시각은 16분입니다

왼쪽에 8분과 6분을 맡기고, 오른쪽에 7분과 5분과 4분을 맡겼습니다. 왼쪽은 14분, 오른쪽은 16분에 끝납니다. 두 기계를 동시에 시작했으므로 14분과 16분을 합해서 기다릴 필요는 없습니다.

14분에는 왼쪽 작업은 끝났지만 오른쪽에는 2분어치 일이 남아 있습니다. 16분이 되어야 모든 결과를 받을 수 있습니다. 그래서 이 배정의 전체 완료 시각은 두 합 중 큰 16분입니다. 이제 작업들을 다시 묶어 16보다 작게 만들 수 있는지 보겠습니다.

두 프린터가 함께 15분에 끝납니다
두 프린터가 함께 15분에 끝납니다

이번에는 8분과 7분을 왼쪽에 함께 맡겼습니다. 합하면 15분입니다. 나머지 6분, 5분, 4분을 오른쪽에 맡겨도 합이 15분입니다. 따라서 두 기계가 모두 15분에 끝납니다.

앞에서 만든 16분 배정보다 1분 빨라졌습니다. 모든 작업을 한 번씩 처리했고, 작업을 쪼개지도 않았습니다. 조건을 지키는 더 좋은 배정을 찾은 것입니다. 이 배정이 가장 좋은지 확인하려면 15분보다 일찍 끝내는 방법이 가능한지 따져야 합니다.

15분보다 빠르게 끝낼 수는 없습니다
15분보다 빠르게 끝낼 수는 없습니다

다섯 작업의 시간을 모두 더하면 30분입니다. 기계 한 대가 혼자 처리하면 30분 동안 해야 하는 양입니다. 두 기계가 14분씩 일하면 합해서 28분어치만 처리할 수 있습니다. 필요한 30분어치 중 2분어치가 남습니다.

일반적으로 두 기계가 t분 일하면 최대 2t분어치를 처리합니다. 30분어치를 끝내려면 2t가 30 이상이어야 해서 t는 적어도 15입니다. 앞에서 실제로 15분에 끝나는 배정도 찾았습니다. 따라서 이 예제의 최적값, 즉 가장 작은 완료 시각은 15분입니다.

빠른 규칙과 변수

작업을 배열 앞에서부터 하나씩 읽습니다. 이번 작업을 맡기기 직전에 두 기계가 얼마나 많은 시간을 맡았는지 비교합니다. 합이 작은 기계에 이번 작업을 추가합니다. 두 합이 같으면 왼쪽을 고르기로 정하겠습니다.

여기서 비교하는 숫자는 기계에 맡겨 놓은 총작업 시간입니다. 아직 실행 전인 배정 계획을 만들고 있습니다. 왼쪽에 8분어치를 맡겼다면 다음 작업을 그 뒤에 이어서 하도록 계획합니다. 각 작업에서 두 합만 비교하므로 빠르게 배정을 만들 수 있습니다.

이제 계산을 코드의 이름과 연결하겠습니다. jobs는 작업 시간 목록입니다. left는 왼쪽 기계에 맡긴 시간의 합이고, right는 오른쪽 기계에 맡긴 시간의 합입니다. 처음에는 아무 일도 맡기지 않았으므로 두 값 모두 0입니다.

duration에는 지금 읽는 작업 하나의 시간을 넣습니다. 첫 번째에는 8이고, 그다음에는 7, 6, 5, 4입니다. duration이 다음 값으로 바뀌어도 left와 right에 쌓아 둔 합은 계속 남습니다. 두 합에 이번 시간을 더하면서 배정 계획을 완성합니다.

Python 최종 답안
def two_machine_time(jobs):
    left = 0
    right = 0
    for duration in jobs:
        if left <= right:
            left += duration
        else:
            right += duration
    return max(left, right)
코드를 한 줄씩 읽고 다섯 작업을 배정합니다
첫 작업 8분을 배정합니다
첫 작업 8분을 배정합니다

이번에 duration으로 읽은 값은 8입니다. 배정 직전 left는 0, right는 0입니다. 두 합이 같아서 약속대로 왼쪽을 고릅니다. 5행의 left <= right는 참이므로 6행에서 left에 이번 시간을 더합니다.

기존 합 0에 8을 더해서 8으로 저장합니다. 다른 기계의 합은 그대로입니다. 그림에서 노란 막대가 방금 추가한 작업이고, 초록 막대는 앞에서 맡긴 작업입니다. 이 두 합을 유지한 채 다음 작업 시간을 읽습니다.

둘째 작업 7분을 배정합니다
둘째 작업 7분을 배정합니다

이번에 duration으로 읽은 값은 7입니다. 배정 직전 left는 8, right는 0입니다. 오른쪽 합이 더 작습니다. 5행의 left <= right는 거짓이므로 else 아래 8행에서 right에 이번 시간을 더합니다.

기존 합 0에 7을 더해서 7으로 저장합니다. 다른 기계의 합은 그대로입니다. 그림에서 노란 막대가 방금 추가한 작업이고, 초록 막대는 앞에서 맡긴 작업입니다. 이 두 합을 유지한 채 다음 작업 시간을 읽습니다.

셋째 작업 6분을 배정합니다
셋째 작업 6분을 배정합니다

이번에 duration으로 읽은 값은 6입니다. 배정 직전 left는 8, right는 7입니다. 오른쪽 합이 더 작습니다. 5행의 left <= right는 거짓이므로 else 아래 8행에서 right에 이번 시간을 더합니다.

기존 합 7에 6을 더해서 13으로 저장합니다. 다른 기계의 합은 그대로입니다. 그림에서 노란 막대가 방금 추가한 작업이고, 초록 막대는 앞에서 맡긴 작업입니다. 이 두 합을 유지한 채 다음 작업 시간을 읽습니다.

넷째 작업 5분을 배정합니다
넷째 작업 5분을 배정합니다

이번에 duration으로 읽은 값은 5입니다. 배정 직전 left는 8, right는 13입니다. 왼쪽 합이 더 작습니다. 5행의 left <= right는 참이므로 6행에서 left에 이번 시간을 더합니다.

기존 합 8에 5을 더해서 13으로 저장합니다. 다른 기계의 합은 그대로입니다. 그림에서 노란 막대가 방금 추가한 작업이고, 초록 막대는 앞에서 맡긴 작업입니다. 이 두 합을 유지한 채 다음 작업 시간을 읽습니다.

다섯째 작업 4분을 배정합니다
다섯째 작업 4분을 배정합니다

이번에 duration으로 읽은 값은 4입니다. 배정 직전 left는 13, right는 13입니다. 두 합이 같아서 약속대로 왼쪽을 고릅니다. 5행의 left <= right는 참이므로 6행에서 left에 이번 시간을 더합니다.

기존 합 13에 4을 더해서 17으로 저장합니다. 다른 기계의 합은 그대로입니다. 그림에서 노란 막대가 방금 추가한 작업이고, 초록 막대는 앞에서 맡긴 작업입니다. 다섯 작업을 모두 읽었습니다. 왼쪽은 17분어치, 오른쪽은 13분어치를 맡았습니다.

C 함수와 한 줄씩 설명
int two_machine_time(const int jobs[], int n) {
    int left = 0;
    int right = 0;
    for (int i = 0; i < n; ++i) {
        int duration = jobs[i];
        if (left <= right) {
            left += duration;
        } else {
            right += duration;
        }
    }
    if (left >= right) return left;
    return right;
}

함수 이름 앞의 int는 정수 하나를 반환한다는 표시입니다. const int jobs[]는 정수들이 들어 있는 입력 배열입니다. const는 함수 안에서 이 입력 배열의 값을 바꾸지 않겠다는 표시이고, 대괄호는 배열을 나타냅니다. n은 배열의 원소 개수입니다.

2행과 3행의 int left=0, int right=0은 누적 합을 저장할 정수 변수를 만들고 처음 값을 0으로 정합니다. 문장 끝에는 세미콜론을 붙입니다. 입력이 천 개이고 각 값이 최대 백만이므로 전체 합도 최대 10억입니다. 사이트의 32비트 int 범위 안에서 계산할 수 있습니다.

for 괄호 안의 첫 부분은 i를 0으로 만드는 초기화입니다. 둘째 부분 i < n은 아직 읽을 원소가 남았는지 확인합니다. 셋째 부분 ++i는 이번 반복을 마친 뒤 i를 1 늘립니다. n이 5이면 i는 0부터 4까지 쓰고, 5가 되면 반복을 끝냅니다.

5행은 jobs[i]에 있는 시간을 duration에 넣습니다. i가 0일 때 duration은 8, i가 1일 때는 7입니다. 위치 번호 0과 작업 시간 8은 서로 다른 역할입니다. 조건과 덧셈에서 사용할 값은 duration입니다.

6행은 left가 right보다 작거나 같은지 확인합니다. 참이면 첫 중괄호 안으로 들어가 left에 duration을 더합니다. 거짓이면 else 뒤의 중괄호 안으로 들어가 right에 더합니다. 중괄호는 함께 실행할 코드의 범위를 표시합니다.

첫 작업에서는 0과 0이 같아 왼쪽을 고릅니다. 둘째 작업에서는 8보다 0이 작아 오른쪽을 고릅니다. 마지막 작업 직전에는 두 합이 13으로 같아서 왼쪽에 4를 더합니다. 각 반복에서 한쪽 덧셈만 실행하므로 작업을 두 기계에 중복해서 맡기는 일이 없습니다.

11행은 for의 중괄호를 닫습니다. 아직 읽을 작업이 있으면 다음 위치로 반복하고, 전부 읽으면 12행으로 갑니다. left가 right 이상이면 left를 반환합니다. 반환한 순간 함수가 끝나므로 다음 return은 실행하지 않습니다.

예제에서는 17이 13 이상이라 17을 반환합니다. 왼쪽이 더 작은 예제에서는 12행의 조건이 거짓이어서 13행의 right를 반환합니다. 두 값이 같을 때는 같은 숫자 중 왼쪽 것을 반환합니다. Python의 max와 같은 역할입니다.

최적값을 몰라도 두 배 이내인 이유

하한이라는 말을 정하겠습니다. 어떤 배정을 쓰더라도 반드시 필요한 시간이라면 최적 시간도 그보다 작을 수 없습니다. 이렇게 최적 시간의 아래쪽 기준이 되는 숫자를 하한이라고 부릅니다.

예제의 총작업량은 30이므로 두 기계가 최소 15분은 일해야 합니다. 또 4분짜리 E는 어느 한 기계에서 4분을 온전히 써야 합니다. 따라서 4도 하한입니다. 지금 예제에서는 15가 더 강한 기준입니다. 앞으로는 총량으로 얻은 기준과 작업 하나로 얻은 기준을 나누어 사용하겠습니다.

가장 늦게 끝나는 작업으로 나누어 확인합니다
가장 늦게 끝나는 작업은 E입니다
가장 늦게 끝나는 작업은 E입니다

우리 배정에서 왼쪽은 8분짜리와 5분짜리를 마친 뒤 4분짜리 E를 처리합니다. E는 13분에 시작해서 17분에 끝납니다. 오른쪽은 13분에 모두 끝나므로 전체 완료 시각을 정하는 작업은 E입니다.

E가 끝나는 17분을 둘로 나누겠습니다. E 앞에 있는 작업에 쓰는 13분과 E 자체를 처리하는 4분입니다. 두 부분이 각각 최적 시간보다 길지 않다는 것을 보이면 두 부분을 합한 17분은 최적 시간 두 개를 더한 값 이내가 됩니다. 먼저 앞부분 13분을 살펴보겠습니다.

E를 맡기기 직전에는 두 합이 13입니다
E를 맡기기 직전에는 두 합이 13입니다

E를 맡기기 직전으로 돌아가겠습니다. 왼쪽에는 8과 5를 맡겨 13, 오른쪽에는 7과 6을 맡겨 13입니다. 두 합이 같아 E를 왼쪽에 맡기기로 했습니다. E는 앞의 13분어치 일을 끝낸 뒤 시작합니다.

두 숫자 중 작은 숫자는 두 숫자의 평균보다 클 수 없습니다. 이 예제에서는 작은 값도 13이고 평균도 13입니다. 서로 다른 숫자인 8과 13이라면 작은 값 8은 평균 10.5 이하입니다. 규칙이 매번 작은 합을 고르기 때문에 E 앞에 기다리는 시간에도 이 관계를 사용할 수 있습니다.

앞부분 13분은 최적 시간 이내입니다
앞부분 13분은 최적 시간 이내입니다

E를 맡기기 전에는 8, 7, 6, 5를 처리하도록 배정했으므로 총량은 26입니다. 두 기계의 평균은 26을 2로 나눈 13입니다. 우리가 고른 작은 합은 이 평균 이하입니다.

남은 E까지 포함하면 작업량은 30이 됩니다. 모든 작업 시간이 0 이상이므로 전체 총량은 앞서 읽은 총량보다 작아지지 않습니다. 따라서 앞서 계산한 평균 13은 전체 평균 15 이하입니다. 전체 평균 15는 최적 시간의 하한입니다. 작은 합에서 평균, 전체 평균, 최적 시간으로 차례로 비교하면 E 앞의 13분은 최적 시간 이하라는 결론이 나옵니다.

E 자체의 4분도 최적 시간 이내입니다
E 자체의 4분도 최적 시간 이내입니다

이제 뒷부분인 E 자체의 4분을 보겠습니다. 어떤 배정을 선택하더라도 E를 한 번은 끝까지 처리해야 합니다. 왼쪽에 맡겨도 오른쪽에 맡겨도 같은 4분이 필요합니다.

작업을 두 기계에 나누어 동시에 처리할 수 없고, 작업 시간이 0 아래에서 시작하지도 않습니다. 따라서 가장 좋은 배정도 적어도 E의 길이인 4분은 걸립니다. 앞부분 13분이 최적 시간 이하라는 결론에 이어, 뒷부분 4분도 최적 시간 이하라는 결론을 얻었습니다.

두 부분을 더하면 최적의 2배 이내입니다
두 부분을 더하면 최적의 2배 이내입니다

E가 시작되기 전 13분은 최적 시간 이하이고, E 자체의 4분도 최적 시간 이하입니다. 두 비교를 더하면 13 더하기 4는 최적 시간 더하기 최적 시간 이하입니다. 왼쪽 합 17분이 바로 우리 배정의 전체 완료 시각입니다.

따라서 결과가 최적의 두 배 이내입니다. 여기서는 최적값이 정확히 15라는 사실을 이용하지 않았습니다. 어떤 배정에도 필요한 총량 기준과 작업 하나의 길이만 이용했습니다. 그래서 최적 배정을 직접 찾기 어려운 입력에도 같은 논리를 적용할 수 있습니다.

입력의 맨 끝 작업이 가장 늦게 끝나지는 않을 수 있습니다
입력의 맨 끝 작업이 가장 늦게 끝나지는 않을 수 있습니다

다른 입력에서도 같은 증명을 하려면 어느 작업을 고를지 분명히 해야 합니다. [10,1,1]을 읽으면 10은 왼쪽, 두 1은 오른쪽에 들어갑니다. 왼쪽이 10분, 오른쪽이 2분에 끝납니다. 전체 완료 시각을 정하는 작업은 맨 처음 입력된 10분짜리입니다.

따라서 증명에서 말하는 마지막 작업은 입력 배열의 마지막 원소를 뜻하는 표현으로 사용하지 않겠습니다. 완료 시각이 가장 늦은 작업을 고릅니다. 여기서는 그 작업의 앞부분이 0이고 자기 길이는 10입니다. 앞부분과 자기 길이로 나누는 방법은 그대로 적용됩니다.

입력의 크기와 숫자가 달라도 완료 시각이 가장 늦은 작업 하나를 고를 수 있습니다. 그 작업을 맡길 때 규칙은 두 합 중 작은 값을 골랐습니다. 작은 값은 당시 평균 이하이고, 당시까지 읽은 작업량은 전체 작업량 이하입니다. 그래서 그 작업이 시작되기 전 시간은 전체 작업량을 2로 나눈 값 이하입니다. 이 값은 최적 시간 이하입니다.

그 작업 자체의 길이도 최적 시간 이하입니다. 최적 배정도 그 작업을 끝까지 해야 하기 때문입니다. 두 부분을 더하면 어떤 입력에서도 결과가 최적 시간의 두 배 이하입니다. 빈 입력에서는 양쪽 합이 0이고 최적값도 0이어서 같은 결론이 성립합니다.

[3,2,4]를 넣으면 처음 3은 왼쪽에, 다음 2는 오른쪽에 들어갑니다. 마지막 4를 맡길 때 오른쪽 합 2가 왼쪽 3보다 작아서 오른쪽에 더합니다. 최종 3과 6 중 큰 6을 반환합니다. [4,3,2]에서는 왼쪽 4, 오른쪽 3 더하기 2가 되어 5입니다. 같은 작업도 입력 순서에 따라 결과가 달라질 수 있습니다.

시간 0인 작업은 배정해도 합을 늘리지 않습니다. 빈 목록은 반복을 하지 않아 0을 반환합니다. 각 작업에서 비교와 덧셈만 하고 전체 목록을 한 번 읽으므로 시간복잡도는 O(n)입니다. 입력 외에 두 합과 현재 시간 등 일정한 개수의 변수만 사용하므로 추가 공간은 O(1)입니다.

입력 조건과 반환값 전체
같은 속도의 기계 두 대에 모든 작업을 한 번씩 나누어 맡긴다. 두 기계는 시간 0에 함께 시작하고, 각자 맡은 작업을 하나씩 연속해서 처리한다. 작업 하나는 한 기계에서 끝까지 처리한다.

이번 함수는 아래의 빠른 배정 규칙을 그대로 실행하고 전체 완료 시각을 반환한다.
1. 두 기계에 맡긴 시간의 합을 각각 0으로 시작한다.
2. jobs를 앞에서부터 읽는다. 순서를 바꾸지 않는다.
3. 맡긴 시간의 합이 작은 기계에 이번 작업을 추가한다. 같으면 왼쪽을 고른다.
4. 모든 작업을 배정한 뒤 두 합 중 큰 값을 반환한다.

입력
jobs는 작업 시간의 정수 목록이다. 길이는 0~1000이고 각 시간은 0~1,000,000이다.

반환값
위 규칙으로 배정했을 때 모든 작업이 끝나는 시각을 정수 하나로 반환한다. 작업이 없으면 0이다.

예제 1
jobs=[8,7,6,5,4]
배정 뒤 왼쪽은 8+5+4=17, 오른쪽은 7+6=13이다. 반환값은 17이다.
이 입력의 최적 배정은 [8,7]과 [6,5,4]로 나눈 15분이다. 이번 함수는 지정한 규칙을 실행한 결과 17을 반환한다.

예제 2
jobs=[3,2,4]
왼쪽은 3, 오른쪽은 2+4=6이어서 6을 반환한다.

예제 3
jobs=[4,3,2]
왼쪽은 4, 오른쪽은 3+2=5이어서 5를 반환한다.

예제 4
jobs=[]이면 0을 반환한다. 시간이 0인 작업은 배정해도 합을 늘리지 않는다.

근사 보장
결과가 최적 시간의 2배 이내임을 보장한다. 배정한 결과에서 완료 시각이 가장 늦은 작업 하나를 고른다. 그 작업이 시작되기 전의 시간은 당시 작은 합, 당시 평균, 전체 평균 순으로 비교하여 최적 시간 이하임을 알 수 있다. 작업 자체의 길이도 최적 시간 이하이다. 따라서 두 부분을 더한 전체 시간은 최적 시간의 2배 이하이다.

지정한 함수만 작성한다. 입력 준비와 출력은 실행 환경에서 담당한다.

9-1 코딩 연습하기

9-2 상자에 무게 채우기

두 번째 문제는 상자 하나에 물건을 골라 담는 문제입니다. 물건마다 무게가 있고 상자에는 견딜 수 있는 무게 제한이 있습니다. 담은 물건의 무게를 더해서 제한 이하가 되게 해야 합니다. 그 안에서 가능한 한 무겁게 담고 싶습니다.

각 물건은 통째로 넣거나 빼는 선택을 합니다. 한 물건을 두 번 담거나 일부만 잘라 담을 수 없습니다. 같은 무게의 물건이 목록에 두 번 나오면 실제로 두 개가 있는 것입니다. 값으로 비교할 것은 무게뿐입니다. 먼저 작은 예제의 가장 좋은 선택을 직접 찾아보겠습니다.

최적 선택과 빠른 선택의 차이
세 물건 중 무엇을 담을까요?
세 물건 중 무엇을 담을까요?

상자의 제한은 10kg입니다. A는 6kg이고 B와 C는 각각 5kg입니다. 물건 세 개 중 어느 것들을 담을지 골라 보겠습니다. A 하나를 담으면 6kg이고, A와 B를 함께 담으면 11kg여서 제한을 넘습니다. A와 C도 11kg입니다.

B와 C는 숫자가 같지만 서로 다른 물건입니다. 둘을 하나씩 담으면 5 더하기 5로 10kg입니다. 따라서 물건 하나만 비교해서 가장 큰 6을 고르는 것보다 두 5를 함께 고르는 쪽이 더 무겁습니다. 무게의 조합을 생각해야 하는 이유입니다.

가장 무거운 물건을 빼면 더 많이 담깁니다
가장 무거운 물건을 빼면 더 많이 담깁니다

왼쪽은 A 하나를 담은 선택이고 무게는 6kg입니다. 오른쪽은 B와 C를 담은 선택이고 무게는 10kg입니다. 두 상자는 같은 입력에서 가능한 선택을 각각 그린 것입니다. 실제로 사용할 선택 하나를 비교합니다.

제한이 10kg이므로 어떤 선택도 10보다 무거울 수 없습니다. 실제로 10을 만들었으니 이 예제의 최적값은 10kg입니다. 원래 목표는 이처럼 가능한 조합 중 가장 큰 무게 합을 찾는 것입니다. 이번에는 물건이 많아도 빠르게 실행할 수 있는 간단한 규칙을 만들겠습니다.

첫 후보 하나만 쓰면 결과가 작을 수 있습니다
첫 후보 하나만 쓰면 결과가 작을 수 있습니다

첫 후보만으로 충분한지 다른 입력에서 확인하겠습니다. 물건은 1kg과 10kg이고 상자 제한은 10kg입니다. 첫 1kg은 들어가므로 담습니다. 다음 10kg을 더하면 11kg여서 건너뜁니다. 결과는 1kg입니다.

하지만 10kg짜리 하나만 담으면 제한을 꽉 채웁니다. 첫 후보의 1은 최적 10의 절반에도 못 미칩니다. 처음 들어온 작은 물건 때문에 나중의 큰 물건을 놓칠 수 있습니다. 이 경우를 보완하기 위해 두 번째 후보를 따로 만들겠습니다.

한 물건만 담는 계획도 함께 비교합니다
한 물건만 담는 계획도 함께 비교합니다

두 번째 후보는 혼자 들어갈 수 있는 물건 중 가장 무거운 것 하나입니다. [1,10]에서는 10kg이 혼자 들어가므로 두 번째 후보는 10kg입니다. 첫 후보 1과 두 번째 후보 10을 비교해서 더 큰 10을 선택합니다.

그림 왼쪽과 오른쪽은 상자에 담는 서로 다른 계획입니다. 결과로 실제 사용할 것은 하나입니다. 무게 1과 10을 더해서 11을 만들지 않습니다. 이렇게 순서대로 담은 합과 가장 무거운 단일 물건을 함께 기억하면, 첫 후보가 작을 때 단일 물건 후보가 결과를 보완합니다.

입력과 두 후보

코드에서 사용할 두 변수의 뜻을 정하겠습니다. total은 처음부터 순서대로 담은 물건들의 무게 합입니다. single은 지금까지 확인한 물건 중 혼자 들어갈 수 있는 가장 무거운 물건의 무게입니다.

single에 어떤 물건을 기록했다고 해서 그 물건을 total의 상자에도 넣는 것은 아닙니다. 두 변수는 다른 계획을 기록합니다. [1,10]에서는 total이 1인 상태여도 single은 10으로 바뀝니다. 마지막에 두 계획 중 더 큰 무게를 선택합니다. 선택 과정은 코드에서 max(total, single)로 씁니다.

함수 이름은 approx_weight입니다. 첫 입력 weights에는 물건 무게를 순서대로 넣습니다. 둘째 입력 capacity는 상자가 버티는 무게 제한입니다. 각 무게와 제한은 양의 정수이고, 무게 목록은 비어 있을 수 있습니다.

물건 하나가 제한보다 무거우면 혼자도 담을 수 없으므로 두 후보에서 모두 제외합니다. 나머지 물건을 읽으며 total과 single을 만듭니다. 함수가 반환할 숫자는 두 후보 중 큰 무게입니다. [6,5,5]와 제한 10에서는 두 후보가 모두 6이라 6을 반환합니다. 최적 조합 5와 5는 나중에 결과의 품질을 비교할 때 사용합니다.

Python 최종 답안
def approx_weight(weights, capacity):
    total = 0
    single = 0
    for weight in weights:
        if weight > capacity:
            continue
        if weight > single:
            single = weight
        if total + weight <= capacity:
            total += weight
    return max(total, single)

1행에서 weights와 capacity를 받습니다. 2행과 3행에서 두 후보를 0으로 만듭니다. 아직 담은 물건도, 혼자 담을 후보도 확인하지 않았기 때문입니다. 이 초기화는 반복문 바깥에서 한 번만 합니다.

4행은 weights에서 무게를 하나씩 꺼내 weight에 넣습니다. 이름 끝에 s가 있는 weights는 전체 목록이고, weight는 현재 물건 하나의 무게입니다. 예제에서는 6, 첫 번째 5, 두 번째 5를 차례로 읽습니다. 같은 숫자 5도 실제로는 다른 두 물건입니다.

5행의 크다 기호는 무게가 제한을 넘는지 확인합니다. 예를 들어 12kg를 제한 10kg 상자에 넣을 수 없으므로 조건이 참입니다. continue를 만나면 이번 물건의 나머지 계산을 건너뛰고 for 문에서 다음 무게를 읽습니다. 함수 전체가 끝나는 동작은 아닙니다.

무게가 정확히 10이고 제한도 10이면 이 조건은 거짓입니다. 그대로 아래로 내려가 두 후보의 검사에 참여합니다. 혼자도 못 넣는 물건만 먼저 제외하기 때문에 single이나 total에 사용할 수 없는 무게가 섞이지 않습니다.

7행에서는 이번 무게 weight가 single보다 큰지 확인합니다. 앞의 검사에서 제한보다 무거운 물건을 제외했으므로, 여기 온 weight는 혼자 넣을 수 있는 무게입니다. 더 크면 8행에서 single을 그 값으로 바꿉니다.

처음 single이 0일 때 6을 읽으면 6으로 바뀝니다. 다음 5는 더 크지 않으므로 6을 유지합니다. 다른 입력 [1,10]에서는 single이 1에서 10으로 바뀝니다. 이 줄은 더 큰 물건 하나를 기억하는 동작이므로 이전 single에 무게를 더하지 않습니다.

9행은 이번 물건을 기존 total에 더한 값을 제한과 비교합니다. 더한 값이 제한 이하이면 10행에서 total에 weight를 더합니다. 정확히 제한과 같아도 허용하므로 작거나 같다 기호를 사용합니다.

total이 6일 때 5를 읽으면 11이 되어 담지 못합니다. 하지만 다음 물건이 4라면 10이 되어 담을 수 있습니다. 따라서 한 물건을 거절했다고 전체 반복을 멈추지 않습니다. total은 실제로 담기로 한 물건의 합이므로 이 검사 덕분에 항상 제한 이하로 유지됩니다.

마지막 줄은 두 후보 중 큰 무게 하나를 반환합니다. [6,5,5]에서는 6과 6을 비교해 6, [1,10]에서는 1과 10을 비교해 10입니다. [6,5,4]에서는 6을 담고 5를 넘긴 뒤 4를 추가해 total이 10이고 single은 6이라 10을 반환합니다.

이 줄은 for 밖에 있습니다. 모든 물건을 확인한 뒤 실행해야 나중에 나오는 큰 단일 물건이나 남은 공간에 들어갈 작은 물건도 반영할 수 있습니다. 반환하는 값은 실제 선택할 한 계획의 무게입니다.

실제 변수와 두 계획이 바뀌는 모습
첫 6kg를 읽으면 두 후보 모두 6입니다
첫 6kg를 읽으면 두 후보 모두 6입니다

입력 [6,5,5]와 제한 10에 실제 값을 넣겠습니다. 첫 weight는 6입니다. 6은 10보다 크지 않으므로 continue를 지나 아래로 갑니다. single은 0이었으므로 더 큰 6으로 바뀝니다.

total도 0이었습니다. 0에 6을 더하면 10 이하이므로 6을 담아 total이 6이 됩니다. 왼쪽 후보에는 첫 물건 하나를 담았고, 오른쪽 단일 후보도 같은 첫 물건입니다. 둘은 각각 대안이므로 같은 물건을 기억해도 괜찮습니다.

다음 5kg는 total에 추가하지 못합니다
다음 5kg는 total에 추가하지 못합니다

둘째 물건 weight는 5입니다. 혼자서는 들어가므로 두 후보의 검사를 받습니다. single에는 이미 6이 있으므로 더 작은 5로 바꾸지 않습니다.

total에 더하면 6 더하기 5가 11이 되어 제한 10을 넘습니다. 따라서 total에도 추가하지 않고 6을 유지합니다. 두 후보가 모두 6인 상태로 다음 물건을 읽습니다. 거절한 5는 상자 밖에 남습니다.

마지막 5kg도 못 담아 반환값은 6입니다
마지막 5kg도 못 담아 반환값은 6입니다

셋째 물건도 5입니다. 앞의 물건과 숫자는 같지만 목록에서 다른 물건을 읽는 것입니다. single과 비교하면 6보다 작고, total에 더하면 11이라 제한을 넘습니다. 따라서 두 변수는 계속 6입니다.

모든 물건을 읽었으므로 max(total,single)을 계산합니다. max(6,6)은 6이어서 최종 반환값은 6입니다. 손으로 찾은 최적 조합은 두 5를 담은 10이었습니다. 이번 규칙이 최적보다 덜 담는 예입니다.

[1,10]에서는 첫 후보와 단일 후보가 달라집니다
[1,10]에서는 첫 후보와 단일 후보가 달라집니다

이번에는 [1,10] 입력을 다시 보겠습니다. 첫 1을 읽은 뒤 total과 single은 둘 다 1입니다. 다음 weight가 10이면 혼자 제한에 맞게 들어갑니다. 10은 single의 1보다 크므로 single이 10으로 바뀝니다.

total에는 이미 1을 담았습니다. 여기에 10을 더하면 11이므로 추가하지 못하고 total은 1로 남습니다. 두 변수의 값이 달라지는 장면입니다. 마지막에 max(1,10)을 계산해 10을 반환합니다. 실제로는 10kg 물건 하나를 담는 계획을 택한 것입니다.

C 함수와 한 줄씩 설명
int approx_weight(const int weights[], int n, int capacity) {
    int total = 0;
    int single = 0;
    for (int i = 0; i < n; ++i) {
        int weight = weights[i];
        if (weight > capacity) continue;
        if (weight > single) single = weight;
        if (total + weight <= capacity) {
            total += weight;
        }
    }
    if (total >= single) return total;
    return single;
}

함수 이름 앞의 int는 정수 결과를 돌려준다는 뜻입니다. const int weights[]는 정수 무게 배열입니다. n으로 배열 길이를 따로 받고, capacity로 제한을 받습니다. const가 붙어 있으므로 입력 목록을 바꾸지 않고 읽습니다.

2행과 3행은 total과 single이라는 정수 변수를 0으로 만듭니다. total과 single은 각각 제한 이하로 유지됩니다. total에 혼자 들어가는 weight를 더해 보는 중간 값도 최대 백만 더하기 백만으로 200만입니다. 사이트의 32비트 int 범위에서 처리할 수 있습니다.

for 문은 i를 0으로 만들어 첫 물건에서 시작합니다. i가 n보다 작은 동안 반복하고, 반복 하나를 마칠 때마다 ++i로 위치를 하나 늘립니다. 물건 세 개이면 0번, 1번, 2번 위치를 읽고 i가 3일 때 끝납니다.

5행의 int weight = weights[i]는 지금 위치에 있는 무게를 정수 변수 weight에 저장합니다. 첫 위치에서는 6, 둘째에서는 5, 셋째에서도 5입니다. 위치 번호와 무게는 서로 다른 값이므로 이후 무게 조건에서는 weight를 사용합니다.

6행은 조건 뒤에 continue 한 문장이 붙은 if입니다. 이번 물건이 제한보다 크면 continue를 실행하고 다음 반복으로 갑니다. 7행 이하의 single과 total 계산은 하지 않습니다. 제한 이하이면 다음 줄로 진행합니다.

7행도 한 문장을 붙인 if입니다. 이번 무게가 기존 single보다 크면 single = weight를 실행합니다. 이 두 조건은 서로 다른 질문을 합니다. 첫째는 혼자 들어가는지, 둘째는 지금까지 본 단일 후보보다 무거운지를 확인합니다.

8행은 total 더하기 weight가 제한 이하인지 검사합니다. 참이면 중괄호 안의 9행에서 total에 weight를 더합니다. 6에 5는 넘으므로 그대로 두고, 6에 4는 제한 10과 같으므로 10으로 바꿉니다.

이 조건이 거짓이어도 반복문은 끝나지 않습니다. 다음 위치를 읽어서 새 물건으로 같은 검사를 합니다. single에 저장한 후보 역시 그대로 남습니다. 따라서 [1,10]의 10을 total에 담지 못하더라도 single=10은 마지막 비교에 사용할 수 있습니다.

11행에서 반복 범위를 닫고, 12행에서 total이 single보다 크거나 같은지 확인합니다. 참이면 total을 반환하고 함수가 끝납니다. 거짓이면 다음 줄로 내려가 single을 반환합니다.

이 두 줄이 Python의 max와 같은 역할입니다. 6과 6이면 6, 1과 10이면 10을 반환합니다. 어느 물건도 담을 수 없으면 두 변수는 0으로 남아 0을 반환합니다. 모든 물건을 확인한 뒤 하나의 결과를 돌려준다는 위치도 Python과 같습니다.

최적 무게의 절반 이상인 이유

첫 문제에서는 작게 끝낼수록 좋아서 결과가 최적의 두 배보다 커지지 않는다고 말했습니다. 이번에는 많이 담을수록 좋습니다. 따라서 결과가 최적 무게의 절반보다 작아지지 않는다는 관계를 보이겠습니다.

상자의 제한이 10이면 최적 무게도 10 이하입니다. 우리 결과가 5 이상이면 최적이 10이든 9든 그 절반 이상을 담은 것입니다. 하지만 최적이 4처럼 제한보다 훨씬 작을 수도 있으므로, 언제나 제한의 절반을 담아야 한다고 가정하지 않습니다. 가능한 물건이 적은 경우까지 나누어 확인하겠습니다.

거절 당시 합부터 전체 경우를 확인합니다
total이 상자 절반 이상이면 이미 충분합니다
total이 상자 절반 이상이면 이미 충분합니다

첫 경우입니다. 마지막 total이 상자 제한의 절반 이상이면 어떻게 될까요? [6,5,5]와 제한 10에서는 total이 6입니다. 6은 제한의 절반인 5 이상입니다.

어떤 최적 선택도 상자의 제한 10을 넘지 못합니다. 그래서 최적 무게의 절반 역시 5 이하입니다. 마지막 결과는 total과 single 중 큰 값이라 total보다 작아지지 않습니다. 결과가 total 이상이고 total이 이미 최적의 절반 이상이므로 이 경우는 충분합니다.

total이 작아도 무거운 single이 보완합니다
total이 작아도 무거운 single이 보완합니다

total이 제한의 절반보다 작은 경우를 보겠습니다. [3,8]과 제한 10에서 3은 담지만 8을 더하면 11이 되어 거절합니다. total은 3이고 single은 8입니다. 마지막에는 8을 택합니다.

첫 후보 3은 절반인 5보다 작지만, 추가하지 못했던 물건 8이 혼자 들어가므로 단일 후보가 결과를 보완했습니다. 이것이 어떤 입력에서도 성립하는지 보려면 물건을 거절한 당시 total과, 모든 물건을 읽은 뒤의 total 사이 관계를 확인해야 합니다.

3kg에 못 더한 8kg를 혼자 담습니다
3kg에 못 더한 8kg를 혼자 담습니다

왼쪽 상자는 3kg를 먼저 담은 계획입니다. 옆의 8kg를 추가하면 11kg라서 제한을 넘습니다. 오른쪽은 8kg 물건 하나만 담는 다른 계획입니다. 상자 제한은 둘 다 10kg입니다.

오른쪽 8kg는 제한의 절반 5kg보다 무겁습니다. 그리고 혼자서는 제한 이하로 들어갑니다. 함수는 왼쪽 total 3과 오른쪽 single 8 중 큰 8을 반환합니다. 이제 예제의 숫자를 일반적인 조건으로 바꾸어 보겠습니다.

거절한 당시 합은 최종 합보다 클 수 없습니다
거절한 당시 합은 최종 합보다 클 수 없습니다

입력 [3,8,1]과 제한 10을 보겠습니다. 처음 3을 담고, 8은 11이 되어 거절합니다. 그 뒤 1은 들어가므로 최종 total은 4입니다. 거절한 순간의 합 3과 마지막 합 4는 서로 다를 수 있습니다.

하지만 total은 물건을 담을 때 더하기만 합니다. 빼는 동작이 없고 모든 무게가 양수이므로 과거의 합은 마지막 합보다 클 수 없습니다. 따라서 마지막 합이 제한의 절반 미만이라면, 어떤 물건을 거절한 당시의 합도 절반 미만입니다. 이 관계 덕분에 거절한 순간을 이용해 일반적인 보장을 설명할 수 있습니다.

작은 합에 절반 이하 물건은 반드시 들어갑니다
작은 합에 절반 이하 물건은 반드시 들어갑니다

제한 10에서 현재 합이 3이라고 하겠습니다. 제한의 절반은 5입니다. 지금 합은 절반보다 작습니다. 여기에 절반 이하인 5kg 물건을 더하면 8kg라서 들어갑니다. 5보다 가벼운 물건도 당연히 들어갑니다.

일반적으로 절반보다 작은 수와 절반 이하인 수를 더하면 전체 제한보다 작습니다. 따라서 최종 total이 절반 미만으로 끝난 실행에서, 혼자 들어가는 물건을 추가하지 못했다면 그 물건의 무게는 절반보다 커야 합니다. 절반 이하 물건이라면 방금 계산대로 담을 수 있었기 때문입니다.

못 담은 물건이 절반보다 크면 single에 남습니다
못 담은 물건이 절반보다 크면 single에 남습니다

지금까지의 관계를 연결하겠습니다. 최종 total이 절반보다 작고, 혼자 들어가지만 추가하지 못한 물건이 있었다면 그 물건은 제한의 절반보다 큽니다. 이 물건은 혼자 들어가므로 single을 갱신하는 검사에 참여했습니다.

single에는 지금까지 본 가장 무거운 단일 물건이 남습니다. 따라서 마지막 single은 이 물건의 무게 이상입니다. 결과는 total과 single 중 큰 값이어서 single 이상입니다. 결국 결과는 제한의 절반보다 크고, 최적 무게의 절반 이상이 됩니다. single을 먼저 갱신하고 total을 따로 검사한 코드의 순서가 여기서 역할을 합니다.

거절이 없었다면 가능한 물건을 모두 담았습니다
거절이 없었다면 가능한 물건을 모두 담았습니다

마지막 경우입니다. total은 절반보다 작지만, 혼자 들어가는 물건을 한 번도 거절하지 않았다면 어떨까요? [1,2,15]와 제한 10에서는 1과 2를 모두 담습니다. 15는 혼자도 들어가지 않으므로 처음부터 제외합니다. total은 3입니다.

다른 선택도 15를 사용할 수 없고, 남은 1과 2는 이미 전부 담았습니다. 따라서 최적값도 3입니다. 제한의 절반 5까지 채우지 못했어도 가능한 물건을 모두 담았으니 최적입니다. 물건이 하나도 없거나 모두 제한보다 무거운 경우도 같은 논리로 최적값과 결과가 모두 0입니다.

세 경우를 확인하면 절반 이상이 보장됩니다
세 경우를 확인하면 절반 이상이 보장됩니다

total이 상자 절반 이상이면 그 자체로 최적의 절반 이상입니다. 절반 미만이면 혼자 들어가지만 추가하지 못한 물건이 있는지 봅니다. 있다면 그 물건은 절반보다 무겁고 single이 기억합니다. 없다면 가능한 물건을 모두 담았으므로 total이 최적입니다.

이 세 경우가 모든 실행을 포함합니다. 따라서 최적 조합을 미리 계산하지 않고도 우리 결과가 최적 무게의 절반 이상이라고 말할 수 있습니다. 이미 확인했듯 두 후보는 각각 실제로 담을 수 있으므로, 제한을 지키면서 이 무게를 얻습니다.

입력 [6,5,5]와 제한 10의 답은 6, [1,10]의 답은 10입니다. [6,5,4]는 5를 거절해도 뒤의 4를 계속 확인해서 총 10을 담습니다. [12,15]는 둘 다 혼자도 들어가지 못해 0이고, 빈 목록도 두 후보가 0으로 남습니다.

각 물건에서 하는 일은 조건 세 개와 값 갱신입니다. 물건 수 n에 비례해서 계산하므로 시간복잡도는 O(n)입니다. 입력 외에는 total, single, 현재 weight 같은 일정한 개수의 변수만 써서 추가 공간은 O(1)입니다. 반환한 무게는 실제로 담을 수 있고 최적의 절반 이상이라는 것까지 확인했습니다.

입력 조건과 반환값 전체
무게 제한 capacity인 상자에 물건을 골라 담는다. 각 물건은 한 번만 통째로 담을 수 있다. 같은 무게가 여러 번 나오면 서로 다른 물건이다. 원래 목표는 제한 이하에서 무게 합을 최대화하는 것이다.

이번 함수는 다음 두 후보를 만드는 빠른 규칙을 그대로 구현한다.
1. total=0, single=0에서 시작한다. weights를 앞에서부터 읽는다.
2. 이번 무게가 capacity보다 크면 혼자도 못 들어가므로 다음 물건을 읽는다.
3. 혼자 들어가는 무게라면 지금까지의 single보다 클 때 single을 이번 무게로 바꾼다.
4. total에 이번 무게를 더해도 capacity 이하이면 total에 더한다. 넘으면 total을 유지하고 다음 물건을 읽는다.
5. 모든 물건을 읽고 total과 single 중 큰 값을 반환한다.

total은 순서대로 담은 물건들의 합이고, single은 혼자 담는 가장 무거운 물건이다. 서로 다른 계획이므로 두 후보를 더하지 않는다. 앞에서 담은 물건은 꺼내지 않고 입력을 정렬하지 않는다.

입력
weights는 무게 목록이다. 길이는 0~1000이고 각 무게는 1~1,000,000인 정수이다.
capacity는 1~1,000,000인 정수이다.

반환값
지정 규칙으로 만든 두 후보 중 큰 무게를 정수 하나로 반환한다. 담을 수 있는 물건이 없으면 0이다.

예제 1
weights=[6,5,5], capacity=10
total은 6이고 single도 6이어서 6을 반환한다. 직접 찾은 최적 선택은 두 5를 담은 10이지만 이 함수는 규칙의 결과를 반환한다.

예제 2
weights=[1,10], capacity=10
total은 1, single은 10이므로 10을 반환한다.

예제 3
weights=[6,5,4], capacity=10
6을 담고 5를 넘긴 뒤 4를 담아 total=10이다. single=6과 비교해 10을 반환한다.

예제 4
weights=[15,4,7,3,8,2], capacity=12
15를 제외하고 total=4+7=11, single=8이므로 11을 반환한다.

예외
weights=[]이면 0이다. weights=[12,15], capacity=10도 0이다. 물건 하나를 담지 못해도 뒤의 물건을 계속 확인한다.

근사 보장
결과는 최적 무게의 절반 이상이다. total이 제한의 절반 이상이면 이미 충분하다. total이 작고 혼자 들어가는 물건을 거절했다면, 거절 당시 합도 최종 합 이하라 절반 미만이었으므로 그 물건은 절반보다 크다. 그 무게가 single에 반영된다. 그런 거절이 없었다면 가능한 물건을 전부 담아 total 자체가 최적이다.

지정한 함수만 작성한다. 입력 준비와 출력은 실행 환경에서 담당한다.

9-2 코딩 연습하기

9-3 선마다 한 끝점을 고르기 · 정점 커버

동그라미로 표시한 점을 골라, 모든 선의 양 끝 중 적어도 한 점을 고른 상태로 만듭니다. 가능한 선택 중 점의 개수를 줄이는 문제입니다. 이 조건을 만족한 점들의 모음을 정점 커버라고 부릅니다.

먼저 점 0·1·2·3과 선 0–1, 1–2, 2–3을 사용합니다. 점을 고르면 그 동그라미만 색칠합니다. 서로 떨어진 점도 고를 수 있습니다.

1번 하나로 0–1과 1–2를 해결하지만 2–3은 남습니다.
1번 하나로 0–1과 1–2를 해결하지만 2–3은 남습니다.
2번을 더 고르면 세 선이 모두 해결됩니다.
2번을 더 고르면 세 선이 모두 해결됩니다.
점을 눌러서 직접 확인하세요.

초록 점은 고른 점입니다. 초록 선은 한 끝 이상을 골랐고, 빨간 선은 양 끝 모두 안 골랐습니다.

0번과 3번만 고르면 가운데 1–2가 남습니다. 0번과 2번, 또는 1번과 3번을 고르면 이 세 선은 모두 해결됩니다. 각 선에 직접 붙은 점의 색으로 확인합니다.

선 두 개를 더한 그래프로 계속 설명합니다

이제 0–2와 1–3도 포함한 다섯 선을 모두 해결해야 합니다.
이제 0–2와 1–3도 포함한 다섯 선을 모두 해결해야 합니다.
1번과 3번을 골라도 0–2가 남습니다.
1번과 3번을 골라도 0–2가 남습니다.
0번과 2번을 골라도 1–3이 남습니다.
0번과 2번을 골라도 1–3이 남습니다.
1번과 2번이면 다섯 선을 모두 해결합니다.
1번과 2번이면 다섯 선을 모두 해결합니다.
선 다섯 개에서 고르는 점을 바꿔 보세요.

노란색으로 표시한 0–1과 2–3 두 선에 집중하겠습니다. 0–1을 해결하려면 0번이나 1번이 필요합니다. 2–3을 해결하려면 2번이나 3번이 필요합니다. 첫 선에서 쓸 수 있는 점과 둘째 선에서 쓸 수 있는 점이 전부 다릅니다. 하나의 점으로 이 두 선을 함께 해결할 수 없어서 적어도 두 점이 필요합니다.

앞 장에서 1번과 2번 두 점으로 다섯 선 전체를 해결했습니다. 적어도 두 점이 필요하고, 실제로 두 점이면 됩니다. 그래서 이 작은 그래프의 최적값은 2입니다. 이후에는 같은 그래프에 빠른 선택 규칙을 적용하겠습니다.

큰 입력을 빠르게 처리하는 선택 규칙

점 네 개인 그림은 가능한 조합을 손으로 살펴보기 쉽습니다. 점마다 고르거나 빼는 두 선택이 있으므로 네 개이면 전체 조합이 16개입니다. 점이 30개이면 약 10억 개가 됩니다. 점이 많은 입력에서 모든 조합을 직접 확인하는 방식은 시간이 많이 듭니다.

이번에는 선 목록을 한 번 읽으면서 점을 정하는 빠른 방법을 사용하겠습니다. 이 방법이 고른 점의 수는 최적값보다 커질 수 있습니다. 대신 어떤 입력에서도 최적 개수의 두 배를 넘지 않는다는 한도를 확인하겠습니다. 방금 최적값이 2라고 확인한 작은 그림에서는 실제로 어떤 결과가 나오는지 바로 비교할 수 있습니다.

선택 규칙을 정하겠습니다. 처음에는 아무 점도 고르지 않습니다. 입력된 선을 앞에서부터 하나씩 읽고, 이번 선의 양 끝을 확인합니다. 두 끝을 모두 아직 안 골랐다면 두 점을 함께 고릅니다. 새 점을 두 개 골랐으니 개수에도 2를 더합니다.

어느 한쪽 끝이라도 이미 골랐다면 그 선은 조건을 만족합니다. 이때는 점을 더하지 않고 다음 선을 읽습니다. 한 번 고른 점은 이후에도 계속 고른 상태로 둡니다. 이 규칙이 전체에서 가장 적은 점을 고르지는 못할 수 있습니다. 양 끝을 함께 고르는 선택 덕분에 얻는 두 배 한도는 코드 실행을 확인한 다음 설명하겠습니다.

한 선에 한 점이면 충분한데, 왜 두 점을 함께 고를까요?
가운데 0번에 다섯 선이 붙어 있습니다. 바깥 점만 계속 고르면 다섯 점을 씁니다.
가운데 0번에 다섯 선이 붙어 있습니다. 바깥 점만 계속 고르면 다섯 점을 씁니다.

양쪽을 함께 고르는 이유를 보기 위해 잠깐 다른 그림을 사용하겠습니다. 가운데 0번에서 바깥의 다섯 점으로 선이 뻗어 있습니다. 모든 선에 공통으로 붙은 0번만 고르면 전체를 해결하므로 최적값은 1입니다.

선을 하나씩 보면서 매번 바깥 점만 고른다고 해 보겠습니다. 첫 선에서는 1번, 다음 선에서는 2번을 고르는 식입니다. 결국 바깥 점 다섯 개를 모두 골라야 합니다. 한 선에서는 한쪽만으로 충분해도, 어느 쪽을 고르는지 계속 빗나가면 전체 개수가 커집니다.

첫 선에서 가운데와 바깥 점을 함께 고르면 두 점으로 끝납니다.
첫 선에서 가운데와 바깥 점을 함께 고르면 두 점으로 끝납니다.

같은 그림에 이번 규칙을 적용하겠습니다. 첫 선 0–1의 양 끝이 모두 비어 있으므로 0번과 1번을 함께 고릅니다. 두 점을 골랐습니다.

다음 선들도 모두 가운데 0번에 붙어 있습니다. 0번을 이미 골랐으므로 점을 더할 필요가 없습니다. 따라서 두 점으로 끝납니다. 최적은 0번 하나이고, 이번 규칙은 0번과 1번 두 개를 씁니다. 이제 선 다섯 개였던 원래 예제로 돌아가, 이 규칙을 함수로 작성하겠습니다.

입력과 상태를 읽은 뒤 Python 코드를 따라갑니다

n = 4
edges = [[0,1], [1,2], [2,3], [0,2], [1,3]]

이제 원래 예제의 다섯 선을 함수에 넣겠습니다. 함수 이름은 cover_size입니다. 괄호 안의 n에는 전체 점 수 4를 넣습니다. edges에는 선 다섯 개를 적은 목록을 넣습니다. 대괄호 안의 0과 1 한 쌍은 0번과 1번 사이에 선이 있다는 뜻입니다. 선의 양쪽은 서로 다른 점이고, 점 번호는 0부터 n보다 하나 작은 번호까지입니다. 선에는 방향이 없어서 한 선 안의 두 번호가 바뀌어도 같은 연결입니다.

선 목록의 순서는 0–1, 1–2, 2–3, 0–2, 1–3 그대로 지킵니다. 함수가 돌려줄 값은 이 순서에 선택 규칙을 적용해서 실제 고른 점의 개수입니다. 손으로 알아낸 최적값 2는 나중에 결과의 품질을 비교할 때 사용합니다. 문제의 입력 범위는 점 1개부터 100개, 선 0개부터 1000개입니다.

점마다 고른 상태를 기억해야 하므로 chosen이라는 목록을 만듭니다. chosen의 0번 칸은 0번 점, 1번 칸은 1번 점의 상태를 담습니다. 대괄호 안의 숫자가 어느 칸을 읽을지 알려 줍니다. 예를 들어 chosen[1]은 1번 점의 상태입니다.

False는 안 골랐다는 표시이고 True는 골랐다는 표시입니다. 처음에는 네 칸 모두 False입니다. 0번과 1번을 고르면 앞의 두 칸이 True로 바뀌고 나머지는 False로 남습니다. answer라는 변수에는 지금까지 고른 점의 개수를 담습니다. 처음에는 0이고, 두 점을 고른 뒤에는 2입니다.

u와 v는 지금 확인할 선의 두 점 번호를 담는 변수입니다. 첫 번째 쌍 [0,1]을 읽으면 u는 0, v는 1입니다. 그러면 chosen[u]는 0번 점의 상태이고 chosen[v]는 1번 점의 상태입니다.

다음 [1,2]를 읽을 때는 u가 1, v가 2로 바뀝니다. 셋째 선은 2와 3, 넷째 선은 0과 2, 마지막 선은 1과 3입니다. 이처럼 확인할 선은 계속 바뀝니다. 앞에서 고른 상태를 적은 chosen과 개수를 적은 answer는 선이 바뀌어도 이어서 사용합니다.

조건을 읽기 전에 not과 and를 보겠습니다. chosen[u]가 True이면 u번을 골랐다는 뜻입니다. 여기에 not을 붙이면 값이 뒤집힙니다. 따라서 not chosen[u]는 u번을 안 골랐을 때 True가 됩니다. not chosen[v]도 v번을 안 골랐을 때 True입니다.

and는 양쪽이 모두 True일 때만 True입니다. 두 표현을 and로 연결하면 u번도 아직 안 골랐고 v번도 아직 안 골랐는지를 확인합니다. 이 조건이 True일 때만 두 점을 함께 고릅니다. 어느 한 점이라도 이미 골랐다면 전체 조건은 False가 되어 추가 선택을 하지 않습니다.

Python 최종 답안
def cover_size(n, edges):
    chosen = [False] * n
    answer = 0
    for u, v in edges:
        if not chosen[u] and not chosen[v]:
            chosen[u] = True
            chosen[v] = True
            answer += 2
    return answer
다섯 선을 읽는 코드 실행
첫 선 0–1은 양쪽 모두 False입니다
첫 선 0–1은 양쪽 모두 False입니다

첫 선은 0–1입니다. u는 0이고 v는 1입니다. 그림에서 두 점은 모두 비어 있고 chosen의 두 칸도 False입니다. 각각에 not을 붙이면 True가 됩니다. True and True이므로 전체 조건은 True입니다.

조건 바로 아래로 들어가서 두 점을 골랐다고 기록할 차례입니다. 아직 이 화면은 선택하기 전입니다. 고른 점은 없고 answer도 0입니다. 다음 화면에서 여섯째, 일곱째, 여덟째 줄이 값을 어떻게 바꾸는지 보겠습니다.

0번과 1번을 고르면 기록이 계속 남습니다
0번과 1번을 고르면 기록이 계속 남습니다

chosen[u] = True에서 지금 u는 0이므로 0번 칸을 True로 바꿉니다. 다음 chosen[v] = True에서는 1번 칸을 True로 바꿉니다. 그림의 0번과 1번에 색을 칠한 상태입니다. answer += 2는 기존 값에 2를 더해 다시 저장하라는 문장입니다. 0이던 answer가 2가 됩니다.

이제 기록은 [True,True,False,False]입니다. 이후에 False로 되돌리는 문장은 없으므로 0번과 1번의 선택은 계속 남습니다. 두 점을 추가했던 0–1 선에는 굵은 밑선을 표시했습니다. 어떤 선에서 개수에 2를 더했는지 마지막에 모아서 확인하겠습니다.

다음 1–2는 이미 고른 1번을 공유합니다
다음 1–2는 이미 고른 1번을 공유합니다

둘째 선은 1–2입니다. 이번 u는 1, v는 2입니다. 1번은 앞에서 골라서 True이고 2번은 아직 False입니다. 조건에 넣으면 not True and not False, 즉 False and True가 됩니다. 전체 조건은 False입니다.

따라서 아래의 세 줄을 건너뛰고 다음 선으로 갑니다. 2번을 추가하지 않고 answer도 2로 유지합니다. 이 선은 앞서 고른 1번에 붙어 있어 이미 해결되었습니다. 0–1과 1–2는 1번을 공유하지만, 두 점을 새로 추가한 선은 현재 0–1 하나뿐입니다.

다음 2–3은 두 점 모두 아직 비어 있습니다
다음 2–3은 두 점 모두 아직 비어 있습니다

셋째 선은 2–3입니다. 2번과 3번은 아직 고르지 않아서 두 기록이 모두 False입니다. 조건은 True and True가 되므로 이번에는 아래 세 줄을 실행합니다.

지금까지 고른 점은 0번과 1번입니다. 이번에 고를 2번과 3번은 그 둘과 전혀 다른 점입니다. 만약 어느 한 점이라도 앞에서 골랐다면 그 칸이 True여서 방금 1–2처럼 조건이 False가 되었을 것입니다. 지금은 두 점 모두 비어 있으므로 추가할 수 있습니다.

2번과 3번을 추가하면 answer는 4입니다
2번과 3번을 추가하면 answer는 4입니다

2번 칸과 3번 칸을 True로 바꾸고 answer에 2를 더합니다. 앞에서 2였으므로 이제 4입니다. 네 칸이 전부 True이고, 그림의 네 동그라미에도 모두 색이 들어갔습니다.

지금까지 두 점씩 추가한 선은 첫 선 0–1과 셋째 선 2–3입니다. 두 선의 끝점은 각각 0번, 1번과 2번, 3번으로 겹치지 않습니다. 이 성질은 모든 입력에서 같은 방식으로 유지됩니다. 남은 두 선도 읽은 뒤 그 이유를 정리하겠습니다.

0–2는 이미 고른 점이 양쪽에 있습니다
0–2는 이미 고른 점이 양쪽에 있습니다

넷째 선은 0–2입니다. 0번은 첫 선에서, 2번은 셋째 선에서 이미 골랐습니다. 두 기록 모두 True이므로 not을 붙이면 각각 False입니다. 조건은 False and False가 되어 아래의 추가 선택을 건너뜁니다.

answer는 4로 남습니다. 원래 그래프에는 0–1과 0–2처럼 끝점을 공유하는 선들이 있습니다. 코드가 두 점을 새로 추가한 선들만 모았을 때에는 0–2가 포함되지 않습니다. 이미 고른 끝점이 있어서 조건을 통과하지 못하기 때문입니다.

마지막 1–3도 추가 없이 넘어갑니다
마지막 1–3도 추가 없이 넘어갑니다

다섯째 선은 1–3입니다. 1번은 첫 선에서 골랐고 3번은 셋째 선에서 골랐습니다. 두 칸이 모두 True이므로 이번 조건도 False입니다. 아무 점도 더하지 않고 answer를 4로 유지합니다.

이제 선 다섯 개를 전부 읽었습니다. 선택한 점은 0번, 1번, 2번, 3번입니다. 개수에 2를 더한 순간은 0–1을 읽었을 때와 2–3을 읽었을 때, 두 번이었습니다. 다음에는 이 최종 개수를 함수 밖으로 돌려줍니다.

입력에 더 읽을 선이 없으면 for 반복이 끝납니다. 마지막 return answer가 지금 answer에 들어 있는 4를 함수를 호출한 쪽으로 돌려줍니다.

return의 들여쓰기는 for와 같습니다. 따라서 선을 하나 읽을 때마다 실행되는 범위 밖에 있습니다. return을 for 안으로 들여쓰면 첫 선만 읽고 함수가 끝나므로 주의해야 합니다. 이번 실행은 선 다섯 개를 다 읽었고, 두 번에 걸쳐 두 점씩 골라 최종 4를 반환합니다.

C 함수와 최종 답안
int cover_size(int n, const int edges[][2], int m) {
    int chosen[100] = {0};
    int answer = 0;
    for (int i = 0; i < m; ++i) {
        int u = edges[i][0];
        int v = edges[i][1];
        if (!chosen[u] && !chosen[v]) {
            chosen[u] = 1;
            chosen[v] = 1;
            answer += 2;
        }
    }
    return answer;
}

함수 이름 앞의 int는 이 함수가 정수를 반환한다는 표시입니다. 입력 edges는 정수로 된 표이고 한 행마다 두 점 번호가 있습니다. 뒤의 [2]가 각 행의 칸 수를 나타냅니다. const는 함수 안에서 이 입력 표를 바꾸지 않겠다는 표시입니다.

문제에서 점은 최대 100개이므로 chosen에 정수 100칸을 준비했습니다. {0}으로 초기화하면 첫 칸과 나머지 칸이 모두 0이 됩니다. 예제에는 점이 네 개여서 0번부터 3번 칸을 사용합니다. 모든 칸을 한꺼번에 0으로 만들었으므로 여기서 n번 반복해서 초기화할 필요가 없습니다. answer도 0으로 시작합니다.

for 괄호 안에는 세 부분이 있습니다. int i = 0으로 첫 행부터 시작합니다. i < m은 아직 읽을 행이 남았는지 확인합니다. m이 5이므로 i가 0, 1, 2, 3, 4일 때 반복합니다. 한 번의 처리를 끝낸 뒤 ++i로 i를 1 늘립니다. i가 5가 되면 반복을 끝냅니다.

edges[i][0]은 i번째 행의 첫 칸이고 edges[i][1]은 둘째 칸입니다. 첫 행 [0,1]에서는 u가 0, v가 1입니다. 둘째 행 [1,2]에서는 u가 1, v가 2입니다. 각 반복에서 이 두 점의 선택 기록을 확인합니다.

C의 느낌표는 참과 거짓을 뒤집습니다. 숫자 0은 거짓으로 읽으므로 !0은 참이고, 선택 표시 1은 참으로 읽으므로 !1은 거짓입니다. &&는 양쪽이 모두 참일 때 참입니다.

첫 선에서는 chosen[0]과 chosen[1]이 모두 0입니다. !0 && !0이 참이라 중괄호 안에 들어갑니다. 두 칸을 1로 바꾸고 answer에 2를 더합니다. 둘째 선에서는 chosen[1]이 이미 1입니다. !1 && !0은 거짓이므로 중괄호 안을 건너뜁니다. 셋째 선에서 두 점을 더 고른 뒤에는 개수가 4가 됩니다.

닫는 중괄호는 어느 범위가 끝나는지를 알려 줍니다. 11행의 중괄호는 if 안에서 두 점을 추가하는 범위를 끝냅니다. 12행의 중괄호는 선을 한 개 처리하는 반복 범위를 끝냅니다. 아직 읽을 선이 있으면 for로 돌아가 다음 행을 읽습니다.

i가 m인 5에 도달하면 더 읽을 행이 없으므로 반복을 끝내고 13행의 return answer를 실행합니다. 저장된 4를 정수 결과로 돌려줍니다. 마지막 중괄호는 함수 전체의 끝입니다. 입력 다섯 행을 모두 읽고 반환한다는 흐름을 중괄호 위치에서 확인할 수 있습니다.

결과가 모든 선을 해결하는 이유

함수가 만든 선택이 모든 선을 해결하는지 확인하겠습니다. 선을 읽었을 때 이미 고른 끝점이 있으면 그 선은 해결된 상태입니다. 양 끝을 모두 안 골랐다면 두 점을 골라서 그 선을 해결합니다. 어느 경우든 이번 선은 해결된 채로 다음 선으로 넘어갑니다.

그 뒤에 고른 점을 빼는 동작이 없으므로 앞에서 해결한 선도 계속 해결되어 있습니다. 이 과정을 입력의 모든 선에 수행하면 마지막에는 모든 선이 해결됩니다. 예제에서는 네 점을 전부 골랐고 다섯 선이 모두 초록색입니다. 따라서 반환한 4는 유효한 정점 커버의 크기입니다.

앞에서 손으로 찾은 최적 선택은 1번과 2번이었습니다. 반면 코드는 첫 선에서 0번과 1번을 골랐습니다. 고른 점을 빼거나 다른 조합으로 바꾸지 않으므로 셋째 선에서 2번과 3번까지 추가했습니다. 결과는 네 점입니다.

가능한 최소는 두 점인데 이번 규칙은 네 점을 사용했습니다. 이 입력에서는 정확히 두 배입니다. 그래도 전체 선은 모두 해결하고, 계산은 선 목록을 한 번 읽으면 끝납니다. 이제 어떤 입력에서도 두 배를 넘지 않는 이유를 설명하겠습니다. 그 전에 선의 순서가 바뀌면 같은 규칙의 결과도 달라지는지 확인하겠습니다.

같은 다섯 선을 1–2부터 읽어 보겠습니다. 첫 선의 양 끝이 모두 비어 있어 1번과 2번을 고릅니다. answer는 2입니다. 다음 0–1은 1번을 골라서 해결되고, 2–3과 0–2는 2번을 골라서 해결됩니다. 마지막 1–3도 1번에 붙어 있습니다.

추가 선택이 한 번도 없어 2를 반환합니다. 이 순서에서는 최적 선택과 같은 결과가 나왔습니다. 앞의 순서는 4개, 이번 순서는 2개를 골랐습니다. 어느 순서에서도 최적의 두 배를 넘지 않는 성질은 같습니다.

끝점이 겹치지 않는 이유부터 2배 보장까지
두 점을 추가했던 선만 노란색으로 표시합니다
두 점을 추가했던 선만 노란색으로 표시합니다

두 배 한도를 확인할 때는 처음의 입력 순서로 돌아가겠습니다. 두 점을 새로 골랐던 선은 0–1과 2–3이었습니다. 이 두 선만 노란색으로 표시했습니다. 다른 세 선도 원래 그래프에 그대로 있지만, 그 선을 읽을 때는 이미 고른 끝이 있어 개수를 늘리지 않았습니다.

노란 선 하나에서 점을 두 개씩 골랐습니다. 노란 선이 두 개이므로 코드가 고른 점은 네 개입니다. 이제 이 노란 선들만 보고, 어떤 정답이라도 최소한 몇 점이 필요한지 따져 보겠습니다. 먼저 두 노란 선의 끝점이 겹치지 않는 이유를 코드와 연결하겠습니다.

앞의 끝점을 공유하면 새 두 점을 고를 수 없습니다
앞의 끝점을 공유하면 새 두 점을 고를 수 없습니다

왜 노란 선들의 끝점은 겹치지 않을까요? 첫 노란 선에서 두 점을 고르면 두 칸이 True가 됩니다. 이후에 이 기록을 False로 되돌리는 코드가 없습니다. 따라서 나중 선이 그 점을 어느 쪽 끝에서 만나든 해당 조건에 not True가 들어갑니다.

and의 한쪽이 False이면 전체가 False입니다. 그 선에서는 새 두 점을 고를 수 없습니다. 나중에 두 점을 새로 고르려면 양쪽 모두 처음 만나는 점이어야 합니다. 이 과정을 계속 적용하면 두 점을 추가했던 선들끼리는 끝점을 전혀 공유하지 않습니다. 예제에서 1–2, 0–2, 1–3이 노란 선에 포함되지 않았던 이유가 바로 이 조건입니다.

노란 선 0–1에는 어떤 정답도 한 점이 필요합니다
노란 선 0–1에는 어떤 정답도 한 점이 필요합니다

0–1 선부터 보겠습니다. 어떤 정점 커버든 이 선을 해결해야 합니다. 그러려면 0번이나 1번 중 적어도 하나를 골라야 합니다. 다른 점만 골라서는 이 선의 양 끝이 계속 비어 있습니다.

이때 최적 선택이 0번을 골랐는지 1번을 골랐는지는 알 필요가 없습니다. 둘 중 적어도 한 점이 반드시 필요하다는 사실만 사용합니다. 그래서 이 노란 선에 최소 한 점이라고 적었습니다.

노란 선 2–3에도 별도로 한 점이 필요합니다
노란 선 2–3에도 별도로 한 점이 필요합니다

둘째 노란 선 2–3도 해결해야 합니다. 이 선에는 2번이나 3번 중 적어도 한 점이 필요합니다. 앞의 0–1에서 쓸 수 있는 점은 0번과 1번이었고, 여기서 쓸 수 있는 점은 2번과 3번입니다. 서로 같은 점이 없습니다.

따라서 앞 선을 위해 고른 한 점을 이 선의 끝점으로도 사용할 수 없습니다. 이 선을 위해 별도로 최소 한 점을 더 골라야 합니다. 두 노란 선만 확인해도 어떤 정답이든 적어도 두 점을 쓴다는 사실을 알 수 있습니다.

최적값을 몰라도 최소 2개라는 기준을 압니다
최적값을 몰라도 최소 2개라는 기준을 압니다

두 노란 선은 원래 그래프에 실제로 들어 있습니다. 나머지 선들까지 전부 해결하려는 정답은 이 두 선도 당연히 해결해야 합니다. 0–1에 한 점, 2–3에 별도로 한 점이 필요하므로 모든 선을 해결하는 최소 개수는 적어도 2입니다.

어떤 정답이든 반드시 필요한 최소 기준을 하한이라고 부릅니다. 여기서 얻은 하한은 2입니다. 이 단계에서는 최적 선택의 전체 모양을 찾지 않았습니다. 꼭 해결해야 하는 두 선만으로 최적값이 2보다 작을 수 없다는 사실을 얻었습니다.

코드의 4개가 최적의 2배 이내인 이유
코드의 4개가 최적의 2배 이내인 이유

코드는 두 노란 선에서 두 점씩 골라 총 4개를 썼습니다. 최적값은 앞에서 확인한 하한 2 이상입니다. 최적값이 2 이상이면, 그 두 배는 4 이상입니다. 따라서 코드가 쓴 4는 최적값의 두 배를 넘지 않습니다.

이것이 최적값을 직접 구하지 않고 품질을 보장하는 계산입니다. 이 작은 예제는 최적값이 정확히 2여서 결과 4가 정확히 두 배입니다. 더 큰 입력에서도 두 점을 추가한 선의 수를 세면 같은 형태의 기준을 얻을 수 있습니다.

그런 선이 세 개이면 같은 계산을 합니다
그런 선이 세 개이면 같은 계산을 합니다

더 큰 그래프에서 두 점을 추가했던 선이 세 개였다고 해 보겠습니다. 그 세 선만 뽑아 그렸습니다. 코드의 조건 때문에 세 선의 끝점은 모두 다릅니다.

어떤 정답도 첫 선에서 한 점, 둘째 선에서 별도의 한 점, 셋째 선에서 또 한 점이 필요합니다. 따라서 최적값은 적어도 3입니다. 우리 코드는 선마다 두 점씩 총 6개를 골랐습니다. 최적값이 3 이상이면 그 두 배는 6 이상이므로, 결과 6은 역시 최적의 두 배 이내입니다.

선이 k개이면 코드 2k개, 최적은 k개 이상입니다
선이 k개이면 코드 2k개, 최적은 k개 이상입니다

마지막으로 개수에 이름을 붙이겠습니다. 두 점을 새로 추가했던 선의 수를 k라고 하겠습니다. 이 선들끼리는 끝점이 겹치지 않으므로, 어떤 정답도 선마다 별도의 한 점을 써야 합니다. 최적값은 k 이상입니다.

코드는 그 선 하나마다 새 점 두 개를 골랐으므로 총 2k개를 씁니다. 최적값이 k 이상이면 최적값의 두 배는 2k 이상입니다. 따라서 코드의 결과 2k는 최적값의 두 배 이내입니다. k가 2였던 예제에서는 4개, k가 3이면 6개라는 계산을 그대로 일반화한 것입니다.

마지막 확인

같은 선이 두 번 주어져도 선택 기록을 유지합니다. [0,1]을 처음 읽을 때 0번과 1번을 골랐다면, 다시 읽을 때는 두 기록이 이미 True입니다. 따라서 두 번째에는 더하지 않아 2를 반환합니다.

어떤 점이 어느 선에도 등장하지 않으면 그 점을 고르는 문장을 실행할 일이 없습니다. 선을 해결하는 데 필요하지 않은 점입니다. 선 목록 자체가 비어 있으면 for를 한 번도 실행하지 않고 처음 answer인 0을 반환합니다. 이때는 아무 점도 고르지 않아도 모든 조건을 만족하므로 최적값 역시 0입니다.

계산 시간을 세어 보겠습니다. Python은 처음 chosen에 점 수만큼 n칸을 준비합니다. 그다음 선이 m개이면 반복을 m번 합니다. 한 번의 반복에서 하는 일은 두 기록을 읽고, 필요하면 두 기록과 개수를 바꾸는 정도입니다. 따라서 준비 시간과 반복 시간을 합해 O(n+m)입니다. 점별 상태를 저장하는 공간은 O(n)입니다.

예제의 C 코드는 문제 제한이 최대 100점이라 100칸을 한 번에 초기화합니다. 정해진 제한 안에서 초기화한 뒤 선 m개를 읽습니다. 점 수에 맞춰 배열을 준비하는 일반적인 구현으로 보면 같은 O(n+m) 시간과 O(n) 공간입니다. 모든 점 조합을 비교하는 과정 없이 선을 한 번씩 읽습니다.

같은 선택 규칙으로 입력 순서와 빈 입력을 확인합니다.
같은 선택 규칙으로 입력 순서와 빈 입력을 확인합니다.
문제의 입력 조건과 반환값 전체
점들과 두 점 사이를 잇는 선들이 주어진다. 선마다 양 끝 중 적어도 한 점을 골라야 한다. 모든 선에서 이 조건을 만족하는 점들의 모음을 정점 커버라고 부른다.

이 문제에서는 다음의 빠른 선택 규칙을 그대로 구현한다.
1. 처음에는 아무 점도 고르지 않는다.
2. edges의 선을 앞에서부터 한 쌍씩 읽는다.
3. 양 끝점을 모두 아직 안 골랐다면 두 점을 함께 고른다.
4. 한 끝점이라도 이미 골랐다면 점을 추가하지 않는다.
5. 모든 선을 읽은 뒤 실제로 고른 점의 개수를 반환한다.

한 번 고른 점은 끝까지 유지한다. 입력된 선의 순서를 지키고, 같은 점을 중복해서 세지 않는다.

입력
n은 전체 점 수로 1~100의 정수이다. 점 번호는 0부터 n-1까지이다.
edges는 선 목록으로 길이는 0~1000이다. 각 [u,v]는 서로 다른 두 점 u와 v를 잇는 선이다. 선에는 방향이 없다. 같은 선이 여러 번 주어질 수 있다.

반환값
위 규칙을 입력 순서대로 적용해서 고른 점의 개수를 반환한다. 선과 연결되지 않은 점은 고르지 않고, 선이 없으면 0을 반환한다.

예제 1
n=4, edges=[[0,1],[1,2],[2,3],[0,2],[1,3]]
반환값은 4이다.
첫 선에서 0번과 1번을 골라 2개가 된다. 다음 1–2는 1번을 이미 골랐으므로 넘어간다. 2–3에서 2번과 3번을 더 골라 4개가 된다. 뒤의 0–2와 1–3에서는 점을 추가하지 않는다.
이 그래프는 1번과 2번 두 점으로도 모든 선을 해결한다. 위 규칙을 이 순서로 실행한 결과는 4이다.

예제 2
n=4, edges=[[1,2],[0,1],[2,3],[0,2],[1,3]]
반환값은 2이다.
처음 고른 1번과 2번이 나머지 모든 선을 해결하므로 더 고르지 않는다.

예제 3
n=4, edges=[[0,1],[0,1]]
반환값은 2이다. 같은 선을 다시 읽어도 이미 고른 두 점을 또 세지 않는다.

예제 4
n=4, edges=[]
반환값은 0이다. 해결할 선이 없어 점을 고를 필요가 없다.

근사 보장
이 규칙이 만든 선택은 모든 선을 해결하고, 그 개수는 가능한 최소 개수의 2배 이내이다. 두 점을 새로 추가한 선들끼리는 끝점을 공유하지 않는다. 따라서 어떤 정답도 그런 선마다 별도의 한 점이 필요하고, 이 규칙은 선마다 두 점씩 사용한다.

9-3 코딩 연습하기

추가 연습 문제입니다. 기말고사 출제 범위에서 제외합니다.

9-4 추가 연습 · 새 원소를 가장 많이 덮는 집합 선택 · 조금 도전

전체 원소는 0부터 n−1까지이다. 여러 집합 중 아직 덮지 못한 원소를 가장 많이 포함하는 집합을 하나 고른다. 새로 덮는 수가 같으면 입력에서 먼저 나온 집합을 고른다. 고른 집합의 원소를 덮음으로 표시하고 이 과정을 반복한다.

모든 원소를 덮으면 선택한 집합 수, 끝까지 덮을 수 없으면 −1을 반환하시오.

greedy_set_cover(n, sets)

입력

n
전체 원소 수. 1~20의 정수
sets
0~30개 집합을 나타내는 정수 배열. 각 값은 0~2ⁿ−1

반환값과 조건

정해진 선택 절차의 횟수를 반환한다. 가능한 모든 조합 중 최소 집합 수를 구하는 문제는 아니다.

  • 집합은 원소 k가 들어 있으면 2ᵏ를 더한 정수로 나타낸다. {0,1}은 1+2=3이다.
  • n=4일 때 3은 {0,1}, 6은 {1,2}, 12는 {2,3}을 나타낸다. 0은 빈 집합이다.
  • 이미 덮은 원소는 새로 덮는 수에 포함하지 않는다.
  • 남은 원소가 있는데 어느 집합도 새 원소를 덮지 못하면 −1이다.

동률에서 먼저 고른 집합이 이후 선택을 바꾼다

두 집합으로 완료
n=4, sets=[3,6,12]

반환값: 2

처음에는 동률이라 3={0,1}을 고른다. 남은 {2,3}은 12로 덮는다.

동률에서 3을 먼저 고름
n=4, sets=[3,5,10]

반환값: 3

3={0,1} 다음에는 5={0,2}와 10={1,3}이 각각 하나씩 더 필요하다.

같은 집합들의 순서 변경
n=4, sets=[5,10,3]

반환값: 2

5={0,2}를 먼저 고르면 10={1,3}으로 바로 끝난다.

덮을 수 없는 원소
n=4, sets=[3]

반환값: -1

원소 2와 3은 어느 집합에도 없다.

집합이 없음
n=4, sets=[]

반환값: -1

전체 원소는 있는데 사용할 집합이 없다.

빈 집합은 도움 없음
n=1, sets=[0,1]

반환값: 1

0은 아무것도 덮지 못한다. {0}을 뜻하는 1을 한 번 고른다.

집합 전체 크기 대신 새로 덮는 수를 센다

A={0,1}, B={1,2}, C={2,3}이면 처음에는 세 집합 모두 두 원소를 덮는다. A를 고른 뒤 남은 원소는 2와 3이다. 이때 B는 원소2 한 개, C는 원소2와3 두 개를 새로 덮으므로 C를 고른다. 비트마스크는 이 포함 여부를 정수의 0/1 자리로 적은 표현이다.

C 함수의 인자
int greedy_set_cover(int n, const int sets[], int m)

n은 전체 원소 수, m은 집합 수이다. sets의 길이는 m이다.

이 문제 연습하기

10장 휴리스틱 알고리즘

10-1 상하좌우 이동 거리 · 아주 쉬움

장애물이 없는 격자의 출발점 (x1,y1)에서 도착점 (x2,y2)로 간다. 한 번에 상·하·좌·우 중 한 방향으로 한 칸 움직인다. 대각선 이동은 허용하지 않는다.

도착점까지 필요한 최소 이동 횟수를 반환하시오.

manhattan(x1, y1, x2, y2)

입력

x1, y1
출발점 좌표. 각각 −10,000~10,000의 정수
x2, y2
도착점 좌표. 각각 −10,000~10,000의 정수

반환값과 조건

최소 이동 횟수 |x1−x2|+|y1−y2|를 정수로 반환한다.

  • 좌표가 음수여도 같은 격자의 점이다. 거리에는 좌표 차이의 절댓값을 쓴다.
  • 두 점이 같으면 이동하지 않아 답은 0이다.

음수 좌표와 대각선 방향의 도착점

가로와 세로 이동
출발 (0,0), 도착 (3,2)

반환값: 5

가로 세 번과 세로 두 번이 필요하다.

같은 점
출발과 도착이 모두 (2,3)

반환값: 0

이동할 필요가 없다.

음수 좌표 포함
출발 (2,−1), 도착 (−2,2)

반환값: 7

가로 |2−(−2)|=4, 세로 |−1−2|=3으로 합은 7이다.

대각선 방향
출발 (0,0), 도착 (1,1)

반환값: 2

오른쪽과 위로 한 번씩 가야 한다. 한 번에 대각선으로 갈 수 없다.

방향과 상관없이 필요한 칸 수를 더한다

x좌표 차이는 가로로 움직여야 하는 칸 수이고 y좌표 차이는 세로 칸 수이다. 왼쪽이나 아래로 가면 차이가 음수가 될 수 있지만 이동 횟수는 음수가 될 수 없다. 두 차이의 절댓값을 더한다. 이런 거리를 맨해튼 거리라고 부른다.

C 함수의 인자
int manhattan(int x1, int y1, int x2, int y2)

네 인자는 Python과 같은 뜻이다.

이 문제 연습하기

10-2 가까운 도시부터 방문하는 순회 · 쉬움

0번 도시에서 출발한다. 현재 도시에서 아직 방문하지 않은 도시 중 이동 비용이 가장 작은 곳으로 간다. 비용이 같으면 번호가 작은 도시를 고른다. 모든 도시를 방문하면 0번으로 돌아온다.

이 선택 규칙을 그대로 실행한 왕복 비용을 반환하시오.

nearest_neighbor(dist)

입력

dist
도시 1~9개의 정사각 비용 표. 값은 0~100, 대각선은 0

반환값과 조건

가까운 도시부터 방문한 경로의 비용을 정수로 반환한다. 모든 순서를 비교한 최솟값과 다를 수 있다.

  • 모든 이동이 가능하며 방향별 비용은 달라도 된다.
  • 이미 방문한 도시는 다음 후보에서 뺀다. 마지막 귀환 비용은 더한다.
  • 도시가 하나이면 0이다.

가까운 선택을 반복해도 전체 최적 경로와 다를 수 있다

기본 순회
dist=[[0,3,1],[3,0,2],[1,2,0]]

반환값: 6

0에서 2를 고르고 1로 간 뒤 귀환해 1+2+3=6이다.

동률은 작은 번호
dist=[[0,1,1],[5,0,1],[2,7,0]]

반환값: 4

0에서 1과2의 비용이 같아 1을 먼저 고른다. 비용은 1+1+2=4이다.

가까운 선택의 한계
dist=[[0,1,2,9],[1,0,1,9],[2,1,0,50],[9,9,50,0]]

반환값: 61

규칙의 경로 0,1,2,3,0은 61이다. 더 싼 경로가 있어도 규칙대로 계산한 61을 반환한다.

두 도시
dist=[[0,5],[8,0]]

반환값: 13

왕복 비용 5+8이다.

도시 하나
dist=[[0]]

반환값: 0

추가로 방문할 도시가 없다.

먼저 가까운 곳을 골라 생기는 결과

네 도시 사례에서는 0에서 비용1인 1을 고르고, 1에서 비용1인 2를 고른다. 남은 3으로 가는 비용은 50이어서 전체 비용은 61이 된다. 0,2,1,3,0은 비용21이지만, 이 함수는 전체 최적 경로를 찾는 함수가 아니라 주어진 가까운 도시 선택 규칙을 구현한다.

C 함수의 인자
int nearest_neighbor(const int dist[][9], int n)

dist는 비용 표, n은 도시 수이다.

이 문제 연습하기

10-3 새 후보를 받아들일지 판단하기 · 기본

비용을 줄이는 과정에서 현재 해를 새 후보로 바꿀지 결정한다. 후보 비용이 현재보다 작거나 같으면 항상 받아들인다. 더 비싼 후보는 온도 temp와 주어진 숫자 u를 사용해 아래 규칙으로 판단한다.

새 후보를 받아들이면 1, 거부하면 0을 반환하시오.

accept_move(current, candidate, temp, u)

입력

current, candidate
현재 비용과 새 후보 비용. 각각 0~10,000의 정수
temp
온도. 0~1000의 실수
u
비교에 쓸 숫자. 0 이상 1 미만의 실수

반환값과 조건

수락 여부인 정수 1 또는 0을 반환한다. 새 비용을 반환하지 않는다.

  • candidate≤current이면 temp와 u에 관계없이 1이다.
  • candidate>current이고 temp=0이면 0이다.
  • 더 비싸고 temp>0이면 p=exp((current−candidate)/temp)를 계산한다. u<p이면 1, 그 외에는 0이다.
  • 새 난수를 만들지 말고 입력 u를 쓴다. 양의 온도에서 u=0이면 수락한다.

같은 후보도 온도와 u에 따라 판단이 달라진다

더 싼 후보
current=10, candidate=8, temp=0, u=0.9

반환값: 1

비용을 줄이므로 온도가 0이어도 받아들인다.

비용이 같음
current=10, candidate=10, temp=0, u=0.99

반환값: 1

같은 비용도 첫 조건에 따라 수락한다.

더 비싸고 온도 0
current=10, candidate=12, temp=0, u=0

반환값: 0

온도 0에서 더 비싼 후보는 거부한다. u=0이어도 이 조건이 먼저이다.

작은 u
current=10, candidate=12, temp=2, u=0.2

반환값: 1

p=exp(−1)≈0.368이고 0.2<p이다.

큰 u
같은 비용과 온도, u=0.8

반환값: 0

0.8은 약 0.368보다 크므로 거부한다.

온도 2
current=10, candidate=12, temp=2, u=0.5

반환값: 0

0.5는 수락 확률 약 0.368보다 크다.

온도만 4로 변경
current=10, candidate=12, temp=4, u=0.5

반환값: 1

p=exp(−0.5)≈0.607로 커져 이번에는 수락한다.

좋은 후보부터 처리하고 나눗셈은 나중에 한다

조건의 순서가 중요하다. 좋은 후보나 같은 비용의 후보는 먼저 수락하고, 남은 경우에서 온도가 0인지 확인한다. 그다음에만 확률식을 계산하므로 0으로 나누지 않는다. exp는 지수 함수이며 Python의 math.exp, C의 math.h에 있는 exp를 사용한다. 이 한 단계의 판단은 담금질 기법에서 쓰는 수락 규칙이다.

C 함수의 인자
int accept_move(int current, int candidate, double temp, double u)

temp와 u는 double형이다. 나머지 조건은 Python과 같다.

이 문제 연습하기

추가 연습 문제입니다. 기말고사 출제 범위에서 제외합니다.

10-4 추가 연습 · 도시 두 위치를 한 번 교환한 최소 비용 · 조금 도전

도시를 방문하는 원래 경로 route가 주어진다. 첫 위치의 도시0은 그대로 두고, 나머지 위치 중 두 곳을 골라 한 번 맞바꾼다. 아무것도 바꾸지 않은 원래 경로도 후보로 포함한다.

이 후보들의 왕복 비용 중 가장 작은 값을 반환하시오.

best_swap_cost(dist, route)

입력

dist
도시 1~9개의 정사각 비용 표. 각 값 0~100, 대각선 0
route
0으로 시작하며 0~n−1을 한 번씩 포함하는 길이 n의 배열

반환값과 조건

원래 경로 또는 한 번 교환한 경로의 최소 비용을 반환한다. 바꾼 경로 자체는 반환하지 않는다.

  • 모든 이동이 가능하고 방향별 비용은 달라도 된다. 마지막 귀환 비용도 포함한다.
  • 각 후보는 원래 경로에서 새로 만든다. 한 번 좋아진 경로에서 계속 교환을 누적하지 않는다.
  • 두 위치를 고를 수 없으면 원래 비용을 반환한다. 입력 route의 내용도 바꾸지 않는다.

바꾸지 않는 경우도 후보에 넣는다

교환해서 개선
dist=[[0,3,1,8],[3,0,8,2],[1,8,0,4],[8,2,4,0]], route=[0,1,2,3]

반환값: 10

2와3의 위치를 바꾼 [0,1,3,2]의 비용은 10이다. 원래 비용은 23이다.

원래 경로가 더 쌈
dist=[[0,1,9],[4,0,2],[3,6,0]], route=[0,1,2]

반환값: 6

원래 비용은 1+2+3=6이고, 교환하면 9+6+4=19라 그대로 둔다.

같은 표, 다른 시작 경로
같은 dist, route=[0,2,1]

반환값: 6

1과2의 위치를 바꾸면 앞 사례의 비용6인 경로가 된다.

교환할 두 위치가 없음
dist=[[0,5],[8,0]], route=[0,1]

반환값: 13

첫 위치를 고정하면 남은 위치가 하나뿐이라 원래 비용을 반환한다.

도시 하나
dist=[[0]], route=[0]

반환값: 0

바꿀 위치도 없고 왕복 비용도 0이다.

후보 하나를 계산한 뒤 원래 순서로 돌린다

[0,1,2,3]에서 바꿀 수 있는 위치 쌍은 (1,2),(1,3),(2,3)이다. 각 쌍을 바꾼 비용을 계산한 다음 같은 두 위치를 다시 바꿔 복구한다. 복구하지 않으면 다음 후보가 원래 경로에서 두 번 바뀐 경로가 되어 문제의 조건과 달라진다.

C 함수의 인자
int best_swap_cost(const int dist[][9], int n, const int route[])

dist는 비용 표, n은 도시 수, route는 길이 n인 방문 순서이다.

이 문제 연습하기