2차시에서 우리는 어떤 문제를 기계에게 맡길지를 점수로 갈랐습니다.
맡기기로 정했다면 다음 일이 남습니다 — 그 문제를 기계가 읽을 수 있는 모양으로 다시 적는 일입니다.
오늘은 눈금 없는 물병 두 개로 정확히 4L를 만드는 문제를, 컴퓨터가 길 찾기로 풀 수 있는 지도로 바꿔 봅니다.
성취기준 12인기01-02
상태행동목표상태 공간도달 가능상태 폭발
🎯 학습 목표
물병 문제를 상태·행동·목표 세 낱말로 다시 적고, 그것이 곧 지도 위의 길 찾기임을 설명할 수 있다.
상태 공간을 코드로 펼쳐 도달 가능한 상태 16가지와 좌표상 24가지를 재고, 그 차이의 까닭을 댈 수 있다.
용량을 바꿔 만들 수 없는 문제를 직접 만들고, 만들 수 있는 양이 최대공약수의 배수뿐임을 확인할 수 있다.
🤔
여는 장면 — 눈금이 없다
앞에 물병이 두 개 있습니다. 하나는 3L짜리, 다른 하나는 5L짜리입니다.
수도꼭지는 옆에 있어 물은 얼마든지 쓸 수 있고, 하수구도 있어 언제든 버릴 수 있습니다.
해야 할 일은 하나입니다. 정확히 4L를 만드세요.
여기에 한 가지 조건이 붙습니다. 두 병에는 눈금이 하나도 없습니다.
그러니 "5L 병에 4L만 따른다"는 선택지는 없어요. 병에 물을 붓다가 멈출 수 있는 순간은 딱 둘뿐입니다 —
붓는 병이 바닥나는 순간, 아니면 받는 병이 가득 차는 순간.
그 사이 어디쯤에서 "이만큼이면 되겠다"고 멈추는 일은 불가능합니다.
실험실에서 쓰는 눈금실린더에는 50ml짜리부터 500ml짜리까지 눈금이 촘촘히 새겨져 있어, 원하는 양에서 붓기를 멈출 수 있습니다. 오늘 우리가 다룰 병에는 그 눈금이 없어요.
눈금 하나가 사라지면 가능한 행동의 가짓수가 확 줄어들고, 그 대신 문제가 컴퓨터에게 넘길 만한 모양이 됩니다.
출처: Lilly_M, Wikimedia Commons (CC BY-SA 3.0)
손으로 몇 번 해 보면 답은 나옵니다. 여러분도 지금 종이에 끄적이면 5분 안에 찾을 수 있을 거예요.
그런데 오늘의 물음은 답 자체가 아닙니다.
💭 오늘의 물음
이 문제를, 컴퓨터가 풀 수 있는 모양으로
어떻게 다시 적을까?
사람은 "5L를 채우고, 3L로 옮기고…" 하는 식으로 이야기를 만들며 풉니다.
컴퓨터는 이야기를 못 읽어요. 컴퓨터에게 넘기려면 문제를 숫자와 규칙으로 다시 적어야 합니다.
그리고 그 '다시 적는 법'은 물병에만 쓰이는 요령이 아닙니다. 이 단원이 끝날 때까지 —
미로, 8-퍼즐, 내비게이션 지도, 규칙 기반 추론까지 — 같은 문법이 되풀이됩니다.
오늘 그 문법을 배웁니다.
📌 오늘 확인할 숫자 세 개
이 물병 문제에서 좌표상 있을 수 있는 상태는 24가지인데,
실제로 갈 수 있는 곳은 16가지뿐입니다. 나머지 8가지는 아무리 물을 부어도 닿지 못해요.
왜 그런지, 그리고 그 8가지가 정확히 어느 것인지를 오늘 여러분이 직접 재게 됩니다.
1
문제를 세 낱말로 다시 적는다 — 상태 · 행동 · 목표
인공지능이 문제를 다루는 방식은 놀랄 만큼 단순한 틀에서 출발합니다.
어떤 문제든 세 가지만 정하면 컴퓨터가 손댈 수 있는 모양이 됩니다.
🔵 상태 (state)
어느 한 순간의 모습을 한 장으로 찍은 사진입니다.
물병 문제라면 두 병에 각각 물이 얼마나 들어 있는지, 그것만 알면 됩니다.
(작은 병, 큰 병) = (0, 5)
🟣 행동 (action)
상태를 다른 상태로 바꾸는 한 걸음입니다.
물병 문제에서 할 수 있는 일은 여섯 가지뿐이에요.
채우기 2 · 비우기 2 · 붓기 2
🟢 목표 (goal)
도달하려는 상태입니다. 상태 하나를 콕 집을 수도 있고,
조건으로 적을 수도 있습니다.
어느 한 병에 정확히 4L
이 세 가지를 정하고 나면 놀라운 일이 벌어집니다.
문제 풀이가 길 찾기로 바뀝니다.
상태 = 지도 위의 한 점
행동 = 점과 점을 잇는 한 줄
문제 풀이 = 시작점에서 목표점까지 길 찾기
이렇게 만들어진 지도 전체를 상태 공간이라고 부릅니다.
그리고 상태 공간 위에서 길을 찾는 일을 탐색(search)이라고 하지요.
4차시부터 9차시까지 우리가 배울 것이 전부 이 탐색입니다.
물병 문제의 여섯 가지 행동을 하나씩 적어 봅시다. 지금 상태를 (a, b)라 하고,
작은 병 용량을 3, 큰 병 용량을 5라고 하면 이렇습니다.
행동
바뀐 상태
(2, 3)에서 하면
왜 이 값인가
작은 병 가득 채우기
(3, b)
(3, 3)
수도꼭지에서 받으니 큰 병은 그대로
큰 병 가득 채우기
(a, 5)
(2, 5)
작은 병은 손대지 않는다
작은 병 비우기
(0, b)
(0, 3)
하수구에 버린다
큰 병 비우기
(a, 0)
(2, 0)
버린 물은 세지 않는다
작은 병 → 큰 병
(a−d, b+d)
(0, 5)
d = min(2, 5−3) = 2 — 작은 병이 먼저 바닥났다
큰 병 → 작은 병
(a+d, b−d)
(3, 2)
d = min(3, 3−2) = 1 — 작은 병이 먼저 가득 찼다
앞의 네 줄은 쉽습니다. 어려운 것은 아래 두 줄, 붓기예요.
붓기에서 실제로 옮겨지는 양 d는 얼마일까요?
여는 장면에서 말한 그대로입니다 — 주는 병이 바닥나거나, 받는 병이 가득 차거나, 둘 중 먼저 오는 쪽에서 멈춥니다.
그러니 d는 둘 중 작은 쪽입니다.
작은 병 → 큰 병 : d = min(a, 5 − b)
큰 병 → 작은 병 : d = min(b, 3 − a)
상태 하나가 행동 하나를 만나 다른 상태가 됩니다. 두 병 모두 눈금이 없다는 점을 보세요 —
그래서 d를 사람이 고를 수 없고, min이 대신 정해 줍니다.
이 그림에서는 작은 병(3L)이 먼저 바닥나서 d = 3이 되었습니다.
💡 min 한 글자가 이 문제의 전부다
"눈금이 없다"는 조건은 말로는 한 줄이지만, 코드에서는 min 한 글자입니다.
만약 min을 빼고 d = a라고 적으면 어떻게 될까요?
작은 병의 물을 전부 큰 병에 붓는다는 뜻이 되어, 큰 병이 5L를 넘어도 그냥 넘칩니다.
그러면 큰 병의 값이 6, 7, 8… 하고 끝없이 늘어나 상태 공간이 무한이 됩니다.
오늘 실습에서 실제로 이 일이 일어나면 어떻게 되는지 보게 될 거예요.
2
좋은 상태 표현이 절반이다
여기까지는 "그렇게 적으면 되겠네"로 넘어가기 쉽습니다. 하지만 상태를 어떻게 적느냐는
문제 풀이의 성패를 가릅니다. 같은 물병 문제를 이렇게 적을 수도 있었어요.
상태를 이렇게 적으면
상태 하나의 예
상태 공간의 크기
판정
두 병의 물의 양
(2, 5)
24칸(좌표상)
좋다
물의 양 + 지금까지 부은 횟수
(2, 5, 7)
끝이 없다
나쁘다
물의 양 + 물 온도 + 병의 색
(2, 5, 18℃, 파랑)
엄청나게 커진다
나쁘다
"큰 병이 반쯤 찼다" 같은 말
(적음, 반쯤)
아주 작다
나쁘다
세 번째와 네 번째는 왜 나쁜지 금방 보입니다. 온도와 색은 목표를 판정하는 데 아무 쓸모가 없습니다.
쓸모없는 것을 상태에 넣으면 탐색해야 할 공간만 커집니다.
반대로 네 번째는 너무 뭉갰어요 — "반쯤 찼다"로는 정확히 4L인지를 판정할 수 없습니다.
상태가 목표 판정에 필요한 정보를 잃으면 그 표현으로는 문제를 풀 수 없습니다.
어려운 것은 두 번째입니다. '지금까지 몇 번 부었는가'는 그럴듯해 보여요.
기록을 남기면 나중에 쓸 데가 있을 것 같지요. 그런데 이렇게 하면 상태 공간이 끝없이 커집니다.
물을 0L 붓는 헛동작도 횟수만 1 올린 새로운 상태가 되기 때문입니다.
(0,0,1), (0,0,2), (0,0,3)… 물병 모양은 똑같은데 상태만 계속 늘어나요.
오늘 실습에서 이 값을 실제로 세어 보고, 얻는 것이 정말 있는지 확인합니다.
⚠️ 상태 설계의 규칙
상태에는 '목표를 판정하고 다음 행동을 정하는 데 필요한 것'만 담는다.
하나라도 더 넣으면 공간이 커지고, 하나라도 덜 넣으면 문제를 못 푼다.
이 줄타기가 인공지능에서 문제 표현(problem representation)이라고 부르는 일이며,
많은 경우 알고리즘을 고르는 것보다 여기가 더 중요합니다.
정리하면 이렇습니다. 물병 문제의 상태는 숫자 두 개면 충분합니다.
두 병에 물이 얼마나 들었는지만 알면, 어떤 행동을 할 수 있는지도 정해지고 목표에 닿았는지도 판정됩니다.
물이 어떤 순서로 그 상태에 왔는지는 앞으로 무엇을 할 수 있는가에 아무 영향이 없어요.
이런 성질을 마르코프 성질이라 부르는데, 이름은 몰라도 됩니다.
기억할 것은 한 줄입니다 — 지금 모습만 보면 되는 문제라면, 지금 모습만 상태에 담는다.
3
갈 수 있는 곳과 있을 법한 곳은 다르다 — 24 대 16
상태를 (a, b)로 정했으니 상태 공간의 크기를 세어 봅시다.
작은 병에는 0·1·2·3 중 하나가 들어 있을 수 있고, 큰 병에는 0·1·2·3·4·5 중 하나입니다.
그러니 좌표상 있을 수 있는 상태는 4 × 6 = 24가지입니다.
여기까지가 종이 위의 계산입니다. 그런데 실제로 그 24칸에 다 갈 수 있을까요?
예를 들어 (1, 2) — 작은 병에 1L, 큰 병에 2L가 들어 있는 상태를 만들 수 있나요?
눈금이 없다는 것을 다시 떠올려 보세요. 잠깐 멈추고 직접 시도해 봅시다.
못 만듭니다. 그리고 그 까닭은 한 줄로 적힙니다.
붓기를 멈출 수 있는 순간은 어느 한 병이 비거나 가득 찰 때뿐이니,
물을 붓고 난 직후의 상태에는 반드시 비었거나 가득 찬 병이 하나 있습니다.
채우기와 비우기도 마찬가지고요. 그러니 두 병이 동시에 어중간한 상태는 영영 만들어지지 않습니다.
갈 수 있는 상태 ⟺ a = 0 또는 a = 3 또는 b = 0 또는 b = 5
이 조건을 24칸 격자 위에 그려 보면 모양이 아주 또렷합니다.
갈 수 있는 16칸은 정확히 격자의 테두리입니다.
안쪽에 갇힌 8칸((1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4))이
아무리 물을 부어도 닿지 못하는 곳이에요. 초록은 출발 (0,0),
노랑은 목표를 만족하는 두 칸 (0,4)·(3,4)입니다.
테두리 칸 수를 세면 2×3 + 2×5 = 16, 안쪽은 2×4 = 8 — 딱 맞습니다.
이 그림에서 두 가지를 얻습니다. 첫째, 문제를 잘 적으면 실제로 뒤져야 할 공간이 줄어듭니다.
24칸을 다 뒤질 필요가 없어요. 물병의 규칙 자체가 8칸을 이미 잘라냈습니다.
둘째, 목표 상태가 어디에 있는지도 보입니다.
'어느 한 병에 정확히 4L'를 만족하는 칸은 (0,4)와 (3,4) 둘뿐이고,
둘 다 테두리 위에 있으니 적어도 갈 수는 있다는 것을 풀기 전에 알 수 있습니다.
📌 병이 커지면 이 차이가 벌어진다
두 용량이 서로소일 때 갈 수 있는 상태는 늘 테두리 전부,
곧 2×(작은 용량) + 2×(큰 용량)개입니다.
3L·5L면 16개(전체의 66.67%)지만, 7L·11L면 36개인데 좌표상은 96개라 37.50%로 떨어져요.
97L·100L까지 키우면 394개 / 9,898개 = 3.98%가 됩니다.
병이 커질수록 '있을 법한 곳' 대부분이 헛것이 되는 셈이지요.
오늘 시뮬레이터에서 7L·11L까지는 직접 확인할 수 있습니다.
그런데 방금 "서로소일 때"라는 단서를 달았습니다. 서로소가 아니면 어떻게 될까요?
4L·6L 병을 생각해 봅시다. 테두리 칸을 세면 2×4 + 2×6 = 20이어야 할 것 같은데,
실제로 갈 수 있는 상태는 10가지뿐입니다.
두 용량이 모두 짝수라 홀수 리터는 아예 만들어지지 않기 때문이에요.
그래서 4L·6L 병으로는 5L를 만들 수 없습니다.
길이 험해서가 아니라, 그런 상태가 지도 위에 아예 없어서입니다.
이것이 오늘 여러분이 직접 확인할 반례이고, 규칙은 이렇게 적힙니다.
만들 수 있는 양 = gcd(두 용량)의 배수 중 큰 병 용량 이하의 수
3과 5의 최대공약수는 1이므로 0~5를 모두 만들 수 있고,
4와 6의 최대공약수는 2이므로 0·2·4·6만 만들 수 있습니다.
수학에서는 이것을 베주 항등식(Bézout's identity)이라고 부릅니다 —
4x + 6y 꼴로 적을 수 있는 정수는 2의 배수뿐이라는 정리예요.
물병에 물을 붓는 일이 결국 용량을 더하고 빼는 일이니 당연한 결과지만,
오늘 우리는 정리를 외워서가 아니라 상태 공간을 통째로 펼쳐서 이 사실에 닿을 겁니다.
4
상태 폭발 — 왜 '적게 보는 법'이 인공지능의 능력인가
물병 문제는 상태가 24칸뿐이라 컴퓨터에게는 우스운 크기입니다. 전부 뒤져도 눈 깜짝할 사이예요.
문제는 조금만 복잡해져도 상태 수가 무섭게 불어난다는 데 있습니다.
한 상태에서 갈 수 있는 갈림길이 b개이고, 목표까지 d걸음이 걸린다고 합시다.
그러면 살펴봐야 할 갈래는 대략 bd개입니다.
갈림길이 하나 늘 때마다 곱해지는 것이 아니라, 걸음이 하나 늘 때마다 곱해집니다.
이것이 무서운 이유예요.
갈림길 b
깊이 d
살펴볼 갈래 bd
느낌
3
10
59,049
노트북이 눈 깜짝할 사이에 끝낸다
6
6
46,656
깊이가 얕으면 갈림길이 많아도 견딘다
3
20
3,486,784,401
깊이만 두 배로 늘렸는데 5만 → 35억
세 번째 줄을 보세요. 갈림길은 그대로 3인데 깊이만 10에서 20으로 늘렸더니
5만 가지가 35억 가지가 되었습니다. 약 6만 배입니다.
이것을 상태 폭발이라고 부릅니다.
19×19 바둑판에 놓일 수 있는 합법 배치의 수는 약 2.08 × 10170입니다
(John Tromp가 2016년에 정확한 값을 계산해 발표했습니다).
관측 가능한 우주의 원자 수가 약 1080개이니, 바둑판 배치가 우주의 원자보다 약 1090배 많습니다.
"전부 세어 보고 가장 좋은 수를 고른다"는 방법은 컴퓨터가 아무리 빨라져도 불가능합니다.
출처: Chad Miller, Wikimedia Commons (CC BY-SA 2.0)
여기서 인공지능의 자리가 생깁니다.
"모두 세어 본다"가 불가능하니, "적게 보고도 답을 찾는 법"이 곧 능력이 됩니다.
4차시부터 9차시까지 배울 탐색 알고리즘들은 전부 이 한 가지를 겨루는 방법들이에요 —
어떻게 하면 덜 보고도 답에 닿는가.
그런데 물병 문제는 어땠나요? 갈림길이 6개이고 6걸음이면 66 = 46,656갈래인데,
실제로 서로 다른 상태는 16가지뿐이었습니다. 46,656 대 16.
이 엄청난 차이는 어디서 왔을까요? 놀랍게도 코드 한 줄에서 옵니다.
# 이미 본 상태는 대기실에 다시 넣지 않는다 — 이 한 줄이 46,656을 16으로 만든다if n not in seen:
seen.add(n)
q.append(n)
같은 상태에 여러 갈래로 닿을 수 있기 때문입니다. (0,5)에 이르는 길은 하나가 아니에요.
그런데 어떤 길로 왔든 그 상태에서 할 수 있는 일은 똑같습니다.
그러니 두 번째부터는 뒤져 볼 까닭이 없지요.
이것이 개념 2에서 말한 "지금 모습만 보면 되는 문제"라는 성질의 값어치입니다 —
상태를 잘 적으면, 서로 다른 길이 같은 상태로 합쳐지면서 공간이 접힙니다.
⚠️ 이 한 줄을 지우면 어떻게 되나
서로 다른 상태는 16가지뿐인데도 대기실은 끝없이 불어납니다.
20만 번 꺼낸 시점에 대기실에 1,000,001개가 쌓여 있었어요 — 꺼낸 수의 다섯 배입니다.
같은 곳을 몇 번이고 다시 밟으며 영원히 돌기 때문이지요.
오늘 코드에 상한(LIMIT)이 걸려 있는 것은 이 때문입니다. 지우지 마세요.
💻
손으로 — 지도를 펼쳐 보고, 코드로 세어 본다
오늘 15분은 둘로 나뉩니다. 먼저 상태 공간 지도를 눈으로 펼쳐 보고,
그다음 같은 일을 파이썬에게 시켜 봅니다.
두 곳에서 나오는 숫자는 반드시 같아야 해요 — 다르면 둘 중 하나가 틀린 것입니다.
공책을 펴 두세요. 아래 표에 적을 값이 확인 문제에 그대로 나옵니다.
① 상태 공간 지도 — 용량을 바꾸면 지도가 다시 그려진다
🗺️ 물병 상태 공간 지도INTERACTIVE
가로축은 작은 병에 든 물, 세로축은 큰 병에 든 물입니다.
점 하나가 상태 하나예요. 처음에는 (0,0) 하나만 켜져 있습니다.
▶ 한 걸음을 누를 때마다 대기실에서 상태를 하나 꺼내 그 이웃을 켜고, 어떤 행동으로 왔는지 화살표를 긋습니다.
슬라이더로 용량을 바꾸면 지도가 통째로 다시 그려집니다.
흐린 점은 좌표상 있을 수 있지만 갈 수 없는 곳입니다.
3L5L4L
좌표상 칸24
갈 수 있는 칸16
갈 수 없는 칸8
비율66.67%
최대공약수1
목표까지6걸음
만들 수 있는 양0, 1, 2, 3, 4, 5
[안내] 작은 병 3L · 큰 병 5L · 목표 4L 로 시작합니다.
💡 지도를 읽는 법
점 안의 숫자는 출발에서 몇 걸음 만에 닿는가입니다.
초록 테두리는 출발 (0,0), 노란 테두리는 목표를 만족하는 상태예요.
목표에 닿는 가장 짧은 길은 굵은 노란 선으로 그려집니다.
화살표는 그 상태를 처음 발견하게 해 준 행동만 그립니다 — 모든 행동을 다 그리면 화면이 뒤엉켜 아무것도 안 보입니다.
지도로 하는 세 가지 과제
버튼만 눌러 보고 끝내면 3분이면 끝납니다. 아래 세 가지를 반드시 해서 공책에 적으세요.
표 채우기. 아래 네 설정을 슬라이더로 만들고 네 칸씩 채웁니다.
(3,5)부터 하면 답을 맞춰 볼 수 있어요 — 좌표상 24칸, 갈 수 있는 칸 16, gcd 1입니다.
반례 만들기. 목표를 4L로 두고,
4L를 만들 수 없는 용량 조합을 두 개 찾으세요.
그리고 두 조합이 서로 다른 까닭으로 실패하도록 골라 봅니다. (까닭은 두 종류밖에 없습니다.)
비율 재기. 작은 병 7L·큰 병 11L로 맞추고
'갈 수 있는 칸'과 '좌표상 칸'을 적으세요. (3,5)의 66.67%와 견주면 비율이 어떻게 되나요?
설정
좌표상 칸
갈 수 있는 칸
최대공약수
만들 수 있는 양
(3, 5)
(4, 6)
(6, 9)
(7, 11)
설정
좌표상
갈 수 있는 칸
gcd
만들 수 있는 양
(3, 5)
24
16
1
0,1,2,3,4,5
(4, 6)
35
10
2
0,2,4,6
(6, 9)
70
10
3
0,3,6,9
(7, 11)
96
36
1
0,1,…,11 (전부)
네 줄이 전부 같은 규칙을 따릅니다.
만들 수 있는 양은 gcd의 배수 중 큰 병 용량 이하의 수이고, 예외가 하나도 없어요.
과제 ②의 답은 두 종류입니다.
하나는 (6, 9)처럼 gcd가 4를 나누지 못하는 경우예요 —
만들 수 있는 양이 0·3·6·9뿐이라 4가 아예 없습니다.
다른 하나는 (1, 3)처럼 4가 큰 병보다 큰 경우입니다 —
만들 수 있는 양은 0·1·2·3인데 4를 담을 그릇 자체가 없어요.
'gcd의 배수'와 '큰 병 이하'라는 두 조건 중 어느 쪽이 깨졌는지가 두 까닭을 가릅니다.
과제 ③의 답: (7, 11)은 갈 수 있는 칸 36,
좌표상 96이므로 37.50%입니다.
(3,5)의 66.67%에서 절반 가까이 떨어졌어요.
병이 커질수록 '있을 법한 곳' 가운데 헛것의 비중이 커집니다.
② 파이썬으로 세어 본다 — 빈칸 두 곳을 채우세요
이제 같은 일을 코드로 시킵니다. 아래 코드에는 빈칸이 두 곳(?????) 있어요.
둘 다 개념 1에서 이미 답이 나온 자리입니다 — 붓기에서 실제로 옮겨지는 양 d를 적는 곳이지요.
채우고 실행하면 오늘 배운 숫자들이 화면에 그대로 찍혀야 합니다.
빈칸 두 곳을 채운다. 힌트는 코드 주석에 있습니다.
실행해서 도달 가능한 상태 : 16 가지와 걸음 수: 6이 나오면 성공입니다.
시뮬레이터에서 적은 값과 같은지 대조하세요.
깊이 우선으로 바꿔 본다.search_path() 안의
q.popleft()가 order에 따라 q.pop()으로 바뀝니다.
[2]가 이미 두 방식을 나란히 찍어 주니, 목표 4L에서는 걸음 수가 같다는 것을 먼저 확인하세요.
그리고 [2]의 마지막 줄에 나오는 목표 1L의 결과를 보세요. 무엇이 달라졌나요?
만들 수 없게 만들어 본다.[3]은 이미 (4, 6)으로 5L를 시도합니다.
출력에 경로: None이 찍히지요. 이때 프로그램이 멈춰 버린 것인지, 다 뒤지고 없다고 답한 것인지
같은 줄의 '꺼내 본 상태' 수를 보고 판단하세요.
일부러 부순다. 빈칸 ①을 min 없이 d = a로 바꿔 실행해 보세요.
답이 틀리는 것이 아니라 끝나지 않습니다.
안전장치가 잡아 주는 메시지를 읽고, 왜 무한이 되는지 한 줄로 적으세요.
⚠️ LIMIT 줄을 지우지 마세요
이 코드는 브라우저 안에서 돕니다. 파이썬이 끝나지 않으면 화면 전체가 멈춰요.
코드 위쪽의 LIMIT = 200000과 그것을 검사하는 두 줄이 그 사고를 막습니다.
실습 4번에서 실제로 그 안전장치가 작동하는 것을 보게 됩니다 —
망가지더라도 말은 하고 망가지게 만드는 것이 프로그램을 짜는 사람의 예의입니다.
📌 처음 한 번만 오래 걸립니다 — 정상입니다
▶ 실행을 처음 누르면 파이썬 엔진(Pyodide)을 내려받느라
몇 초에서 수십 초까지 걸릴 수 있습니다. 인터넷 속도에 달렸어요.
두 번째부터는 1초 안팎에 끝납니다.
그 1초의 대부분은 [6]에서 20만 개까지 세어 보고 "끝이 없다"를 확인하는 데 쓰입니다 —
무한을 확인하는 일에는 원래 값이 치릅니다.
실행하는 동안 화면이 잠깐 멈춘 것처럼 보여도 버튼을 다시 누르지 마세요.
파이썬이 브라우저 안에서 도는 동안에는 화면을 그릴 겨를이 없어서 그렇습니다.
[1] 상태 공간의 크기.도달 가능한 상태 16 / 좌표상 24 / 갈 수 없는 8.
그리고 O와 .로 찍힌 지도가 개념 3의 그림과 같은 모양입니다 —
O가 테두리에만 있어요. 갈 수 없는 8가지는
(1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4)이고,
도달한 상태는 모두 '한 병이 비었거나 가득 찼다'를 만족하는가? -> True가
그 까닭을 코드로 확인해 줍니다.
[2] 최단 경로.6걸음이고, 그 길을 찾느라 꺼내 본 상태는 14개입니다.
갈 수 있는 16가지 중 14개를 봤으니 거의 다 본 셈이에요. 경로는 이렇습니다.
(0,0) → 큰 병 가득 채우기 → (0,5) → 큰 병→작은 병 3L → (3,2)
→ 작은 병 비우기 → (0,2) → 큰 병→작은 병 2L → (2,0)
→ 큰 병 가득 채우기 → (2,5) → 큰 병→작은 병 1L → (3,4)← 큰 병에 4L!
마지막 걸음을 보세요. 작은 병에 이미 2L가 있어서 1L만 더 들어가고,
그 바람에 큰 병에 정확히 4L가 남습니다.
4L를 직접 재려 한 것이 아니라, 3L짜리 병이 대신 재 준 것입니다.
깊이 우선과의 차이.pop()으로 바꾸면 꺼내 본 상태가 14 → 7로 줄고,
걸음 수는 6으로 같습니다. "깊이 우선이 더 좋네"라고 결론 내리기 딱 좋은 자리예요.
그런데 목표만 1L로 바꾸면 너비 우선 4걸음 / 깊이 우선 8걸음으로 두 배가 됩니다.
4L에서 같았던 것은 우연입니다.
한 가지 설정에서 돌려 보고 "되던데요"라고 말할 수 없는 까닭이 이것이고,
이 이야기가 다음 4차시의 주제입니다.
[3] 만들 수 없는 문제.(4, 6)으로 5L를 찾으면 경로: None인데,
같은 줄에 꺼내 본 상태 10 개가 붙어 있습니다.
갈 수 있는 상태 10개를 하나도 남김없이 다 뒤지고 나서 '없다'고 답한 것이지 멈춘 것이 아니에요.
도달한 상태를 보면 숫자가 전부 짝수입니다.
[6] 부은 횟수를 상태에 넣으면. 개념 2에서 "나쁜 표현"이라고 했던 것을 실제로 세어 봅니다.
허용 횟수 kmax를 올릴 때마다 상태가 16개씩 늘어나
16 × kmax − 8이 됩니다(kmax가 2 이상일 때).
상한을 두지 않으면 20만 개에서 강제로 멈춰야 했고,
그렇게 늘린 대가로 얻은 것은 아무것도 없습니다 — 최단 답은 여전히 6걸음입니다.
실습 4번(일부러 부수기).d = a로 바꾸면 큰 병이 용량을 넘어 계속 불어납니다.
안전장치가 없던 시절에 실제로 재 보니 강제 종료 시점에 큰 병 값이 149,999까지 갔어요.
"틀린 답이 나온다"가 아니라 "끝나지 않는다"가 정확한 관찰입니다.
이 둘은 전혀 다른 종류의 고장이에요.
📖
정리 — 오늘 얻은 것은 문법 하나다
오늘 배운 것을 물병 문제로만 기억하면 아무 데도 못 씁니다.
기억해야 할 것은 세 낱말로 문제를 다시 적는 문법입니다.
같은 문법이 전혀 다른 문제에도 그대로 들어맞아요.
문제
상태
행동
목표
물병 붓기 (오늘)
(작은 병, 큰 병)
채우기·비우기·붓기 6가지
어느 한 병에 4L
미로 찾기 (4차시)
(행, 열)
상·하·좌·우 4가지
출구 칸에 도착
8-퍼즐 (8차시)
조각 8개와 빈칸 하나의 배치
빈칸을 상하좌우로 밀기
1~8이 순서대로
늑대·양·양배추 강 건너기
(양쪽 기슭에 무엇이 있나, 배의 위치)
배에 하나 태우고 건너기
셋 다 건너편에
루빅스 큐브
여섯 면 54칸의 색 배치
면 하나를 90°·180°·270° 돌리기 18가지
여섯 면이 각각 한 색
표의 마지막 줄을 보세요. 루빅스 큐브는 상태가 약 4.3 × 1019가지입니다.
물병의 16가지와 견줄 수 없지요. 그런데 적는 방식은 똑같습니다.
달라지는 것은 상태의 크기이지 문법이 아니에요.
그리고 상태가 커지면 "전부 뒤진다"가 불가능해지므로 다른 방법이 필요해집니다.
그 방법을 배우는 것이 4차시부터 9차시까지입니다.
오늘 얻은 숫자도 다시 짚어 둡시다.
24 대 16 대 8. 좌표상 있을 수 있는 24칸 중 실제로 갈 수 있는 곳은 16칸,
아무리 애써도 못 가는 곳이 8칸. 문제의 규칙 자체가 공간을 잘라 준다.
6걸음, 꺼내 본 상태 14개. 답에 이르는 길은 여섯 걸음이고,
그 길을 찾느라 열네 개의 상태를 살펴봤다. 답의 길이와 찾는 비용은 별개의 값이다.
gcd의 배수만 만들 수 있다. 3L·5L(gcd 1)로는 0~5를 다 만들지만
4L·6L(gcd 2)로는 5L를 영영 만들 수 없다. 길이 어려운 게 아니라 지도에 그 점이 없다.
46,656 대 16. 갈래 수로는 4만 6천이지만 서로 다른 상태는 16가지.
그 차이는 if n not in seen: 한 줄에서 왔다.
다음 시간에는 오늘 만든 지도 위에서 어떤 순서로 뒤질 것인가를 다룹니다.
오늘 코드의 search_path()에서 popleft()냐 pop()이냐 한 곳만
바뀌었던 것 기억하지요? 그 한 글자가 너비 우선 탐색(BFS)과
깊이 우선 탐색(DFS)을 가릅니다.
그리고 오늘 물병에서는 우연히 같았던 걸음 수가, 미로에서는 확실하게 갈라집니다.
그때 이름 하나가 더 붙습니다. 오늘 우리가 '대기실'이라고 부른 것 —
가 볼 수는 있는데 아직 안 가 본 상태들을 담아 두는 그릇 — 의 정식 이름은
프론티어(frontier)입니다. 오늘 코드의 q가 바로 그것이고,
이미 본 상태를 담은 seen은 방문 집합이라고 부릅니다.
탐색 알고리즘은 결국 이 두 그릇을 어떻게 쓰느냐로 갈립니다.
🔁 되돌아보기
오늘 물병 문제를 상태·행동·목표 세 낱말로 다시 적어
상태 공간 24칸 중 16칸만 갈 수 있음을 직접 셌고, 4L·6L로는 5L를 만들 수 없다는 반례까지 확인했습니다.
다음 시간에는 같은 지도를 큐로 뒤질 때와 스택으로 뒤질 때 무엇이 달라지는지를 미로에서 잽니다.
오늘 나온 popleft()와 pop()이 그 이야기의 출발점입니다.
✅
확인 문제
✍️ 문제마다 답을 쓰고 제출하기를 누르세요. 제출하면 모범 답안이 열리고, 제출한 답은 선생님께 전달됩니다.
1. "문제를 푸는 일은 탐색이다"라는 말을
상태·행동·목표 세 낱말을 모두 써서 풀어 쓰시오.
그리고 물병 문제에서 세 낱말이 각각 무엇이었는지 함께 적으시오.
📖 모범 답안
문제를 상태(어느 한 순간의 모습)들의 모임으로 적고,
행동(상태를 다른 상태로 바꾸는 한 걸음)으로 상태와 상태를 이으면
문제 전체가 하나의 지도, 곧 상태 공간이 된다.
그러면 문제를 푸는 일은 시작 상태에서 출발해 행동을 이어 붙여 목표 상태에 닿는 길을 찾는 일이 되고,
그것이 곧 탐색이다.
물병 문제에서는 상태 = (작은 병의 물, 큰 병의 물),
행동 = 채우기 2가지·비우기 2가지·붓기 2가지 해서 모두 6가지,
목표 = "어느 한 병에 정확히 4L가 들어 있다"였다.
목표를 상태 하나가 아니라 조건으로 적었다는 점도 눈여겨볼 것 —
(0,4)와 (3,4) 두 상태가 모두 목표를 만족한다.
2.8-퍼즐(3×3 판에 1~8 조각과 빈칸 하나가 있고,
빈칸으로 조각을 밀어 1~8을 순서대로 맞추는 놀이)의 상태·행동·목표를 각각 한 줄로 적으시오.
그리고 '지금까지 민 횟수'를 상태에 넣으면 왜 나쁜지 한 줄로 덧붙이시오.
📖 모범 답안
상태 — 3×3 칸에 1~8과 빈칸이 놓인 배치 한 장.
(예: (1,2,3, 4,5,6, 7,0,8)처럼 아홉 자리로 적을 수 있다.) 행동 — 빈칸을 위·아래·왼쪽·오른쪽 중 한 방향으로 옮기기.
최대 4가지이고, 빈칸이 모서리에 있으면 2가지로 줄어든다. 목표 — 1~8이 순서대로 놓이고 빈칸이 정해진 자리에 있는 배치. 민 횟수를 넣으면 나쁜 까닭 — 같은 배치가 '몇 번 만에 왔는가'에 따라 서로 다른 상태로 셈해져
상태 수가 몇 배로 불어나는데, 다음에 무엇을 할 수 있는지도 목표에 닿았는지도 배치만 보면 알 수 있으므로
늘어난 만큼의 정보를 전혀 얻지 못한다. 오늘 물병에서 16 × kmax − 8로 늘어나던 그 일과 같다.
3.(오늘 실행한 결과)
코드를 돌려 얻은 도달 가능한 상태 수와 좌표상 있을 수 있는 상태 수를 적고,
갈 수 없는 상태들이 어떤 공통점을 가지는지 쓰시오.
또 최단 경로가 몇 걸음이었고 그때 꺼내 본 상태는 몇 개였는지 적으시오.
📖 모범 답안
도달 가능 16가지 / 좌표상 24가지 / 갈 수 없는 8가지이고,
갈 수 없는 8가지는 (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4)다. 공통점: 작은 병이 0도 3도 아니면서(즉 어중간하면서) 동시에 큰 병도 0도 5도 아닌 칸들이다.
두 병이 동시에 어중간한 상태인 셈이다.
그런 상태가 안 나오는 까닭은 눈금이 없어서 붓기를 멈출 수 있는 순간이 '주는 병이 비거나 받는 병이 가득 찰 때'뿐이기 때문이다.
채우기·비우기도 마찬가지로 한쪽을 0이나 최대로 만든다.
그래서 갈 수 있는 16칸은 정확히 격자의 테두리이고, 2×3 + 2×5 = 16으로 개수까지 맞는다. 최단은 6걸음, 꺼내 본 상태는 14개다. 갈 수 있는 16개 중 14개를 살펴본 셈이니,
답이 짧다고 찾는 일까지 싼 것은 아니다.
4.(오늘 실행한 결과)
시뮬레이터에서 채운 표를 보고, (4,6)·(6,9)·(7,11)의
갈 수 있는 칸 수와 만들 수 있는 양을 적으시오.
그리고 (4,6)으로 5L를 만들 수 없는 까닭을 최대공약수를 써서 설명하시오.
📖 모범 답안
(4,6) 갈 수 있는 칸 10(좌표상 35), 만들 수 있는 양 0·2·4·6. (6,9) 갈 수 있는 칸 10(좌표상 70), 만들 수 있는 양 0·3·6·9. (7,11) 갈 수 있는 칸 36(좌표상 96), 만들 수 있는 양 0부터 11까지 전부. 5L가 안 되는 까닭: 물병에 할 수 있는 일은 용량만큼 더하거나 빼는 것뿐이므로,
병에 남는 물의 양은 언제나 4x + 6y 꼴로 적힌다. 4와 6은 둘 다 2의 배수이니 이 값도 반드시 2의 배수다.
5는 홀수이므로 아무리 부어도 만들어질 수 없다(베주 항등식).
곧 만들 수 있는 양은 gcd(4,6)=2의 배수 중 6 이하인 0·2·4·6뿐이다.
중요한 점은 이것이 길이 어려워서가 아니라 지도 위에 그 점이 아예 없어서라는 것이다.
그래서 탐색은 갈 수 있는 10개를 다 뒤진 뒤 정상적으로 None을 돌려준다.
5. 갈림길이 3개이고 깊이가 10이면 살펴볼 갈래는 대략 몇 가지인지 계산하시오.
그런데 물병 문제에서는 서로 다른 상태가 16가지뿐이었다.
이 차이는 코드의 어느 한 줄에서 오는지 짚고, 그 줄을 지우면 무슨 일이 벌어지는지 쓰시오.
📖 모범 답안
310 = 59,049가지다.
(깊이를 20으로만 늘려도 320 = 약 34억 8천만가지가 된다.)
차이가 나는 까닭은 if n not in seen: 한 줄이다.
같은 상태에 여러 갈래로 닿을 수 있지만, 어떤 길로 왔든 그 상태에서 할 수 있는 일은 똑같으므로
두 번째부터는 살펴볼 까닭이 없다. 서로 다른 길들이 같은 상태에서 하나로 합쳐지면서 공간이 접히는 것이다. 지우면: 서로 다른 상태는 여전히 16가지뿐인데도 대기실만 끝없이 불어난다.
실제로 재 보니 20만 번을 꺼낸 시점에 대기실에 1,000,001개가 쌓여 있었고 끝나지 않았다.
같은 곳을 몇 번이고 다시 밟기 때문이다. 그래서 이 코드에는 LIMIT이 걸려 있다.
6. 물병 문제의 상태에 '지금까지 부은 횟수'를 함께 넣어
(작은 병, 큰 병, 부은 횟수)로 적으면 상태 공간이 어떻게 되는지 쓰고,
그것이 좋은 선택인지 판단하시오. 판단의 근거를 숫자로 대시오.
📖 모범 답안
상태 공간이 끝없이 커진다.
물을 0L 붓는 헛동작조차 횟수만 1 올린 새 상태가 되므로, 같은 물병 모양이 횟수마다 따로 셈해진다.
허용 횟수 kmax를 두고 세어 보면 이렇다.
kmax
0
1
2
3
5
10
100
1000
없음
상태 수
4
12
24
40
72
152
1,592
15,992
무한
kmax가 2 이상이면 정확히 16 × kmax − 8이다.
곧 허용 횟수를 한 칸 늘릴 때마다 원래의 16가지가 통째로 한 벌씩 복사된다. 판단: 나쁜 선택이다. 근거는 두 가지다.
첫째, 상한을 두지 않으면 20만 개에서 강제로 멈춰야 할 만큼 끝없이 늘어난다.
둘째, 그렇게 늘린 대가로 얻은 것이 하나도 없다 — 이 표현으로 최단 경로를 찾아도 답은 여전히 6걸음이다.
공간만 무한이 되고 정보는 0인 것이다.
상태에는 목표를 판정하고 다음 행동을 정하는 데 필요한 것만 담는다는 규칙이 여기서 나온다.
🔎
더 알아보기
같은 상태를 두 번 세지 않는 법, 그리고 출발과 목표를 적는 일이 답을 어떻게 바꾸나
원리 더 깊이
길은 여럿, 상태는 하나 — 바둑의 '배치 수'와 '대국 수'
그림에서 (0,0)을 출발해 작은 병을 먼저 채우든 큰 병을 먼저 채우든 두 걸음 뒤에는 똑같이 (3,5)에 닿습니다.
걸어온 순서마다 따로 세면 왼쪽처럼 끝 칸이 둘이 되고, 상태로 세면 오른쪽처럼 두 길이 한 칸에서 만납니다.
왼쪽 모양을 트리, 오른쪽 모양을 그래프라고 부릅니다.
오늘 본 46,656 대 16의 차이가 바로 이 둘의 차이였고, if n not in seen: 한 줄이 트리를 그래프로 접는 일을 했습니다.
바둑의 크기를 말할 때도 이 두 가지 수가 자주 섞여 쓰입니다.
합법 배치 수는 규칙에 어긋나지 않게 돌이 놓일 수 있는 판의 모양이 몇 가지인가로, 19×19에서 약 2.08 × 10170입니다.
John Tromp가 2016년에 정확한 정수 값을 계산해 발표했지요. 오른쪽 그림처럼 상태를 센 수입니다.
반면 가능한 대국 수는 처음부터 끝까지 둘 수 있는 진행 순서가 몇 가지인가로, 왼쪽 그림처럼 갈래를 센 수입니다.
한 수에 갈림길이 약 250개, 한 판이 약 150수라고 잡은 250150, 곧 약 10360으로 흔히 어림해요 — 오늘 배운 bd 계산 그대로입니다.
같은 배치에 이르는 순서가 여럿이니 배치 수보다 훨씬 큽니다.
다만 바둑은 그래프로 접어도 10170이라, 접는 것만으로는 모자라고 덜 보고도 좋은 수를 고르는 방법이 따로 필요합니다.
역사
4.3 × 1019가지 지도에서 가장 먼 칸 찾기 — 루빅스 큐브
정리 표의 마지막 줄, 루빅스 큐브도 오늘의 문법으로 적힙니다. 상태는 사진처럼 여섯 면 스티커가 뒤섞인 배치 하나하나,
행동은 한 면을 90°나 180° 돌리는 것, 목표는 여섯 면이 각각 한 색이 되는 것이에요.
서로 다른 배치는 정확히 43,252,003,274,489,856,000가지, 약 4.3 × 1019입니다.
큐브가 나온 뒤로 사람들이 오래 물어 온 질문이 있습니다. "어떤 배치에서 출발해도 몇 걸음이면 반드시 맞출 수 있는가?"
상태 공간의 말로 바꾸면 목표에서 가장 먼 칸은 몇 걸음 떨어져 있는가입니다.
이 답은 2010년에야 나왔습니다. 토마스 로키키(Tomas Rokicki), 헤르베르트 코치엠바(Herbert Kociemba), 몰리 데이비드슨(Morley Davidson), 존 데스리지(John Dethridge)가
20걸음(반 바퀴 돌리기도 한 걸음으로 셈)이면 충분하다는 것을 컴퓨터로 증명했어요. 20걸음이 꼭 필요한 배치도 실제로 있습니다.
4.3 × 1019칸을 하나씩 뒤진 것은 아닙니다. 큐브를 통째로 돌리거나 거울에 비추면 같아지는 배치는 한 번만 세고,
배치를 큰 묶음으로 나눠 묶음째 처리했지요. 그러고도 구글이 내준 컴퓨터로 약 35 CPU-년이 걸렸습니다.
오늘 seen이 같은 상태를 두 번 세지 않아 46,656을 16으로 줄였듯, 같은 것을 다시 세지 않는 요령이 불가능해 보이던 계산을 끝낼 수 있게 했습니다.
사진: 색이 뒤섞인 루빅스 큐브 · 출처: Lars Karlsson (Keqs), Wikimedia Commons (CC BY-SA 3.0)
생각할 거리
출발과 목표를 바꾸면 — 지도는 그대로인데 답이 달라진다
출발을 (0,0)이 아니라 안쪽 칸 (1,1)로 바꾸면 갈 수 있는 상태가 16개에서 17개로 딱 하나 늡니다.
늘어난 하나는 (1,1) 자기 자신이에요. 그림의 화살표처럼 (1,1)에서 여섯 행동을 하면
(3,1) (1,5) (0,1) (1,0) (0,2) (2,0)으로 모두 테두리에 떨어지고,
테두리에서는 어떤 행동을 해도 테두리에 머물기 때문에 다시 안쪽으로 돌아올 수 없습니다. 만들 수 있는 양은 여전히 0~5 그대로입니다.
이 실험이 보여 주는 것은 "도달 가능"은 출발점에 따라 달라진다는 점입니다.
상태 공간이라는 지도 자체는 문제의 규칙만으로 정해지지만, 그 지도의 어디까지 갈 수 있는가는 어디서 출발했느냐가 정합니다.
이번에는 목표를 '작은 병에 정확히 4L'로 바꿔 봅시다. 그런 칸은 지도에 하나도 없습니다 — 작은 병은 3L까지밖에 담지 못하니까요.
탐색은 갈 수 있는 16개를 전부 뒤진 뒤 "없다"고 답할 뿐, 목표가 애초에 말이 되는지는 알려 주지 않습니다.
문제를 상태·행동·목표로 다시 적는 일은 사람의 몫이고, 그 일이 틀리면 알고리즘이 아무리 좋아도 소용없습니다.
