U E D R , A S I H C RSS

Self-describing Sequence/1002

approach

1์ฐจ ์‹œ๋„

๋Œ€๋žต ์—ฐ์Šต์žฅ์— ์ˆ˜์—ด์ด ๋งŒ๋“ค์–ด์งˆ ๋ชจ์Šต์„ ์ƒ๊ฐํ•˜๋ฉด์„œ ๋””์ž์ธ, 20๋ถ„ ์ •๋„ ์ฝ”๋”ฉ.


~cpp
def selfDescrib(n):
    table = [1,2,2]
    e=2
    while e!=n+1:
        e+=1
        table += [e] * table[e-1]
        if len(table) > n-1:
            return table[n-1]

for i in [100,9999,123456,1000000000]: print selfDescrib(i)

2์ฐจ ์‹œ๋„

๋ฌธ์ œ๋Š”, 1000000000 ์˜ ๊ฒฝ์šฐ์— ๋Œ€ํ•ด์„œ ๋‹ต์ด ๋‚˜์˜ค๋Š” ์‹œ๊ฐ„์ด ์—„์ฒญ๋‚˜๊ฒŒ ๊ฑธ๋ฆฐ๋‹ค๋Š” ์ ์ด๋‹ค. ์ด์— ๋Œ€ํ•ด์„œ ์–ด๋–ป๊ฒŒ ํ•  ๊ฒƒ์ธ๊ฐ€ ๊ณ ๋ฏผ,
์—ฌ๋Ÿฌ ์ ‘๊ทผ๋ฒ•์— ๋Œ€ํ•ด์„œ ์ƒ๊ฐํ•˜๊ฒŒ ๋จ.
  • ์ˆ˜์—ด์— ๋Œ€ํ•œ ์ผ๋ฐ˜์‹์ด ์žˆ์„๊นŒ?
  • k ๊ฐ’ ๋Œ€๋น„ f(k) ๊ฐ’์„ ํ›จ์”ฌ๋” ๋งŽ์ด ์•Œ์•„๋‚ผ ์ˆ˜ ์žˆ์„ํ…๋ฐ, ์ด๋ฅผ ์ด์šฉํ•  ๋ฐฉ๋ฒ•์ด ์žˆ์„๊นŒ?
๊ทธ์™€ ๊ด€๋ จํ•˜์—ฌ ํ”„๋กœ๊ทธ๋ž˜๋ฐ์„ ์ง„ํ–‰ํ•ด๋ณด์•˜์œผ๋‚˜ ๊ทธ๋ฆฌ ์„ฑ๊ณผ๊ฐ€ ์—†์Œ.

3์ฐจ ์‹œ๋„

์–ด์ œ์— ์ด์–ด์„œ ๊ณ ๋ฏผํ•˜๋˜ ์ค‘, ๋ฌธ์ œ์ ์— ๋Œ€ํ•ด์„œ ๋‹ค์‹œ ์ƒ๊ฐ. ๊ฒฐ๊ตญ์€ f(k) ๋ฅผ ์œ„ํ•œ table ์ƒ์„ฑ์—์„œ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ๋งŽ์ด ์“ด๋‹ค๋Š” ์ ์ด ๋ฌธ์ œ.
์ด์— ๋Œ€ํ•ด์„œ ๋‹ค๋ฅด๊ฒŒ representation ํ•  ๋ฐฉ๋ฒ•์„ ์ƒ๊ฐํ•˜๋‹ค๊ฐ€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด representation ํ•  ๋ฐฉ๋ฒ•์„ ๋– ์˜ฌ๋ฆฌ๊ฒŒ ๋จ.
f(1) : 1
f(2) ~ f(3) : 2
f(4) ~ f(5) : 3
f(6) ~ f(8) : 4
f(9) ~ f(11) : 5
.
.

์ด์— ๋Œ€ํ•ด์„œ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ตฌํ˜„
~cpp
# ํ•ด๋‹น ์ˆซ์ž ๋ฒ”์œ„๋ฅผ ์กฐ์‚ฌํ•˜์—ฌ ์–ด๋–ค ๊ฐ’์ด ๋‚˜์˜ฌ์ง€๋ฅผ return
def findGroupIdx(table,n,startPos=0):
	for i in xrange(len(table)):
		x,y=table[i]
		if x<=n<=y: return i+1

def selfDescrib2(n):
    table=[(1,1),(2,3)]
    if n==1 or n==2: return n

    for i in xrange(3,n+1):
        start = table[-1][-1] + 1
        theGroupIdx = findGroupIdx(table,i)
        repeat = theGroupIdx
        end = start + repeat - 1
        table.append((start,end))
        if start >= n:
            return findGroupIdx(table,n)

