도전 프로그래밍(알고리즘 및 데이터 구조)

기사 목록

피보나치 수열

(LCS)

(LIS)

매트릭스 체인 곱셈

동전 문제

0-1 가방 문제

최대 정사각형

최대 직사각형

가방 문제

피보나치 수열
제목 11.2 링크 Fibonacci Number 해결 피보나치 수열 세 가지 방법 1> 직접 귀속

fib(n)
	if n==0 || n==1
		return 1
	return fib(n-1)+fib(n-2)

2>기억화 귀속

fib(n)
	if n==0 || n==1
		return F[n] = 1
	if F[n]
		return F[n]
	return F[n] = fib(n-1)+fib(n-2)

3 > 동적 계획

fib()
	F[0] = 1
	F[1] = 1
	for i = 2-n
		F[i] = F[i-1]+F[i-2]

코드는 다음과 같습니다.

#include 
#include 
using namespace std;

const int Max = 50;
int F[Max];

int Fib(int n)
{
    F[0] = 1;
    F[1] = 1;
    if(n==0 || n==1) return F[n];
    if(F[n])
        return F[n];
    return F[n] = Fib(n-1)+Fib(n-2);
}
void makeFib()
{
    F[0] = 1;
    F[1] = 1;
    for(int i=2; i<Max; i++)
    {
        F[i] = F[i-1]+F[i-2];
    }
}
int main()
{
    int n;
    cin >> n;
    memset(F, 0, sizeof(F));
    cout << Fib(n) << endl;
}

최대 공용 하위 열(LCS)
제목 11.3 링크 Longest Common Subsequence 해석: 다음 변수를 설정할 수 있습니다
변수
함의
c[m+1][n+1]
c[i][j]는 X i와 Y j X_를 나타냅니다.{i} 및 Y_Xi 및 Yj의 LCS 길이
X i와 Y j X_ 구하기{i} 및 Y_{j} Xi와 Yj의 LCS는 두 가지 상황을 고려해야 합니다.

x m = y n x_{m}=y_{n}xm=yn 시 X m−1 및 Y n−1 X_{m-1} 및 Y_{n-1} Xm−1 및 Yn−1 LCS 추가 필요

x m ! = y n x_{m}!=y_{n} xm!=yn 시 X m와 Y n−1 X_{m} 및 Y_{n-1} Xm와 Yn−1의 LCS 및 Xm−1 및 Yn X_{m-1} 및 Y_{n} Xm−1 및 Yn의 LCS 크기

