세상의 모든 Software 지식을 정리

문제: https://algospot.com/judge/problem/read/PINBALL * 공이 가장 일찍 장애물과충돌하는 위치를 찾자 f(t)=p+t*d(t>=0) 중심이 c 반지름이 r |c-f(t)|=r

*문자열에서 K번이상 등장하는 부분 문자열을 말버릇이라고 한다. -->해결방법은 접미사배열을 만든 후, 접미사배열의 각 접미사들은 접두사로 만들어 부분문자열을 만들 수있다. 어차피 중복되는 부분문자열을 접미사배열에서 인접해 있기 때문에 각 A[i]와 A[i+k-1]의 가장 긴 길이를 구하며 그것이 k개 이상의 공통부분문자열이 된다.

문제: https://algospot.com/judge/problem/read/JAEHASAFE 두 문자열을 이어 붙여 검색한다 KMP알고리즘의 수행시간은 두 문자열의 길이에 선형 비례하므로 shifts()는 문자열의 길이에 해당하는 O(L)시간만에 동작한다. int shifts(const string& original,const string& target) {   return kmpsearch(original+original,target)[0]; }

<두 가지 방법> 1. 동적계획 2.  비동적계획 1번: 비대칭 타일이 되는 경우의 수를 모두 더한다

Q) 여름 장마가 찾아와 매일 비가 올 확률이 50%에서 75%로 올라갔다고 합시다. 이때 m일동안 N미터 만큼 달팽이가 N미터를 오를 확률을 구하시오 (단, 비가 오지 않으면 2미터를 오르고, 비가오면 1미터를 오른다) ---->>> climb2(days,climbed)=달팽이가 지금까지 days일동안 climbed미터를 기어올라 왔을 때 m일전까지 n미터 이상 기어 올라 갈 수 있을 확률 오늘 비가 올 경우와 오지 않을경우 , 달팽이가 우물을 탈출할 확률은 각각 climb2(days+1,climbed+1)과 climb2(days+1,climbed+2)로 표현 할 수 있다. 이 경우는 비가 올 확률과 오지 않을 확률이 각각 50%인 경우이다. 75%로 하게 된다면 climb2(days,climbed)=0.75*climb2(days+1,climbed+1)+0.25*(days+1,climbed+2)이다.

숫자로 이루어진 삼각형이 주어졌을 때, 최대경로 합의 갯수를 구하기 단, 아래 또는 오른쪽 대각선으로만 움직 일 수 있다. count(y,x)=(y,x)에서 시작해 맨 아래줄까지 내려가는 최대 경로의 수                        count(y+1,x) (path2(y+1,x)>path2(y+1,x+1)) count(y,x)=max(  count(y+1,x+1)  (path2(y+1,x+1)>path2(y+1,x))                        count(y+1,x+1)+count(y+1,x)   (path2(y+1,x+1)==path2(y+1,x)) --->>> 중요한 점 삼각형 경로에서 path(y+1,x+1)과 path(y+1,x)의 크기를 비교 할 때 단순기 경로사의 수를 비교하는 게 아니라 경로상의 최대합의 크기를 비교해야 한다. 그 이유는 만약 바로 다음 경로의 크기가 작다고 하더라도 다다음의 크기가 압도적으로 클 수 있다.     (a)        |     (b) 9             |    24 5 7          |     13  15 1 3 2        |     6    8   8 3 5 5 6     |     3     5   5 ...

문제) 2Xn 크기의 사각형을 2X1 크기의 타일로 채우는 방법의 수 tiling(n)=2Xn크기의 사각형을 타일로 덮는 방법 tiling(n)=tiling(n-1)+tiling(n-2); private static int dp[]; public static void main(String[] args) { // TODO Auto-generated method stub int N=5;       dp=new int[N+1];       Arrays.fill(dp, -1);             System.out.println(tiling(N)); } private static int tiling(int n){ if(n==0)return 1; if(n<0)return 0; if(dp[n]!=-1)return dp[n]; int ret=0; ret+=tiling(n-1)+tiling(n-2); return dp[n]=ret; }

<문제> https://algospot.com/judge/problem/read/QUANTIZE <key 포인트> N개의 숫자를 S개의 묶음으로 묶어서 해결 할 것. 만약 첫 묶음의 크기를 x라고 한다면 이제 나머지 묶음의 크기는 n-x개의 숫자를 S-1개로 묶는다. 이때 나머지 S-1개의 묶음의 합이 최소 값이어 야한다. 구간의 오차제곱의 최소합 구하기( 한개의 숫자로 표현했을시) 예를들어 1,4,6을 4로 표현  b ∑(A[i]-m)^2=(b-a+1)^2*m^2 -2*( ∑A[i])*m+ ∑(A[i])^2  a 이를 미분해서 정리하면 결국 m=( ∑A[i])/(b-a+1)로 평균이 된다. 이를 일일히 구하면 O(n)시간이 들지만  O(1)에 계산 할 수도 있다. 바로 A의 부분합을 계산하면 된다. pSum[k]=i는 0부터 k 까지의 A[i]의 합이라 할때 pSum[b]-pSum[a-1]=i가 0부터 b까지인 A[i]의 합 - i가 0부터 a-1까지인 A[i]의 합으로 나타 낼 수 있다. 오차제곱도 일일히 계산하면 오래걸린다.  오차제곱의 합= i가 a부터 b까지 일때 (A[i]-m)^2을 더한 값으로 이는 상수인 A[i]^2의 합- 2*m*(A[i]의 합)+m^2(b-a+1)이다. 이때, 첫 인자와 두번째는 m과 관련없는 부분합으로 미리 계산해 둔다. public class Quantization { private static int N; //사이즈 private static int p; private static int A[]; private static int pSum[]; private static int pSqSum[]; private static int cache[][]; private static final int INF=9999; public static void main(String[] a...

정수수열 S의 부분 수열이란 S에서 0개 이상의 숫자를 지우고 남은 수열을 말한다. 예를들어, '1 2 4'는 '1 5 2 4 7'의 부분 수열이다. {3,2,1,7,5,4,2,6}의 최대 부분 수열의 길이를 구하라 <내가 푼 방법> private static int Lis(int A[],int index){ if(index==N) return 1; int max=0; for(int i=index+1;i<N;i++){ if(A[index]<A[i]) max=Math.max(max,Lis(A,i+1)+1); } return max; } <책 내용> private static int Lis(Vector<Integer> v){ if(v.isEmpty())return 1; int ret=0; for(int i=0;i<v.size();i++){ Vector<Integer> temp=new Vector<Integer>(); for(int j=i+1;j<v.size();j++){ if(v.get(i)<v.get(j)) temp.addElement(v.get(j)); ret=Math.max(ret,Lis(temp)+1); } } return ret; }