무엇을 만드나
가장 좋은 자리를 찾으려면 다 놓아 봐야 합니다.
주어진 문제
5×5 격자에 칸마다 캘 수 있는 광석의 양이 적혀 있습니다. 한 번에 3×3만큼 캘 수 있는 기계를 어디에 놓아야 가장 많이 캐는지 찾아 그때의 합을 내놓는 프로그램을 만듭니다.
이런 격자가 주어집니다
12 34 11 20 15 22 45 67 12 8 31 18 9 44 27 5 10 33 21 19 40 2 14 50 3
수업에서 원리를 확인하려고 지어낸 값입니다. 실제 광산 자료가 아닙니다.
눈으로 큰 숫자만 따라가면 답이 나올 것 같지만 언제나 그렇지는 않습니다. 큰 수가 든 자리보다 고만고만한 수 아홉 개가 모인 자리의 합이 더 클 수 있기 때문입니다. 결국 놓을 수 있는 모든 자리를 다 더해 보는 수밖에 없습니다. 가능한 경우를 빠짐없이 확인하는 완전 탐색을 격자 위에서 해 봅니다.
| 단계 | 여기서 답할 질문 |
|---|---|
| 1 요구 분석 | 격자와 기계의 크기가 정해져 있는가, 무엇을 내놓는가 |
| 2 설계 | 기계를 놓을 수 있는 자리가 몇 개인가 |
| 3 구현 | 반복을 몇 겹으로 쌓아야 하는가 |
| 4 테스트 | 가장 큰 값이 정말 그것인지 어떻게 확인하는가 |
먼저 개발 문서 양식을 내려받으세요
읽기만 하지 말고 직접 채워 보세요. 단계마다 자기 답을 적어 두면 그 기록이 요구 사항 명세서이자 설계서가 됩니다. 답을 보기 전에 먼저 적어 봅니다.
요구 분석과 설계는 언어와 상관없습니다. 두 양식의 앞부분은 같고, 구현을 적는 자리만 언어에 맞춰 다릅니다. 수업에서 쓰는 언어에 맞는 것을 받으면 됩니다. 이 강의노트의 코드 예시는 파이썬으로 되어 있습니다.
1단계 · 무엇을 만들 것인가
「가장 많이 캐는 곳」은 무엇을 내놓으라는 말일까요?
되물어야 할 것들
- 합을 내놓나요, 자리를 내놓나요? 둘 다인가요
- 가장 좋은 자리가 여럿이면? 합이 같은 자리가 둘일 수 있습니다
- 기계가 격자 밖으로 나가도 되나요? 절반만 걸치는 자리는요
- 격자 크기가 늘 5×5인가요? 기계는 늘 3×3인가요
- 음수가 들어올 수 있나요?
정리한 요구 사항
- 격자는 5줄로 입력받는다. 한 줄에 정수 다섯 개를 공백으로 띄운다.
- 기계 크기는 3×3으로 고정한다.
- 기계는 격자 안에 온전히 들어가야 한다. 밖으로 걸치는 자리는 세지 않는다.
- 가능한 모든 자리 중 합이 가장 큰 값 하나를 내놓는다.
- 자리는 내놓지 않는다. 합이 같은 자리가 여럿이어도 값은 하나이므로 문제되지 않는다.
- 값은 0 이상이 들어온다고 본다.
5번이 문제를 훨씬 쉽게 만듭니다
자리까지 내놓기로 했다면 「합이 같은 자리가 둘이면 어느 쪽?」을 정해야 합니다. 합만 내놓기로 하면 그 물음이 아예 사라집니다. 요구 사항을 어떻게 정하느냐가 프로그램의 어려움을 정합니다.
요구 사항 6번에서 값이 0 이상이라고 정했습니다. 만약 음수가 들어올 수 있다면, 가장 큰 값을 찾는 방법에서 무엇을 조심해야 할까요?
2단계 · 놓을 자리가 몇 개인가
5칸 위에 3칸짜리를 놓으면 몇 자리가 나올까요?
| 토막 | 무엇을 정하는가 |
|---|---|
| 입력 | 5줄 × 5개의 정수 |
| 처리 | 기계를 놓을 수 있는 모든 자리에서 아홉 칸을 더하고, 가장 큰 값을 남긴다 |
| 출력 | 가장 큰 합 하나 |
기계의 왼쪽 위 모서리만 정하면 된다
기계 크기가 정해져 있으니 왼쪽 위 모서리가 어디인지만 정하면 나머지 여덟 칸은 따라옵니다. 그러니 모서리를 놓을 수 있는 자리가 몇 개인지만 세면 됩니다.
가로로 보면, 모서리를 인덱스 0 · 1 · 2 칸에는 놓을 수 있지만 인덱스 3에 놓으면 기계가 격자 밖으로 나갑니다. 그러니 5 − 3 + 1 = 3가지입니다. 세로도 같으므로 모두 3 × 3 = 9자리를 확인하게 됩니다.
가장 큰 값을 남기는 방법
아홉 개의 합을 모두 어딘가에 담아 두었다가 나중에 고를 필요가 없습니다. 지금까지 본 것 중 가장 큰 값 하나만 들고 다니면 됩니다. 새 합이 나올 때마다 들고 있던 것보다 크면 바꿔 들고, 아니면 버립니다. 끝까지 돌고 나면 손에 남은 것이 답입니다.
푸는 순서
- 다섯 줄을 받아 격자로 담는다.
- 가장 큰 값을 0으로 놓는다.
- 모서리의 행을 0부터 2까지 반복한다.
- 그 안에서 모서리의 열을 0부터 2까지 반복한다.
- 합을 0으로 놓고, 모서리에서 시작해 세 줄 세 칸을 더한다.
- 그 합이 들고 있던 값보다 크면 바꿔 든다.
- 반복이 다 끝나면 들고 있는 값을 내놓는다.
합을 0으로 되돌리는 자리가 중요합니다
5번에서 합을 0으로 놓는 일이 자리마다 새로 일어나야 합니다. 이 줄이 반복 밖으로 나가면 아홉 자리의 합이 전부 쌓여 말도 안 되게 큰 값이 나옵니다. 반대로 2번의 「가장 큰 값」은 반복 밖에 있어야 합니다. 안에 있으면 돌 때마다 지워져 마지막 자리의 합이 답이 되어 버립니다. 두 줄의 자리가 정반대라는 것을 눈여겨보세요.
격자가 7×7이고 기계가 3×3이라면 확인할 자리가 몇 개일까요? 설계에서 쓴 식을 그대로 대 보세요.
3단계 · 파이썬으로 옮기기
반복이 네 겹으로 쌓입니다.
먼저 스스로 적어 본 뒤에 코드를 보세요.
자리를 고르는 반복 둘 안에 아홉 칸을 더하는 반복 둘이 들어갑니다.
설계에서 말한 목록은 파이썬의 리스트([ ])이고, 목록 안의 목록은 리스트 안에 리스트를 담은 것입니다.
광산.기본.py
# 다섯 줄을 받아 5x5 격자로 담는다
grid = []
for _ in range(5):
grid.append(list(map(int, input().split())))
best = 0
# 3x3 상자를 놓을 수 있는 왼쪽 위 자리는 3x3가지다
for i in range(3):
for j in range(3):
total = 0
# 그 자리에서 세 줄, 세 칸을 더한다
for r in range(i, i + 3):
for c in range(j, j + 3):
total += grid[r][c]
if total > best:
best = total
print(best)목록 안에 목록을 담는다
한 줄이 다섯 개짜리 목록이고, 그런 줄이 다섯 개 모여 격자가 됩니다. 그래서 칸 하나를 꺼내려면 인덱스를 두 번 대야 합니다. 먼저 몇째 줄, 그다음 그 줄의 몇째 칸입니다. 순서를 바꿔 대면 엉뚱한 칸이 나옵니다. 이 격자는 정사각형이라 멈추지 않고 틀린 답을 내므로 더 알아채기 어렵습니다.
반복이 네 겹인데 몇 번 도나
바깥 둘이 9자리, 안쪽 둘이 자리마다 9칸이니 모두 81번 더합니다. 네 겹이라고 무섭게 많은 것은 아닙니다. 다만 격자가 커지면 빠르게 늘어납니다. 「격자가 커지면」 과제에서 직접 계산해 보세요.
안쪽 반복의 범위가 모서리에서 시작해 세 칸입니다. 만약 0부터 세 칸으로 적으면 어떻게 될까요? 어느 자리를 계속 더하게 될까요?
4단계 · 넣어 보고 확인하기
답이 하나뿐인 프로그램은 검산이 어렵습니다.
답을 미리 아는 격자를 일부러 만들어 넣어 봅니다. 나온 숫자 하나가 맞는지 눈으로는 알 수 없기 때문입니다.
| 넣은 격자 | 나와야 할 결과 | 무엇을 보려는 값인가 |
|---|---|---|
| 모든 칸이 1 | 9 | 아홉 칸을 제대로 더하는지 |
| 모든 칸이 0 | 0 | 가장 큰 값의 시작이 0이어도 되는지 |
| 왼쪽 위 3×3만 1, 나머지 0 | 9 | 첫 자리(0, 0)를 확인하는지 |
| 오른쪽 아래 3×3만 1, 나머지 0 | 9 | 마지막 자리(2, 2)까지 가는지 |
| 문제에 주어진 격자 | 260 | 실제 값으로 확인 |
결과가 어긋났다면 여기부터 봅니다
- 말도 안 되게 큰 값이 나온다 — 합을 0으로 되돌리는 줄이 반복 밖에 있습니다
- 오른쪽 아래만 1인 격자에서 9보다 작게 나온다 — 자리 반복 범위가 짧습니다. 인덱스 2 자리까지 가야 합니다
- 없는 자리를 찾다가 멈춘다 — 자리 반복이 인덱스 3 이상까지 가고 있습니다. 기계가 격자 밖으로 나갑니다
- 답이 마지막 자리의 합과 같다 — 가장 큰 값을 반복 안에서 0으로 되돌리고 있습니다
- 가로세로가 뒤집힌 것 같다 — 칸을 꺼낼 때 줄 번호와 칸 번호 순서를 봅니다
가장 큰 값이 정말 260인지 어떻게 아나
프로그램이 260을 내놓았다고 그것이 최댓값이라는 보장은 없습니다. 확인하려면 아홉 자리의 합을 모두 내놓게 해서 눈으로 세어 보면 됩니다. 답 하나만 내놓는 프로그램을 확인할 때 자주 쓰는 방법입니다. 중간 값을 잠깐 다 보이게 만들어 보는 것입니다.
「모든 칸이 1」인 격자로는 잡히지 않는 실수가 있습니다. 어떤 자리에서 더하든 답이 9로 같기 때문입니다. 어떤 실수가 안 잡힐까요?
더 해 보기
고정해 둔 크기를 풀어 봅시다.
격자와 기계 크기를 입력받는다
5와 3을 고정한 것을 풀어 봅니다. 설계에서 쓴 「격자 − 기계 + 1」 식이 그대로 쓰입니다. 기계가 격자보다 크면 어떻게 할지도 정해야 합니다.
가장 좋은 자리도 함께
요구 사항 5번을 풀어 모서리 자리까지 내놓게 합니다. 합이 같은 자리가 둘일 때 어느 쪽을 고를지를 먼저 요구 사항에 적어야 합니다.
음수를 허용한다
요구 사항 6번을 풀면 가장 큰 값을 0으로 시작하는 것이 틀리게 됩니다. 모든 합이 음수면 답이 0으로 나와 버립니다. 무엇으로 시작해야 할까요?
격자가 커지면
100×100 격자에 10×10 기계라면 몇 번을 더하게 될지 계산해 보세요. 겹치는 칸을 다시 더하고 있다는 것을 알아차렸다면, 더 빠른 방법이 있다는 뜻입니다.
「격자가 커지면」 과제의 「겹치는 칸을 다시 더한다」를 생각해 보세요. 기계를 오른쪽으로 한 칸 옮기면 아홉 칸 중 몇 칸이 그대로인가요?