ํ’€๊ณ  ๋‚˜๋‹ˆ, ๊ทธ๋ž˜๋„ ์—ญ์‹œ 1000000000 ์— ๋Œ€ํ•ด์„œ๋Š” ๊ต‰์žฅํžˆ ๋А๋ฆผ. ๋А๋ฆด ๋ถ€๋ถ„์„ ์ƒ๊ฐํ•˜๋˜ ์ค‘ findGroupIdx ๋ถ€๋ถ„์ด
๋ฌธ์ œ์ž„์„ ์ƒ๊ฐ. ์ด๋ฅผ binary search ๊ตฌํ˜„์œผ๋กœ ๋ฐ”๊ฟˆ.
~cpp
def findGroupIdx(table,n,startPos=0):
    midIdx = len(table)/2
    mid = table[midIdx]
    x,y=mid
    if x<=n<=y: return midIdx+1+startPos
    if n<x: return findGroupIdx(table[:midIdx],n,startPos)
    else: return findGroupIdx(table[midIdx+1:],n,startPos+midIdx+1)

binary search ๋กœ ๋ฐ”๊พธ๊ณ  ๋‚˜์„œ๋„ ์—ญ์‹œ ์˜ค๋ž˜๊ฑธ๋ฆผ. ๋‹ค๋ฅธ ๊ฒ€์ƒ‰๋ฒ•์— ๋Œ€ํ•ด์„œ ์ƒ๊ฐํ•˜๋˜ ์ค‘, findGroupIdx ํ•จ์ˆ˜ ํ˜ธ์ถœ์„ ํ• ๋•Œ๋ฅผ ์ƒ๊ฐ.
์ˆ˜์—ด์˜ ๊ฐ’์ด ๋Š˜ ์ฆ๊ฐ€ํ•œ๋‹ค ํ• ๋•Œ ๋‹ค์Œ๋ฒˆ์— ๊ฒ€์ƒ‰ํ•˜๋Š” ๊ฒฝ์šฐ ์•ž์—์„œ ๊ฒ€์ƒ‰ํ–ˆ๋˜ ๊ทธ๋ฃน ์•„๋‹ˆ๋ฉด ๊ทธ ๋‹ค์Œ ๊ทธ๋ฃน์ž„์„ ์ƒ๊ฐํ•˜๊ฒŒ ๋จ.
~cpp
class FindGroupIdxs:
    def __init__(self,table):
        self._table = table
        self._prevSearchPos = 0
    def find(self,n):
        while True:
            x,y=self._table[self._prevSearchPos]
            if x<=n<=y: return self._prevSearchPos+1
            self._prevSearchPos+=1

def selfDescrib2(n):
    table=[(1,1),(2,3)]
    if n==1 or n==2: return n

    finder = FindGroupIdxs(table)

    for i in xrange(3,n+1):
        start = table[-1][-1] + 1
        theGroupIdx = finder.find(i)
        repeat = theGroupIdx
        end = start + repeat - 1
        table.append((start,end))
        if start >= n:
            return finder.find(n)

def main():
    import time
    for e in [100,9999,123456,1000000000]: 
        start=time.time()
        print e,selfDescrib2(e)
        print "time : ", time.time()-start

import psyco
psyco.full()
main()

์ˆ˜ํ–‰ ์‹œ๊ฐ„ : 1000000000 ๊ธฐ์ค€ 0.95์ดˆ(with psyco) 2.18์ดˆ(without psyco)
๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰ : 31MB

๋А๋‚Œ

  • ์ง€์†์ ์œผ๋กœ ํผํฌ๋จผ์Šค ํŠœ๋‹์„ ์œ„ํ•ด ๋‹ค๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ์ ‘๊ทผ์„ ํ•ด๋ณธ ์ ์ด ์ข‹์•˜์Œ.
  • ํ•˜์ง€๋งŒ, ์ˆ˜ํ•™์ ์ธ ๊ด€๊ณ„๋ฅผ ์ฐพ์•„๋‚ด๋Š”๋ฐ์—๋Š” ์—ญ์‹œ ํ•œ๊ณ„๋ฅผ ๋ณด์ž„. ๊ทธ๋ƒฅ ํผํฌ๋จผ์Šค ํ–ฅ์ƒ์„ ์œ„ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ์„ ๋ฒ•์œผ๋กœ๋งŒ ์ ‘๊ทผ.
    ๋„ˆ๋ฌด ์ง๊ด€์—๋งŒ ์˜์กดํ•˜์—ฌ ํ‘ผ ์ ์ด ์•„์‰ฝ๊ธด ํ•จ.
  • ๋‹ค์‹œ๊ธˆ '์ด ๋ฌธ์ œ์—์„œ ์š”๊ตฌํ•œ ๋ฐฉ๋ฒ•์ด ์ด ๋ฐฉ๋ฒ•์ด์˜€์„๊นŒ?' ์— ๋Œ€ํ•ด์„œ ๊ณ ๋ฏผํ•˜๊ฒŒ ๋จ. ๋น„๋ก ์›ํ•˜๋Š” ์„ฑ๋Šฅ์€ ๋‚˜์˜ค๊ธด ํ–ˆ์ง€๋งŒ.
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:28:00
Processing time 0.0084 sec