풀면 기념품 준다는 사이냅소프트 문제 :: 2007/09/10 11:54


기탁님 블로그에 오늘 재미난 내용이 올라왔더군요. 다름 아닌 사이냅소프트에서 개발자들을 상대로 하는 이벤트 였습니다. 그런데 기념품이 먼지를 모르겠습니다. 마지막까지 가르쳐주지 않더군요. 갈수록 코딩을 더 마니 요구하는 문제들이 나옵니다. 사실 2,3,4단계는 전부 같은 문제입니다. 문제 푸는 분들의 삽질 시간을 덜어 드리기 위해서 간단한 소개와 힌트만 담아보았습니다.

일 단계: 피보나치
피보나치 수열에 관한 문제입니다.
문제는 여기서 보실 수 있습니다.

저는 이 문제에서 완전 삽질했습니다. 왜냐하면 문제가 a, b 두 수가 주어졌을때 사이에 존재하는 피보나치 숫자 개수를 구하는 건줄 알았거든요. a+b뭐 이런 식이 답이 되는 줄 알았던거죠. 생각하고 적고, 구글링을 해도 답을 찾을 수가 없었습니다. 한탄하고 있는 이 때 문제를 다시 보았습니다. 밑에 다른 글씨로 뭔가 적혀있더군요. 그렇습니다. 그 숫자 사이의 피보나치 숫자의 합을 구하는게 문제였습니다. 이건 뭐 쉽죠. 숫자가 커서 __int64로 구해야 합니다. 그러면 금방 답이 나오죠.

이 단계: SYNAP + SOFT = WANTS + YOU
다음 단계는 헨리 듀드라는 사람이 만든 암호문에 관한 문제 입니다. 알파벳 각 자리가 한 가지 숫자에 대응하는 쉬운 암호죠. 아래는 원리를 가르쳐주는 간단한 암호문입니다.

SEND + MORE = MONEY
9567 +1085 = 10652[E=5, D=7, M=1, O=0, N=6, S=9, R=8, Y=2]

문제는 SYNAP + SOFT = WANTS + YOU의 암호문을 만족하는 숫자들을 구하는 겁니다.
푸는 방법이야 여러가지가 있겠지만 저는 걍 무식하게(brute force)로 풀었습니다.
그래도 금방 끝나더군요. 이 문제의 경우 알파벳과 숫자가 각각 열 개기 때문에
C++에 있는 next_permutation을 사용하면 쉽게 구할 수 있습니다.

삼 단계: 78, 79번째 단어를 구하기
그 다음 단계도 문제는 똑같습니다. 동일한 암호문 문제를 푸는 거죠.
사전 파일이 주어지고 그 중에 암호가 있는 78, 79번째 단어를 구하는 겁니다.

한 가지 주의해야 할 것은 여기서는 next_permutation이 안통합니다.
왜냐하면 글자는 5개고, 숫자는 10개인 뭐 그런 경우가 있기 때문이죠.
저는 걍 간단하게 재귀로 만들어서 돌렸습니다.
좌변은 같고 우변만 틀리기 때문에 우변만 처리할 수 있도록 만들었죠.

무식하게 풀어서 생각보다 쪼금 오래 걸리더군요.
78, 79번째 단어라 다행이었습니다.
1078, 1079였으면 생각하기 시러지죠.

사 단계: 헨리 듀드 암호 해독 프로그램 작성
파이날 단계도 똑같습니다. 헨리 듀드 암호문을 해독하는 프로그램을 만드는 겁니다.
아래와 같이 암호문이 주어지고 그것에 답을 구하는 프로그램을 만드는 문제입니다.
SYNAP + SOFT = WANTS + YOU
SEND +MORE = MONEY
EMAIL= SPAM + SPAM + SPAM + SPAM + SPAM + SPAM
FORTY +TEN+ TEN= SIXTY
NUMBER = SQUARE + SQUARE + SQUARE + SQUARE
SEVENTY = FIVE + SEVEN + ELEVEN + TWELVE + FIFTEEN + TWENTY
MANET + MANTISSE + MIRO + MONET + RENOIR = ARTISTS
SIX+SIX+SIX = NINE + NINE
ABCDE*F=GGGGGG
ADAM+AND+EVE=MOVED
FIVE+FIVE+NINE+ELEVEN=THIRTY
CROSS+ROADS=DANGER
USE + LESS = KIDDY
BILL + WILLIAM + MONICA = CLINTON
GREEN + ORAGNE = COLORS
CEZANNE + MANET + MATISSE = ARTISTS
OLD+SALT+TOLD+TALL=TALES
COFFEE + COFFEE + COFFEE = THEOREM
SEND * ME = EMAIL
POWER = YOUR + SHOW
ALLEN = K * JEON
갈수록 노가다틱해지죠. ㅋㅋ 저는 이제껏 쓰던 거에서 문자열을 처리할 수 있는 간단한 스캐너를 추가하고, 좌변 우변을 리스트로 등록해서 계산하는 방법으로 문제를 풀었습니다. 사실 암호푸는 코드보다 부가적인 코드를 더 마니 만들어야하는 부분입니다. 다항식을 리스트로 연결해서 구하는게 핵심이라면 핵심일 수 있겠네요.

