알고리즘 코딩 이벤트 마지막 문제

By | 2012년 9월 12일

자… 이제 마지막 문제입니다.

앞서 세 문제를 생각보다 쉽게(?) 풀어주신 덕에, 이번 문제는 『코딩 인터뷰 완전 분석』의 ‘고난이도 연습문제’에서 선택했습니다.

하지만, 공성을 위해 달려가는 오크 워리어처럼 열정 넘치게 달려들어주시길 기대하겠습니다. ^^

(아… 아이폰 출시에 묻히면 안 되는데… ㅠㅠ)

 

유의사항

1. 풀이과정이나 해답 등은 각자 블로그에 올리신 후, 트랙백 혹은 댓글로 알려주세요.
트랙백 주소 : http://www.insightbook.co.kr/post/3917/trackback
(트랙백은 조금 시간이 걸린 후 등록됩니다.)

2. 블로그 글 제목을 다음처럼 작성해주세요.
‘코딩 인터뷰 완전 분석 215쪽 문제 18.10 풀이’

3. (선택사항 : 글에 『코딩 인터뷰 완전 분석』 표지를 넣어주시면 감사하겠습니다. ㅎㅎ)

4. 이번 문제는 1주일간(9월 18일 화요일 자정까지) 응모받습니다.

 

문제

『코딩 인터뷰 완전 분석』215쪽 고난이도 연습문제 18.10

사전에 등장하고 길이가 같은 두 단어가 주어졌을 때, 한 번에 글자 하나만 바꾸어 한 단어를 다른 단어로 변환하는 프로그램을 작성하라. 변환 과정에서 만들어지는 각 단어도 사전에 있는 단어여야 한다.

[실행 예]

input : DAMP, LIKE
output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

[사전 데이터]

네 글자 단어 – word4

다섯 글자 단어 – word5

 

[심화 문제 – 풀지 않아도 됩니다]

심화문제 1: 가장 적은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다.
심화문제 2: 최대한 많은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다. 단, 변환 과정에서 같은 단어가 두 번 나오면 안됩니다.

 

상품

3주간 진행될 『문제로 풀어보는 알고리즘』『구글러가 전하는 IT 취업 가이드』『코딩 인터뷰 완전 분석』 발간 기념 문제 풀이 이벤트에 참여해 정답을 올리신 분 중,
한 분께는 HP 프로라이언트 마이크로서버를,
다섯 분께는 요즘 가장 핫! 한 아이템 중 하나인 Raspberry Pi를 각 하나씩 선물로 드립니다.
(Raspberry PI를 생각보다 빨리 구했습니다. 현재 출판사 사무실에서 두근거리는 마음으로 주인이 결정되기를 기다리고 있답니다. ㅎㅎ)

다소곳한 Raspberry Pi의 모습

 

관련 도서

구글러가 전하는 IT 취업 가이드

구글러가 전하는 IT 취업 가이드

구글러가 전하는 IT 취업 가이드 지은이 : 게일 맥도웰 / 옮긴이 : 강은진 정가 : 16,000원   344쪽 / 판형 : 145*227 / 판 출간일 : 2012년 7월 15일 ISBN-13 : 978-89-6626-042-3 지은이 소개 게일 맥도웰(Gayle McDowell) 구글에서 3년간 일하면서 채용 위원회에서 1000명이 넘는 지원자의 면접 결정 과정에 참여했다. 마이크로소프트와 애플에서 인턴으...
문제로 풀어보는 알고리즘 : 프로그래밍 트레이닝 Q&A

문제로 풀어보는 알고리즘 : 프로그래밍 트레이닝 Q&A

  소스코드   지은이 : 황인욱, 김용혁 정가 : 25,000원   408쪽 / 1판 출간일 : 2012년 8월 1일 ISBN-13 : 978-89-6626-046-1     저자소개 황인욱 서울대학교 컴퓨터공학부에서 학사와 석사 학위를 취득하였다. 티맥스소프트 연구소에서 검색엔진과 웹 크롤러를 개발하였고, 삼성전자 생산기술연구소에서 반도체 설비 장애예측, 생산성 향상 시스...
생각하는 프로그래밍(신판_무선)

생각하는 프로그래밍(신판_무선)

