algorithm self describing sequence - andstudy/forge GitHub Wiki

Mastojun

문제 풀이

쉬운문제인줄 알았는데, 썩 쉬운건 아니더군요. 숫자 범위가 가장 큰 걸림돌 이였습니다.
최대 입력값이 20억 이기 때문에 20억의 배열에 각각의 결과를 미리 구해두는 방법으로 처음에 접근 했으나 배열의 크기가 0xffffffff를 넘었기 때문에 컴파일 에러.
배열을 두개로 쪼개서 해보았지만 스택 영역이 제한이 넘어서 에러.
사실 이건 컴파일 성공하더라도 실행시간이 매우 크기 때문에 (일반적으로 Big-O 로 표현했을때 최대값에 대한 결과가 1억이 넘으면 시간초과가 떨어집니다, 10억이였나;) 불가능한 방법이였습니다.
결국에 역으로 생각을 했습니다. 1이 시작하는 숫자, 2가 시작하는 숫자, 3이 시작하는 숫자, 이런식으로 저장하면 배열의 크기를 매우 많이 감소시킬 수 있거든요.
하지만 이 방법도 함수 내부에 있으면 스택크기 초과로 컴파일 안되더군요, 그래서 전역으로 두었습니다.
여하튼.... 힘들게 Solved받았네요

소스 코드

    #include <iostream>
    using namespace std;
    
    int Set[1000000];
    
    int main()
    {
    
    	Set[1] = 1;
    	Set[2] = 2;
    	Set[3] = 4;
    	Set[4] = 6;
    	Set[5] = 9;
    
    	int remember = 1;
    	for( int i = 6; i < 1000000; i++ )
    	{
    		int Temp = Set[i-1];
    		int j;
    
    		for( j = remember; j < i; j++ )
    		{
    			if( Set[j+1] >= i ) break;
    		}
    
    		Set[i]	 = Temp + j;
    		remember = j;
    	}
    
    	int in;
    
    	while( cin >> in )
    	{
    		if( in == 0 ) break;
    
    		int i;
    
    		for(i = 1; i < 1000000; i++ )
    		{
    			if( Set[i+1] > in ) break;
    		}
    
    		cout << i << endl;
    	}
    
    	return 0;
    }

CynicJJ

최종적으로는 몇줄 안되는 코드지만 엄청 고생했습니다.
설계도 두번이나 뒤집었고요.
TDD도 잘 안되서 고치고 실행하고 고치고 실행하고 반복에 늪에 빠진 기분이었음.
큰 수 일때 성능이 좀 떨어지네요.

!SelfDescribingSequence.vb

    ' $Id: SelfDescribingSequence.vb 121 2008-03-04 05:18:53Z 정희종 $
    
    Public Class SelfDescribingSequence
    
    	Private _sequence As Dictionary(Of Integer, Integer) = New Dictionary(Of Integer, Integer)
    
    	Function GetValue(ByVal k As Integer) As Integer
    		Dim key As Integer = 1
    		Dim value As Integer = 1
    
    		While True
    			If Not _sequence.ContainsKey(key) Then
    				_sequence.Add(key, value)
    			End If
    
    			key = key + GetValueCount(value)
    			If key > k Then Exit While
    			value = value + 1
    		End While
    
    		Return value
    	End Function
    
    	Private Function GetValueCount(ByVal value As Integer) As Integer
    		While Not _sequence.ContainsKey(value)
    			value -= 1
    		End While
    		Return _sequence(value)
    	End Function
    End Class

!SelfDescribingSequenceTest.vb

    <TestClass()> _
    Public Class SelfDescribingSequenceTest
    	<TestMethod()> _
    	Public Sub GetValueTestInit()
    		Dim sds As SelfDescribingSequence = New SelfDescribingSequence
    		Assert.AreEqual(1, sds.GetValue(1))
    		Assert.AreEqual(2, sds.GetValue(2))
    		Assert.AreEqual(2, sds.GetValue(3))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetValueTestSmall()
    		Dim sds As SelfDescribingSequence = New SelfDescribingSequence
    		Assert.AreEqual(5, sds.GetValue(10))
    		Assert.AreEqual(8, sds.GetValue(22))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetValueTestLarge()
    		Dim sds As SelfDescribingSequence = New SelfDescribingSequence
    		Assert.AreEqual(21, sds.GetValue(100))
    		Assert.AreEqual(356, sds.GetValue(9999))
    		Assert.AreEqual(1684, sds.GetValue(123456))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetValueTestHuge()
    		Dim sds As SelfDescribingSequence = New SelfDescribingSequence
    		Assert.AreEqual(438744, sds.GetValue(1000000000))
    		Assert.AreEqual(673365, sds.GetValue(2000000000))
    	End Sub
    End Class

ParkPD

