4번 - 큰 수와 작은 수의 합 - 실전 유형 코딩 테스트 모의고사 - 시즌4
실전 유형 코딩 테스트 모의고사 - 시즌4
    • 01
      모의고사 소개
    • 본 과목 소개
      FAQ
    • 02
      모의고사 진행
    • 시험 시작하기
      문제 이동하기
      코딩 테스트 화면
      시험 결과 확인
    • 03
      [1차 모의고사] 2016년도 문제 해설
    • 1차 모의고사 총평
      1번 - 가장 가까운 두 점
      2번 - 펠린드롬 넘버 만들기
      3번 - 단어 찾아내기
      4번 - 큰 수와 작은 수의 합
    • 04
      [2차 모의고사] 2015년도 문제 해설
    • 2차 모의고사 총평
      1번 - 길 확인하기
      2번 - 괄호 짝 맞추기
      3번 - 단어 빈도 추출
      4번 - 사천성 시뮬레이터
    • 05
      [부록] 시험 대비하기
    • 시험 환경 체험하기
      실력 기르기
    • 06
      [부록] 선배의 꿀팁
    • 2016년 입사자의 꿀팁 - 1
      2016년 입사자의 꿀팁 - 2
    4번 - 큰 수와 작은 수의 합
    03 [1차 모의고사] 2016년도 문제 해설
    4번 - 큰 수와 작은 수의 합

    큰 수와 작은 수의 합 문제는 두 가지 솔루션으로 풀이할 수 있습니다. 


    그리디 솔루션


    이 문제는 주어지는 숫자의 개수가 적기 때문에 다양한 풀이를 적용할 수 있지만, 결과로 출력해야 할 숫자가 크기 때문에 64비트 정수형을 사용하지 않으면 계산 과정에서 문제가 생길 수 있습니다. 항상 출력 결과가 어떤 범위를 가지게 될 지 고민하시기 바랍니다.

    •  실제 문제지에서는 출력 범위에 대한 언급이 전혀 없었습니다. 즉, 20자리 99999999999999999999와 같은 숫자가 정답이 되는 입력이 들어와도 이상하지는 않다는 이야기죠. 이럴 경우에는 큰 수에 대한 처리까지 작성해야 만점을 받을 수 있습니다.
    • 다만, 시험 방식의 차이를 고려하여 문제의 난이도 조절을 위해 본 모의고사에서는 64비트 정수형 범위 이내로 제한했습니다. 

      아마 가장 쉽게 떠올릴 수 있는 솔루션은 그리디하게 생각하는 것입니다. 아래와 같은 순서로 접근하면 됩니다.

    • 모든 숫자를 정확히 한 번씩 사용 해야한다.
      • 어떻게 조합하더라도 자릿수는 같다는 걸 알 수 있습니다.
    • 숫자를 배치할 때 앞 자리가 9에 가까운 숫자를 앞으로 꺼내면 유리해보입니다.
    • 마찬가지로 작은 숫자는 앞자리가 1에 가까운 숫자를 앞으로 꺼내면 유리해보입니다.
      • 숫자를 정렬하여 접근하는 방법을 떠올려 볼 수 있습니다.


     하지만 이것으로 끝이 아닙니다. 바로 숫자의 가장 앞자리가 같은 예외 경우를 고려해야 합니다. 예를 들어서 32, 3, 34라는 세 숫자를 이어붙이는 케이스를 고민해봅시다. 단순히 대소관계로 정렬하면 3, 32, 34가 됩니다. 이 경우 뒤에서부터 이어붙이는 전략을 택하면 34323이 되는데, 이는 34332라는 반례가 존재합니다. 즉, 3과 32는 앞자리가 서로 같지만 3은 뒤에 다른 3x류의 숫자를 놓아 33...로 이어져 갈 수 있는 반면에 32은 항상 32.... 로 시작하는 패턴을 만들게 됩니다. 하지만 34는 항상 3보다 먼저 쓰는게 유리하다는 걸 알 수 있죠.

     그래서 이 문제의 키는 한 자리 숫자에 대한 새로운 대소 관계를 아래와 같이 정의하면 됩니다. 

    •    31 < 32 < 3 < 33 < 34 < 35 ...
    •    41 < 42 < 43 < 4 < 44 < 45 ...


     이제 이를 구현하는 일이 남았습니다. 물론 수 많은 if문으로 처리할 수 있습니다. 한번 고민해보세요. Java 답안 코드에서는 문자열로 가상의 두 자리 숫자를 만들어 정렬하는 방법을 소개합니다.

    • 예를 들어, 실제로는 4일지라도 정렬을 위한 비교 과정에서는 44처럼 비교하는 겁니다. 첨부된 코드를 참고해보세요.


    동적계획법 솔루션


     이 문제는 사용해야 할 숫자의 개수가 적고 각 숫자는 사용 한다/안한다 두 경우만이 가능하므로, 어떤 시점에서 숫자들을 사용한 현황을 0과 1로 표현되는 비트로 표현할 수 있습니다. 어떤 숫자 X가 마지막으로(가장 오른쪽에) 사용되었을 때 이 숫자를 포함해 총 k개의 숫자를 사용해서 만들 수 있는 가장 큰 숫자는 무엇일까요?

    • 만약에 이 X를 제외한 (k-1)개의 숫자를 사용하여 만들 수 있는 가장 큰 숫자를 알고있고 그 값을 Y라고 한다면,
    • 이 경우에는 YX와 같이 이어붙이는 것이 이 질문에 대한 답이라고 할 수 있습니다.


     즉, 사용하고자 하는 어떤 k개의 숫자에 대하여 이 숫자를 모두 사용하여 만들 수 있는 가장 큰 숫자는

    • 1번째 숫자가 가장 마지막에 사용된 경우 만들 수 있는 가장 큰 숫자 
    • 2번 째 숫자가 가장 ...
    • ..
    • k번째 숫자가 가장 ...

     위의 k가지 경우 중 하나라는 걸 알 수 있습니다. 즉, 전체 k개의 숫자로 만들 수 있는 숫자를 조회하기 위하여 k-1개의 숫자를 통해 만들 수 있던 결과에 사용하지 않는다고 가정한 숫자를 뒤에 이어붙이며 만들 수 있습니다. 그리고 이런 방식으로 숫자의 사용현황으로 하나의 상태를 표현할 수 있습니다.


    앞서 언급한 아래와 같은 값을 함수 long long dp(S)로 정의해 봅시다. 

    • long long dp(S)  := S에 포함 된 모든 숫자를 사용해 총 k개의 숫자를 사용해서 만들 수 있는 가장 큰 숫자
    • S는 k개의 숫자에 대한 사용 여부를 정수로 표현한 값입니다. 아래의 수식을 참고하세요.
    • 이 처럼 가변적인 길이의 상태를 하나의 정수로 표현하여 상태공간을 설계하는 동적 계획법을 Bit DP라고 합니다. 

     위와 같은 형태로 동적 계획법이 가능한 형태의 함수 dp(S)를 설계할 수 있으며, 이에 대해 동적계획법을 구현하면 됩니다. 상세한 구현은 아래 C++ 코드를 참고하시기 바랍니다.

    • 최소값에 대해서는 위의 함수를 최소 기준으로 수정하면 구현할 수 있으므로 생략합니다.


    답안 코드


    아래에 두 언어로 각기 다른 방법을 이용해 작성한 코드를 첨부합니다. 두 가지 언어와 방법을 보고 공부해보세요.


    C++ 답안코드

    Bit DP를 활용한 풀이입니다.


    Java 답안 코드

     문자열 정렬을 이용한 그리디한 풀이입니다.

    Q & A
    Q&A forum that anyone can ask and answer.
    Share your questions and answers with other students and grow together!

    Registered Questions(0)