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

• ��������������� ������������ ��������� ������ ������ ���고������������ ���근��� ������ ������ ���������.
  
• ���������, ������������ ���계��� ��������������������� ������ ���계��� ������. 그��� ������������ ��������� ������ ���고������ 개��������������� ���근.
  
  ������ ������������ ������������ ��� ������ �������� ���.
  
• ������금 '��� ������������ ���구��� ��������� ��� ���������������까?' ��� ��������� 고������게 ���. ������ ��������� ��������� �������� ���������.