2 단계에서 4 단계로 오면서 느끼겠지만 코드는 점점 더 제너럴한 솔루션을 구하는 걸 원합니다. 사실 2 단계 때 벌써 범용적으로 쓸 수 있는 코드를 만들었다면 4 단계 까지는 금방 가죠. 저는 그 때 그 때 답을 구하는데 맞춰서 작성해서 4 단계 때 제법 마니 뜯어 고쳐야 했습니다. ㅋㅋ

차마 조잡해서 소스는 못 보내고, 화면만 보내도 기념품 준다길래 화면만 보냈습니다. 답이 맞는지 아닌지도 모르겠습니다. 그나저나 헨리 듀드같은 저런 문제는 어디서 구하는걸까요? 20세기 최고의 퍼즐리스트라는데 저는 처음 들어봤습니다. ㅎㅎ

스폰서
글타래

  • 2주간 인기 글
  • 2주간 인기글이 없습니다.
Trackback Address :: http://jiniya.net/tt/trackback/601
  • Gravatar Image.
    snaiper | 2007/09/10 13:09 | PERMALINK | EDIT/DEL | REPLY

    뭐 준다고 하냐?...어제 피곤해서 3단계에서 스톱해놓은 상태...^^:
    사실 Constraint Programming인데, 이번 기회에...제대로 배운다는 ^^

    근데 니 이름 리스트에 없던데...그거 안 남길수도 있는거였냐? 몰랐삼 ㅠ.ㅠ

    글고 "a, b 두 수가 주어졌을때 사이에 존재하는 피보나치 숫자 개수" 도 나름 쉽다. 구간별로 갯수가 일정하게 나오거든...일반적으로 처리하기에는 조금 고민해야 하는데..(그래봐야 코드 한 두줄 차이겠지만..)이런 문제니까.. 한두번 정도만 시도하면 뭐...ㅎㅎㅎ

    • Gravatar Image.
      codewiz | 2007/09/10 13:39 | PERMALINK | EDIT/DEL

      개수 구하는 코드야 만들기 쉽죠 ㅠㅠ
      a,b에 대한 수식으로 풀 수 있느냐를 물은 거예용...

    • Gravatar Image.
      snaiper | 2007/09/10 16:08 | PERMALINK | EDIT/DEL

      어느 정도 constant로 나와서 잘만하면 풀수 있을거라 봤는데...object 님의 말씀들어보니 일반화할 수 있는 공식이 아닌 듯 싶네요

  • Gravatar Image.
    object | 2007/09/10 14:10 | PERMALINK | EDIT/DEL | REPLY

    앗.. 여기에서도.. snaiper님의 말씀에 약간 딴지(?)를 걸어보자면.. 개수가 일정하지는 않아요. 예를 들어, 31개나 35자리 숫자들은 4개만 있어요. 아, 7자리 숫자들도 4개만 있네요.

    • Gravatar Image.
      snaiper | 2007/09/10 16:07 | PERMALINK | EDIT/DEL

      아 그래요? 30개까지는 안해봐서...7자리는 해봤는데 5개 나오던데..계속 잘못 했나봐요 ^^:

    • Gravatar Image.
      codewiz | 2007/09/10 17:41 | PERMALINK | EDIT/DEL

      object님은 수학도 잘하시는 군요. 부럽습니다.
      저도 초등학교때는 산수 꽤나 했는데 ㅠㅠ

  • Gravatar Image.
    object | 2007/09/10 18:09 | PERMALINK | EDIT/DEL | REPLY

    그냥 엑셀로 2분만에 뚝딱했다니깐요 ^^; n번쨰 피보나치 수는 a = (1+sqrt(5))/2로 했을 때, (1/sqrt(5))*(a^n - (1-a)^n) 입니당.. 자리수 변화는 그냥 여기에다가 log10만 씌어주면 쉽게 나오고요 ㅎㅎ

Name
Password
Homepage
Secret