자연수 n을 입력받고, n!의 계산 결과 중 마지막에 붙은 연속된 0의 개수와 연속된 0 바로 앞에 나오는 숫자를 구하라.

[실행 예] input n: 15 output: 3 8

[설명] 15!은 1307674368000이므로, 마지막에 연속된 0은 3개이고, 바로 앞의 숫자는 8이다.

• 조건 *

n의 범위는 1 이상, 10000 이하입니다. 테스트 입력은 다음과 같습니다. 20! = 2432902008176640000 30! = 265252859812191058636308480000000 40! = 815915283247897734345611269596115894272000000000 50! = 30414093201713378043612608166064768844377641568960512000000000000 100! = 93326215443944152681699238856266700490715968264381621468592963 8952175999932299156089414639761565182862536979208272237582511852 10916864000000000000000000000000 프로그래밍 언어에서 제공하는 자릿수 제한 없는 곱셈을 이용하거나, 이런 형태의 곱셈 함수를 직접 구현해도 답을 얻을 수 있지만, 문제의 의도와는 다릅니다. 정답 검토의 편의를 위해 블로그 포스팅에 2012!와 10000!의 결과를 남겨주세요. (심화 문제) 연속된 0 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^

1. Simple Approach

아주 간단하게 생각해서 굳이 다 계산할 필요없이 마지막 원하는 자릿수만 남겨보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# simple.factorial.coffee
n = 1
k = 3
N = 2012
digit = 1

digit = digit * 10 while k-- isnt 0
zero = 0
for i in [1..N]
    n = n*i
    while n % 10 is 0
        n = n/10
        zero++

    n = n%digit
    console.log "#{i}! = ...#{n}*10^#{zero}"

k는 원하는 자리 수. 3자리만 끊어서 보도록 했다. 결과는

1
2

2012! = ...928*10^501
[Finished in 0.7s]

2. without 2, 5

0의 개수를 결정하는 2와 5는 따로 처리한다. N까지 숫자를 모두 곱해서 소인수분해를 하면 2가 5보다 항상 클까? non-zero digit of factorial로 검색하니 바로 맨 위에 이 포스팅이 나왔다. Approach1은 누구나 생각할 수 있고 2에 대한 수학적인 증명이 있어야할텐데 그건 차차 생각해보도록 하고 일단 구현해보도록 했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#reduce2and5.factorial.coffee
n = 1
k = 3
N = 2012

digit = 1
while k-- isnt 0
    digit = digit * 10

zero = 0
n2 = 0

for i in [1..N]
    j = i

    while j % 10 is 0
        j /= 10
        zero++

    while j % 2 is 0
        j /= 2
        n2++

    while j % 5 is 0
        j /= 5
        n2--
        console.error i if n2 is 0
        zero++

    n = n*j % digit

while n2-- isnt 0
    n = n*2 % digit
console.log "#{N}! = ...#{n}*10^#{zero}"

결과는

1
2

2012! = ...928*10^501
[Finished in 0.2s]

확실하게 줄었다. Approach3과 4에 대해서는 더 생각해봐야겠는데 일단 카페 마감 시간이라 나가도록 하겠다.

자연수 n을 입력받아 집합 {0, 1, 2, …, n-1}을 하나 이상의 집합으로 나누는 방법을 모두 출력하는 프로그램을 작성하세요. [실행 예] input n: 3 {0, 1, 2} {0} {1, 2} {1} {0, 2} {2} {0, 1} {0} {1} {2}

• 참고 *

1. n의 범위는 크게 상관이 없지만, 대략 16 이하라고 가정하시면 되겠습니다. ^^

2. 집합으로 나눈 경우를 출력하는 방법은 상관없습니다.

• {1} {0, 2}를 {0, 2} {1}로 표현해도 되고, 1, 0 2로 표현해도 됩니다. (다른 형식도)
• 또, {0} {1, 2}가 먼저 출력되든, {0} {1} {2}가 먼저 출력되든 상관 없습니다. 빠짐없이 출력하기만 하면 됩니다.

곰곰히 생각해서 나름대로 잘 풀었다고 생각했는데 다른 사람들의 풀이를 보니 다 똑같아서 알고리즘의 설명은 생략하겠다. 그 대신에 잠깐 생각해본게 과연 이렇게 하나씩 추가하는 알고리즘에서 중복(순서가 바뀐 같은 집합)이 존재하지 않을까? 하는 의문이다. { ArrayN, ArrayM, ... } 이렇게 부분집합 n, m 이 있을 때 { ArrayM, ArrayN, ... } 라고 순서가 바뀐 다른 부분집합이 있을까? 답은 없다. n에서 제일 작은 n[0]과 m에서 제일 작은 m[0]가 있을 때 n[0] < m[0]라면 항상 n[0]가 앞에 있는 집합에 속해있다. 크기 순서대로 입력이 된다고 가정했을 때 m[0]가 n[0]보다 앞에 있으려면 n[0]보다 작은 숫자가 먼저 입력되어있는 부분 집합에 m[0]가 속해야하는데 그럼 그 집합에서 가장 작은 숫자가 m[0]가 아니기 때문에 모순되므로 m[0]가 n[0]보다 앞에 올 수 없어서 중복된 집합은 존재하지 않는다.

