1. 근사 알고리즘 프린터 두 대와 파일 다섯 개가 있습니다. 두 프린터는 속도가 같고, 시간 0에 같이 출발합니다. A는 8분, B는 7분, C는 6분, D는 5분, E는 4분이 걸립니다. 각 파일을 어느 프린터에 맡길지 우리가 정하겠습니다. 어떤 프린터가 먼저 끝나도 다른 프린터의 일이 남아 있으면 기다려야 합니다. 파일 다섯 개를 모두 받을 때까지 걸리는 시간을 줄이고 싶습니다. 먼저 직접 좋은 배정을 찾아보고, 그다음 빠른 규칙으로 만든 배정과 비교하겠습니다. 두 번째 문제에서는 상자에 물건을 담으며 같은 방식으로 최적과 근사를 비교합니다. 2. 9-1 같은 일을 두 기계에 나눠 맡깁니다 각 작업은 한 번씩만 처리합니다. 작업 하나는 한 기계에 맡겨 끝까지 처리합니다. 예를 들어 8분짜리를 두 기계에 4분씩 나누는 배정은 허용하지 않습니다. 두 기계는 같은 속도이고, 처음부터 모든 작업이 준비되어 있습니다. 기계 한 대는 맡은 작업을 한 번에 하나씩 처리합니다. 그 기계에 8분과 6분을 맡기면 8분짜리를 끝낸 뒤 6분짜리를 처리해서 14분에 끝납니다. 다른 기계도 자신에게 맡겨진 일을 이어서 합니다. 작업이 전부 끝나는 시각은 두 기계 중 늦게 끝난 쪽의 시각입니다. 3. 9-1 14분과 16분이면 모두 끝나는 시각은 16분입니다 왼쪽에 8분과 6분을 맡기고, 오른쪽에 7분과 5분과 4분을 맡겼습니다. 왼쪽은 14분, 오른쪽은 16분에 끝납니다. 두 기계를 동시에 시작했으므로 14분과 16분을 합해서 기다릴 필요는 없습니다. 14분에는 왼쪽 작업은 끝났지만 오른쪽에는 2분어치 일이 남아 있습니다. 16분이 되어야 모든 결과를 받을 수 있습니다. 그래서 이 배정의 전체 완료 시각은 두 합 중 큰 16분입니다. 이제 작업들을 다시 묶어 16보다 작게 만들 수 있는지 보겠습니다. 4. 9-1 두 프린터가 함께 15분에 끝납니다 이번에는 8분과 7분을 왼쪽에 함께 맡겼습니다. 합하면 15분입니다. 나머지 6분, 5분, 4분을 오른쪽에 맡겨도 합이 15분입니다. 따라서 두 기계가 모두 15분에 끝납니다. 앞에서 만든 16분 배정보다 1분 빨라졌습니다. 모든 작업을 한 번씩 처리했고, 작업을 쪼개지도 않았습니다. 조건을 지키는 더 좋은 배정을 찾은 것입니다. 이 배정이 가장 좋은지 확인하려면 15분보다 일찍 끝내는 방법이 가능한지 따져야 합니다. 5. 9-1 15분보다 빠르게 끝낼 수는 없습니다 다섯 작업의 시간을 모두 더하면 30분입니다. 기계 한 대가 혼자 처리하면 30분 동안 해야 하는 양입니다. 두 기계가 14분씩 일하면 합해서 28분어치만 처리할 수 있습니다. 필요한 30분어치 중 2분어치가 남습니다. 일반적으로 두 기계가 t분 일하면 최대 2t분어치를 처리합니다. 30분어치를 끝내려면 2t가 30 이상이어야 해서 t는 적어도 15입니다. 앞에서 실제로 15분에 끝나는 배정도 찾았습니다. 따라서 이 예제의 최적값, 즉 가장 작은 완료 시각은 15분입니다. 6. 9-1 작업이 많으면 배정할 조합도 많아집니다 작업마다 왼쪽에 맡길지 오른쪽에 맡길지 두 가지를 고를 수 있습니다. 작업이 다섯 개이면 두 기계를 구분해서 세는 배정은 32개입니다. 스무 개이면 약 백만 개, 마흔 개이면 약 1조 1천억 개로 늘어납니다. 모든 배정을 비교하는 방법 외에도 앞에서 배운 탐색과 동적 계획법을 사용할 수 있습니다. 다만 입력의 크기와 숫자 범위가 커지면 계산량을 고려해야 합니다. 여기서는 각 작업을 읽을 때 짧은 계산만 해서 배정을 빨리 만드는 방법을 배우겠습니다. 그 결과가 최적과 얼마나 차이 날 수 있는지도 확인합니다. 7. 9-1 덜 맡은 기계에 다음 작업을 보냅니다 작업을 배열 앞에서부터 하나씩 읽습니다. 이번 작업을 맡기기 직전에 두 기계가 얼마나 많은 시간을 맡았는지 비교합니다. 합이 작은 기계에 이번 작업을 추가합니다. 두 합이 같으면 왼쪽을 고르기로 정하겠습니다. 여기서 비교하는 숫자는 기계에 맡겨 놓은 총작업 시간입니다. 아직 실행 전인 배정 계획을 만들고 있습니다. 왼쪽에 8분어치를 맡겼다면 다음 작업을 그 뒤에 이어서 하도록 계획합니다. 각 작업에서 두 합만 비교하므로 빠르게 배정을 만들 수 있습니다. 8. 9-1 코드에 쓰는 이름을 먼저 정합니다 이제 계산을 코드의 이름과 연결하겠습니다. jobs는 작업 시간 목록입니다. left는 왼쪽 기계에 맡긴 시간의 합이고, right는 오른쪽 기계에 맡긴 시간의 합입니다. 처음에는 아무 일도 맡기지 않았으므로 두 값 모두 0입니다. duration에는 지금 읽는 작업 하나의 시간을 넣습니다. 첫 번째에는 8이고, 그다음에는 7, 6, 5, 4입니다. duration이 다음 값으로 바뀌어도 left와 right에 쌓아 둔 합은 계속 남습니다. 두 합에 이번 시간을 더하면서 배정 계획을 완성합니다. 9. 9-1 함수가 받을 입력과 반환할 숫자 작성할 함수의 이름은 two_machine_time입니다. 괄호 안 jobs로 작업 목록을 받습니다. 기계가 항상 두 대이므로 기계 수를 따로 받지 않습니다. 입력은 작업이 없을 수도 있고 최대 천 개일 수도 있습니다. 각 시간은 0 이상 백만 이하입니다. 함수는 정해진 규칙을 실행해서 두 합 중 큰 값을 정수 하나로 반환합니다. 예제의 최적값 15는 결과를 비교하기 위해 우리가 따로 알아낸 값입니다. 함수 안에서 최적 배정을 다시 탐색하는 과정은 없습니다. 이제 같은 [8,7,6,5,4]를 넣고 코드가 어떻게 작동하는지 보겠습니다. 10. 9-1 비교하고 더하는 기호를 읽습니다 작거나 같다 기호는 왼쪽이 더 작거나 두 값이 같을 때 참입니다. 0과 0을 비교해도 참이므로 동점에서 왼쪽을 고를 수 있습니다. 거짓이면 오른쪽 합이 더 작은 경우입니다. 더하기 등호는 기존 값에 더해서 저장한다는 문장입니다. left가 8인 상태에서 left += 5를 실행하면 13이 됩니다. max는 두 숫자 중 큰 숫자를 고릅니다. 마지막에 max를 사용하면 두 기계의 작업이 모두 끝나는 시각을 구합니다. 11. 9-1 Python 전체 답안 첫 줄의 def는 함수를 정의합니다. 함수 이름 뒤 괄호의 jobs가 입력을 받는 자리입니다. 2행과 3행에서 두 합을 0으로 준비합니다. 4행부터는 jobs의 각 시간을 duration에 넣으며 반복합니다. 5행에서 두 합을 비교하고 6행이나 8행 중 하나를 실행합니다. 같거나 왼쪽이 작으면 6행, 오른쪽이 작으면 8행입니다. 작업 목록을 모두 읽으면 9행에서 큰 합을 반환합니다. 오른쪽으로 들여쓴 줄이 반복이나 조건 안에 들어 있습니다. 이제 이 줄들이 실제 숫자를 어떻게 바꾸는지 보겠습니다. 12. 9-1 두 합은 시작할 때 한 번 0으로 만듭니다 2행과 3행은 반복을 시작하기 전에 한 번 실행합니다. 두 합을 0으로 만든 뒤 4행의 반복문으로 들어갑니다. for duration in jobs는 목록에서 다음 시간을 하나 꺼내 duration에 넣습니다. 첫 값은 8입니다. 이번 작업을 처리한 뒤 반복문으로 돌아오면 다음 값 7을 읽습니다. 4행으로 돌아오기 때문에 앞에서 계산한 합은 그대로 남습니다. 모든 작업을 배정하려면 이 누적 기록을 유지해야 합니다. 13. 9-1 첫 작업 8분을 배정합니다 이번에 duration으로 읽은 값은 8입니다. 배정 직전 left는 0, right는 0입니다. 두 합이 같아서 약속대로 왼쪽을 고릅니다. 5행의 left <= right는 참이므로 6행에서 left에 이번 시간을 더합니다. 기존 합 0에 8을 더해서 8으로 저장합니다. 다른 기계의 합은 그대로입니다. 그림에서 노란 막대가 방금 추가한 작업이고, 초록 막대는 앞에서 맡긴 작업입니다. 이 두 합을 유지한 채 다음 작업 시간을 읽습니다. 14. 9-1 둘째 작업 7분을 배정합니다 이번에 duration으로 읽은 값은 7입니다. 배정 직전 left는 8, right는 0입니다. 오른쪽 합이 더 작습니다. 5행의 left <= right는 거짓이므로 else 아래 8행에서 right에 이번 시간을 더합니다. 기존 합 0에 7을 더해서 7으로 저장합니다. 다른 기계의 합은 그대로입니다. 그림에서 노란 막대가 방금 추가한 작업이고, 초록 막대는 앞에서 맡긴 작업입니다. 이 두 합을 유지한 채 다음 작업 시간을 읽습니다. 15. 9-1 셋째 작업 6분을 배정합니다 이번에 duration으로 읽은 값은 6입니다. 배정 직전 left는 8, right는 7입니다. 오른쪽 합이 더 작습니다. 5행의 left <= right는 거짓이므로 else 아래 8행에서 right에 이번 시간을 더합니다. 기존 합 7에 6을 더해서 13으로 저장합니다. 다른 기계의 합은 그대로입니다. 그림에서 노란 막대가 방금 추가한 작업이고, 초록 막대는 앞에서 맡긴 작업입니다. 이 두 합을 유지한 채 다음 작업 시간을 읽습니다. 16. 9-1 넷째 작업 5분을 배정합니다 이번에 duration으로 읽은 값은 5입니다. 배정 직전 left는 8, right는 13입니다. 왼쪽 합이 더 작습니다. 5행의 left <= right는 참이므로 6행에서 left에 이번 시간을 더합니다. 기존 합 8에 5을 더해서 13으로 저장합니다. 다른 기계의 합은 그대로입니다. 그림에서 노란 막대가 방금 추가한 작업이고, 초록 막대는 앞에서 맡긴 작업입니다. 이 두 합을 유지한 채 다음 작업 시간을 읽습니다. 17. 9-1 다섯째 작업 4분을 배정합니다 이번에 duration으로 읽은 값은 4입니다. 배정 직전 left는 13, right는 13입니다. 두 합이 같아서 약속대로 왼쪽을 고릅니다. 5행의 left <= right는 참이므로 6행에서 left에 이번 시간을 더합니다. 기존 합 13에 4을 더해서 17으로 저장합니다. 다른 기계의 합은 그대로입니다. 그림에서 노란 막대가 방금 추가한 작업이고, 초록 막대는 앞에서 맡긴 작업입니다. 다섯 작업을 모두 읽었습니다. 왼쪽은 17분어치, 오른쪽은 13분어치를 맡았습니다. 18. 9-1 빨리 만든 배정은 17분에 끝납니다 다섯 작업을 모두 배정했습니다. 왼쪽에는 8분, 5분, 4분을 맡겨 합이 17입니다. 오른쪽에는 7분과 6분을 맡겨 합이 13입니다. 그림의 두 막대는 시간 0에 같이 시작합니다. 오른쪽이 13분에 먼저 끝나도 왼쪽에는 4분어치 일이 더 남아 있습니다. 따라서 모든 파일을 받는 시각은 17분입니다. 최종 left와 right 중 큰 값을 반환하는 이유가 이 그림에 나타납니다. 먼저 찾았던 15분 배정과 비교하면 이번 규칙은 2분 더 걸립니다. 19. 9-1 return은 모든 작업을 읽은 뒤 실행합니다 마지막 return은 반복문이 끝난 뒤 실행합니다. 왼쪽과 오른쪽 합을 max에 주면 두 값 중 큰 17이 나옵니다. return은 그 숫자를 함수를 호출한 곳으로 돌려주고 함수를 끝냅니다. 9행은 for와 들여쓰기가 같습니다. 작업을 하나씩 처리하는 범위 밖에 있어 모든 작업을 읽고 나서 한 번 실행합니다. 만약 반복문 안에 넣으면 첫 8분짜리만 배정한 뒤 함수가 끝나므로 전체 작업의 답을 계산하지 못합니다. 20. 9-1 C로도 같은 배정을 만듭니다 C에서도 두 합을 0으로 만들고, 입력 순서대로 작은 합에 이번 시간을 더합니다. C 함수는 jobs 배열과 함께 길이 n도 받습니다. 이 예제에서는 작업 다섯 개이므로 n은 5입니다. 배열에서 어느 위치를 읽을지 i에 저장하고, jobs[i]의 시간을 duration에 넣습니다. 나머지 조건과 덧셈은 Python과 같습니다. 마지막 두 줄은 두 합 중 큰 값을 반환합니다. int, 배열의 대괄호, 반복문의 기호를 다음 장에서 각각 설명하겠습니다. 21. 9-1 C에서 int와 입력 배열을 읽습니다 함수 이름 앞의 int는 정수 하나를 반환한다는 표시입니다. const int jobs[]는 정수들이 들어 있는 입력 배열입니다. const는 함수 안에서 이 입력 배열의 값을 바꾸지 않겠다는 표시이고, 대괄호는 배열을 나타냅니다. n은 배열의 원소 개수입니다. 2행과 3행의 int left=0, int right=0은 누적 합을 저장할 정수 변수를 만들고 처음 값을 0으로 정합니다. 문장 끝에는 세미콜론을 붙입니다. 입력이 천 개이고 각 값이 최대 백만이므로 전체 합도 최대 10억입니다. 사이트의 32비트 int 범위 안에서 계산할 수 있습니다. 22. 9-1 C의 위치 번호 i와 작업 시간을 구분합니다 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입니다. 23. 9-1 C의 if와 else도 한쪽에만 더합니다 6행은 left가 right보다 작거나 같은지 확인합니다. 참이면 첫 중괄호 안으로 들어가 left에 duration을 더합니다. 거짓이면 else 뒤의 중괄호 안으로 들어가 right에 더합니다. 중괄호는 함께 실행할 코드의 범위를 표시합니다. 첫 작업에서는 0과 0이 같아 왼쪽을 고릅니다. 둘째 작업에서는 8보다 0이 작아 오른쪽을 고릅니다. 마지막 작업 직전에는 두 합이 13으로 같아서 왼쪽에 4를 더합니다. 각 반복에서 한쪽 덧셈만 실행하므로 작업을 두 기계에 중복해서 맡기는 일이 없습니다. 24. 9-1 C는 반복을 마친 뒤 큰 합을 반환합니다 11행은 for의 중괄호를 닫습니다. 아직 읽을 작업이 있으면 다음 위치로 반복하고, 전부 읽으면 12행으로 갑니다. left가 right 이상이면 left를 반환합니다. 반환한 순간 함수가 끝나므로 다음 return은 실행하지 않습니다. 예제에서는 17이 13 이상이라 17을 반환합니다. 왼쪽이 더 작은 예제에서는 12행의 조건이 거짓이어서 13행의 right를 반환합니다. 두 값이 같을 때는 같은 숫자 중 왼쪽 것을 반환합니다. Python의 max와 같은 역할입니다. 25. 9-1 이제 결과 17분의 품질을 따져 봅니다 빠른 규칙은 모든 작업을 조건에 맞게 배정했습니다. 다만 이 예제의 최적값은 15분이고, 규칙의 결과는 17분입니다. 실제 비율은 17을 15로 나눈 값으로 약 1.13배입니다. 이제 어떤 입력에서도 지키는 한도를 확인하겠습니다. 규칙으로 구한 시간이 최적 시간의 두 배를 넘지 않는지 보겠습니다. 최적값 자체를 직접 구하지 않고도 반드시 필요한 시간과 비교해서 이 한도를 알 수 있습니다. 26. 9-1 어떤 배정에도 필요한 시간을 하한이라 부릅니다 하한이라는 말을 정하겠습니다. 어떤 배정을 쓰더라도 반드시 필요한 시간이라면 최적 시간도 그보다 작을 수 없습니다. 이렇게 최적 시간의 아래쪽 기준이 되는 숫자를 하한이라고 부릅니다. 예제의 총작업량은 30이므로 두 기계가 최소 15분은 일해야 합니다. 또 4분짜리 E는 어느 한 기계에서 4분을 온전히 써야 합니다. 따라서 4도 하한입니다. 지금 예제에서는 15가 더 강한 기준입니다. 앞으로는 총량으로 얻은 기준과 작업 하나로 얻은 기준을 나누어 사용하겠습니다. 27. 9-1 가장 늦게 끝나는 작업은 E입니다 우리 배정에서 왼쪽은 8분짜리와 5분짜리를 마친 뒤 4분짜리 E를 처리합니다. E는 13분에 시작해서 17분에 끝납니다. 오른쪽은 13분에 모두 끝나므로 전체 완료 시각을 정하는 작업은 E입니다. E가 끝나는 17분을 둘로 나누겠습니다. E 앞에 있는 작업에 쓰는 13분과 E 자체를 처리하는 4분입니다. 두 부분이 각각 최적 시간보다 길지 않다는 것을 보이면 두 부분을 합한 17분은 최적 시간 두 개를 더한 값 이내가 됩니다. 먼저 앞부분 13분을 살펴보겠습니다. 28. 9-1 E를 맡기기 직전에는 두 합이 13입니다 E를 맡기기 직전으로 돌아가겠습니다. 왼쪽에는 8과 5를 맡겨 13, 오른쪽에는 7과 6을 맡겨 13입니다. 두 합이 같아 E를 왼쪽에 맡기기로 했습니다. E는 앞의 13분어치 일을 끝낸 뒤 시작합니다. 두 숫자 중 작은 숫자는 두 숫자의 평균보다 클 수 없습니다. 이 예제에서는 작은 값도 13이고 평균도 13입니다. 서로 다른 숫자인 8과 13이라면 작은 값 8은 평균 10.5 이하입니다. 규칙이 매번 작은 합을 고르기 때문에 E 앞에 기다리는 시간에도 이 관계를 사용할 수 있습니다. 29. 9-1 앞부분 13분은 최적 시간 이내입니다 E를 맡기기 전에는 8, 7, 6, 5를 처리하도록 배정했으므로 총량은 26입니다. 두 기계의 평균은 26을 2로 나눈 13입니다. 우리가 고른 작은 합은 이 평균 이하입니다. 남은 E까지 포함하면 작업량은 30이 됩니다. 모든 작업 시간이 0 이상이므로 전체 총량은 앞서 읽은 총량보다 작아지지 않습니다. 따라서 앞서 계산한 평균 13은 전체 평균 15 이하입니다. 전체 평균 15는 최적 시간의 하한입니다. 작은 합에서 평균, 전체 평균, 최적 시간으로 차례로 비교하면 E 앞의 13분은 최적 시간 이하라는 결론이 나옵니다. 30. 9-1 E 자체의 4분도 최적 시간 이내입니다 이제 뒷부분인 E 자체의 4분을 보겠습니다. 어떤 배정을 선택하더라도 E를 한 번은 끝까지 처리해야 합니다. 왼쪽에 맡겨도 오른쪽에 맡겨도 같은 4분이 필요합니다. 작업을 두 기계에 나누어 동시에 처리할 수 없고, 작업 시간이 0 아래에서 시작하지도 않습니다. 따라서 가장 좋은 배정도 적어도 E의 길이인 4분은 걸립니다. 앞부분 13분이 최적 시간 이하라는 결론에 이어, 뒷부분 4분도 최적 시간 이하라는 결론을 얻었습니다. 31. 9-1 두 부분을 더하면 최적의 2배 이내입니다 E가 시작되기 전 13분은 최적 시간 이하이고, E 자체의 4분도 최적 시간 이하입니다. 두 비교를 더하면 13 더하기 4는 최적 시간 더하기 최적 시간 이하입니다. 왼쪽 합 17분이 바로 우리 배정의 전체 완료 시각입니다. 따라서 결과가 최적의 두 배 이내입니다. 여기서는 최적값이 정확히 15라는 사실을 이용하지 않았습니다. 어떤 배정에도 필요한 총량 기준과 작업 하나의 길이만 이용했습니다. 그래서 최적 배정을 직접 찾기 어려운 입력에도 같은 논리를 적용할 수 있습니다. 32. 9-1 입력의 맨 끝 작업이 가장 늦게 끝나지는 않을 수 있습니다 다른 입력에서도 같은 증명을 하려면 어느 작업을 고를지 분명히 해야 합니다. [10,1,1]을 읽으면 10은 왼쪽, 두 1은 오른쪽에 들어갑니다. 왼쪽이 10분, 오른쪽이 2분에 끝납니다. 전체 완료 시각을 정하는 작업은 맨 처음 입력된 10분짜리입니다. 따라서 증명에서 말하는 마지막 작업은 입력 배열의 마지막 원소를 뜻하는 표현으로 사용하지 않겠습니다. 완료 시각이 가장 늦은 작업을 고릅니다. 여기서는 그 작업의 앞부분이 0이고 자기 길이는 10입니다. 앞부분과 자기 길이로 나누는 방법은 그대로 적용됩니다. 33. 9-1 어떤 입력에서도 같은 비교가 성립합니다 입력의 크기와 숫자가 달라도 완료 시각이 가장 늦은 작업 하나를 고를 수 있습니다. 그 작업을 맡길 때 규칙은 두 합 중 작은 값을 골랐습니다. 작은 값은 당시 평균 이하이고, 당시까지 읽은 작업량은 전체 작업량 이하입니다. 그래서 그 작업이 시작되기 전 시간은 전체 작업량을 2로 나눈 값 이하입니다. 이 값은 최적 시간 이하입니다. 그 작업 자체의 길이도 최적 시간 이하입니다. 최적 배정도 그 작업을 끝까지 해야 하기 때문입니다. 두 부분을 더하면 어떤 입력에서도 결과가 최적 시간의 두 배 이하입니다. 빈 입력에서는 양쪽 합이 0이고 최적값도 0이어서 같은 결론이 성립합니다. 34. 9-1 다른 입력의 반환값도 직접 확인합니다 [3,2,4]를 넣으면 처음 3은 왼쪽에, 다음 2는 오른쪽에 들어갑니다. 마지막 4를 맡길 때 오른쪽 합 2가 왼쪽 3보다 작아서 오른쪽에 더합니다. 최종 3과 6 중 큰 6을 반환합니다. [4,3,2]에서는 왼쪽 4, 오른쪽 3 더하기 2가 되어 5입니다. 같은 작업도 입력 순서에 따라 결과가 달라질 수 있습니다. 시간 0인 작업은 배정해도 합을 늘리지 않습니다. 빈 목록은 반복을 하지 않아 0을 반환합니다. 각 작업에서 비교와 덧셈만 하고 전체 목록을 한 번 읽으므로 시간복잡도는 O(n)입니다. 입력 외에 두 합과 현재 시간 등 일정한 개수의 변수만 사용하므로 추가 공간은 O(1)입니다. 35. 9-2 이번에는 상자에 담은 무게를 크게 만듭니다 두 번째 문제는 상자 하나에 물건을 골라 담는 문제입니다. 물건마다 무게가 있고 상자에는 견딜 수 있는 무게 제한이 있습니다. 담은 물건의 무게를 더해서 제한 이하가 되게 해야 합니다. 그 안에서 가능한 한 무겁게 담고 싶습니다. 각 물건은 통째로 넣거나 빼는 선택을 합니다. 한 물건을 두 번 담거나 일부만 잘라 담을 수 없습니다. 같은 무게의 물건이 목록에 두 번 나오면 실제로 두 개가 있는 것입니다. 값으로 비교할 것은 무게뿐입니다. 먼저 작은 예제의 가장 좋은 선택을 직접 찾아보겠습니다. 36. 9-2 세 물건 중 무엇을 담을까요? 상자의 제한은 10kg입니다. A는 6kg이고 B와 C는 각각 5kg입니다. 물건 세 개 중 어느 것들을 담을지 골라 보겠습니다. A 하나를 담으면 6kg이고, A와 B를 함께 담으면 11kg여서 제한을 넘습니다. A와 C도 11kg입니다. B와 C는 숫자가 같지만 서로 다른 물건입니다. 둘을 하나씩 담으면 5 더하기 5로 10kg입니다. 따라서 물건 하나만 비교해서 가장 큰 6을 고르는 것보다 두 5를 함께 고르는 쪽이 더 무겁습니다. 무게의 조합을 생각해야 하는 이유입니다. 37. 9-2 가장 무거운 물건을 빼면 더 많이 담깁니다 왼쪽은 A 하나를 담은 선택이고 무게는 6kg입니다. 오른쪽은 B와 C를 담은 선택이고 무게는 10kg입니다. 두 상자는 같은 입력에서 가능한 선택을 각각 그린 것입니다. 실제로 사용할 선택 하나를 비교합니다. 제한이 10kg이므로 어떤 선택도 10보다 무거울 수 없습니다. 실제로 10을 만들었으니 이 예제의 최적값은 10kg입니다. 원래 목표는 이처럼 가능한 조합 중 가장 큰 무게 합을 찾는 것입니다. 이번에는 물건이 많아도 빠르게 실행할 수 있는 간단한 규칙을 만들겠습니다. 38. 9-2 물건이 많아지면 담을 조합도 많아집니다 물건 하나마다 넣을지 뺄지 두 가지를 고를 수 있습니다. 물건 세 개이면 조합은 여덟 개라 직접 비교하기 쉽습니다. 스무 개가 되면 약 백만 개, 마흔 개가 되면 약 1조 1천억 개가 됩니다. 동적 계획법으로 제한 무게별 상태를 계산할 수도 있지만, 물건 수와 무게 범위가 커질 때의 계산량을 고려해야 합니다. 이번 방법은 목록을 한 번 읽으면서 두 개의 후보를 만듭니다. 최적보다 덜 담을 수 있어도, 최적 무게의 절반 이상은 담는다는 보장을 확인하겠습니다. 39. 9-2 첫 후보는 들어가는 물건을 순서대로 담습니다 첫 번째 후보를 만드는 규칙입니다. 목록을 앞에서부터 읽고, 지금까지 담은 합에 이번 무게를 더해 봅니다. 더한 값이 상자 제한 이하이면 담습니다. 넘으면 그 물건을 건너뛰고 다음 물건을 확인합니다. [6,5,5]에서 처음 6은 들어가므로 담습니다. 다음 5를 더하면 11이 되어 넘습니다. 마지막 5도 똑같이 11이므로 못 담습니다. 첫 후보는 6kg입니다. 이 과정에서는 앞에서 담은 6을 꺼내 두 5로 바꾸는 계산을 하지 않습니다. 그래서 직접 찾은 최적값 10과 차이가 납니다. 40. 9-2 첫 후보 하나만 쓰면 결과가 작을 수 있습니다 첫 후보만으로 충분한지 다른 입력에서 확인하겠습니다. 물건은 1kg과 10kg이고 상자 제한은 10kg입니다. 첫 1kg은 들어가므로 담습니다. 다음 10kg을 더하면 11kg여서 건너뜁니다. 결과는 1kg입니다. 하지만 10kg짜리 하나만 담으면 제한을 꽉 채웁니다. 첫 후보의 1은 최적 10의 절반에도 못 미칩니다. 처음 들어온 작은 물건 때문에 나중의 큰 물건을 놓칠 수 있습니다. 이 경우를 보완하기 위해 두 번째 후보를 따로 만들겠습니다. 41. 9-2 한 물건만 담는 계획도 함께 비교합니다 두 번째 후보는 혼자 들어갈 수 있는 물건 중 가장 무거운 것 하나입니다. [1,10]에서는 10kg이 혼자 들어가므로 두 번째 후보는 10kg입니다. 첫 후보 1과 두 번째 후보 10을 비교해서 더 큰 10을 선택합니다. 그림 왼쪽과 오른쪽은 상자에 담는 서로 다른 계획입니다. 결과로 실제 사용할 것은 하나입니다. 무게 1과 10을 더해서 11을 만들지 않습니다. 이렇게 순서대로 담은 합과 가장 무거운 단일 물건을 함께 기억하면, 첫 후보가 작을 때 단일 물건 후보가 결과를 보완합니다. 42. 9-2 total과 single은 서로 다른 후보입니다 코드에서 사용할 두 변수의 뜻을 정하겠습니다. total은 처음부터 순서대로 담은 물건들의 무게 합입니다. single은 지금까지 확인한 물건 중 혼자 들어갈 수 있는 가장 무거운 물건의 무게입니다. single에 어떤 물건을 기록했다고 해서 그 물건을 total의 상자에도 넣는 것은 아닙니다. 두 변수는 다른 계획을 기록합니다. [1,10]에서는 total이 1인 상태여도 single은 10으로 바뀝니다. 마지막에 두 계획 중 더 큰 무게를 선택합니다. 선택 과정은 코드에서 max(total, single)로 씁니다. 43. 9-2 함수의 입력과 반환값을 정합니다 함수 이름은 approx_weight입니다. 첫 입력 weights에는 물건 무게를 순서대로 넣습니다. 둘째 입력 capacity는 상자가 버티는 무게 제한입니다. 각 무게와 제한은 양의 정수이고, 무게 목록은 비어 있을 수 있습니다. 물건 하나가 제한보다 무거우면 혼자도 담을 수 없으므로 두 후보에서 모두 제외합니다. 나머지 물건을 읽으며 total과 single을 만듭니다. 함수가 반환할 숫자는 두 후보 중 큰 무게입니다. [6,5,5]와 제한 10에서는 두 후보가 모두 6이라 6을 반환합니다. 최적 조합 5와 5는 나중에 결과의 품질을 비교할 때 사용합니다. 44. 9-2 한 물건을 읽을 때 확인하는 순서 이번 물건을 읽으면 가장 먼저 혼자 들어갈 수 있는지 확인합니다. 제한보다 무거우면 다음 물건으로 갑니다. 혼자 들어갈 수 있다면 지금까지 single에 저장한 값과 비교해 더 무거운 값을 남깁니다. 그다음 total에 추가할 수 있는지를 별도로 확인합니다. [1,10]의 10을 읽을 때 single은 10으로 바뀌지만 total에는 추가하지 못합니다. single을 갱신하는 조건과 total에 더하는 조건이 서로 달라야 이 결과가 나옵니다. 이제 이 순서를 전체 코드와 연결하겠습니다. 45. 9-2 Python 전체 답안 함수는 두 입력을 받고 total과 single을 0으로 만듭니다. for 문은 무게 하나를 weight에 넣습니다. 5행에서 상자보다 무거운지 검사하고, 그렇다면 6행의 continue로 다음 물건을 읽습니다. 7행과 8행은 single을 갱신합니다. 9행과 10행은 total에 물건을 추가할지 결정합니다. 모든 물건을 읽은 뒤 11행에서 두 변수 중 큰 값을 반환합니다. 코드 오른쪽으로 들어간 줄들이 어떤 반복과 조건에 속하는지도 함께 확인하겠습니다. 46. 9-2 두 후보는 처음에 한 번 0으로 만듭니다 1행에서 weights와 capacity를 받습니다. 2행과 3행에서 두 후보를 0으로 만듭니다. 아직 담은 물건도, 혼자 담을 후보도 확인하지 않았기 때문입니다. 이 초기화는 반복문 바깥에서 한 번만 합니다. 4행은 weights에서 무게를 하나씩 꺼내 weight에 넣습니다. 이름 끝에 s가 있는 weights는 전체 목록이고, weight는 현재 물건 하나의 무게입니다. 예제에서는 6, 첫 번째 5, 두 번째 5를 차례로 읽습니다. 같은 숫자 5도 실제로는 다른 두 물건입니다. 47. 9-2 혼자도 못 들어가는 물건은 continue로 건너뜁니다 5행의 크다 기호는 무게가 제한을 넘는지 확인합니다. 예를 들어 12kg를 제한 10kg 상자에 넣을 수 없으므로 조건이 참입니다. continue를 만나면 이번 물건의 나머지 계산을 건너뛰고 for 문에서 다음 무게를 읽습니다. 함수 전체가 끝나는 동작은 아닙니다. 무게가 정확히 10이고 제한도 10이면 이 조건은 거짓입니다. 그대로 아래로 내려가 두 후보의 검사에 참여합니다. 혼자도 못 넣는 물건만 먼저 제외하기 때문에 single이나 total에 사용할 수 없는 무게가 섞이지 않습니다. 48. 9-2 single에는 더 큰 단일 무게를 남깁니다 7행에서는 이번 무게 weight가 single보다 큰지 확인합니다. 앞의 검사에서 제한보다 무거운 물건을 제외했으므로, 여기 온 weight는 혼자 넣을 수 있는 무게입니다. 더 크면 8행에서 single을 그 값으로 바꿉니다. 처음 single이 0일 때 6을 읽으면 6으로 바뀝니다. 다음 5는 더 크지 않으므로 6을 유지합니다. 다른 입력 [1,10]에서는 single이 1에서 10으로 바뀝니다. 이 줄은 더 큰 물건 하나를 기억하는 동작이므로 이전 single에 무게를 더하지 않습니다. 49. 9-2 total에는 합이 제한 이하일 때만 더합니다 9행은 이번 물건을 기존 total에 더한 값을 제한과 비교합니다. 더한 값이 제한 이하이면 10행에서 total에 weight를 더합니다. 정확히 제한과 같아도 허용하므로 작거나 같다 기호를 사용합니다. total이 6일 때 5를 읽으면 11이 되어 담지 못합니다. 하지만 다음 물건이 4라면 10이 되어 담을 수 있습니다. 따라서 한 물건을 거절했다고 전체 반복을 멈추지 않습니다. total은 실제로 담기로 한 물건의 합이므로 이 검사 덕분에 항상 제한 이하로 유지됩니다. 50. 9-2 첫 6kg를 읽으면 두 후보 모두 6입니다 입력 [6,5,5]와 제한 10에 실제 값을 넣겠습니다. 첫 weight는 6입니다. 6은 10보다 크지 않으므로 continue를 지나 아래로 갑니다. single은 0이었으므로 더 큰 6으로 바뀝니다. total도 0이었습니다. 0에 6을 더하면 10 이하이므로 6을 담아 total이 6이 됩니다. 왼쪽 후보에는 첫 물건 하나를 담았고, 오른쪽 단일 후보도 같은 첫 물건입니다. 둘은 각각 대안이므로 같은 물건을 기억해도 괜찮습니다. 51. 9-2 다음 5kg는 total에 추가하지 못합니다 둘째 물건 weight는 5입니다. 혼자서는 들어가므로 두 후보의 검사를 받습니다. single에는 이미 6이 있으므로 더 작은 5로 바꾸지 않습니다. total에 더하면 6 더하기 5가 11이 되어 제한 10을 넘습니다. 따라서 total에도 추가하지 않고 6을 유지합니다. 두 후보가 모두 6인 상태로 다음 물건을 읽습니다. 거절한 5는 상자 밖에 남습니다. 52. 9-2 마지막 5kg도 못 담아 반환값은 6입니다 셋째 물건도 5입니다. 앞의 물건과 숫자는 같지만 목록에서 다른 물건을 읽는 것입니다. single과 비교하면 6보다 작고, total에 더하면 11이라 제한을 넘습니다. 따라서 두 변수는 계속 6입니다. 모든 물건을 읽었으므로 max(total,single)을 계산합니다. max(6,6)은 6이어서 최종 반환값은 6입니다. 손으로 찾은 최적 조합은 두 5를 담은 10이었습니다. 이번 규칙이 최적보다 덜 담는 예입니다. 53. 9-2 [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 물건 하나를 담는 계획을 택한 것입니다. 54. 9-2 모든 물건을 읽고 큰 후보 하나를 반환합니다 마지막 줄은 두 후보 중 큰 무게 하나를 반환합니다. [6,5,5]에서는 6과 6을 비교해 6, [1,10]에서는 1과 10을 비교해 10입니다. [6,5,4]에서는 6을 담고 5를 넘긴 뒤 4를 추가해 total이 10이고 single은 6이라 10을 반환합니다. 이 줄은 for 밖에 있습니다. 모든 물건을 확인한 뒤 실행해야 나중에 나오는 큰 단일 물건이나 남은 공간에 들어갈 작은 물건도 반영할 수 있습니다. 반환하는 값은 실제 선택할 한 계획의 무게입니다. 55. 9-2 C 전체 답안 C 함수는 무게 배열 weights와 물건 수 n, 제한 capacity를 받습니다. total과 single은 정수 변수로 만들고 0에서 시작합니다. 반복문은 i번째 물건의 무게를 weight로 읽습니다. 혼자도 못 들어가면 continue로 넘어갑니다. 나머지 물건에서는 single을 갱신한 뒤 total에 더할지를 검사합니다. 반복을 마치면 더 큰 변수를 반환합니다. Python의 마지막 max를 C에서는 조건문과 두 return으로 썼습니다. 다음 장에서 기호와 각 줄을 연결하겠습니다. 56. 9-2 C의 입력과 초기값을 읽습니다 함수 이름 앞의 int는 정수 결과를 돌려준다는 뜻입니다. const int weights[]는 정수 무게 배열입니다. n으로 배열 길이를 따로 받고, capacity로 제한을 받습니다. const가 붙어 있으므로 입력 목록을 바꾸지 않고 읽습니다. 2행과 3행은 total과 single이라는 정수 변수를 0으로 만듭니다. total과 single은 각각 제한 이하로 유지됩니다. total에 혼자 들어가는 weight를 더해 보는 중간 값도 최대 백만 더하기 백만으로 200만입니다. 사이트의 32비트 int 범위에서 처리할 수 있습니다. 57. 9-2 C의 i는 위치, weight는 물건 무게입니다 for 문은 i를 0으로 만들어 첫 물건에서 시작합니다. i가 n보다 작은 동안 반복하고, 반복 하나를 마칠 때마다 ++i로 위치를 하나 늘립니다. 물건 세 개이면 0번, 1번, 2번 위치를 읽고 i가 3일 때 끝납니다. 5행의 int weight = weights[i]는 지금 위치에 있는 무게를 정수 변수 weight에 저장합니다. 첫 위치에서는 6, 둘째에서는 5, 셋째에서도 5입니다. 위치 번호와 무게는 서로 다른 값이므로 이후 무게 조건에서는 weight를 사용합니다. 58. 9-2 C는 혼자 못 들어가는 물건만 먼저 넘깁니다 6행은 조건 뒤에 continue 한 문장이 붙은 if입니다. 이번 물건이 제한보다 크면 continue를 실행하고 다음 반복으로 갑니다. 7행 이하의 single과 total 계산은 하지 않습니다. 제한 이하이면 다음 줄로 진행합니다. 7행도 한 문장을 붙인 if입니다. 이번 무게가 기존 single보다 크면 single = weight를 실행합니다. 이 두 조건은 서로 다른 질문을 합니다. 첫째는 혼자 들어가는지, 둘째는 지금까지 본 단일 후보보다 무거운지를 확인합니다. 59. 9-2 C도 합을 확인하고 total을 늘립니다 8행은 total 더하기 weight가 제한 이하인지 검사합니다. 참이면 중괄호 안의 9행에서 total에 weight를 더합니다. 6에 5는 넘으므로 그대로 두고, 6에 4는 제한 10과 같으므로 10으로 바꿉니다. 이 조건이 거짓이어도 반복문은 끝나지 않습니다. 다음 위치를 읽어서 새 물건으로 같은 검사를 합니다. single에 저장한 후보 역시 그대로 남습니다. 따라서 [1,10]의 10을 total에 담지 못하더라도 single=10은 마지막 비교에 사용할 수 있습니다. 60. 9-2 C에서 큰 후보를 반환하는 두 줄 11행에서 반복 범위를 닫고, 12행에서 total이 single보다 크거나 같은지 확인합니다. 참이면 total을 반환하고 함수가 끝납니다. 거짓이면 다음 줄로 내려가 single을 반환합니다. 이 두 줄이 Python의 max와 같은 역할입니다. 6과 6이면 6, 1과 10이면 10을 반환합니다. 어느 물건도 담을 수 없으면 두 변수는 0으로 남아 0을 반환합니다. 모든 물건을 확인한 뒤 하나의 결과를 돌려준다는 위치도 Python과 같습니다. 61. 9-2 두 후보는 각각 실제로 담을 수 있습니다 근사 보장에 앞서, 반환값이 실제로 담을 수 있는 무게인지 확인하겠습니다. total은 합이 제한을 넘지 않을 때만 물건을 추가했습니다. 처음 0에서 시작했으므로 마지막에도 제한 이하입니다. 각 물건을 한 번씩만 읽어 같은 물건을 중복해서 담지 않습니다. single은 혼자 들어가는 물건만 비교해 가장 무거운 것을 남겼습니다. 이 물건도 제한 이하입니다. 마지막 max는 두 유효한 계획 중 하나를 선택하므로 실제로 상자에 담을 수 있습니다. 다음은 결과가 너무 작아지지 않는다는 보장입니다. 62. 9-2 최대화 문제의 보장은 최적 무게의 절반 이상입니다 첫 문제에서는 작게 끝낼수록 좋아서 결과가 최적의 두 배보다 커지지 않는다고 말했습니다. 이번에는 많이 담을수록 좋습니다. 따라서 결과가 최적 무게의 절반보다 작아지지 않는다는 관계를 보이겠습니다. 상자의 제한이 10이면 최적 무게도 10 이하입니다. 우리 결과가 5 이상이면 최적이 10이든 9든 그 절반 이상을 담은 것입니다. 하지만 최적이 4처럼 제한보다 훨씬 작을 수도 있으므로, 언제나 제한의 절반을 담아야 한다고 가정하지 않습니다. 가능한 물건이 적은 경우까지 나누어 확인하겠습니다. 63. 9-2 total이 상자 절반 이상이면 이미 충분합니다 첫 경우입니다. 마지막 total이 상자 제한의 절반 이상이면 어떻게 될까요? [6,5,5]와 제한 10에서는 total이 6입니다. 6은 제한의 절반인 5 이상입니다. 어떤 최적 선택도 상자의 제한 10을 넘지 못합니다. 그래서 최적 무게의 절반 역시 5 이하입니다. 마지막 결과는 total과 single 중 큰 값이라 total보다 작아지지 않습니다. 결과가 total 이상이고 total이 이미 최적의 절반 이상이므로 이 경우는 충분합니다. 64. 9-2 total이 작아도 무거운 single이 보완합니다 total이 제한의 절반보다 작은 경우를 보겠습니다. [3,8]과 제한 10에서 3은 담지만 8을 더하면 11이 되어 거절합니다. total은 3이고 single은 8입니다. 마지막에는 8을 택합니다. 첫 후보 3은 절반인 5보다 작지만, 추가하지 못했던 물건 8이 혼자 들어가므로 단일 후보가 결과를 보완했습니다. 이것이 어떤 입력에서도 성립하는지 보려면 물건을 거절한 당시 total과, 모든 물건을 읽은 뒤의 total 사이 관계를 확인해야 합니다. 65. 9-2 3kg에 못 더한 8kg를 혼자 담습니다 왼쪽 상자는 3kg를 먼저 담은 계획입니다. 옆의 8kg를 추가하면 11kg라서 제한을 넘습니다. 오른쪽은 8kg 물건 하나만 담는 다른 계획입니다. 상자 제한은 둘 다 10kg입니다. 오른쪽 8kg는 제한의 절반 5kg보다 무겁습니다. 그리고 혼자서는 제한 이하로 들어갑니다. 함수는 왼쪽 total 3과 오른쪽 single 8 중 큰 8을 반환합니다. 이제 예제의 숫자를 일반적인 조건으로 바꾸어 보겠습니다. 66. 9-2 거절한 당시 합은 최종 합보다 클 수 없습니다 입력 [3,8,1]과 제한 10을 보겠습니다. 처음 3을 담고, 8은 11이 되어 거절합니다. 그 뒤 1은 들어가므로 최종 total은 4입니다. 거절한 순간의 합 3과 마지막 합 4는 서로 다를 수 있습니다. 하지만 total은 물건을 담을 때 더하기만 합니다. 빼는 동작이 없고 모든 무게가 양수이므로 과거의 합은 마지막 합보다 클 수 없습니다. 따라서 마지막 합이 제한의 절반 미만이라면, 어떤 물건을 거절한 당시의 합도 절반 미만입니다. 이 관계 덕분에 거절한 순간을 이용해 일반적인 보장을 설명할 수 있습니다. 67. 9-2 작은 합에 절반 이하 물건은 반드시 들어갑니다 제한 10에서 현재 합이 3이라고 하겠습니다. 제한의 절반은 5입니다. 지금 합은 절반보다 작습니다. 여기에 절반 이하인 5kg 물건을 더하면 8kg라서 들어갑니다. 5보다 가벼운 물건도 당연히 들어갑니다. 일반적으로 절반보다 작은 수와 절반 이하인 수를 더하면 전체 제한보다 작습니다. 따라서 최종 total이 절반 미만으로 끝난 실행에서, 혼자 들어가는 물건을 추가하지 못했다면 그 물건의 무게는 절반보다 커야 합니다. 절반 이하 물건이라면 방금 계산대로 담을 수 있었기 때문입니다. 68. 9-2 못 담은 물건이 절반보다 크면 single에 남습니다 지금까지의 관계를 연결하겠습니다. 최종 total이 절반보다 작고, 혼자 들어가지만 추가하지 못한 물건이 있었다면 그 물건은 제한의 절반보다 큽니다. 이 물건은 혼자 들어가므로 single을 갱신하는 검사에 참여했습니다. single에는 지금까지 본 가장 무거운 단일 물건이 남습니다. 따라서 마지막 single은 이 물건의 무게 이상입니다. 결과는 total과 single 중 큰 값이어서 single 이상입니다. 결국 결과는 제한의 절반보다 크고, 최적 무게의 절반 이상이 됩니다. single을 먼저 갱신하고 total을 따로 검사한 코드의 순서가 여기서 역할을 합니다. 69. 9-2 거절이 없었다면 가능한 물건을 모두 담았습니다 마지막 경우입니다. total은 절반보다 작지만, 혼자 들어가는 물건을 한 번도 거절하지 않았다면 어떨까요? [1,2,15]와 제한 10에서는 1과 2를 모두 담습니다. 15는 혼자도 들어가지 않으므로 처음부터 제외합니다. total은 3입니다. 다른 선택도 15를 사용할 수 없고, 남은 1과 2는 이미 전부 담았습니다. 따라서 최적값도 3입니다. 제한의 절반 5까지 채우지 못했어도 가능한 물건을 모두 담았으니 최적입니다. 물건이 하나도 없거나 모두 제한보다 무거운 경우도 같은 논리로 최적값과 결과가 모두 0입니다. 70. 9-2 세 경우를 확인하면 절반 이상이 보장됩니다 total이 상자 절반 이상이면 그 자체로 최적의 절반 이상입니다. 절반 미만이면 혼자 들어가지만 추가하지 못한 물건이 있는지 봅니다. 있다면 그 물건은 절반보다 무겁고 single이 기억합니다. 없다면 가능한 물건을 모두 담았으므로 total이 최적입니다. 이 세 경우가 모든 실행을 포함합니다. 따라서 최적 조합을 미리 계산하지 않고도 우리 결과가 최적 무게의 절반 이상이라고 말할 수 있습니다. 이미 확인했듯 두 후보는 각각 실제로 담을 수 있으므로, 제한을 지키면서 이 무게를 얻습니다. 71. 9-2 큰 입력도 같은 검사로 처리합니다 물건이 여섯 개인 입력입니다. 제한 12보다 무거운 15는 continue로 넘어갑니다. 4와 7은 차례로 담겨 total이 11이 됩니다. 다음 3과 8과 2는 total에 더하면 제한을 넘어서 담지 않습니다. 하지만 8은 혼자 들어가고 기존 single 7보다 무거우므로 single은 8이 됩니다. 최종 두 후보는 11과 8이고 반환값은 11입니다. 직접 조합을 바꾸어 보면 7과 3과 2로 12를 만들 수 있습니다. 따라서 이 입력에서 최적은 12이고, 빠른 규칙의 결과는 11입니다. 규칙은 같은 조건을 물건마다 반복해 결과를 만들었습니다. 72. 9-2 최종 답과 경계 입력을 확인합니다 입력 [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)입니다. 반환한 무게는 실제로 담을 수 있고 최적의 절반 이상이라는 것까지 확인했습니다. 73. 9-3 모든 선에 닿도록 점을 고릅니다 이번 문제에서는 점과 선이 주어집니다. 점은 동그라미로 그리고, 선은 두 점을 이어서 그리겠습니다. 우리가 고를 대상은 동그라미입니다. 고른 동그라미는 초록색으로 칠하겠습니다. 고르는 점들은 서로 떨어져 있어도 됩니다. 지켜야 할 조건은 선마다 같습니다. 선의 양쪽 끝 중 적어도 한 점에 색이 있어야 합니다. 모든 선이 이 조건을 만족하면 정점 커버를 하나 찾은 것입니다. 가능한 정점 커버 중에서 점의 개수가 가장 적은 것을 찾고 싶습니다. 간단한 그림에서 어떤 선택이 가능한지 확인한 뒤, 빠르게 선택하는 규칙을 코드로 만들겠습니다. 74. 9-3 선마다 양쪽 끝을 확인합니다 점 네 개를 0번, 1번, 2번, 3번이라고 부르겠습니다. 번호는 점의 이름입니다. 선은 0번과 1번, 1번과 2번, 2번과 3번 사이에 하나씩 있습니다. 0–1 선은 0번이나 1번을 고르면 조건을 만족합니다. 두 점을 모두 골라도 됩니다. 1–2 선에서는 1번이나 2번, 2–3 선에서는 2번이나 3번을 골라야 합니다. 앞으로 조건을 만족한 선은 초록색, 아직 양 끝이 모두 비어 있는 선은 빨간색으로 표시하겠습니다. 지금은 점을 하나도 고르지 않아 세 선이 모두 빨간색입니다. 75. 9-3 1번 하나로는 마지막 선이 남습니다 1번 점 하나에 색을 칠했습니다. 0–1 선은 끝에 고른 1번이 있어서 초록색입니다. 1–2 선도 고른 1번이 붙어 있어 초록색입니다. 한 점이 여러 선에 붙어 있으면 그 선들을 함께 해결할 수 있습니다. 2–3 선의 끝은 2번과 3번입니다. 두 점 모두 비어 있으므로 이 선은 빨간색으로 남았습니다. 따라서 1번 하나만 고른 선택으로는 문제의 조건을 모두 만족하지 못합니다. 남은 선을 해결할 점을 더 골라야 합니다. 76. 9-3 2번을 더 고르면 세 선이 모두 해결됩니다 앞의 상태에서 2번을 더 골랐습니다. 이제 초록색 동그라미는 1번과 2번, 두 개입니다. 0–1 선은 1번 때문에 조건을 만족합니다. 1–2 선은 양 끝을 모두 골랐고, 2–3 선은 2번을 골랐기 때문에 조건을 만족합니다. 가운데 선처럼 양 끝을 모두 골라도 괜찮습니다. 각 선에서 요구하는 것은 적어도 한 끝점이기 때문입니다. 세 선이 모두 초록색이므로 1번과 2번은 유효한 정점 커버입니다. 고른 점의 개수는 2개입니다. 77. 9-3 0번과 3번을 고르면 가운데 선이 남습니다 이번에는 0번과 3번에만 색을 칠했습니다. 0–1 선은 0번을 골라서 해결되고, 2–3 선은 3번을 골라서 해결됩니다. 하지만 1–2 선의 양 끝은 1번과 2번입니다. 두 동그라미가 모두 비어 있어 가운데 선은 빨간색입니다. 0번부터 3번까지 번호가 넓게 떨어져 있어도, 실제로 색을 칠한 동그라미는 0번과 3번 두 곳입니다. 각 선에 직접 붙어 있는 점의 색을 확인합니다. 이 선택은 점 두 개를 썼지만 모든 선을 해결하지 못했습니다. 78. 9-3 0번과 2번을 골라도 해결됩니다 0번과 2번을 골랐습니다. 0–1 선은 0번에 붙어 있고, 1–2와 2–3 선은 2번에 붙어 있습니다. 따라서 세 선이 모두 초록색입니다. 앞에서 고른 1번과 2번 외에도 다른 정점 커버가 나왔습니다. 정답으로 쓸 수 있는 점의 조합은 여러 개일 수 있습니다. 이 선택도 두 점을 사용합니다. 어떤 번호를 골랐는지와 그 선택이 모든 선을 해결하는지를 함께 봅니다. 79. 9-3 1번과 3번도 이 그림에서는 가능합니다 1번과 3번을 고르면 0–1과 1–2는 1번이 해결하고, 2–3은 3번이 해결합니다. 이 조합도 두 점으로 모든 선을 해결합니다. 지금 그림에서는 0번과 2번을 골라도 되고, 1번과 3번을 골라도 됩니다. 이것은 방금 확인한 세 선의 연결에서 나온 결과입니다. 다음에는 선을 두 개 더 넣겠습니다. 같은 번호를 골랐을 때 새 선까지 모두 해결되는지 다시 확인하겠습니다. 80. 9-3 이제 선 두 개를 더한 그래프를 사용합니다 앞의 세 선에 0–2와 1–3을 추가했습니다. 점은 그대로 네 개이고, 선이 다섯 개가 되었습니다. 그림을 읽기 편하게 0번과 1번을 위에, 2번과 3번을 아래에 배치했습니다. 대각선은 1–2입니다. 각 선 옆의 번호가 그 선의 두 끝점입니다. 이제 0–1, 1–2, 2–3, 0–2, 1–3을 모두 해결해야 합니다. 앞의 그림에서 가능했던 선택도 새 선을 놓칠 수 있습니다. 이 다섯 선을 기준으로 최적 선택을 먼저 확인하고, 같은 그림을 입력으로 넣어 코드가 어떤 점을 고르는지 끝까지 따라가겠습니다. 81. 9-3 1번과 3번을 고르면 0–2가 남습니다 1번과 3번에 색을 칠했습니다. 앞의 세 선은 여전히 모두 해결됩니다. 추가한 1–3도 양 끝을 골랐으니 해결됩니다. 하지만 또 하나 추가한 0–2는 0번과 2번 모두 비어 있어서 빨간색입니다. 따라서 이 다섯 선에서는 1번과 3번만으로 부족합니다. 점 번호가 홀수인지 짝수인지로 결정하면 이 선을 놓칩니다. 입력으로 주어진 각 선의 두 끝을 확인해야 합니다. 82. 9-3 0번과 2번을 고르면 1–3이 남습니다 이번에는 0번과 2번을 골랐습니다. 0–1, 1–2, 2–3, 0–2는 해결됩니다. 오른쪽의 1–3 선을 보면 1번과 3번이 모두 비어 있습니다. 그래서 이 선은 빨간색으로 남습니다. 이 그래프에서는 짝수 번호만 고르는 선택도 부족합니다. 앞의 세 선짜리 그림에서 가능했던 조합을 그대로 가져오면 추가한 연결을 놓칩니다. 우리가 해결할 대상은 지금 그림의 다섯 선 전부입니다. 83. 9-3 1번과 2번이면 다섯 선을 모두 해결합니다 1번과 2번을 골랐습니다. 위쪽 0–1은 1번이 해결하고, 대각선 1–2는 양 끝을 모두 골랐습니다. 아래쪽 2–3은 2번이 해결합니다. 추가한 왼쪽 0–2도 2번이 해결하고, 오른쪽 1–3도 1번이 해결합니다. 다섯 선이 모두 초록색입니다. 따라서 두 점으로 해결할 수 있다는 사실을 확인했습니다. 두 점보다 더 적게 해결할 수 있는지도 확인하면 이 그림의 최적값을 알 수 있습니다. 84. 9-3 이 그래프의 최적값은 2입니다 노란색으로 표시한 0–1과 2–3 두 선에 집중하겠습니다. 0–1을 해결하려면 0번이나 1번이 필요합니다. 2–3을 해결하려면 2번이나 3번이 필요합니다. 첫 선에서 쓸 수 있는 점과 둘째 선에서 쓸 수 있는 점이 전부 다릅니다. 하나의 점으로 이 두 선을 함께 해결할 수 없어서 적어도 두 점이 필요합니다. 앞 장에서 1번과 2번 두 점으로 다섯 선 전체를 해결했습니다. 적어도 두 점이 필요하고, 실제로 두 점이면 됩니다. 그래서 이 작은 그래프의 최적값은 2입니다. 이후에는 같은 그래프에 빠른 선택 규칙을 적용하겠습니다. 85. 9-3 큰 그래프에서는 빠른 선택 규칙을 씁니다 점 네 개인 그림은 가능한 조합을 손으로 살펴보기 쉽습니다. 점마다 고르거나 빼는 두 선택이 있으므로 네 개이면 전체 조합이 16개입니다. 점이 30개이면 약 10억 개가 됩니다. 점이 많은 입력에서 모든 조합을 직접 확인하는 방식은 시간이 많이 듭니다. 이번에는 선 목록을 한 번 읽으면서 점을 정하는 빠른 방법을 사용하겠습니다. 이 방법이 고른 점의 수는 최적값보다 커질 수 있습니다. 대신 어떤 입력에서도 최적 개수의 두 배를 넘지 않는다는 한도를 확인하겠습니다. 방금 최적값이 2라고 확인한 작은 그림에서는 실제로 어떤 결과가 나오는지 바로 비교할 수 있습니다. 86. 9-3 한 선만 보면 한 끝점으로 충분합니다 0번 하나만 고르면 0–1 선은 조건을 만족합니다. 같은 0번에 붙은 0–2도 함께 해결됩니다. 하지만 나머지 선에는 아직 비어 있는 양 끝이 남아 있습니다. 한 선을 해결할 때 그 선의 두 끝 중 어느 점을 고르느냐에 따라 다른 선을 함께 해결하는 정도가 달라집니다. 모든 선을 고려해서 가장 좋은 한쪽을 찾는 것이 원래의 최적화 문제입니다. 이번 빠른 방법에서는 양쪽이 모두 비어 있는 선을 만날 때 두 끝을 함께 고르겠습니다. 87. 9-3 아직 비어 있는 선을 만나면 두 끝을 고릅니다 선택 규칙을 정하겠습니다. 처음에는 아무 점도 고르지 않습니다. 입력된 선을 앞에서부터 하나씩 읽고, 이번 선의 양 끝을 확인합니다. 두 끝을 모두 아직 안 골랐다면 두 점을 함께 고릅니다. 새 점을 두 개 골랐으니 개수에도 2를 더합니다. 어느 한쪽 끝이라도 이미 골랐다면 그 선은 조건을 만족합니다. 이때는 점을 더하지 않고 다음 선을 읽습니다. 한 번 고른 점은 이후에도 계속 고른 상태로 둡니다. 이 규칙이 전체에서 가장 적은 점을 고르지는 못할 수 있습니다. 양 끝을 함께 고르는 선택 덕분에 얻는 두 배 한도는 코드 실행을 확인한 다음 설명하겠습니다. 88. 9-3 한쪽을 계속 잘못 고르면 점을 많이 씁니다 양쪽을 함께 고르는 이유를 보기 위해 잠깐 다른 그림을 사용하겠습니다. 가운데 0번에서 바깥의 다섯 점으로 선이 뻗어 있습니다. 모든 선에 공통으로 붙은 0번만 고르면 전체를 해결하므로 최적값은 1입니다. 선을 하나씩 보면서 매번 바깥 점만 고른다고 해 보겠습니다. 첫 선에서는 1번, 다음 선에서는 2번을 고르는 식입니다. 결국 바깥 점 다섯 개를 모두 골라야 합니다. 한 선에서는 한쪽만으로 충분해도, 어느 쪽을 고르는지 계속 빗나가면 전체 개수가 커집니다. 89. 9-3 두 끝을 함께 고르면 이 그림은 두 점으로 끝납니다 같은 그림에 이번 규칙을 적용하겠습니다. 첫 선 0–1의 양 끝이 모두 비어 있으므로 0번과 1번을 함께 고릅니다. 두 점을 골랐습니다. 다음 선들도 모두 가운데 0번에 붙어 있습니다. 0번을 이미 골랐으므로 점을 더할 필요가 없습니다. 따라서 두 점으로 끝납니다. 최적은 0번 하나이고, 이번 규칙은 0번과 1번 두 개를 씁니다. 이제 선 다섯 개였던 원래 예제로 돌아가, 이 규칙을 함수로 작성하겠습니다. 90. 9-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개입니다. 91. 9-3 chosen은 점마다 고른 상태를 적는 목록입니다 점마다 고른 상태를 기억해야 하므로 chosen이라는 목록을 만듭니다. chosen의 0번 칸은 0번 점, 1번 칸은 1번 점의 상태를 담습니다. 대괄호 안의 숫자가 어느 칸을 읽을지 알려 줍니다. 예를 들어 chosen[1]은 1번 점의 상태입니다. False는 안 골랐다는 표시이고 True는 골랐다는 표시입니다. 처음에는 네 칸 모두 False입니다. 0번과 1번을 고르면 앞의 두 칸이 True로 바뀌고 나머지는 False로 남습니다. answer라는 변수에는 지금까지 고른 점의 개수를 담습니다. 처음에는 0이고, 두 점을 고른 뒤에는 2입니다. 92. 9-3 u와 v에는 지금 읽는 선의 두 점 번호를 넣습니다 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는 선이 바뀌어도 이어서 사용합니다. 93. 9-3 두 점 모두 안 골랐는지 확인하는 조건 조건을 읽기 전에 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가 되어 추가 선택을 하지 않습니다. 94. 9-3 Python 전체 답안 전체 함수입니다. 첫 줄의 def는 함수를 정의한다는 표시이고, cover_size가 함수 이름입니다. 괄호 안의 n과 edges는 호출할 때 받을 입력입니다. 둘째 줄은 점마다 상태를 기억할 목록을 만들고, 셋째 줄은 고른 개수를 0으로 정합니다. 넷째 줄부터 선을 하나씩 읽습니다. 다섯째 줄의 조건이 True일 때 여섯째부터 여덟째 줄을 실행해서 두 점의 기록과 개수를 바꿉니다. 모든 선을 읽으면 마지막 줄이 개수를 반환합니다. 코드 오른쪽으로 들어간 줄들은 어떤 반복이나 조건에 속하는지 보여 줍니다. 입력의 다섯 선을 넣어 한 단계씩 확인하겠습니다. 95. 9-3 먼저 네 점의 기록과 개수를 준비합니다 함수를 호출하면 입력 n에 4가 들어옵니다. [False]는 False 한 개가 있는 목록입니다. 여기에 n을 곱하는 문장은 False가 네 개 들어 있는 목록을 만듭니다. 이것을 chosen이라는 이름으로 저장합니다. 따라서 chosen의 네 칸은 모두 False입니다. 모든 점을 아직 안 골랐다는 뜻입니다. 다음 answer = 0은 고른 점의 개수를 0으로 저장합니다. 이제 chosen은 [False,False,False,False]이고 answer는 0입니다. 이 상태에서 첫 선 0–1을 읽기 시작합니다. 96. 9-3 for 문이 선 목록을 한 쌍씩 꺼냅니다 for u, v in edges는 edges에 있는 선을 앞에서부터 한 쌍씩 꺼내라는 문장입니다. 처음 꺼낸 [0,1]에서 앞 숫자 0은 u에, 뒤 숫자 1은 v에 들어갑니다. 이 두 번호로 아래의 조건과 선택을 실행합니다. 아래쪽 일을 마치면 다시 for 문으로 돌아와 다음 쌍 [1,2]를 읽습니다. 다섯 쌍을 모두 읽을 때까지 같은 과정을 반복합니다. 반복할 때마다 새로운 chosen을 만드는 줄은 없습니다. 함수 시작 때 만든 목록에 선택 기록을 계속 쌓습니다. 97. 9-3 첫 선 0–1은 양쪽 모두 False입니다 첫 선은 0–1입니다. u는 0이고 v는 1입니다. 그림에서 두 점은 모두 비어 있고 chosen의 두 칸도 False입니다. 각각에 not을 붙이면 True가 됩니다. True and True이므로 전체 조건은 True입니다. 조건 바로 아래로 들어가서 두 점을 골랐다고 기록할 차례입니다. 아직 이 화면은 선택하기 전입니다. 고른 점은 없고 answer도 0입니다. 다음 화면에서 여섯째, 일곱째, 여덟째 줄이 값을 어떻게 바꾸는지 보겠습니다. 98. 9-3 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를 더했는지 마지막에 모아서 확인하겠습니다. 99. 9-3 다음 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 하나뿐입니다. 100. 9-3 다음 2–3은 두 점 모두 아직 비어 있습니다 셋째 선은 2–3입니다. 2번과 3번은 아직 고르지 않아서 두 기록이 모두 False입니다. 조건은 True and True가 되므로 이번에는 아래 세 줄을 실행합니다. 지금까지 고른 점은 0번과 1번입니다. 이번에 고를 2번과 3번은 그 둘과 전혀 다른 점입니다. 만약 어느 한 점이라도 앞에서 골랐다면 그 칸이 True여서 방금 1–2처럼 조건이 False가 되었을 것입니다. 지금은 두 점 모두 비어 있으므로 추가할 수 있습니다. 101. 9-3 2번과 3번을 추가하면 answer는 4입니다 2번 칸과 3번 칸을 True로 바꾸고 answer에 2를 더합니다. 앞에서 2였으므로 이제 4입니다. 네 칸이 전부 True이고, 그림의 네 동그라미에도 모두 색이 들어갔습니다. 지금까지 두 점씩 추가한 선은 첫 선 0–1과 셋째 선 2–3입니다. 두 선의 끝점은 각각 0번, 1번과 2번, 3번으로 겹치지 않습니다. 이 성질은 모든 입력에서 같은 방식으로 유지됩니다. 남은 두 선도 읽은 뒤 그 이유를 정리하겠습니다. 102. 9-3 0–2는 이미 고른 점이 양쪽에 있습니다 넷째 선은 0–2입니다. 0번은 첫 선에서, 2번은 셋째 선에서 이미 골랐습니다. 두 기록 모두 True이므로 not을 붙이면 각각 False입니다. 조건은 False and False가 되어 아래의 추가 선택을 건너뜁니다. answer는 4로 남습니다. 원래 그래프에는 0–1과 0–2처럼 끝점을 공유하는 선들이 있습니다. 코드가 두 점을 새로 추가한 선들만 모았을 때에는 0–2가 포함되지 않습니다. 이미 고른 끝점이 있어서 조건을 통과하지 못하기 때문입니다. 103. 9-3 마지막 1–3도 추가 없이 넘어갑니다 다섯째 선은 1–3입니다. 1번은 첫 선에서 골랐고 3번은 셋째 선에서 골랐습니다. 두 칸이 모두 True이므로 이번 조건도 False입니다. 아무 점도 더하지 않고 answer를 4로 유지합니다. 이제 선 다섯 개를 전부 읽었습니다. 선택한 점은 0번, 1번, 2번, 3번입니다. 개수에 2를 더한 순간은 0–1을 읽었을 때와 2–3을 읽었을 때, 두 번이었습니다. 다음에는 이 최종 개수를 함수 밖으로 돌려줍니다. 104. 9-3 모든 선을 읽은 뒤 4를 반환합니다 입력에 더 읽을 선이 없으면 for 반복이 끝납니다. 마지막 return answer가 지금 answer에 들어 있는 4를 함수를 호출한 쪽으로 돌려줍니다. return의 들여쓰기는 for와 같습니다. 따라서 선을 하나 읽을 때마다 실행되는 범위 밖에 있습니다. return을 for 안으로 들여쓰면 첫 선만 읽고 함수가 끝나므로 주의해야 합니다. 이번 실행은 선 다섯 개를 다 읽었고, 두 번에 걸쳐 두 점씩 골라 최종 4를 반환합니다. 105. 9-3 같은 선택 규칙을 C로 작성합니다 방금 실행한 선택 규칙을 C로 작성한 전체 함수입니다. C에서는 선택 상태를 정수로 저장합니다. 0은 안 골랐다는 표시, 1은 골랐다는 표시로 사용하겠습니다. int는 정수를 담는 자료형입니다. 입력의 n은 점 수이고 m은 선 수입니다. 예제에서는 n이 4, m이 5입니다. C에서는 선 목록과 함께 그 길이 m도 받습니다. 반복할 선의 위치를 i에 담고, 그 행에서 두 점 번호 u와 v를 읽습니다. 같은 다섯 선을 넣으므로 고르는 점과 반환값도 Python에서 본 결과와 같습니다. 106. 9-3 C의 입력과 선택 기록을 준비합니다 함수 이름 앞의 int는 이 함수가 정수를 반환한다는 표시입니다. 입력 edges는 정수로 된 표이고 한 행마다 두 점 번호가 있습니다. 뒤의 [2]가 각 행의 칸 수를 나타냅니다. const는 함수 안에서 이 입력 표를 바꾸지 않겠다는 표시입니다. 문제에서 점은 최대 100개이므로 chosen에 정수 100칸을 준비했습니다. {0}으로 초기화하면 첫 칸과 나머지 칸이 모두 0이 됩니다. 예제에는 점이 네 개여서 0번부터 3번 칸을 사용합니다. 모든 칸을 한꺼번에 0으로 만들었으므로 여기서 n번 반복해서 초기화할 필요가 없습니다. answer도 0으로 시작합니다. 107. 9-3 C는 행 번호 i로 선을 하나씩 읽습니다 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입니다. 각 반복에서 이 두 점의 선택 기록을 확인합니다. 108. 9-3 C도 양쪽이 0일 때만 두 점을 추가합니다 C의 느낌표는 참과 거짓을 뒤집습니다. 숫자 0은 거짓으로 읽으므로 !0은 참이고, 선택 표시 1은 참으로 읽으므로 !1은 거짓입니다. &&는 양쪽이 모두 참일 때 참입니다. 첫 선에서는 chosen[0]과 chosen[1]이 모두 0입니다. !0 && !0이 참이라 중괄호 안에 들어갑니다. 두 칸을 1로 바꾸고 answer에 2를 더합니다. 둘째 선에서는 chosen[1]이 이미 1입니다. !1 && !0은 거짓이므로 중괄호 안을 건너뜁니다. 셋째 선에서 두 점을 더 고른 뒤에는 개수가 4가 됩니다. 109. 9-3 C도 반복문 밖에서 결과를 반환합니다 닫는 중괄호는 어느 범위가 끝나는지를 알려 줍니다. 11행의 중괄호는 if 안에서 두 점을 추가하는 범위를 끝냅니다. 12행의 중괄호는 선을 한 개 처리하는 반복 범위를 끝냅니다. 아직 읽을 선이 있으면 for로 돌아가 다음 행을 읽습니다. i가 m인 5에 도달하면 더 읽을 행이 없으므로 반복을 끝내고 13행의 return answer를 실행합니다. 저장된 4를 정수 결과로 돌려줍니다. 마지막 중괄호는 함수 전체의 끝입니다. 입력 다섯 행을 모두 읽고 반환한다는 흐름을 중괄호 위치에서 확인할 수 있습니다. 110. 9-3 반환할 때 모든 선이 해결되는 이유 함수가 만든 선택이 모든 선을 해결하는지 확인하겠습니다. 선을 읽었을 때 이미 고른 끝점이 있으면 그 선은 해결된 상태입니다. 양 끝을 모두 안 골랐다면 두 점을 골라서 그 선을 해결합니다. 어느 경우든 이번 선은 해결된 채로 다음 선으로 넘어갑니다. 그 뒤에 고른 점을 빼는 동작이 없으므로 앞에서 해결한 선도 계속 해결되어 있습니다. 이 과정을 입력의 모든 선에 수행하면 마지막에는 모든 선이 해결됩니다. 예제에서는 네 점을 전부 골랐고 다섯 선이 모두 초록색입니다. 따라서 반환한 4는 유효한 정점 커버의 크기입니다. 111. 9-3 같은 그래프에서 최적은 2, 이번 결과는 4입니다 앞에서 손으로 찾은 최적 선택은 1번과 2번이었습니다. 반면 코드는 첫 선에서 0번과 1번을 골랐습니다. 고른 점을 빼거나 다른 조합으로 바꾸지 않으므로 셋째 선에서 2번과 3번까지 추가했습니다. 결과는 네 점입니다. 가능한 최소는 두 점인데 이번 규칙은 네 점을 사용했습니다. 이 입력에서는 정확히 두 배입니다. 그래도 전체 선은 모두 해결하고, 계산은 선 목록을 한 번 읽으면 끝납니다. 이제 어떤 입력에서도 두 배를 넘지 않는 이유를 설명하겠습니다. 그 전에 선의 순서가 바뀌면 같은 규칙의 결과도 달라지는지 확인하겠습니다. 112. 9-3 1–2를 먼저 읽으면 반환값은 2입니다 같은 다섯 선을 1–2부터 읽어 보겠습니다. 첫 선의 양 끝이 모두 비어 있어 1번과 2번을 고릅니다. answer는 2입니다. 다음 0–1은 1번을 골라서 해결되고, 2–3과 0–2는 2번을 골라서 해결됩니다. 마지막 1–3도 1번에 붙어 있습니다. 추가 선택이 한 번도 없어 2를 반환합니다. 이 순서에서는 최적 선택과 같은 결과가 나왔습니다. 앞의 순서는 4개, 이번 순서는 2개를 골랐습니다. 어느 순서에서도 최적의 두 배를 넘지 않는 성질은 같습니다. 113. 9-3 두 점을 추가했던 선만 노란색으로 표시합니다 두 배 한도를 확인할 때는 처음의 입력 순서로 돌아가겠습니다. 두 점을 새로 골랐던 선은 0–1과 2–3이었습니다. 이 두 선만 노란색으로 표시했습니다. 다른 세 선도 원래 그래프에 그대로 있지만, 그 선을 읽을 때는 이미 고른 끝이 있어 개수를 늘리지 않았습니다. 노란 선 하나에서 점을 두 개씩 골랐습니다. 노란 선이 두 개이므로 코드가 고른 점은 네 개입니다. 이제 이 노란 선들만 보고, 어떤 정답이라도 최소한 몇 점이 필요한지 따져 보겠습니다. 먼저 두 노란 선의 끝점이 겹치지 않는 이유를 코드와 연결하겠습니다. 114. 9-3 앞의 끝점을 공유하면 새 두 점을 고를 수 없습니다 왜 노란 선들의 끝점은 겹치지 않을까요? 첫 노란 선에서 두 점을 고르면 두 칸이 True가 됩니다. 이후에 이 기록을 False로 되돌리는 코드가 없습니다. 따라서 나중 선이 그 점을 어느 쪽 끝에서 만나든 해당 조건에 not True가 들어갑니다. and의 한쪽이 False이면 전체가 False입니다. 그 선에서는 새 두 점을 고를 수 없습니다. 나중에 두 점을 새로 고르려면 양쪽 모두 처음 만나는 점이어야 합니다. 이 과정을 계속 적용하면 두 점을 추가했던 선들끼리는 끝점을 전혀 공유하지 않습니다. 예제에서 1–2, 0–2, 1–3이 노란 선에 포함되지 않았던 이유가 바로 이 조건입니다. 115. 9-3 노란 선 0–1에는 어떤 정답도 한 점이 필요합니다 0–1 선부터 보겠습니다. 어떤 정점 커버든 이 선을 해결해야 합니다. 그러려면 0번이나 1번 중 적어도 하나를 골라야 합니다. 다른 점만 골라서는 이 선의 양 끝이 계속 비어 있습니다. 이때 최적 선택이 0번을 골랐는지 1번을 골랐는지는 알 필요가 없습니다. 둘 중 적어도 한 점이 반드시 필요하다는 사실만 사용합니다. 그래서 이 노란 선에 최소 한 점이라고 적었습니다. 116. 9-3 노란 선 2–3에도 별도로 한 점이 필요합니다 둘째 노란 선 2–3도 해결해야 합니다. 이 선에는 2번이나 3번 중 적어도 한 점이 필요합니다. 앞의 0–1에서 쓸 수 있는 점은 0번과 1번이었고, 여기서 쓸 수 있는 점은 2번과 3번입니다. 서로 같은 점이 없습니다. 따라서 앞 선을 위해 고른 한 점을 이 선의 끝점으로도 사용할 수 없습니다. 이 선을 위해 별도로 최소 한 점을 더 골라야 합니다. 두 노란 선만 확인해도 어떤 정답이든 적어도 두 점을 쓴다는 사실을 알 수 있습니다. 117. 9-3 최적값을 몰라도 최소 2개라는 기준을 압니다 두 노란 선은 원래 그래프에 실제로 들어 있습니다. 나머지 선들까지 전부 해결하려는 정답은 이 두 선도 당연히 해결해야 합니다. 0–1에 한 점, 2–3에 별도로 한 점이 필요하므로 모든 선을 해결하는 최소 개수는 적어도 2입니다. 어떤 정답이든 반드시 필요한 최소 기준을 하한이라고 부릅니다. 여기서 얻은 하한은 2입니다. 이 단계에서는 최적 선택의 전체 모양을 찾지 않았습니다. 꼭 해결해야 하는 두 선만으로 최적값이 2보다 작을 수 없다는 사실을 얻었습니다. 118. 9-3 코드의 4개가 최적의 2배 이내인 이유 코드는 두 노란 선에서 두 점씩 골라 총 4개를 썼습니다. 최적값은 앞에서 확인한 하한 2 이상입니다. 최적값이 2 이상이면, 그 두 배는 4 이상입니다. 따라서 코드가 쓴 4는 최적값의 두 배를 넘지 않습니다. 이것이 최적값을 직접 구하지 않고 품질을 보장하는 계산입니다. 이 작은 예제는 최적값이 정확히 2여서 결과 4가 정확히 두 배입니다. 더 큰 입력에서도 두 점을 추가한 선의 수를 세면 같은 형태의 기준을 얻을 수 있습니다. 119. 9-3 그런 선이 세 개이면 같은 계산을 합니다 더 큰 그래프에서 두 점을 추가했던 선이 세 개였다고 해 보겠습니다. 그 세 선만 뽑아 그렸습니다. 코드의 조건 때문에 세 선의 끝점은 모두 다릅니다. 어떤 정답도 첫 선에서 한 점, 둘째 선에서 별도의 한 점, 셋째 선에서 또 한 점이 필요합니다. 따라서 최적값은 적어도 3입니다. 우리 코드는 선마다 두 점씩 총 6개를 골랐습니다. 최적값이 3 이상이면 그 두 배는 6 이상이므로, 결과 6은 역시 최적의 두 배 이내입니다. 120. 9-3 선이 k개이면 코드 2k개, 최적은 k개 이상입니다 마지막으로 개수에 이름을 붙이겠습니다. 두 점을 새로 추가했던 선의 수를 k라고 하겠습니다. 이 선들끼리는 끝점이 겹치지 않으므로, 어떤 정답도 선마다 별도의 한 점을 써야 합니다. 최적값은 k 이상입니다. 코드는 그 선 하나마다 새 점 두 개를 골랐으므로 총 2k개를 씁니다. 최적값이 k 이상이면 최적값의 두 배는 2k 이상입니다. 따라서 코드의 결과 2k는 최적값의 두 배 이내입니다. k가 2였던 예제에서는 4개, k가 3이면 6개라는 계산을 그대로 일반화한 것입니다. 121. 9-3 같은 선과 비어 있는 입력도 규칙대로 처리합니다 같은 선이 두 번 주어져도 선택 기록을 유지합니다. [0,1]을 처음 읽을 때 0번과 1번을 골랐다면, 다시 읽을 때는 두 기록이 이미 True입니다. 따라서 두 번째에는 더하지 않아 2를 반환합니다. 어떤 점이 어느 선에도 등장하지 않으면 그 점을 고르는 문장을 실행할 일이 없습니다. 선을 해결하는 데 필요하지 않은 점입니다. 선 목록 자체가 비어 있으면 for를 한 번도 실행하지 않고 처음 answer인 0을 반환합니다. 이때는 아무 점도 고르지 않아도 모든 조건을 만족하므로 최적값 역시 0입니다. 122. 9-3 계산 시간은 점 수와 선 수에 비례합니다 계산 시간을 세어 보겠습니다. Python은 처음 chosen에 점 수만큼 n칸을 준비합니다. 그다음 선이 m개이면 반복을 m번 합니다. 한 번의 반복에서 하는 일은 두 기록을 읽고, 필요하면 두 기록과 개수를 바꾸는 정도입니다. 따라서 준비 시간과 반복 시간을 합해 O(n+m)입니다. 점별 상태를 저장하는 공간은 O(n)입니다. 예제의 C 코드는 문제 제한이 최대 100점이라 100칸을 한 번에 초기화합니다. 정해진 제한 안에서 초기화한 뒤 선 m개를 읽습니다. 점 수에 맞춰 배열을 준비하는 일반적인 구현으로 보면 같은 O(n+m) 시간과 O(n) 공간입니다. 모든 점 조합을 비교하는 과정 없이 선을 한 번씩 읽습니다. 123. 9-3 입력 순서와 최종 반환값을 확인합니다 첫 실행의 목록은 [0,1], [1,2], [2,3], [0,2], [1,3]입니다. 첫 선과 셋째 선에서 두 점씩 골라 4를 반환합니다. 두 번째는 [1,2]를 맨 앞으로 옮긴 목록입니다. 처음 고른 1번과 2번이 나머지 모든 선을 해결해서 2를 반환합니다. 같은 선을 두 번 읽으면 처음에만 두 점을 골라 2이고, 빈 목록이면 0입니다. 이번 함수는 입력 순서대로 규칙을 실행해 실제 선택한 점의 개수를 돌려줍니다. 선택한 점은 모든 선을 해결합니다. 두 점을 추가했던 선들이 끝점을 공유하지 않는다는 성질로, 개수가 최적값의 두 배 이내라는 것도 확인했습니다. 124. 세 문제에서 구현하는 함수와 원래 목표 세 문제를 정리하겠습니다. 첫 문제의 원래 목표는 완료 시간을 최소화하는 것입니다. 다섯 작업에서 최적은 십오지만 지정 규칙의 결과는 십칠입니다. 둘째 문제는 제한 안에서 담은 무게를 최대화합니다. 육과 오와 오에서 최적은 십이고, 지정 함수의 결과는 육입니다. 셋째 문제는 모든 선을 덮을 점 수를 최소화합니다. 점 네 개와 선 다섯 개인 예제에서 최적은 2이고, 0–1부터 읽은 빠른 규칙의 결과는 4입니다. 이제 짧은 코드가 무엇을 해결하는지 설명할 수 있습니다. 먼저 조건을 모두 지킨 답을 만들고, 최적과 비교한 품질을 보장합니다. 실제로 더 빠른 계획이 필요한 상황에서 이런 방법을 선택할 수 있습니다. 정확한 최적해가 필요한 경우에는 앞에서 배운 탐색이나 동적 계획법과 계산 비용을 비교해서 선택하면 됩니다. 125. 9-4 추가 연습 · 모든 구역을 적은 팀으로 맡기기 마지막은 기말 범위 밖의 추가 연습입니다. 네 구역에 담당 팀을 정합니다. 에이는 영번과 일번, 비는 영번과 이번, 씨는 일번과 삼번에 갈 수 있습니다. 팀을 골랐을 때 그 팀이 갈 수 있는 여러 구역을 함께 맡길 수 있습니다. 모든 구역을 맡기되 선택한 팀 수가 가장 적어야 합니다. 잠깐 직접 두 팀을 골라 보세요. 비와 씨를 고르면 네 구역을 모두 맡길 수 있습니다. 한 팀이 네 곳을 다 갈 수는 없으므로 최적은 두 팀입니다. 이제 지금 남은 구역을 가장 많이 맡는 팀부터 고르면 어떤 결과가 나오는지 비교하겠습니다. 126. 9-4 아직 맡기지 않은 구역을 가장 많이 덮는 팀 이 함수에서 팀을 고르는 절차까지 정해져 있습니다. 처음에는 네 구역이 모두 남았습니다. 각 팀이 현재 남은 구역 가운데 몇 곳을 맡을 수 있는지를 세고 수가 가장 큰 팀을 고릅니다. 같은 수를 맡을 수 있으면 입력에서 먼저 나온 팀이 선택됩니다. 한 팀을 고른 다음에는 그 팀이 맡은 곳을 남은 목록에서 지웁니다. 그리고 남은 목록을 기준으로 다시 비교합니다. 모든 구역을 맡겼다면 고른 팀 수를 반환합니다. 아직 남은 구역이 있는데 어떤 팀도 새로 맡을 곳이 없으면 마이너스 1을 반환합니다. 모든 조합을 살피지 않고 지금 가장 많이 맡을 팀을 고르는 방식입니다. 127. 9-4 처음에는 세 팀이 모두 두 곳씩 맡습니다 표를 처음부터 한 번 볼게요. A가 갈 수 있는 0과 1이 모두 남아 있습니다. B가 갈 수 있는 0과 2도 모두 남아 있고, C가 갈 수 있는 1과 3도 모두 남아 있습니다. 오른쪽에 적힌 2, 2, 2는 첫 선택 직전에 세었던 새 구역의 수입니다. 셋 다 수가 같으니 입력에서 맨 먼저 나온 A를 고릅니다. 아래 구역 그림에 0번과 1번을 맡았다고 A를 썼습니다. 그래서 이제 남은 구역은 2번과 3번뿐입니다. 지금 중요한 건 각 팀의 원래 담당 범위는 그대로이고, 다음에 셀 기준인 남은 구역만 바뀌었다는 점입니다. 128. 9-4 두 번째에는 B와 C가 한 곳씩 맡을 수 있습니다 이번에는 담당 팀이 없는 2번과 3번만 셉니다. A가 갈 수 있는 0과 1은 둘 다 이미 맡겨서 A가 더할 수 있는 곳은 0개입니다. B는 0과 2에 갈 수 있지만 0은 이미 맡겼습니다. 그래서 B가 이번에 더할 수 있는 곳은 2번 한 곳입니다. C도 1과 3 중에서 3만 더할 수 있습니다. 새로 맡는 수가 1로 같아서 목록에서 먼저 나온 B를 선택합니다. 아래의 구역 그림에서 2번 칸에 B를 적었습니다. A가 맡았던 0번은 그대로입니다. 이제 담당 팀이 없는 칸은 3번뿐이니 다시 그 한 곳을 기준으로 셉니다. 129. 9-4 마지막 남은 3번을 C에게 맡깁니다 3번 한 곳을 남겨 두고 점수를 다시 셉니다. A는 0과 1만 갈 수 있어 새로 맡는 곳이 0개입니다. B도 0과 2만 갈 수 있으므로 0개입니다. C는 3번에 갈 수 있어서 새로 맡는 곳이 한 곳입니다. 그래서 이번에는 C를 고릅니다. 마지막 칸에 C를 적으니 아래에 비어 있는 구역이 하나도 없습니다. 이제 팀을 고른 횟수를 세면 됩니다. A를 한 번, B를 한 번, C를 한 번 선택했으니 3입니다. 다음 장에서는 같은 세 팀을 다른 순서로 넣어 결과를 비교합니다. 130. 9-4 처음 B를 고르면 두 팀으로 끝납니다 오른쪽에서 후보 순서만 바꿨습니다. 처음에 2곳으로 동점이 됐을 때 맨 앞의 B가 골라집니다. B가 0번과 2번을 맡아서 1번과 3번이 남습니다. 이번에는 C가 남은 두 곳을 다 맡을 수 있습니다. A는 1번 한 곳을 새로 맡을 수 있어서 C가 더 좋습니다. 따라서 두 번째 선택은 C이고, 두 팀으로 끝났습니다. 팀마다 맡을 수 있는 곳은 두 곳뿐입니다. 네 곳을 한 팀만으로 채우기는 불가능하고, B와 C 두 팀으로는 가능합니다. 그래서 가능한 최소가 2팀이라는 것도 확인했습니다. 왼쪽 결과는 3팀이므로 최적과 비교하면 3 나누기 2, 1.5배입니다. 이렇게 매번 지금 가장 많이 맡을 팀을 고르는 방법을 탐욕법이라고 부릅니다. 131. 9-4 팀이 맡을 수 있는 칸에 1을 씁니다 코딩테스트에서는 A라는 글자 대신 그 팀에 관한 정수 하나를 받습니다. 구역마다 칸 하나를 두고 맡을 수 있는 곳에는 1, 그 외에는 0을 씁니다. 이 문제는 구역 0을 맨 오른쪽 칸에 두기로 약속했습니다. 따라서 오른쪽에서 왼쪽으로 0번, 1번, 2번, 3번 순서입니다. A 팀은 0과 1을 맡을 수 있으니 오른쪽 두 칸만 1이고 다른 칸은 0입니다. 이 그림을 왼쪽부터 읽으면 0, 0, 1, 1입니다. 각 자리의 1이 뜻하는 수는 오른쪽부터 1, 2, 4, 8입니다. 그래서 오른쪽 두 칸이 켜진 A팀은 숫자로 2 더하기 1, 3으로 들어옵니다. 132. 9-4 3과 5는 서로 다른 두 구역을 뜻합니다 3과 5를 나란히 보세요. 3은 2와 1을 더한 값입니다. 2에 해당하는 1번 칸과 1에 해당하는 0번 칸이 켜져 있습니다. 5는 4와 1을 더한 값입니다. 그래서 2번 칸과 0번 칸이 켜져 있습니다. 값은 각각 3과 5인데, 켜진 칸의 수는 둘 다 두 개입니다. 10은 8과 2를 더한 값이라 3번과 1번을 담습니다. 0은 켜진 칸이 하나도 없어서 맡을 구역이 없는 팀입니다. 실제 입력 [3, 5, 10]은 앞에서 본 A, B, C의 목록입니다. 이렇게 여러 개의 표시를 한 정수에 모아 놓은 것을 여기서는 마스크라고 부르겠습니다. 133. 9-4 입력과 반환값 예제 엔은 구역 수입니다. 엔이 4이므로 네 칸을 사용합니다. 세츠는 팀의 배열입니다. 첫 정수 3은 A, 5는 B, 10은 C가 맡을 수 있는 구역을 뜻합니다. 배열에 원래 적혀 있던 순서가 동점을 해결할 기준입니다. 이 입력에서는 먼저 A, 그다음 B, 끝에 C를 골랐으니 돌려주는 값이 3입니다. 입력 [5, 10, 3]에서는 같은 구역을 맡길 팀을 같은 수만큼 받습니다. 맨 앞이 B로 달라져서, 앞서 확인한 대로 B와 C만 고릅니다. 어떤 팀도 맡을 수 없는 구역이 나오는 예도 따로 봅니다. 134. 9-4 처음에는 남은 구역의 네 칸이 모두 1입니다 지금부터 코드를 만들기 위해 남은 구역도 같은 방식으로 적어 보겠습니다. 처음에는 모든 곳이 남았으니 오른쪽 네 칸을 전부 1로 만들어야 합니다. 필요한 수는 1 더하기 2 더하기 4 더하기 8이라 15입니다. 코드에서 1 뒤에 작은 부호를 두 번 쓰고 4를 적으면, 1을 이진수에서 왼쪽으로 네 칸 민다는 뜻입니다. 자리를 밀면 오른쪽이 0으로 채워지고 정수 16이 됩니다. 거기에서 1을 빼면 오른쪽 네 칸이 모두 1인 15가 됩니다. 구역이 네 곳일 때만 쓰는 계산처럼 보여도, 4 자리에 엔을 넣으면 구역 수에 맞춘 초기 상태를 만들 수 있습니다. 135. 9-4 네 칸의 뜻을 그림 아래에 그대로 기록합니다 남은 구역 그림과 팀의 그림을 같은 번호 순서로 놓았습니다. 첫 줄은 2번과 3번이 남았다는 표시여서 왼쪽 두 칸이 1입니다. 둘째 줄은 B가 0번과 2번을 갈 수 있어 그 두 칸이 1입니다. 이제 칸마다 위아래를 맞춰 봅니다. 3번은 첫 줄만 1이라 제외됩니다. 2번은 둘 다 1이라 남습니다. 1번은 둘 다 0, 0번은 둘째 줄만 1이라서 남기지 않습니다. 마지막 줄에는 2번만 1입니다. 이것을 컴퓨터에서 한 번에 계산하는 기호가 앰퍼샌드 한 개입니다. 136. 9-4 이번에 필요한 수는 ‘1이 몇 개 있는가’입니다 B의 새 구역 표시는 숫자 4이고 C의 새 구역 표시는 8입니다. 8이 더 큰 수지만 그림에서는 둘 다 켜진 칸이 딱 하나입니다. 지금 고르려는 팀은 새 구역의 개수가 많은 팀이었습니다. 그래서 파이썬의 비트 카운트를 호출합니다. 정수에 들어 있는 1의 개수만 세어 주는 기능입니다. 4의 그림에서는 하나, 8의 그림에서도 하나를 반환합니다. 두 팀이 1로 같아졌으므로 입력에서 앞쪽인 B를 고릅니다. 위치를 담은 표시와 구역 수를 담은 숫자가 이렇게 이어집니다. 137. 9-4 맡길 팀을 고른 뒤 해당 칸을 0으로 바꿉니다 B를 골랐으니 이 팀이 맡아 줄 수 있는 구역은 남은 목록에서 지웁니다. 맨 위의 2번은 1이었는데, B가 갈 수 있는 곳이라 마지막 줄에서 0이 됩니다. 맨 위의 3번은 B가 갈 수 없어서 1로 남겨 둡니다. 0번은 B가 갈 수 있지만 이미 A에게 맡긴 곳이었습니다. 그래서 전에도 0, 후에도 0입니다. 결과적으로 3번 하나만 남고 정수로는 8입니다. 이 장면을 코드 한 줄로 쓰면 선택한 마스크의 해당 비트들을 리메이닝에서 끄는 연산이 됩니다. 138. 9-4 겹치는 칸에만 1을 남겨 계산합니다 A를 고른 직후에는 2번과 3번만 남아서 리메이닝의 네 칸이 1, 1, 0, 0입니다. B의 담당 구역은 2번과 0번이라 아래쪽은 0, 1, 0, 1입니다. 두 줄을 위아래로 놓고 같은 자리끼리 봅니다. 3번은 위에만 1이 있고, 0번은 아래에만 1이 있으므로 결과는 둘 다 0입니다. 2번에서만 양쪽이 모두 1이라 결과에 1이 남습니다. 앰퍼샌드 한 개는 이렇게 정수의 자리를 하나씩 비교하는 연산입니다. 결과의 네 자리는 0, 1, 0, 0이고, 정수로 읽으면 4입니다. 그 네 자리 중 1인 자리를 세면 이번에 B가 새로 맡을 수 있는 구역 수가 나옵니다. 2번 칸 한 곳만 1이어서 결과는 1입니다. 139. 9-4 선택한 팀의 구역을 남은 목록에서 지웁니다 B를 골랐으니 B가 갈 수 있는 칸을 남은 목록에서 끕니다. 물결표를 마스크 앞에 쓰면 그 정수의 비트가 뒤집힙니다. 표에서는 우리가 쓰는 오른쪽 네 칸만 봅니다. B의 마스크가 0, 1, 0, 1이니까 뒤집으면 1, 0, 1, 0입니다. 뒤집은 결과에서 0인 자리가 B가 담당할 수 있는 위치입니다. 이 표시와 선택 전 리메이닝을 앰퍼샌드로 묶습니다. 3번은 위쪽도 1이고 뒤집은 마스크도 1이라 계속 남습니다. 2번은 위가 1이었는데 뒤집은 마스크가 0이라 사라집니다. 0번은 이미 위에서 0이라서 계속 0입니다. 남은 구역은 3번 하나, 정수값은 8입니다. 오른쪽 네 칸 밖은 리메이닝 쪽에서 모두 0이므로 결과에 들어오지 않습니다. 140. 9-4 남은 구역을 맡을 팀이 없으면 −1입니다 첫 예제는 배열 [3, 6, 12]입니다. 3은 0과 1, 6은 1과 2, 12는 2와 3을 맡는 팀입니다. 처음에는 모두 두 곳씩이라 3을 먼저 고릅니다. 다음에는 남아 있는 2와 3을 모두 맡을 수 있는 12를 골라 두 번으로 끝납니다. 다음 예 [3]에서는 0과 1을 맡긴 뒤 2와 3이 남습니다. 같은 3을 다시 확인해도 새로 맡는 곳은 한 곳도 없습니다. 이 상태에서 멈추어 마이너스 1을 반환합니다. 팀 목록이 비어 있어도 처음부터 같은 상황입니다. 마지막 줄의 0은 빈 팀입니다. 맡을 수 있는 곳이 없으니 구역 0을 맡는 마스크 1을 골라 한 번에 끝납니다. 141. 9-4 Python 1~5행 · 이번 선택의 기록을 초기화 첫 줄은 구역 수와 팀 목록을 받습니다. 여러 구역을 한꺼번에 기록할 리메이닝은 처음에 15입니다. 카운트는 지금까지 몇 팀을 선택했는지 적는 값이므로 0에서 시작합니다. 네 번째 줄의 와일에는 리메이닝만 써 있습니다. 정수가 0이 아니면 참으로 읽어서, 남은 구역이 한 곳이라도 있을 때 반복을 실행합니다. 다섯 번째 줄은 베스트와 게인을 둘 다 0으로 시작합니다. 베스트는 이번에 가장 나은 팀의 마스크, 게인은 그 팀이 새로 맡을 수 있는 수입니다. 이전에 가장 좋았던 팀도 이번에 남은 구역에서는 점수가 달라질 수 있습니다. 따라서 반복 한 번을 시작할 때 둘을 새로 정합니다. 전체 횟수인 카운트는 바깥에 두어서 앞에서 고른 수를 계속 기억합니다. 142. 9-4 Python 6~9행 · 새 구역을 많이 맡는 팀 찾기 포 문에서 팀의 마스크를 하나씩 꺼냅니다. 마스크 앰퍼샌드 리메이닝으로 그 팀이 갈 수 있는 곳과 남은 곳이 겹치는 칸을 구합니다. 점 비트 카운트는 그 정수에서 1로 켜진 칸이 몇 개인지 돌려줍니다. 그 값이 애디드입니다. 예제에서 A를 고르고 나면 2와 3이 남습니다. A를 다시 검사할 때는 겹치는 곳이 없어 애디드가 0입니다. B는 2번 한 곳이 겹쳐 1이 나옵니다. 이전 게인 0보다 크니까 베스트에 B의 숫자 5를, 게인에 1을 씁니다. C에서 나온 애디드도 1입니다. 이미 기록한 1과 같아서 교체하지 않습니다. 그래서 들어온 순서에서 B가 먼저라는 규칙이 코드에 반영됩니다. 143. 9-4 Python 10~14행 · 진행이 되면 남은 곳 갱신 팀을 모두 훑은 다음에 게인을 봅니다. 아직 구역이 남았는데 게인이 0이면 누구를 골라도 새로 맡길 곳이 없습니다. 그래서 더 반복하기 전에 마이너스 1을 돌려줍니다. 게인이 1 이상이면 베스트에 고를 팀의 마스크가 들어 있습니다. 리메이닝에 앰퍼샌드 물결표 베스트를 적용해 그 팀이 맡는 구역을 지웁니다. 그런 다음 팀을 한 번 골랐으니까 카운트를 하나 늘립니다. 표의 첫 번째 줄에서는 15였던 리메이닝이 12, 카운트가 1이 됩니다. 세 번째 줄까지 가면 리메이닝이 0이 되고 카운트는 3입니다. 다음 와일의 조건이 거짓이라 밖으로 나가서 3을 반환합니다. 144. 9-4 Python 전체 풀이 전체를 위에서부터 읽으면 먼저 모든 곳이 남아 있다고 표시합니다. 남은 구역이 있는 동안, 모든 팀을 살펴 새로 맡는 곳이 가장 많은 팀을 기억합니다. 고를 수 있는 팀이 없으면 마이너스 1, 있으면 맡긴 구역을 지운 다음 고른 수를 하나 올립니다. 새로 선택한 팀은 남은 곳을 한 곳 이상 줄입니다. 따라서 계속 끝없이 반복될 일도 없습니다. 전부 맡기는 데 성공하면 리메이닝이 0이 되어 빠져나옵니다. 예제 숫자 15, 12, 8, 0을 각각 구역 표시로 바꿔 보면서, 화면에서 담당자를 채웠던 과정과 값이 같은지 확인해 보세요. 145. 9-4 C에서는 오른쪽 끝 1을 하나씩 읽습니다 파이썬의 비트 카운트와 같은 일을 씨에서 직접 만들어 보겠습니다. 정수 5는 그림에 보이는 것처럼 이진수 1, 0, 1입니다. 1이라는 정수는 맨 오른쪽만 1이므로, 5와 1을 앰퍼샌드로 묶으면 오른쪽 끝에 있던 1만 꺼낼 수 있습니다. 그 결과를 개수에 더하면 지금까지 하나입니다. 오른쪽으로 한 칸 밀면 끝에 있던 숫자가 사라져 1, 0만 남습니다. 두 번째로 꺼낸 숫자는 0이라 개수는 그대로입니다. 또 한 칸 밀면 1 하나가 남으니 마지막으로 1을 더합니다. 다시 밀었을 때 엑스가 0이면 남은 자리에는 더할 1이 없습니다. 이렇게 5에서 1 두 개를 셉니다. 146. 9-4 C 보조 함수 count_bits 이 보조 함수는 입력 정수 엑스에서 1인 자리의 수를 셉니다. 첫 줄의 스태틱은 이 소스 파일 안에서만 이 함수 이름을 쓰겠다는 표시입니다. 둘째 줄에서 카운트를 0으로 두고, 엑스가 0이 아닐 동안 와일을 반복합니다. 안에서 앰퍼샌드 1은 오른쪽 끝에서 0이나 1만 꺼냅니다. 카운트에 더한 다음에는 엑스를 오른쪽으로 한 칸 밀어 바뀐 값을 엑스에 다시 저장합니다. 5로 호출했다면 엑스가 5, 2, 1, 0 순으로 바뀌고 카운트는 2가 됩니다. 원래 값이 0이라면 반복을 한 번도 하지 않아서 곧바로 0을 돌려줍니다. 아래의 전체 함수 앞에 이 보조 함수를 둡니다. 147. 9-4 C 1~6행 · 팀 수 m을 받아 배열을 읽습니다 씨에서도 처음은 파이썬과 같습니다. 다만 배열 길이를 알 수 있도록 엠을 따로 받습니다. 이 예에서 엔은 구역 수 4이고 엠은 팀 수 3입니다. 오른쪽 비트를 네 개 켜는 계산에는 엔을 씁니다. 배열을 몇 칸 읽을지 정하는 포 문에는 엠을 씁니다. 와일을 한 번 시작하면 이번 선택에 필요한 베스트와 게인을 0으로 둡니다. 그 안에서 아이가 0, 1, 2로 움직이면서 세츠에 있는 3, 5, 10을 읽습니다. 작업 배정에서 씨로 배열의 길이를 받았던 것과 같은 이유입니다. 엔과 엠을 바꿔 쓰면 배열에 없는 항목까지 읽을 수 있으니 어떤 개수인지 구분해 둡니다. 148. 9-4 C 7~12행 · 겹치는 곳을 센 뒤 후보를 갱신 일곱 번째 줄을 괄호 안부터 읽어 보세요. 세츠 아이와 리메이닝을 앰퍼샌드로 묶어 겹치는 구역의 표시를 얻습니다. 2번과 3번이 남은 예에서 B를 검사하면 겹치는 구역은 2번입니다. 그 위치의 1을 정수로 읽으면 4입니다. 카운트 비츠에 4를 보내면 1이 한 자리라 1이 돌아옵니다. C에서는 3번 하나가 겹쳐 마스크가 8이고, 카운트 비츠의 결과는 역시 1입니다. 두 마스크 4와 8에서 각각 1의 개수를 세어 비교합니다. 애디드가 1인 B를 먼저 기록하고, C의 애디드도 1이므로 베스트에는 B가 남습니다. 149. 9-4 C 13~18행 · 남은 곳을 지우고 횟수를 반환 포 문을 돌고 게인이 0이라면 아무 팀도 새로 맡을 곳이 없다는 뜻입니다. 이때는 바로 마이너스 1을 돌려줍니다. 게인이 양수라면 선택한 팀이 맡을 구역을 리메이닝에서 끕니다. 예제에서 베스트가 5인 경우 B가 맡는 곳을 빼면 12에서 8로 바뀝니다. 카운트 앞에 더하기가 두 개 있으면 그 변수에 1을 더하라는 뜻입니다. B를 골랐으니 고른 팀이 하나 늘었습니다. 남은 구역이 0이면 반복을 나오고 카운트를 반환합니다. 앞에서 작성한 카운트 비츠는 켜진 칸의 수를 알려 주고, 지금 이 함수는 팀을 선택한 횟수를 알려 줍니다. 두 함수가 돌려주는 숫자의 의미를 구분해 주세요. 150. 9-4 C 전체 풀이 (1/2) 씨 전체 풀이에서 앞부분은 이번에 고를 팀 후보를 찾을 때까지입니다. 카운트 비츠 보조 함수는 이 함수보다 앞에 놓습니다. 메인 함수에서는 리메이닝을 초기화하고, 바깥 와일 한 번마다 모든 팀을 확인합니다. 새 구역이 가장 많은 팀 하나를 베스트로 기억합니다. 12행의 중괄호는 팀 하나씩 보는 포 문이 끝난 자리입니다. 아직 바깥쪽 와일은 끝나지 않았습니다. 다음 장에는 선택을 실제로 적용하고, 다 맡겼을 때 어떤 값을 돌려주는지 이어집니다. 151. 9-4 C 전체 풀이 (2/2) 13행부터 읽습니다. 고를 수 있는 팀이 없으면 함수가 마이너스 1을 반환합니다. 고를 수 있으면 남은 구역과 선택 횟수 두 값을 바꿉니다. 16행의 중괄호로 바깥 와일이 끝납니다. 그래서 17행의 리턴은 네 구역이 전부 맡겨졌을 때 실행됩니다. 비트 수의 범위도 확인해 두겠습니다. 최대 구역 수는 스무 곳이라 1을 가장 멀리 밀어도 왼쪽으로 스무 칸입니다. 수업 환경의 32비트 인트는 그 값과 그보다 작은 마스크를 담을 수 있습니다. 이번 문제 범위에서는 앞에서 본 정수 연산을 그대로 써도 됩니다.