이게 무슨 순열인지 이해하는 데에만 1시간이 더 걸렸네요. 머리가 굳은 거 같아 걱정이예요.

    -- Library
    
    function fwrite(fmt, ...)
    	return io.write(string.format(fmt, unpack(arg)))
    end
    
    function swrite(fmt, ...)
    	return string.format(fmt, unpack(arg))
    end
    
    function SwapBySize(i1, i2)
    	if (i2 < i1) then
    		return i2, i1
    	end	
    	return i1, i2
    end
    
    function IsBetween(i, i1, i2)
    	i1, i2 = SwapBySize(i1, i2)
    	return i1 <= i and i <= i2
    end
    
    function PrintTable(t)	
    	fwrite("%s\n", ConvertTableToString(t))
    end
    
    function ConvertTableToString(t)
    	s = "["
    	for _, k in pairs(t) do
    		s = s..tostring(k)..' '
    	end
    	s = s .. "]"
    	return s
    end
    
    function pack(...)
    	return arg
    end
    
    function PushBackTable(t, a, n)
    	for _ = 1, n do
    		t[#t + 1] = a
    	end
    	return t
    end
    
    -- UnitTest
    UnitTest = {test = 0, success = 0, failed = 0}
    
    function UnitTest:new(o)
    	o = o or {}
    	setmetatable(o, self)
    	self.__index = self
    	return o
    end
    
    function UnitTest:ShowResult()
    	if UnitTest.failed == 0 then
    		fwrite("Success : %d tests passed\n", UnitTest.success)
    	else
    		fwrite("Failed : %d in tests %d\n", UnitTest.failed, UnitTest.test)
    	end
    end
    
    function Check(name, actual)
    	UnitTest.test = UnitTest.test + 1
    	if not actual then
    		fwrite("Check Failed in %s\n", name)
    		UnitTest.failed = UnitTest.failed + 1
    	else
    		UnitTest.success = UnitTest.success + 1
    	end
    end
    
    function CheckEqual(name, expect, actual)
    	UnitTest.test = UnitTest.test + 1
    	if (expect ~= actual) then
    		fwrite("CheckEqual Failed in %s. %s expected but actual is %s\n", name, tostring(expect), tostring(actual))
    		UnitTest.failed = UnitTest.failed + 1
    	else
    		UnitTest.success = UnitTest.success + 1
    	end
    end
    
    function CheckArrayEqual(name, expect, actual)
    	UnitTest.test = UnitTest.test + 1
    	
    	local fail = false
    	if (#expect == #actual) then
    		for k, v in pairs(expect) do
    			if (actual[k] ~= v) then
    				fail = true
    				break
    			end			
    		end		
    	else
    		fail = true
    	end
    		
    	if (fail) then
    		fwrite("CheckArrayEqual Failed in %s. %s expected but actual is %s\n", name, ConvertTableToString(expect), ConvertTableToString(actual))
    		UnitTest.failed = UnitTest.failed + 1
    	else
    		UnitTest.success = UnitTest.success + 1
    	end
    end
    
    -- Algorithm
    
    GSeq = {Nums = {1, 2}, k = 3, v = 3}
    function GSeq:new(o)
    	o = o or {}
    	setmetatable(o, self)
    	self.__index = self
    	return o
    end
    
    function GSeq:GetNearSeq(num)
    	for i = 0, num do
    		if (self.Nums[num - i] ~= nil) then
    			return self.Nums[num - i]
    		end
    	end
    	
    	assert(0)
    	return -1
    end
    
    -- k 의 위치는 아직 순열을 만들지 않은 최초의 key 를 가리키고
    -- v 의 위치는 바로 이전에 처리한 순열의 마지막 위치를 가리킨다.
    -- 즉, 다음 순열은 k 부터 시작하고, 
    -- k 라는 숫자를 v + 1 위치에서부터 f(k) 만큼 추가해 주면 된다.
    function GSeq:GetF(num)
    	while (self.v < num) do
    		self.Nums[self.v + 1] = self.k
    		if (self.Nums[self.k] ~= nil) then
    			self.v = self.v + self.Nums[self.k]
    		else
    			-- 바로 이전 녀석을 찾는다.
    			self.v = self.v + self:GetNearSeq(self.k)
    		end
    		
    		self.k = self.k + 1
    	end
    	
    	return self:GetNearSeq(num)
    end
    
    -- test part
    
    do
    	local t = {1, 2, 3}
    	local k = PushBackTable(t, 6, 2)
    	CheckArrayEqual("PushBackTable", {1, 2, 3, 6, 6}, k)
    end
    
    do
    	local testSet = 
    		{
    		  	4, 3,
    		  	5, 3,
    		  	6, 4,
    		  	7, 4, 
    		  	8, 4, 
    		  	9, 5
    		}
    
    	for i = 1, #testSet, 2 do
    		CheckEqual("GetF _ "..testSet[i], testSet[i + 1], GSeq:GetF(testSet[i]))
    	end	
    end
    
    do
    	CheckEqual("GetF 1", 21, GSeq:GetF(100))
    	CheckEqual("GetF 1", 356, GSeq:GetF(9999))
    	CheckEqual("GetF 1", 1684, GSeq:GetF(123456))
    	
    	-- 첫 방법으로 했을 때는 메모리가 부족하다고 나왔다. 냠...
    	-- 이정표만 찍으면서 진행하자.
    	CheckEqual("GetF 1", 438744, GSeq:GetF(1000000000))
    end
    
    UnitTest:ShowResult()
    
    -- input part
    
    while 1 do
    	local count = io.read("*number")
    	if count == nil then 
    		break 
    	end
    end

algorithm self describing sequence - andstudy/forge GitHub Wiki

Mastojun

문제 풀이

소스 코드

CynicJJ

!SelfDescribingSequence.vb

!SelfDescribingSequenceTest.vb

ParkPD

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️