Self-describing Sequence/1002

������ ������������ ��������� ������������ ��������� ������하������ ���������, 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)

���������, 1000000000 ��� ��������� ���해��� ������ ��������� ��������� ������������ ������������ ���������. ������ ���해��� ��������� 할 ��������� ������,
������ ������������ ���해��� ������하��� ���.

• ��������� ���한 ������������ ���������?
  
• k ��� ������ f(k) ������ 훨������ ������ ��������� ��� ������텐���, ������ ������할 ��������� ���������?
  

������ ������하��� ����������������� ���행해������������ ������ ��������� ������.

��������� ��������� ������하��� ���, ������������ ���해��� ������ ������. ��������� 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

• ��������������� ��포������ 튜������ ���해 ������ ������������������ ��������� 해��� ������ ���������.
  
• 하������, ���학������ ��������� ��������������������� ������ 한������ ������. ������ ��포������ 향������ ���한 ������������ ������������������ ������.
  
  ������ ������������ ������하��� �� ������ ��������� 함.
  
• ��������� '��� ������������ ������한 ��������� ��� ������������������?' ��� ���해��� ������하��� ���. ������ ���하��� ��������� ��������� 했������.