튜링 머신 - 문제를 푸는 방법(예시문제-B48 KWC)(오류 수정 및 추가 설명)
잘못된 부분을 알려주셔서 수정하고
설명이 미흡했던 부분들을 보충했습니다.
제가 올린 글은 문제를 푸는 접근방법 중 하나일뿐
꼭 이렇게 푸실 필요는 없습니다.
사실 저도 매번 이렇게 풀진않습니다
-------------------------------------
평소 스도쿠나 가쿠로 같은걸 즐겨했었는데
논리적인 수학퍼즐같은 튜링 머신이 한글판으로 나오자마자 바로 질렀습니다.
주로 1인플을 돌리고 저는 꽤 만족하는 게임이지만
모두가 만족할만한 게임은 아니라는 생각이 들더라구요
은근히 셋팅도 번거롭고 다인플로 돌릴만한 게임은 아니라 아쉽지만
추론을 하고 그게 들어맞을때의 쾌감이 짜릿해서
아마 꾸준히 즐길 것 같습니다.
제가 튜링머신을 풀면서 익힌
문제를 푸는 방식에 대해서 전해볼까합니다.
일단 예시로 조건 4개짜리 추가문제 B48 KWC를 예시로 들겠습니다
나중에 이 문제를 풀고싶으신 분들은 뒤로가기를 눌러주세요
먼저 B48 KWC는 4개짜리 조건에서 중간 난이도로
A-2, B-12, C-14, D-18 카드를 사용합니다
A
B
C
D
여기서 처음 임시 코드를 만드실 때 중요한 가정을 해야하는데
저 "4개의 조건을 만족하는 단 1개의 숫자 조합"만 나와야된다는 겁니다
4가지 조건이 모두 O가 나왔는데
이것도 되고 저것도 되는 상황이 나오면 안된다는 겁니다
예) 세모가 3, 네모가 4인 상태에서 동그라미가 3이하라는 정보를 알게됐다면
동그라미가 홀수냐? 짝수냐 라는 조건이 있을때
홀수일 경우 동그라미가 1, 3이 가능하죠
짝수일 경우 동그라미가 2만 가능하죠
그렇다면 동그라미는 짝수가 될 수 밖에 없습니다.
여기서 A는 세모의 숫자를 상당히 구체적으로 알 수 있게 해주는 조건이죠
그리고 나머지 조건들은 정확한 범위보다는 상관관계를 알 수 있는 조건들이고요
여기서 C 조건을 잘 보면 제일 작은 기호를 알 수 있는데
제일 작은게 정해지면 다른 기호가 그 숫자랑 같을 수가 없습니다.
제일 작기 때문에요.
여기서 모든 조건을 종합했을 때 숫자의 조합이 단 1개만 나오도록 만드는 조합들을 생각해봅시다
(조합은 세모-네모-동그라미 순)
예) 4-5-1 : 세모 4, 네모 5, 동그라미 1
만약에 세모가 3보다 크다고 나올 경우1
ㄴB) 무조건 세모보다 동그라미가 커야하고(여기서 세모 4, 동그라미 5가 픽스됩니다)
(같을 경우 세모랑 동그라미가 같기 때문에 이 둘은 제일 작은이 될 수 없고
결국 제일 작은게 네모가 되고 모든 숫자의 합이 홀이든 짝이든 조합이 단 1개가 나올 수 없습니다)
(예) 네모가 제일 작고 홀일 경우 4가지 경우가 나와버려서 실패 5-1-5, 5-3-5, 4-1-4, 4-3-4
네모가 제일 작고 짝일 경우 3가지 경우가 나와버려서 실패 5-2-5, 5-4-5, 4-2-4)
(세모보다 동그라미가 작을 경우는 답이 1개가 나올 수 없겠죠)
----------------------------------------
1-1 O
ㄴC) 세모가 제일 작을 경우
(세모가 3보다 크니깐 4, 5 둘 중 하나인데 제일 작다고 했으니 5가 될 수 없고,
나머지는 세모보다 크니 4-5-5가 됩니다)
ㄴD) 무조건 모든 숫자의 합이 짝수가 나옵니다.(4-5-5)
---------------------------------------
1-2 O
ㄴC) 네모가 제일 작을 경우
ㄴD) 무조건 모든 숫자의 합이 홀수여야합니다(4-2-5)
(세모랑 동그라미 합이 9, 홀수라 모든 숫자 합이 짝수면 네모가 1, 3이 가능해서 안되고, 홀수여야 네모가 2로 픽스됩니다)
$ 만약에 세모가 3보다 큰 걸 알게됐다면, 테스트 B는 무조건 세모보다 동그라미가 클테니 할 필요가 없습니다.
다음 테스트로 C 또는 D를 해서 나온 결과로 바로 코드를 찾을 수 있게됩니다.
세모가 3일 경우 2
----------------------------------------
2-1 O
ㄴB) 세모보다 동그라미가 작을 경우
ㄴC) 무조건 네모가 제일 작게 나옵니다.
(동그라미가 제일 작을 경우 네모는 2~5가 가능하고 홀수든 짝수든 조합이 1개만 나오지 않으니 답이 될 수 없습니다.)
ㄴD) 합이 짝수만 가능하고(3-1-2)
----------------------------------------
2-2 O
ㄴB) 세모와 동그라미가 같을 경우
ㄴC) 무조건 네모가 제일 작을테고
ㄴD) 합은 홀 또는 짝이 나오겠네요
(홀 : 3-1-3, 짝 : 3-2-3)
----------------------------------------
세모보다 동그라미가 클 경우엔 조합이 1개보다 많이 나오기 때문에 답이 될 수 없습니다.
예) 세모가 제일 작고 합이 홀수면 3-2-4, 3-4-4... / 짝수면 3-1-4, 3-3-4...
네모가 제일 작고 합이 홀수면 3-2-4, 3-1-5 / 짝수면 3-1-4, 3-2-5
$ 만약에 세모가 3인걸 알게됐다면, C는 무조건 네모가 제일 작을테니 할 필요가 없습니다.
B는 세모가 동그라미보다 작거나 같을 것이고
D는 짝수가 나오면 한번 더 검증을 해야겠지만 홀수가 나온다면 3-1-3이 됩니다.
(2)-1)은 합이 짝수일때만 답이 나오고 2-2)는 홀일때 짝일때 답이 1개씩 있으므로 홀일 경우엔 2-2) 홀 밖에 없습니다.)
세모가 3보다 작을 경우 3
----------------------------------------
3-1 X
ㄴB) 세모보다 동그라미가 작을 경우
(세모는 2, 동그라미는 1로 고정됩니다)
ㄴC) 무조건 동그라미가 제일 작아야합니다.
ㄴD) 네모가 2~5가 가능하기에 홀이든 짝이든 답이 여러개가 나와서 답이 될 수 없습니다.
----------------------------------------
3-2 O
ㄴB) 세모와 동그라미가 같은 경우
ㄴC) 무조건 네모가 제일 작아야하고
(세모 2, 네모 1, 동그라미 2 픽스)
ㄴD) 무조건 홀수가 나와야합니다(2-1-2)
----------------------------------------
3-3
ㄴB)세모보다 동그라미가 큰 경우
ㄴC)무조건 네모가 제일 작고
(세모 2, 네모 1 픽스)
ㄴD)무조건 홀수가 나와야합니다(2-1-4)
(동그라미가 3, 4, 5가 가능한데 합이 짝수면 3, 5가 가능해서 2개고 합이 홀수면 4만 가능하므로)
----------------------------------------
여러 가설들을 세워서 나올 수 있는 조합들을 생각해서 임시코드를 짜봅니다.
먼저 세모의 범위를 맞추는게 좋겠네요
저는 세모가 3이하라고 가정을 하고
네모는 세모보다 작게
동그라미는 세모보다 크게 설정을 해보겠습니다
임시코드로 2-1-4를 설정합니다
먼저 제일 중요한 A 테스트를 진행합니다.
결과는 O
세모가 3보다 작다고 나왔습니다.
이럴 경우
3-2, 3-3 중에서
둘 다 네모가 제일 작고, 합이 홀수이기 때문에
세모와 동그라미의 관계가 같은지, 큰지만 확인하면 될것같습니다.
B를 테스트해봅니다.
여기서 O가 뜨고, 바로 답이 나와버렸습니다.
답은 2-1-4 네요
임시코드로 3-2-4를 설정했다고 가정해봅시다
처음 A 테스트에서 X가 나왔을 때
2번 케이스는 모두 실패라는 걸 알게됐습니다.
1-1, 1-2, 3-2, 3-3 중에 답이 있다는건데
먼저 B 테스트를 비교해보면 1-1, 1-2, 3-3은 세모보다 동그라미가 크고,
3-2만 세모랑 동그라미가 같습니다.
C 테스트의 경우 1-1만 유일하게 세모가 제일 작고 나머지는 네모가 제일 작습니다.
D 테스트의 경우 짝수면 1-1, 3-3 / 홀수면 1-2, 3-3
여기서는 바로 맞추기 힘들고 B 테스트에서 세모랑 동그라미가 같을 경우에만 쉽게 풀리겠네요
B 테스트를 진행해봤더니 O가 나왔습니다.
이러면 1-1, 1-2, 3-3이 가능하겠네요
마지막으로 C 테스트를 해보니 O가 나왔습니다.
이러면 1-2, 3-3만 남았네요
다음 라운드로 넘어갑니다.
다시 임시코드를 재설정하는데
세모가 3보다 크거나 작은지만 알면 끝납니다
세모에 3을 제외한 아무 코드나 넣고 B 테스트를 거친 뒤 나온 결과에 따라서 답을 고르시면 됩니다.
컴퓨터는 2라운드 질문 4번에 풀었다고 나오네요
지금까지 튜링 머신 문제를 푸는 방법에 대해서 설명을 드렸는데요
제가 설명한 것은 튜링 머신을 푸는 여러 방법 중에 하나일 뿐이니 꼭 이렇게 푸셔야되는건 아닙니다.
각자의 방법으로 재밌게 즐기시길 바랍니다
