'Algorithm'에 해당되는 글 5건

  1. 2010.06.30 UVA231 DP LDS(Longest Decreasing Sequence)
  2. 2010.05.11 codejam 2010 예선 A
  3. 2009.08.18 DP

주어진 수열에서 가장 긴 감소하는 수열의 길이를 구하는 것.

'Algorithm' 카테고리의 다른 글

UVA231 DP LDS(Longest Decreasing Sequence)  (0) 2010.06.30
codejam 2010 예선 A  (0) 2010.05.11
DP  (0) 2009.08.18
Tree  (0) 2009.08.14
Sort  (0) 2009.08.14
Posted by hyunny82
TAG Algorithm, UVA
2010.05.11 21:29
Problem
The Snapper is a clever little device that, on one side, plugs its input plug into an output socket, and, on the other side, exposes an output socket for plugging in a light or other device. When a Snapper is in the ON state and is receiving power from its input plug, then the device connected to its output socket is receiving power as well. When you snap your fingers -- making a clicking sound -- any Snapper receiving power at the time of the snap toggles between the ON and OFF states. In hopes of destroying the universe by means of a singularity, I have purchased N Snapper devices and chained them together by plugging the first one into a power socket, the second one into the first one, and so on. The light is plugged into the Nth Snapper. Initially, all the Snappers are in the OFF state, so only the first one is receiving power from the socket, and the light is off. I snap my fingers once, which toggles the first Snapper into the ON state and gives power to the second one. I snap my fingers again, which toggles both Snappers and then promptly cuts power off from the second one, leaving it in the ON state, but with no power. I snap my fingers the third time, which toggles the first Snapper again and gives power to the second one. Now both Snappers are in the ON state, and if my light is plugged into the second Snapper it will be on. I keep doing this for hours. Will the light be on or off after I have snapped my fingers K times? The light is on if and only if it's receiving power from the Snapper it's plugged into.

Input
The first line of the input gives the number of test cases, T. T lines follow. Each one contains two integers, N and K.

Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either "ON" or "OFF", indicating the state of the light bulb.

Limits
1 ≤ T ≤ 10,000.
 Small dataset 1 ≤ N ≤ 10; 0 ≤ K ≤ 100;
 Large dataset 1 ≤ N ≤ 30; 0 ≤ K ≤ 108;
Sample
 Input   Output
 4
 1 0      Case #1: OFF
 1 1      Case #2: ON
 4 0      Case #3: OFF
 4 47    Case #4: ON

라지셋까지 통과

'Algorithm' 카테고리의 다른 글

UVA231 DP LDS(Longest Decreasing Sequence)  (0) 2010.06.30
codejam 2010 예선 A  (0) 2010.05.11
DP  (0) 2009.08.18
Tree  (0) 2009.08.14
Sort  (0) 2009.08.14
Posted by hyunny82
2009.08.18 04:40

#include <iostream>
#include <cmath>

using namespace std;

int m[100][100]; //matrixPath
int c[100][100]; //matrixPath
int f[100];   //fib
int C[100][100]; //LCS

int matrixPath(int i,int j);
int fib(n);
int LCS(int m,int n);

void hanoi(int n, int from,int by, int to);
void move(int from,int to);
int main()
{
 /*
 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있으면 최적 부분구조를 가졌다고 함.
 최적 부분구조를 가진 문제의 경우 재귀호출을 사용해 문제를 풀 수 있다.
 그래픽에서도 이용. PC5번 그래픽 문제에서 영역 채움등 재귀적으로 해결.
 */
 fib(7);   //피보나찌 7까지....
 hanoi(3,1,2,3); // 원반 세 개를 기둥 1에서 기둥3으로 기둥 2를 이용하여 옮기는 뜻.
 return 0;
}

int fib(n)
{
 /*
 간명하지만 숫자가 커지면 엄청난 비효율... 지수함수에 비례하는 시간이 듬.
 그래서 이들은 한번만 구해 저장해 놓았다가 나중에 다시 사용하면 호출하는 비용을 낮춤.
 -->Memoization 한번 구한것은 메모해놓는다는 뜻에서...
 
 if(n==1 or n==2)
  return 1;
 else return ((fib(n-1)+fib(n-2));
 */
 if(f[n] != 0) return f[n];
 else{
  if(n==1 || n==2)
   return f[n]=1;
  else
   f[n]=fib(n-1)+fib(n-2);
  return f[n];
 }
}
void hanoi(int n, int from,int by, int to)
{
 if(n==1)    //1개의 원반을 움직이는 문제로 줄어듬
  move(form, to);  // 문제의 크기가 1의 크기로 줄었을 때 원반을 실제로 옮김 from 에서 to로
 else
 {
  hanoi(n-1,form,to,by);
  move(frome,to);
  hanoi(n-1,by,from,to);
 }

}
void move(int from,int to)
{
 cout<<from<<"에서"<<to<<"로 이동"<<endl;
}


int matrixPath(int i,int j)
{
 /*
 행렬의 경로 문제
 오른쪽이나 아래쪽으로만 이동할 수 있다.
 왼쪽,위쪽,대각선 이동은 허용하지 않음.
 더한 값이 최대.

 c(i,j) = m(1,1)        if(i=j=1)    원소 (1,1)에 이르는 최고점수를 구하는 것 원소(1,1)이 답
    m(1,j)+c(1,j-1)     if(i=1,j>1)  첫째 행의 한 원소에 이르는 최고점수를 구하는 것.
                첫째 행을 따라 오른쪽으로 수평 이동하는 방법밖에 없다.
                따라서 (1,j)의 바로 왼쪽 원소(1,j-1)에 이르는 점수 ((1,j-1)에 이르는
                유일한 점수이자 최고점수)에 원소(i,j)의 값을 더하면 된다.
    m(i,1)+c(i-1,1)     if(i>1,j=1)
    m(i,j)+max{c(i,j-1),c(i-1,j)}  if(i>1,j>1)
  
 

 if(i==1 && j==1)
  return m[1][1];
 else if(i==1)
  return (m[1][j]+matrixPath(i,j-1));
 else if(j==1)
  return (m[i][1]+matrixPath(i-1,1));
 else
  return (m[i][j]+(max(matrixPath(i-1,j),matrixPath(i,j-1)));
 */
}