생각하는 프로그래밍 (Programming Pearls )       지은이 : 존 벤틀리 / 옮긴이 : 윤성준, 조상민 정가 : 22,000원   424쪽 / 판형 : A5 / 신판 1쇄 출간일 : 2013년 12월 24일 ISBN-10 : 978-89-6626-099-7 ISBN-13 : 978-89-6626-101-7   ...

40 thoughts on “알고리즘 코딩 이벤트 마지막 문제

  1. 석대진

    오…저는 3문제정도 더 남았는 줄 알았는데, 마지막이라는 왠지(?) 아쉽네요.
    앞서 문제는 수정전 글을 보고 많이(?) 고생했기에 이번에는 궁금하거는 충분히 물어보고 싶네요. 그래서 아래와 같이 적어봅니다.

    1. 반드시 한글자씩 변경하는 메소드를 만들어야 하나요? ( output처럼 만들기 위해서는 한글자씩 변경하는 메소드가 필요없을 수도 있을 것 같거든요… )

    2. 혹여 사전에 존재하지 않는 단어가 발생했을 경우 없다고 메세지로 보여주면 되나요? 아니면 거너뛰고 두글자 이상 변경한 사전에 존재하는 단어를 보여주면 되나요? ( 예 LIME, LIKP가 존재하지 않을때 )

    DAMP -> LAMP -> LIMP -> (X) -> LIKE

    3. 당연하겠지만, input단어는 반드시 사전에 있는단어만 진행하면 돼죠?

    아이폰에 관심은 많지만, 휴대폰 약정의 끝이 안보이는 관계로..무관심 -_-;

    Reply
    1. raccoony

      저도 아쉽지만 날이 갈수록 채점의 어려움과 도전하시는 언어의 다양성 덕에, 이쯤에서 그만할까 합니다. ㅎㅎ

      답변 드립니다.

      1. 변경하는 과정 중에는 반드시 한글자씩 변경해야 합니다. 프로그램 내에서 함수나 자료구조는 마음대로 사용하셔도 되고요~

      2. 변경 과정 중 사전에 단어가 존재하지 않는다면, LIMP에서 LIKE로 넘어갈 방법이 없는 셈이니 ‘IMPOSSIBLE’을 출력하시면 되겠습니다.
      (혹은 DAMP -> LAMP -> LIMP -> IMPOSSIBLE)

      3. input 단어와 output 단어가 사전에 없으면 ‘IMPOSSIBLE’을 출력하세요.

      (아이폰에 관심이 없으시다니 다행(?)입니다. 저는 약정이 곧 끝나지만, 예산 절감차 눈을 감고… ㅎㅎ)

      Reply
    2. 석대진

      그리고 심화문제에 보면, 단어수가 있는데…. 한번에 한글자씩 바꾸기 때문에, 길이가 4이면 4번, 5이면 5번아닌가요? 예제 혹은 부연 설명 부탁드립니다.

      Reply
      1. raccoony

        네.

        네 글자 단어장을 사용했을 때 가장 적은 수의 단어는, 첫 단어와 끝 단어를 포함해서 5개가 될 겁니다. 다섯 글자 단어장을 사용하면 6개가 되겠고요. ^^

        가장 많은 수는… 단어장에서 있는 대로 다 찾아야겠죠? ㅎㅎ

        Reply
        1. raccoony

          제가 착각했네요~ 네 글자 단어는 최소 4단계, 다섯 단어는 최소 5단계입니다. ^^

          Reply
    3. nonblock

      다음과 같이 단계를 더 늘릴수 있을 것 같습니다.

      DAMP – LAMP – LIMP – LIME – DIME – DIVE – LIVE – LIKE

      Reply
    4. 석대진

      T_T… 이번에는 문제보다 질문이 더 많을 것 같네요.

      DAMP – LAMP – LIMP – LIME – DIME – DIVE – LIVE – LIKE

      5번째 단어가 “DIME”가 될 수 있는 건가요? 이미 LI?E까지 찾았는데 다시 회귀?
      그리고 DIVE에서 “V”는 두 단어 중 어디도 포함되지 않았는데 나올수 있는건가요?

      Reply
    5. 석대진

      최소는 DAMP -> LAMP -> LIMP -> LIME -> LIKE 어느정도 이해가 되는데, 최대도 예제를 좀 부탁드립니다.
      혹은 이번에는 앞 문제처럼 검증예제 같은건 없나요 -_-;; 테스트자료 찾기가 더 힘드네요 ^^;;

      Reply
  2. Pingback: Tneconni

  3. Pingback: 야생코딩

  4. Pingback: Fearless on my breath.

  5. Pingback: 무규칙이종IT 엘국

  6. Pingback: A 프로그래머

  7. Pingback: 지금 얼마나 신나요?

  8. xgate

    제가 잘못해석한건지 모르겠는데요~

    ‘모든 문자를 한번씩은 반드시 수정해야 한다’고 봐야하나요?

    아니면,

    input: DAMP, LAMP

    이렇게 될때 output은 ‘DAMP -> LAMP’ 이렇게 되는건가요?

    저는 전자로 이해하고 있습니다만 ^^;

    Reply
    1. xgate

      case1: 변환도중 정답을 찾으면 성공!!(꼭 단어길이만큼 안가봐도 됨)

      ex)damp ramp
      damp -> ramp

      case2: 몇번째 문자를 변경해도 관계없으나(중복가능) 반드시 단어길이만큼 수정되야 성공!!

      ex)damp ramp
      damp -> gamp -> lamp -> samp -> ramp

      case3: 모든 문자를 한번씩은 변환해야 성공!!

      ex) damp like
      damp -> lamp -> limp -> lime -> like

      Reply
    2. 석대진

      이번은 정말 문제해석이 어렵죠 T_T
      어떤 분은 거리(?)를 계산하고 푸시는 것 같고….심화문제에 최대한 많은 단어 예제만 들어주셔도 좀 이해가 될듯한데…

      제가 이해한 내용은 아래와 같습니다.

      1234 -> ABCD

      (1,A), (2,B), (3,C), (4,D) 이 중에 하나를 선택해서 사전에 있는 단어를 찾고 찾았다면, ABCD가 될 때까지 계속 반복, 그런데 없다면 IMPOSSIBLE

      코딩인터뷰 책이 없는데, 거기에 먼가 있을까요 ㅎㅎ

      Reply
    3. raccoony

      @xgate 님
      input: DAMP, LAMP 일 때는
      DAMP -> LAMP가 맞습니다.

      모든 문자를 한 번씩 변환할 필요도 없겠네요.
      (제가 네 글자 단어는 네 번 변환된다고 잘못 이야기해서리… 오해를 일으켰습니다. ㅡ,.ㅡ)

      @석대진 님
      책의 문제 페이지에도 별 내용은 없답니다~ ^^a

      Reply
  9. raccoony

    많은 분들이 문제 해석에 어려움을 토로하셔서 출력 예시를 보여드립니다.

    (1) 사전이 {aa, ab, ac, cc}이고, 입력이 aa -> cc일 때는 두 가지 방법이 있습니다. 둘다 맞는 방법입니다. 둘 중에 아무거나 출력해도 됩니다.
    aa-ab-ac-cc
    aa-ac-cc
    (단, 심화문제 1에 대해서는 두 번째가 정답이고, 심화문제 2에 대해서는 첫 번째가 정답입니다.)

    (2) 사전이 {aa, ab, bc, cc}이고, 입력이 aa-cc일 때 방법없음.
    ‘impossible’ 출력

    (3) 사전이 {aa, ab, bb, bc, cc, dd}이고, 입력이 aa -> cc일 때 aa-ab-bb-bc-cc가 유일한 답입니다. 방법이 있기 때문에 ‘impossible’ 출력하면 안 됩니다.

    Reply
    1. xgate

      제가 ‘제대로’ 오해하고 있었군요 ㅜㅜ 다시 풀어야겠네요 ㅋㅋㅋ
      알겠습니다. 감사합니다 🙂

      Reply
  10. Pingback: 개.발.인생

  11. Pingback: 소내기의 겸손한 지식

  12. Pingback: 산수유나무

  13. Pingback: Life is Continuity of Blunder

  14. Pingback: 코딩 인터뷰 완전 분석 215쪽 문제 18.10 풀이 | dlimpid's blog

  15. Pingback: 어머나 이 패는 불러야해

댓글 남기기