Skip to content

algorithm expressions

Jump to bottom
Jongbin Oh edited this page Jun 8, 2013 · 1 revision

해답

  • 해답 없이 규칙 찾기 너무 귀찮음. ㅋ

      #include <stdio.h>
  
  #define NUMBERLENGTH 23
  #define ONEDIGIT 10000
  
  typedef struct _longlong {
  	unsigned int h[NUMBERLENGTH];
  } longlong;
  
  static int n, d;
  static longlong result;
  static longlong c[151][151];
  static longlong e[151];
  static longlong f[151][151];
  
  void assign(longlong *a, unsigned int b)
  {
  	int i;
  	for(i=0 ; i<NUMBERLENGTH ; i++)
  	{
  		a->h[i] = b % ONEDIGIT;
  		b /= ONEDIGIT;
  	}
  }
  
  void add(longlong *c, const longlong *a, const longlong *b)
  {
  	int i, carry;
  
  	carry = 0;
  	for(i=0 ; i<NUMBERLENGTH ; i++)
  	{
  		c->h[i] = a->h[i] + b->h[i] + carry;
  		carry = c->h[i] / ONEDIGIT;
  		c->h[i] %= ONEDIGIT;
  	}
  }
  
  void sub(longlong *c, const longlong *a, const longlong *b)
  {
  	int i, carry;
  
  	carry = 0;
  	for(i=0 ; i<NUMBERLENGTH ; i++)
  	{
  		if(a->h[i] >= b->h[i])
  		{
  			c->h[i] = a->h[i] - b->h[i] + carry;
  			carry = 0;
  		}
  		else
  		{
  			c->h[i] = (ONEDIGIT + a->h[i]) - b->h[i] + carry;
  			carry = -1;
  		}
  	}
  }
  
  void mul(longlong *c, const longlong *a, const longlong *b)
  {
  	int i, j, carry;
  	unsigned int temp;
  	int in, jn;
  	longlong d;
  
  	for(i=0 ; i<NUMBERLENGTH ; i++)
  		d.h[i] = 0;
  	in = jn = NUMBERLENGTH - 1;
  
  	while(a->h[in] == 0)
  		in--;
  	in++;
  	while(b->h[jn] == 0)
  		jn--;
  	jn++;
  
  	for(i=0 ; i<in+1 ; i++)
  	{
  		carry = 0;
  		for(j=0 ; j<jn+1 ; j++)
  		{
  			if(i+j < NUMBERLENGTH)
  			{
  				temp = (d.h[i+j] + a->h[i]*b->h[j] + carry) % ONEDIGIT;
  				carry = (d.h[i+j] + a->h[i]*b->h[j] + carry) / ONEDIGIT;
  				d.h[i+j] = temp;
  			}
  		}
  	}
  
  	for(i=0 ; i<NUMBERLENGTH ; i++)
  		c->h[i] = d.h[i];
  }
  
  void print(const longlong *a)
  {
  	int sw;
  	int i;
  	sw = 0;
  
  	for(i=NUMBERLENGTH-1 ; i>=0 ; i--)
  	{
  		if(!(sw==0 && a->h[i]==0))
  		{
  			if(sw==0)
  			{
  				printf("%d", a->h[i]);
  				sw = 1;
  			}
  			else {
  				printf("%04d", a->h[i]);
  			}
  		}
  	}
  	if(sw==0)
  		printf("0");
  }
  
  void solve(void)
  {
  	int i, j, k;
  	longlong p;
  
  	assign(&e[0], 1);
  	assign(&e[1], 1);
  	assign(&e[2], 2);
  	
  	for(i=3 ; i<=150 ; i++)
  	{
  		assign(&e[i], 0);
  		for(j=1 ; j<=i ; j++)
  		{
  			mul(&p, &e[j-1], &e[i-j]);
  			add(&e[i], &e[i], &p);
  		}
  	}
  	
  	for(i=0 ; i<=150 ; i++)
  	{
  		for(j=0 ; j<=150 ; j++)
  		{
  			if(i==0 && j==0)
  				assign(&f[i][j], 1);
  			else if(i<=j)
  				f[i][j] = e[i];
  			else if(j==1)
  				assign(&f[i][j], 1);
  			else if(j==0)
  				assign(&f[i][j], 0);
  			else
  			{
  				assign(&f[i][j], 0);
  				for(k=1 ; k<=i ; k++)
  				{
  					mul(&p, &f[k-1][j-1], &f[i-k][j]);
  					add(&f[i][j], &f[i][j], &p);
  				}
  			}
  		}
  	}
  }
  
  void main(void)
  {
  	solve();
  
  	while(scanf("%d %d", &n, &d) != EOF)
  	{
  		sub(&result, &f[n/2][d], &f[n/2][d-1]);
  		print(&result);
  		printf("\n");
  	}
  }