그리고 coffeescript를 실행할 때 compile하고 다시 node로 실행시키는 일을 두번 하기 싫은데 coffee에서 직접 파일을 입력받아 실행시키는 옵션은 없고 stdio로 script text를 받아서 실행시키는 옵션은 있어서 출력한 뒤 파이프로 넘기게 계속 명령어를 입력했는데 (cat test.coffee | coffee -s) argument를 입력받게 되니 coffee파일까지 커서를 옮겼다가 다시 argument로 커서를 옮겼다가 하기 귀찮아서 bash script 문서를 구글링해서 하나 만들었다.

1
2
3
4
5
6
7
8

#!/bin/bash
if [ $# -lt 1 ]
then
    echo "you must give me coffee"
    exit
fi

cat $1 | coffee -s ${@:2}

중요한건 이게 아니고 다시 문제로 돌아가서 소스를 보자면

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# subset.coffee
n = parseInt process.argv[3]

Array.prototype.clone = () ->
    ret = []
    for item in this
        item = item.clone() if item.constructor is Array
        ret.push item
    return ret

data = [ [[0]] ]

add = (arr, n) ->
    ret = []
    for row in arr
        for i in [0...row.length]
            (c = row.clone())[i].push n
            ret.push c
        row.push [n]
        ret.push row
    ret

for i in [1...n]
    data = add data, i

console.log data

그리고 실행

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(21:58:11) coffee seoh$ ./c.sh subset.coffee 4
[ [ [ 0, 1, 2, 3 ] ],
  [ [ 0, 1, 2 ], [ 3 ] ],
  [ [ 0, 1, 3 ], [ 2 ] ],
  [ [ 0, 1 ], [ 2, 3 ] ],
  [ [ 0, 1 ], [ 2 ], [ 3 ] ],
  [ [ 0, 2, 3 ], [ 1 ] ],
  [ [ 0, 2 ], [ 1, 3 ] ],
  [ [ 0, 2 ], [ 1 ], [ 3 ] ],
  [ [ 0, 3 ], [ 1, 2 ] ],
  [ [ 0 ], [ 1, 2, 3 ] ],
  [ [ 0 ], [ 1, 2 ], [ 3 ] ],
  [ [ 0, 3 ], [ 1 ], [ 2 ] ],
  [ [ 0 ], [ 1, 3 ], [ 2 ] ],
  [ [ 0 ], [ 1 ], [ 2, 3 ] ],
  [ [ 0 ], [ 1 ], [ 2 ], [ 3 ] ] ]

cat test.coffee | coffee -s로 실행을 하면 내부적으로 어떤 구조로 node를 실행시키는지 모르겠지만 [ 'node', '.', '-s' ] 라는 세 argument가 기본적으로 붙는다. 그런데 -s는 help에도 안나오고 직접 node -s로 하면 unrecognized flag라고 나오고. 뭔지 모르겠지만 귀찮아서 패스.

사실 처음에는 다른 방법으로 접근했다가 포기했다. 어차피 모든 부분집합의 원소의 합은 n으로 일정하니 일단 그 크기를 나누는 것을 n=4일 때를 예로 들어,

4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1

로 나타낼 수 있다. 각 행마다 하나씩 예로 들자면

{ 0, 1, 2, 3 } { 0, 1, 2 }, { 3 } { 0, 1 }, { 2, 3 } { 0, 1 }, { 2 } , { 3 } { 0 }, { 1 }, { 2 }, { 3 }

로 나타낼 수 있다. 그래서

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# split.coffee
n = parseInt process.argv[3]

split = (n) ->
    split.ret.clear
    split.arr.clear

    __split(n, 0, n)
    split.ret

split.arr = []
split.ret = []

__split = (n, i, m) ->
    if n is 0
        split.ret.push split.arr.slice(0, i)
        return
    
    if m > n
        m = n

    for j in [1 .. m]
        split.arr[i] = j
        __split n-j, i+1, j

n && console.log split n
exports && exports.split = split

라고 [1.6 수분할] 챕터를 참고해서 만들었다. 그런데 이걸 깔끔하게 정리해서 개수를 맞춰서 경우의 수를 만들 수 있는 방법을 못찾아서 다른 방법을 강구하게 되었다. 단순히 생각했을 때, memoization처럼 memo['2.1.1']['2'].indexOf('1.2')라는 식으로 2+1+1을 '2.1.1'로 {1, 2}는 '1.2'처럼 문자열로 만들어서 HashMap을 하나 만들면 구현은 편한데 어차피 모든 경우의 수를 만들고 거기에서 필터링하는거나 마찬가지라 (정확히 말하면 '가지치기'의 방법이 떠오르지 않아서) 비효율적이라 포기했다. 나중에 시간나면 지금처럼 bottom-up같은 방법이 아니라 top-down으로 할 수 있는 방법이 없나 찾아봐야겠다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# rotate.coffee
arr = [1..8]
s = 2
t = 6

rotate = (k) ->
    len = t-s+1
    k = k % len
    __rotate k, s, len

__rotate = (k, i, len) ->
    if len is 0 then return
    temp = arr[i]
    next = (i-s+k) % (t-s+1) + s
    __rotate(k, next, len-1)
    arr[next] = temp

rotate 1
console.log arr # [ 1, 2, 7, 3, 4, 5, 6, 8 ]

CoffeeScript를 튜토리얼만 살짝 읽고 언젠가 써봐야지하면서 쓸 일이 없었는데 겸사겸사 이번 기회에 써봤다. 분명 타자는 더 적어진거 같은데 손에 안익어서 문서를 보면서 코딩해서 그런지 시간은 더 늘어난 기분. 튜토리얼말고 제대로 된 문서를 정독하고 나서 나중에 다시 도전해봐야겠다.

배열 arr[]과 위치 s, t가 있을 때, arr[s], arr[s+1], … , arr[t-1]을 오른쪽으로 한 칸씩 이동하고, arr[t]는 arr[s]로 복사하는 것을 ’1만큼 오른쪽으로 회전시켰다’고 한다. 예를 들어 길이가 8인 배열에서 s=2, t=6이면 다음 그림처럼 바뀐다. 길이가 n인 배열의 위치는 0, 1, 2, … , n-1이다. 문제 : k를 인자로 받아서 k만큼 오른쪽으로 회전시키는 함수를 작성하라. 단, 1만큼 오른쪽으로 이동시키는 과정을 k번 반복해서는 안 된다. 조건 1 : 작성하는 언어에는 제한이 없습니다. 조건 2 : 답안으로 작성하신 글 제목에는 ‘문제로 풀어보는 알고리즘 0.3 생각해보기 풀이’라는 문장이 들어가야 합니다. (저희 블로그에도 트랙백을 걸어주세요.) (주의: 이 코딩 인터뷰는 인사이트 입사와는 무관합니다. ㅡㅁㅡ /)

문제에 대해서 접근하자면, 간단하게 생각해서 마지막 숫자를 저장해두고 그 자리에 올 숫자를 마지막 숫자의 자리에 옮기고, 이걸 (t-s+1-1)번 (실제 옮겨지는 아이템의 수 -1) 옮기고 나서 처음에 저장해두었던 숫자를 k만큼 이동하면 된다. 그런데 모듈러 연산이라는게 역산하기 어려운고로 제일 쉬운 방법은 옮길 아이템의 수 (t-s+1) 만큼 공간을 만들고 값을 복사한 뒤에 그림에 나온 것처럼 t-s+1번 이동하는 방법이 제일 간단하고 명확했다. 그런데 몇줄 안나오는 코드로는 재미가 없어서 지금 있는 공간에서 해결할 수 있는 방법을 찾다가 요즘 읽고 있는 그 책에서 자꾸 재귀적인 알고리즘을 강요하듯 반복해서 재귀적으로만 풀이하니 전염이 되었나 한번 재귀적으로 풀어보고 싶었다.

단순하게 생각해서 arr만 가지고 풀기를 시도해보면, [2]에 있는 3을 [3]으로 옮기려한다. 그럼 [3]에 있는 4가 사라지니 3을 일단 메모리에게 들고 있으라고 한 뒤에 4부터 옮기고 3을 [3]에 넣으면 될 것이다. 이런 식으로 들어가야할 자리가 비어있지 않으면 잠시 메모리에 놓고 다음꺼부터 옮기다가 자리가 비어있으면 (t-s+1 번만큼 호출된 후에) 그냥 이동만 하고 아까 메모리에 놔두었던 것들을 원하는 자리에 차례대로 넣으면 된다. 문제는 이런 경우에 자료의 크기 자체에 더해서 call stack만큼의 비용을 추가로 부담하게 되니, 메모리 사용이 4*k에서 (4+@)*k로 늘어나게 되니 오히려 더 비효율적이 될 수도 있고, heap보다 stack이 조금 더 빠르니 비슷할 수도 있다. 원래의 의도는 그냥 재귀적으로 도전해보는 것이었으니 그 이상은 여기까지 생각하고 잘 돌아가는 것에서 만족하도록 하자.