int matrixPath(int n)
{
 //(n,n)에 이르는 최고점수
 c[1][1]=m[1][1];
 for(int i=2;i<n;i++)
  c[i][1]=m[i][1]+c[i-1,1];
 for(int j=2;j<n;j++)
  c[1][j]=m[1][j]+c[1,j-1];
 for(int i=2;i<n;i++)
  for(int j=2;j<n;j++)
   c[i][j]=m[i][j]+max(c[i-1][j],c[i][j-1]);
 return c[n][n];
}
int matrixChain(int i,int j)
{
 /*
 행렬곱셉문제
 해열ㄹ으 ㅣ곱셈에서 (AB)C=A(BC)
 n개의 행렬을 어떤 순서로 두 개씩 짝지어 계산해도 결과는 동일
 4개의 행렬 곱하는 모든 경우의 수
 ((A1A2)A3)A4)
 (A1A2)(A3A4)
 (A1(A2A3))A4)
 A1((A2A3)A4)
 A1(A2(A3A4))
 
 일반적으로 n개의 행렬 곱셈에 대해서 총 n-1번의 곱셈을 한다.

 두행렬 A,B가 각각 p x q, q x r행렬이라면 두 행렬의 곱 AB를 계산하는 데는 pqr번의 스칼라 곱셈이 일어난다.
 이것이 행렬 곱셈 시간을 좌우

 예를 들어 A, B, C가 각각 10x100, 100x5, 5x50 행렬이라면
 (AB)C 와 A(BC)의 스칼라 곱셈 횟수를 구해보면
 (AB)C는 10*100*5=5,000 번에 10*5*50=2,500 번 더해서 총 7500번 필요
 A(BC)는 100*5*50=25,000번 10*100*50=50,000번의 스칼라 곱 총 75000번 필요
 순서에 따라 10배의 차이가 남...
 괄호를 묶는 총 가지 수는 Ω(2^n) 적어도 2의 지수함수 이상에 비례
 행렬 곱셈 문제는 n개의 행렬 주어졌을때 시간을 가장 적게 사용하는지 알아내는 문제.
 
 */
}

int LCS(int m,int n)
{
 /* 최장 공통 부분순서(Longest Common Subsequence)
 문자열<bcdb>는 문자열<abcbdab>의 부분순서이다. 꼭 연속할 필요는 없음.
 <abcbdab>와<bdcaba>에 대하여 문자열 <bca>는 두 문자열에 공통적으로 나타나는 부분순서(공통 부분순서).
 <bcba>는 두 문자열에 존재하는 가장 긴 공통 부분순서 즉 LCS이다.
 
 정리1
 Xm=<x1x2x3...xm>와 Ym=<y1y2y3...ym> 의 LCS 길이가 k라 하자. LCS는 하나 이상 있을 수 있는데 이 중 하나를 Zk=<z1z2...zk>
 xm = ym 이면 zk=xm=ym 이고 Zk-1은 Xm-1과 Yn-1의 LCS이다
 xm != ym 이면 zk != xm 이고 Zk은 Xm-1과 Yn-1의 LCS이다
 xm != ym 이면 zk != ym 이고 Zk은 Xm과 Yn-1의 LCS이다


 점화식
 c(i,j)를 문자열 Xi=<x1x2x3...xi>와 Yi=<y1y2y3...yi>의 LCS의 길이라 한다.

 c(i,j)= 0         if i==0 or j==0
   c(i-1,j-1)+1      if i,j>0 and xi ==yi
   max{ c((i-1),j) , c(i,(j-1)) }  if i,j>0 and xi != yi
 
 if(m==0 or n==0 )
  return 0;
 else if(xm == yn)
  return LCS(m-1,n-1)+1;
 else
  return max(LCS(m-1,n),LCS(m,n-1));
 
 지수함수로 커지는 것을 방지.
 작은 문제들의 해를 아래부터 저장
 이차원 배열 C[][]에 각 부분 문제의 답을 저장하면서 풀어나가는 방식 배열의 총 원소는 (m+1)(n+1)이고
 for루프가 총 mn번 반복하면서 원소를 하나씩 계산 수행시간은 Θ(mn)
 */
 for(int i=0;i<m;i++)
  C[i][0]=0;
 for(int j=0;j<n;j++)
  C[0][j]=0;
 
 for(int i=1;i<m;i++)
  for(int j=1;j<n;j++)
  {
   if(xi==yi)
    C[i][j]=C[i-1][j-1]+1;
   else
    C[i][j]=max(C[i-1][j],C[i][j-1]);
  }
 return C[m][n];
}

 

 

'Algorithm' 카테고리의 다른 글

UVA231 DP LDS(Longest Decreasing Sequence)  (0) 2010.06.30
codejam 2010 예선 A  (0) 2010.05.11
DP  (0) 2009.08.18
Tree  (0) 2009.08.14
Sort  (0) 2009.08.14
Posted by hyunny82
이전버튼 1 2 이전버튼

티스토리 툴바