Outbreak

문제 요약

  • X 라는 문자열 표현식의 규칙을 만족 시키는 경우의 개수를 찾는 문제!
  • 수학적 귀납법을 활용해야 하는 문제.. BUT..

문제 해결

  • X 를 표현하는 3가지 규칙을 이용해 조합 가능한 경우를 모두 찾는다.
    • () 부터 시작해서
      • empty string 과 결합 시킴
      • ()을 씌움
      • 현재 만들어진 X의 집합 원소에 대해 중복순열 구함

소감

  • 손으로 먼저 풀어야 하는데.. 역시나 쉽지 않음.
  • 아래 코드도 최적화 하면 해볼만 하지 않..??
  • 아직은 컴터 성능이 별루인듯? ( ..)
  • 후후;;

풀이

    using System;
    using System.Collections.Generic;
    using System.Text;
    
    namespace Expressions
    {
        class X
        {
            public int depth;
            public string value;
    
            public X(int depth, string value)
            {
                this.depth = depth;
                this.value = value;
            }
    
            // 0 Operation
            public static X operator -(X x1)
            {
                return new X(x1.depth, x1.value);
            }
    
            // 겉옷 입히기
            public static X operator +(X x1)
            {
                return new X(x1.depth+1, string.Format("({0})", x1.value));
            }
    
            // 두개 합하기
            public static X operator +(X x1, X x2)
            {
                return new X(Math.Max(x1.depth, x2.depth), string.Format("{0}{1}", x1.value, x2.value));
            }
    
            public override string ToString()
            {
                return string.Format("{0} : {1}", value, depth);
            }
        }
    
        class Combination
        {
            List<X> pool;
            Dictionary<string, int> dic;
    
            public Combination()
            {
                pool = new List<X>();
                dic = new Dictionary<string, int>();
            }
    
            public void Add(X x)
            {
                if (dic.ContainsKey(x.value))
                    return;
    
                pool.Add(x);
                dic.Add(x.value, 1);
            }
    
            public Combination Next()
            {
                Combination next = new Combination();
    
                foreach (X x in pool)
                {
                    next.Add(-x);
                }
    
                foreach (X x in pool)
                {
                    next.Add(+x);
                }
    
                foreach (X x1 in pool)
                {
                    foreach (X x2 in pool)
                    {
                        next.Add(x1 + x2);
                    }
                }
    
                return next;
            }
    
            public int Find(int length, int depth)
            {
                int result= 0;
    
                foreach (X x in pool)
                {
                    if (x.value.Length==length && x.depth==depth)
                    {
                        //Console.WriteLine("답 : {0}", x);
                        result++;
                    }
                }
    
                return result;
            }
            
            public void Display()
            {
                int order = 0;
                foreach(X x in pool)
                {
                    Console.WriteLine(string.Format("{0}\t{1}", order++, x));
                }
    
                Console.WriteLine();
            }
        }
          
        class Program
        {
            static void Main(string[] args)
            {
                // 1. >  조합 데이터 수집
                Combination combination = new Combination();
    
                combination.Add(new X(1, "()"));
                
                for (int i = 0; i < 4/*1000*/; i++)
                {                
                    // 현재 하드웨어로는 4까지만 해볼만 함
                    combination = combination.Next();
                    combination.Display();
                }
    
                // 2. > 문제 풀기
                Console.WriteLine(combination.Find(6, 2));
                Console.WriteLine(combination.Find(300, 150));
            }
        }
    }

스터디풀이