c [ i ] [ j ] = { 0 , i = 0 o r j = 0 c [ i − 1 ] [ j − 1 ] + 1 , i , j > 0 a n d x i = y j m a x ( c [ i ] [ j − 1 ] , c [ i − 1 ] [ j ] ) , i , j > 0 a n d x i ! = y j c[i][j] =\begin{cases} 0 & & ,i=0 or j=0\\c[i-1][j-1]+1 & & ,i,j>0 and x_{i}=y_{j}\\max(c[i][j-1], c[i-1][j]) & & ,i,j>0 and x_{i}!=y_{j}\\\end{cases} c[i][j]=⎩⎪⎨⎪⎧0c[i−1][j−1]+1max(c[i][j−1],c[i−1][j]),i=0orj=0,i,j>0andxi=yj,i,j>0andxi!=yj 코드는 다음과 같습니다.

#include 
#include 
#include 
using namespace std;

const int Max = 1005;
int c[Max][Max];// 

void lcs(string s1, string s2)
{
    // i j 0 ， 
    for(int i=0; i<=s1.size(); i++)
    {
        c[i][0] = 0;
    }
    for(int i=0; i<=s2.size(); i++)
    {
        c[0][i] = 0;
    }
    s1 = " " + s1;// c ， 
    s2 = " " + s2;
    // 
    for(int i=1; i<=s1.size(); i++)
    {
        for(int j=1; j<=s2.size(); j++)
        {
            if(s1[i]==s2[j]) c[i][j] = c[i-1][j-1]+1;
            else
            {
                c[i][j] = max(c[i][j-1], c[i-1][j]);
            }
        }
    }
}
int main()
{
    int n;
    cin >> n;
    string s1, s2;
    for(int i=0; i<n; i++)
    {
        cin >> s1 >> s2;
        lcs(s1, s2);
        cout << c[s1.size()][s2.size()] << endl;
    }
    return 0;
}

최대 증분 하위 시퀀스(LIS)
제목 17.3 링크 Longest Increasing Subsequence 참고 논문 LIS의 두 가지 방법: DP와 이분법~LIS는 두 가지 방법이 있는데 DP(O(N^2)와 이분법(O(Nlog(N)이 있고 데이터량이 비교적 많을 때 이분법을 사용한다.해석: 다음 변수를 설정할 수 있습니다.
변수
함의
L[i]
L[i]는 길이가 i인 점증 서브시퀀스의 마지막 요소 최소값을 나타냅니다.
l e n g t h i length_{i} lengthi
이전 i개 원소로 구성된 최장 증차 서열의 길이를 나타낸다
2분 검색법: 사고방식: 우리 과정은 줄곧 L 수조를 업데이트하는 것이다. 두 가지 상황이 있다

A[i]>L[length-1]은 L수조를 확장하고 L[++length]=A[i].(A[i]는 하위 시퀀스의 길이를 늘릴 수 있기 때문에 이 시퀀스를 추가합니다)

A[i]<=L[length-1]은 L수조를 업데이트하고 2분 검색 업데이트 L수조 중 첫 번째로 A[i]보다 큰 요소는 A[i]이다.(왜냐하면 L[i]는 길이가 i인 증가자 서열의 마지막 원소(모든 증가자 서열 중 마지막 원소가 가장 작은 것)를 대표하기 때문에 L[i]가 A[i]보다 작은 원소는 모두 A[i]와 증가자 서열을 구성할 수 있기 때문에 A[i]를 사용하여 첫 번째 원소보다 큰 원소를 업데이트할 수 있다.

코드는 다음과 같습니다.

#include 
#include 
using namespace std;

const int MAX = 100005;
int n, length;
int A[MAX], L[MAX];

void LIS()
{
    L[0] = A[0];
    length = 1;
    for(int i=1; i<n; i++)
    {
        if(L[length-1]>=A[i])
        {
            int *p = lower_bound(L,L+length,A[i]);
            *p = A[i];
        }
        else
        {
            L[length++] = A[i];
        }
    }
}
int main()
{

    cin >> n;
    for(int i=0; i<n; i++)
    {
        cin >> A[i];
    }
    LIS();
    cout << length << endl;
    return 0;
}

L[]을 INF로 초기화하여 코드 단순화

// 
int L[MAX]
void solve()
{
	fill(L, L+n, INF);// 
	for(int i=0; i<n; i++)
	{
		*lower_bound(L, L+n, INF) = L[i];
	}
	printf("%d
", lower_bound(L, L+n, INF) - dp);//

DP법:

구조 상태: L[i]은 i자로 끝나는 문자열의 최대 증가 서브열의 길이를 나타냅니다.

종태: max(L[i]), i>0 & i<=N

상태 전환 방정식: L[i] = max{1, L[j]+1}(j

초태: L[i]= 1, i>0 & i<=N 핵심 코드:

int Max = 1;
for(int i=1; i<=p; i++)
            L[i] = 1;
for(int i=2; i<=p; i++)
{
    for(int j=0; j<i; j++)
    {
        if(x[i]>x[j])
            L[i] = max(L[i], L[j]+1);
    }
    if(Max<L[i]) Max = L[i];
}
cout << Max << endl;

행렬 체인 곱셈
제목 11.4 링크 Matrix Chain Multiplication 해석: 다음 변수를 설정할 수 있습니다
변수
함의
m[n+1][n+1]
m[i][j]는 계산(M i M i + 1... M j)(M_{i}M_{i+1}...M_{j})(Mi Mi+1...Mj)가 필요한 곱셈 연산의 최소 횟수임을 나타냅니다.
p[n+1]
행렬을 저장하는 데 사용되는 행렬 수 중 M i는 p [i−1]× p [ i ] M_{i}는 p[i-1]\times p[i] Mi는 p[i−1]입니다.×p[i]의 행렬
사고방식은 가능한 모든 분할 상황을 두루 훑어보고 (M i M i + 1... M j) (M _ {i} M_ {i+1}... M_ {j}) (Mi Mi+1... Mj) 의 최소 연산 횟수, 즉 m [i] [j] = {0, i = j m i ≤k < j (m [i] [k] + 1] [j] + p [i − 1]× p [ k ] × p [ j ] ) , i < j m[i][j] =\begin{cases} 0 & & ,i=j\\min_{i\leq k 추출법: 코드는 다음과 같습니다.

#include 
using namespace std;

const int Max = 200;
int p[Max];
int m[Max][Max];

int main()
{
     int n;
     cin >> n;
     for(int i=1; i<=n; i++)
     {
         cin >> p[i-1] >> p[i];
     }
     for(int i=1; i<=n; i++)// 
        m[i][i] = 0;
     for(int l=2; l<=n; l++)//l ， 2 n
     {
         for(int i=1; i<=n-l+1; i++)//i 
         {
             int j=i+l-1;//j 
             m[i][j] = (1<<21);// 
             for(int k=i; k<j; k++)// 
             {
                 m[i][j] = min(m[i][j], m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]);
             }
         }
     }
     cout << m[1][n] << endl;
     return 0;
}

기억화 검색법 코드는 다음과 같다.

#include 
#include 
#include 
#include 
using namespace std;

const int MAX = 105;
const int INF = 1<<29;
struct Matrix
{
    int r, c;
};
Matrix M[MAX];
int dp[MAX][MAX], n;

int DP(int i, int j)
{
    int &ans = dp[i][j];
    if(ans!=-1) return ans;
    ans = INF;
    for(int k=i; k<j; k++)
    {
        ans = min(ans, DP(i, k)+DP(k+1, j)+M[i].r*M[k].c*M[j].c);
    }
    return ans;
}
int main()
{
    scanf("%d", &n);
    memset(dp, -1, sizeof(dp));
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d", &M[i].r, &M[i].c);
        dp[i][i] = 0;
    }
    printf("%d
", DP(1, n));
    return 0;
}

동전 문제
제목 17.1 링크 Coin Changing 문제 해결: 다음 변수를 설정할 수 있습니다
변수
함의
C[i]
C[i]는 i종 동전의 액면가를 나타냅니다.
T[i][j]
T[i][j]는 0에서 i까지의 동전으로 j를 지불할 때의 최소 동전 개수를 나타낸다
반환식 가능: T[i][j]=min(T[i-1][j], T[i][j-C[i]+1)T[i-1][j]는 제 i종 동전을 사용하지 않고, T[i][j-C[i]+1은 제 i종 동전을 사용하며, 양자 중 가장 작은 것을 제거하면 된다.T 행렬에서 알 수 있듯이 동적 기획을 사용할 수 있고 T를 1차원 그룹으로 간소화하여 작은 것에서 큰 것으로 값을 구할 수 있다.
변수
함의
T[n]
T[j]는 j원을 지불하는 동전의 최소 개수를 나타낸다
귀속 공식은 다음과 같습니다: T[j]=min(T[j], T[j-C[i]]+1)
코드는 다음과 같습니다.

#include 
#include 
using namespace std;

const int Max1 = 50005;
const int Max2 = 30;
const int INF = (1<<29);
int C[Max2], T[Max2][Max1];
int T2[Max1];

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        cin >> C[i];
    }
    //sort(C+1, C+m+1);// 
    for(int j=0; j<=n; j++)
    {
        T2[j] = INF;
    }
    T2[0] = 0;
    for(int i=1; i<=m; i++)// 
    {
        for(int j=C[i]; j<=n; j++)
        {
            T2[j] = min(T2[j], T2[j-C[i]]+1);
        }
    }
    cout << T2[n] << endl;
    return 0;
}

/*  int main() { int n, m; cin >> n >> m; for(int i=1; i<=m; i++) { cin >> C[i]; } sort(C+1, C+m+1); for(int j=0; j<=n; j++) { T[0][j] = INF; } for(int i=0; i<=m; i++) { T[i][0] = 0; } for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) { if(j>=C[i]) T[i][j] = min(T[i-1][j], T[i][j-C[i]]+1); else T[i][j] = T[i-1][j]; } } cout << T[m][n] << endl; return 0; } */

0-1 가방 문제
문제 17.2 링크 0-1 Knapsack 문제 해결: 다음 변수를 설정할 수 있습니다
변수
함의
items[N+1]
구조체 수조입니다. item[i].v、item[i].w 각각 i번째 물품의 가치와 무게를 기록한다
C[N+1][W+1]
C[i][w]는 이전 i개 물품의 적재 용량이 w인 가방이 총 가치의 최대치를 나타낸다
사고방식: 각각 하나의 물건이 있기 때문에 C [i] [w] = {0, i= 0 o r w = 0 m a x(C [i−1], C [i−1] [w− i t e m[i]. w + i t e m [i]. v), i t e m[i]. w <= w C [i−1], i t m [i]. w C[i]=\begin{cases} 0 &, i=0 or w=0\max(C[i-1][w], C[i-1][w-item[i].w]+item[i].v) &, item[i].w<=w\\C[i-1][w] & & ,item[i].w>w\end{cases} C[i][w]=⎩⎪⎨⎪⎧0max(C[i−1][w],C[i−1][w−item[i].w]+item[i].v)C[i−1][w],i=0orw=0,item[i].w<=w,item[i].w>w 코드는 다음과 같습니다.

#include 
using namespace std;

const int Max = 200;
const int W = 10005;
struct Node
{
    int v, w;
};
Node item[Max];
int C[Max][W];

int main()
{
    int N, W;
    cin >> N >> W;
    for(int i=1; i<=N; i++)
    {
        cin >> item[i].v >> item[i].w;
    }
    for(int i=0; i<=N; i++)// 
    {
        C[i][0] = 0;
    }
    for(int w=0; w<=W; w++)
    {
        C[0][w] = 0;
    }
    for(int i=1; i<=N; i++)
    {
        for(int w=1; w<=W; w++)
        {
            if(item[i].w<=w)// 
            {
                C[i][w] = max(C[i-1][w], C[i-1][w-item[i].w]+item[i].v);
            }
            else
            {
                C[i][w] = C[i-1][w];
            }
        }
    }
    cout << C[N][W] << endl;
    return 0;
}

최대 정사각형
제목 17.4 링크 Largest Square 해석: 다음 변수를 설정할 수 있습니다.
변수
함의
dp[H][W]
dp[i][j]는 (i, j)에서 왼쪽 위로 확장할 수 있는 최대 정사각형의 가장자리를 저장합니다.
G[H][W]
G[i][j]는 입력한 그림 (i, j) 요소를 저장합니다.
dp[i][j]의 값은 왼쪽 위, 위와 같습니다.왼쪽 요소 중 가장 작은 값에 1을 추가합니다.그 중에서 초기화할 때 dp[0][j]= 1-G[0][j], dp[i][0]= 1-G[i][0].dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1. 코드는 다음과 같습니다.

#include 
using namespace std;

const int Max = 1500;
int G[Max][Max], dp[Max][Max];
int H, W, LS;

int main()
{
   cin >> H >> W;
   LS = 0;// 
   for(int i=0; i<H; i++)
   {
       for(int j=0; j<W; j++)
       {
           cin >> G[i][j];
       }
   }
   for(int i=0; i<H; i++)// 
   {
       dp[i][0] = 1-G[i][0];
       LS = max(dp[i][0], LS);
   }
   for(int j=0; j<W; j++)
   {
       dp[0][j] = 1-G[0][j];
       LS = max(dp[0][j], LS);
   }
// 
   for(int i=1; i<H; i++)
   {
       for(int j=1; j<W; j++)
       {
           if(G[i][j])
               dp[i][j] = 0;
           else
           {
               dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1;
           }
           LS = max(LS, dp[i][j]);
       }
   }
   cout << LS*LS << endl;
   return 0;
}

최대 직사각형
제목 17.5 링크 Largest Rectangle 해석: 다음 변수를 설정할 수 있습니다
변수
함의
S
S는 스택이며 요소는 구조체(요소 높이, 사각형의 가장 왼쪽 경계 포함)입니다.
스택+DP 네 가지 상황:rect는 구조체의 한 요소이다

창고가 비어 있음 - rect를 창고에 눌러넣기

창고 꼭대기 장방형의 높이가rect의 높이보다 작다 - rect를 창고에 눌러넣기

창고 꼭대기 장방형의 높이는rect의 높이와 같다. - 처리하지 않는다

창고 꼭대기 장방형의 높이가rect의 높이보다 크다 - 최대 장방형의 면적을 업데이트

구체적인 해법은 코드를 참조하십시오.

#include 
#include 
#include 
#include 
using namespace std;

const int Max = 1500;
struct Node// ，height ，pos 
{
    int height, pos;
};
int H, W;
int G[Max][Max], T[Max][Max];//G ，T 

int main()
{
    cin >> H >> W;
    for(int i=0; i<H; i++)
    {
        for(int j=0; j<W; j++)
        {
            cin >> G[i][j];
        }
    }
    // 
    for(int j=0; j<W; j++)
    {
        for(int i=0; i<H; i++)
        {
            if(G[i][j])// 
            {
               T[i][j] = 0;
            }
            else
            {
                if(i==0)// 
                    T[i][j] = 1;
                else// 
                    T[i][j] = T[i-1][j]+1;
            }
           
        }
   
    }

    // 
    stack<Node> S;
    int maxv = 0, area = 0;
    for(int i=0; i<H; i++)
    {
        T[i][W] = 0;// j=W-1 
        for(int j=0; j<=W; j++)
        {
            Node rect;
            rect.height = T[i][j];
            rect.pos = j;
            if(S.empty())
                S.push(rect);
            else
            {
                if(S.top().height<rect.height)
                {
                    S.push(rect);
                }
                else if(S.top().height>rect.height)
                {
                    int target = j;
                    while(!S.empty() && S.top().height>=rect.height)// height rect height
                    {
                        Node pre = S.top(); S.pop();
                        area = (j-pre.pos)*pre.height;// 
                        maxv = max(maxv, area);
                        target = pre.pos;// 
                    }
                    rect.pos = target;
                    S.push(rect);// 
                }
            }
        }
    }
    cout << maxv << endl;
    return 0;
}

가방 문제
참고 박문 가방 문제 요약 문제(동적 기획 01 가방(제k 우해) 완전 가방, 다중 가방)

예제 2의 문제를 두 개의 하위 문제로 나누는 해결 방법에 주의한다.

01번째 가방 k번째 최우해

int i,j,t,k;//k k 
for(i=0;i<n;i++) // 
		for(j=v;j>=vol[i];j--) //  
		{
		
			for(t=1;t<=k;t++)
			{ // 
				a[t]=f[j][t];//f[j][0] 
				b[t]=f[j-vol[i]][t]+val[i];//t=0 
			}
			int m,x,y;
			m=x=y=1;
			a[k+1]=b[k+1]=-1;
			// a b ，  （ a b k ， m ， ）
			while(m<=k && (a[x]!=-1 || b[y]!=-1))
			{
				if(a[x]>b[y])
					f[j][m]=a[x++];
				else 
					f[j][m]=b[y++];	
				if(f[j][m]!=f[j][m-1])
					m++;
			}
		}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

도전 프로그래밍(알고리즘 및 데이터 구조) - DFS 및 BFS 및 일부 어플리케이션

어플리케이션 제목 12.3 링크 Depth First Search DFS는 귀속과 창고를 사용하여 풀 수 있습니다. DFS 적용 관련 설명은 tarjan 알고리즘 구관절점과 p291을 보십시오.변수 설정은 다음과 같...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

도전 프로그래밍(알고리즘 및 데이터 구조) - 동적 계획(DP)

기사 목록

좋은 웹페이지 즐겨찾기