문제 풀이

  • 테스트 1차

      #include <stdio.h>
  typedef unsigned long long BigInteger;
  BigInteger Matrix[151][151];
  
  BigInteger GetMatrix(int n, int d )
  {
  	if( n < 0 || d < 0 ) return 0;
  	if( n < d ) d = n;
  
  	return Matrix[n][d];
  }
  
  void CalMatrix(int n, int d)
  {
  	for(int j = 0; j < n; j++ )
  	{
  		Matrix[n][d] += GetMatrix(j,d-1)*GetMatrix(n-1-j,d);
  	}
  }
  
  void MakeMatrix()
  {
  	Matrix[0][0] = 1;
  
  	for(int i = 1; i <= 150; i++ )
  	{
  		for(int j = 1; j <= i; j++ )
  		{
  			CalMatrix(i, j);
  		}
  	}
  }
  
  void PrintResult(int n, int d)
  {
  	printf("%llu\n", Matrix[n][d] - Matrix[n][d-1]);
  }
  
  int main()
  {
  	int n, d;
  
  	MakeMatrix();
  
  	while( scanf("%d %d", &n, &d) == 2 )
  	{
  		//n /= 2;
  		PrintResult(n, d);
  	}
  
  	return 0;
  }

Mastojun

문제 풀이

  • Solved 받은 코드 입니다. char한개에 1자리 하는것보다 int형 한개에 4자리씩 하는게 속도가 10배정도 빠릅니다.(정확히 잰건 아니고 느낌상,,) 주석처리 한 것을 바꾸어주면 속도비교를 하실 수 있습니다.

    • char형으로 계산할땐 Show메소드를 약간 수정해야 겠네요 ^^;; %04d를 %d로;

  • www.programming-challenges.com 에 제출하면 실행시간이 7초이상, UVa에 제출하면 1초네요.

    • 놀라운건 최고속도가 PC에서 0.019초 라는.... 테스트 입력값을 빼내와서 결과만 뿌려준거라고 추측해봅니다;
      • 소켓 플밍해서 입력값 받을 때, 내 IP로 쏘게 하면 되겠는 걸요! 해봐야지 ㅋㅋ
      • 맞아요! ㅋ 하지만... 그런식으로 입력값 빼와서 결과만 출력하게 3n+1을 만들어서 제출했었는데.. 최고속도보다 느렸었다는 ;;;;;
      • 오.. 좋은 생각인데요.. ㅋㅋ

  • 구현할때 보니, 코딩시연할때는 곱하기를 완전 잘못 구현했었어요, :$

  • 책의 해답보다도 속도 빠른거 같아요!

    • 오~ 나이스~ ^ㅇ^/

  • 역시 피곤할땐 잠을 자주는게 최고, 덕분에 KLDP못갔다는;;;

소스코드

    #include <stdio.h>
    #include <string.h>
    #define max(x,y) ((x)>(y)?(x):(y))
    
    #define MAXLEN 25
    #define ONEDIGIT 10000
    typedef int num;
    /*
    #define MAXLEN 200
    #define ONEDIGIT 10
    typedef char num;
    */
    class BigNumber
    {
    public:
    	BigNumber()
    	{
    		Init();	
    	}
    
    	BigNumber(char* in)
    	{
    		Init();
    
    		length = strlen(in);
    		for(int i = length-1; i >= 0; i-- )
    		{
    			Number[i] = in[length-i-1] - '0';
    		}
    	}
    
    	BigNumber(int in)
    	{
    		Init();
    
    		while(in)
    		{
    			Number[length] = in%ONEDIGIT;
    			in/= ONEDIGIT;
    			length++;
    		}
    	}
    
    	const BigNumber& operator+=(const BigNumber& rhs)
    	{
    		int i;
    		int carry = 0;
    		int MaxLen = max(rhs.length, length);
    
    		for( i = 0; i < MaxLen; i++ )
    		{
    			Number[i] = rhs.Number[i] + Number[i] + carry;
    
    			if( Number[i] >= ONEDIGIT )
    			{
    				Number[i] -= ONEDIGIT;
    				carry = 1;
    			}
    			else
    			{
    				carry = 0;
    			}						
    		}
    
    		if( carry )
    		{
    			length = MaxLen+1;
    			Number[i] = carry;
    		}
    		else
    		{
    			length = MaxLen;
    		}
    
    		return *this;
    	}
    
    	const BigNumber& operator-=(const BigNumber& rhs)
    	{
    
    		for(int i = 0; i < length; i++ )
    		{
    			Number[i] = Number[i] - rhs.Number[i];
    			while( Number[i] < 0 )
    			{
    				Number[i] += ONEDIGIT;
    				Number[i+1] -= 1;
    			}
    		}
    
    		int i;
    
    		for(i = length-1; i >= 0; i-- )
    		{
    			if( Number[i] != 0 )
    			{
    				break;
    			}
    		}
    
    		length = i+1;
    
    		return *this;
    	}
    
    	const BigNumber& operator*=(const BigNumber& rhs)
    	{
    		BigNumber Temp;
    		int i, j;
    		int carry = 0;
    		
    		for( i = 0; i < length; i++ )
    		{
    			for( j = 0; j < rhs.length; j++ )
    			{
    				Temp.Number[i+j] += Number[i]*rhs.Number[j];
    
    				if(Temp.Number[i+j] >= ONEDIGIT )
    				{
    					Temp.Number[i+j+1] += Temp.Number[i+j]/ONEDIGIT;
    					Temp.Number[i+j] %= ONEDIGIT;
    				}
    			}
    		}
    
    		for( i = MAXLEN-1; i >= 0; i-- )
    		{
    			if(Temp.Number[i] != 0 )
    			{
    				Temp.length = i+1;
    				break;
    			}
    		}
    
    		*this = Temp;
    
    		return *this;
    	}
    
    	void Show()
    	{
    		if( length == 0 )
    		{
    			printf("0\n");
    			return;
    		}
    
    		printf("%d", Number[length-1]);
    
    		for(int i = length-2; i >= 0; i-- )
    		{
    			printf("%04d", Number[i]);
    		}
    
    		printf("\n");
    	}
    
    private:
    
    	void Init()
    	{
    		length = 0;
    		for(int i = 0; i < MAXLEN; i++ )
    		{
    			Number[i] = 0;
    		}
    	}
    
    	num Number[MAXLEN];
    	int length;
    };
    
    const BigNumber operator+(const BigNumber& lhs, const BigNumber& rhs)
    {
    	BigNumber Temp(lhs);
    
    	Temp += rhs;
    
    	return Temp;
    }
    
    const BigNumber operator-(const BigNumber& lhs, const BigNumber& rhs)
    {
    	BigNumber Temp(lhs);
    
    	Temp -= rhs;
    
    	return Temp;
    }
    
    const BigNumber operator*(const BigNumber& lhs, const BigNumber& rhs)
    {
    	BigNumber Temp(lhs);
    
    	Temp *= rhs;
    
    	return Temp;
    }
    
    BigNumber Matrix[151][151] = {0};
    
    
    BigNumber GetMatrix(int n, int d )
    {
    	if( n == 0 && d == 0 ) return 1;
    	if( n < d ) d = n;
    	
    
    	return Matrix[n][d];
    }
    
    void PrintResult(int n, int d )
    {
    	BigNumber Temp(GetMatrix(n, d) - GetMatrix(n, d-1));
    
    	Temp.Show();
    }
    
    void CalMatrix(int n, int d )
    {
    	for(int i = 0; i < n; i++ )
    	{
    		Matrix[n][d] += GetMatrix(i, d-1)*GetMatrix(n-1-i, d);
    	}
    }
    
    void MakeMatrix()
    {
    	Matrix[0][0] = 1;
    
    	for(int i = 1; i <= 150; i++ )
    	{
    		for(int j = 1; j <= i; j++ )
    		{
    			CalMatrix(i, j);
    		}
    	}
    }
    
    int main()
    {
    	int n, d;
    
    	MakeMatrix();
    
    	while( scanf("%d %d", &n, &d) == 2 )
    	{
    		n /= 2;
    		PrintResult(n, d);
    	}
    	
    	return 0;
    }

Clone this wiki locally