대엉코딩

https://www.acmicpc.net/problem/1932

1. 풀이방법

- 최대 깊이가 500입니다.

- 모든 경우의 수를 모두 구하면 매우 커짐을 알 수 있습니다.

- 점화식을 세우고, 0과 i==j 일때 (한변에서 양 끝은 선택권이 한개씩 뿐) 처리를 따로 해주시면 됩니다.

- 바텀업 방식으로 작성했습니다.

2. 주의사항

- 없음

3. 나의코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

int triangle[500][500];
int dp[500][500];
int n;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i + 1; j++) {
			cin >> triangle[i][j];
			dp[i][j] = -1;
		}
	}
	dp[0][0] = triangle[0][0];
	
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i + 1; j++) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][j] + triangle[i][j];
			}
			else if (j == i) {
				dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
			}
		}
	}
	int maxr = -1;
	for (int i = 0; i < n; i++) {
		maxr = max(dp[n - 1][i], maxr);
	}
	cout << maxr << "\n";
	return 0;
}

https://www.acmicpc.net/problem/1103

1. 풀이방법

- 처음에는 단순 dfs로 접근하긴 했지만 (오랜만에 풀이라 일단 접근했음)

- 하면서도 분명 제대로 구현되도 시간초과가 뜨거나 스택오버플로우가 날 것 이라 생각했습니다.

- 처음시도는 역시나 시간초과

- 시간초과라면 dp테이블을 이용해보자는 생각 !

- 아, 근데 오랜만에 푸니까 dp적 머리가 잘 돌아가지 않아서 고생을 좀 했습니다....

- 우선 테이블을 모두 -1 처리를 하고 visit이 이미 true인 곳에 다시 오면 그건 싸이클이므로

- -1을 출력 (무한정 왔다리갔다리 가능)

- dp가 -1이 아닐경우 기존에 저장되어 있는 수와 현재의 루트에서 +1 (한번 더 이동) 해서 더 많은 이동횟수로 업데이트

- dfs +dp 라고 할 수 있겠네요. dfs는 간단한 수준이라 생략하겠습니다.

2. 주의사항

- 시간초과

3. 코드

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define endl "\n"
using namespace std;

int N, M;
int ground[50][50];
int dp[50][50];
bool visited[50][50];

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };


void Input(){
    cin >> N >> M;
    for (int i = 0; i < N; i++){
        string inputs;
        cin >> inputs;
        for (int j = 0; j < inputs.length(); j++){
            if (inputs[j] == 'H') ground[i][j] = 0;
            else ground[i][j] = inputs[j] - '0';
        }
    }
}

int DFS(int x, int y){
    if (x < 0 || y < 0 || x >= N || y >= M || ground[x][y] == 0) return 0;
    if (visited[x][y] == true) // 무한반복이 가능
    {
        cout << -1 << endl;
        exit(0);
    }
    if (dp[x][y] != -1) return dp[x][y]; // 바로 dp 테이블에서 리턴

    visited[x][y] = true;
    dp[x][y] = 0;
    for (int i = 0; i < 4; i++){
        int tx = x + (ground[x][y] * dx[i]);
        int ty = y + (ground[x][y] * dy[i]);
        dp[x][y] = max(dp[x][y], DFS(tx, ty) + 1);
    }
    visited[x][y] = false;
    return dp[x][y];
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Input();
    memset(dp, -1, sizeof(dp)); //dp 테이블 초기화
    cout << DFS(0, 0) << endl;
    return 0;
}

www.acmicpc.net/problem/1965

1. 풀이방법

- 간단하게 생각하면 매우 간단합니다. 

- 저 같은 경우 처음에 막혔던 부분이 보통의 dp문제에서 dp테이블은 각각의 n에 따른 정답? 을 가지고 있습니다.

- 이런식으로 짜려고 고민을 하다 보니 상당히 구현이 까다로웠습니다.

- 예를 들면 테스트케이스 가 1, 6, 2, 5, 7, 3, 5, 6   총 8개 인데

- 보통의 dp 테이블이면 만약 dp[6]을 뽑으면 최대치는 1,2,5,7 로서 4가 나와야 하고 

- 이때의 상자의 바깥껍질의 크기인 7을 저장하면 dp[7]을 구하려고 할 때 1,2,5,7,과 1,2,3, +5 를 비교하는 것이 힘들었습니다.

- 설명하기가 조금 곤란한데, 비슷한 고민을 하신 분들은 공감을 하시리라....조심스럽게 생각해봅니다....

- 그래서 이 문제의 경우 n이하의 각각의 정답(즉 최대 상자의 수)를 dp에 저장하는 것이 아니라 

- n에 크기를 늘려가면서 그때까지 차곡차곡 쌓기만한 크기를 저장해 놓은 다음 출력 전에 정렬을 해서 max 값을 

- 출력하였습니다. 물론 정렬(소팅)을 하지않고 최대값만 갱신해도 상관 없습니다.

- 이런식으로 할경우 사실 정렬 전에 dp[6]에는 상자의 개수 3 (1,2,3) dp[5]에는 4 (1,2,5,7) 이 들어가 있습니다.

- 그러므로 n이 6일 때의 정답이 테이블에 들어가 있는 것은 아닌 것이죠. 정렬을 해서 출력을 해줘야 정답이 나오는 

- 것 입니다. 하지만 이렇게 하면 문제의 요구사항에는 전혀 에러가 없고, 구현이 편해집니다.

2. 주의사항

- 위에 기재.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int dp[1001]; // 사실상 정확한 dp를 가지고 있는 테이블은 아니다.
int n;
int narr[1001]; //상자의 크기


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) { //초기화
		cin >> narr[i]; dp[i] = 1;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			if (narr[i] > narr[j] && dp[i]<dp[j]+1) {
				dp[i] = dp[j]+ 1;
			}
		}
	}
	sort(dp + 1, dp + (n + 1));
	cout << dp[n];

	return 0;
}

www.acmicpc.net/problem/11048

1. 풀이방법

- 다이나믹프로그래밍을 이용해서 탑다운 방식으로 해결하였습니다.

- 저 같은 경우 1행의 모든 값과 1열의 모든 값들은 가로 또는 세로로 쭉 이동하는 경우밖에 없으므로

- 초기화할 때 먼저 쭉 작업을 해서 dp 테이블에 넣어놓은 후 시작하였습니다.

2. 주의사항

- 주의사항은 아니고 풀고난 후에 생각난 건데 얻을 수 있는 최대의 사탕의 수를 구하는 것이므로

- 대각선 이동은 빼도 될 것 같습니다.

- 사탕을 뺏어간다는 조건이 있지 않은 이상 대각선이 가로->세로, 또는 세로->가로 로 이동하는 것 보다 많은 사탕을 얻을 수는 없기 때문에 사실 확인하지 않아도 될 것입니다.

3. 나의코드

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

int N, M;
int candymap[1001][10001];
int dp[1001][1001];

void inputs() {//기본셋팅
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> candymap[i][j];
			dp[i][j] = -1; //dp테이블은 -1로 초기화
		}
	}
	dp[1][1] = candymap[1][1];
	for (int i = 2; i <= N; i++) {
		dp[i][1] = dp[i - 1][1]+candymap[i][1];
	}
	for (int j = 2; j <= N; j++) {
		dp[1][j] = dp[1][j-1]+candymap[1][j];
	}
}
int maxthree(int num1, int num2, int num3) {
	int tmp = max(num1, num2);
	tmp = max(tmp, num3);
	return tmp;
}
int getdp(int x, int y) {
	if (dp[x][y] != -1) return dp[x][y];
	else {
		dp[x][y] = maxthree(getdp(x - 1, y), getdp(x, y - 1), getdp(x - 1, y - 1))+candymap[x][y];
		return dp[x][y];
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	cout << getdp(N,M) << "\n";
	return 0;
}

www.acmicpc.net/problem/11726

1. 풀이방법

- 이 문제를 접할 때 점화식을 생각해내는 게 생각보다 어려웠습니다.

- 물론 이런 류의 문제는 알고나면 매우 간단하기는 하지만......!

- 결국 점화식은 dp[n]=dp[n-1] + dp[n-2] 입니다 

- 그림을 보시면 이해가 쉬우실 듯 합니다.

2. 주의사항

- 값을 저장할 테이블을 구성해서 메모이제이션을 활용하여 시간을 단축시켜주었습니다.

- 탑다운 방식으로 재귀함수만을 이용하여 연산하는 경우 중복되는 연산을 너무나 많이 하기때문에

- TIME LIMIT을 만나실 수 있습니다.

- 저장되어있는값이 있으면 바로 리턴해서 가져다 쓰고 새로운 값이면 테이블에 저장을 한 후 리턴해서

- 다음부터는 그 값이 필요할 때 테이블에서 바로 가져다 쓸 수 있도록 하면 됩니다.

3. 나의코드

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

int  n;
int dp[1001];

int getdpvalue(int num) {
	if (dp[num] == 0) { 
		dp[num] = (getdpvalue(num - 1) % 10007 + getdpvalue(num - 2) % 10007);
		return dp[num] % 10007;
	}
	else return dp[num]%10007;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	dp[1] = 1; dp[2] = 2; dp[3] = 3; // 3을 초기화안해줘도 되긴하다
	                                 // (하지만 경우의수 그림 그려놨으니까..아까워서)
	cout<<getdpvalue(n)<<"\n";

	return 0;
}

www.acmicpc.net/problem/7570

1. 풀이방법

 - 몇가지 예시를 직접 종이에 써서 알아보고, 코드로도 짜보고 하면서 알아낸 것이

 - 순방향(? 증가하는) 쪽의 가장 긴 증가수열의 길이를 알아내는 것이 핵심 이었습니다.

 - 근데 한번의 작업으로 맨 앞 혹은 맨 뒤 양 끝으로만 보낼 수 있기 때문에 그냥 최장증가수열이 아닌 !

 - 1씩 증가하는 최장증가수열의 길이를 구해야 했습니다!!!!

 - 입력의 범위를 보니 이중반복문이 들어갈 경우 시간초과가 명백하여서 dp를 통해서 입력을 받으면서 구했습니다.

2. 주의사항 

 - 지금보면 단순해보이는 numarr[tmp]=numarr[tmp-1]+1 이 것을 생각해내는 게 꽤 어려웠습니다 ㅠㅠㅠ

 - dp에 익숙하지 않아서 일까요...꽤 오래걸렸습니다...

 - 보시는 분들 중에 이해가 안되는 분들은 임의의 길이 7 정도의 입력을 직접 그려보면서 써가면서 하시면 

 - 이해가 잘 되실 것 같습니다.

3. 나의코드

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

int N;
int numarr[1000001];
int maxlistcount;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int tmp;
	for (int i = 0; i < N; i++) {
		cin >> tmp; 
		numarr[tmp] = numarr[tmp - 1] + 1;
		maxlistcount = max(maxlistcount, numarr[tmp]);
	}
	cout << N - maxlistcount << "\n";
	return 0;
}

www.acmicpc.net/problem/12865

1. 풀이방법

 - 처음에 떠올린 방법은 브루트 포스로 모든 경우의 수 (조합) 을 모두 계산해 보는 것 

 - 이렇게 짜볼까 하다가 시간초과가 매우 발생할 것 같아서 방향을 바꿨습니다.

 - 그냥 메모리를 사용해서 버틸 수 있는 무게 별로 최대가치를 저장하는 테이블을 선언하자 라고 생각.

 - N개의 물건들을 하나씩 살펴 보면서 버틸 수 있는 무게 K 밑으로 살펴보며 이 물건을 넣어가며 테이블을 갱신

2. 주의사항

 - 아직 알고리즘 문제풀이가 많이 부족해서 기존의 떠오른 생각 방향에서 다른 쪽으로 생각하는게 부족...

 - 열심히 풀어야겠습니다...

3. 나의코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

int N, K;
int dp[100001]; // 버틸 수 있는 무게 별로 최대가치를 저장하는 테이블
int weightarr[101];
int valuearr[101];

void dypro() {
	for (int i = 1; i <= N; i++) {
		for (int j =K; j >= 0; j--) {
			if (weightarr[i]<= j) {
				dp[j] = max(dp[j], dp[j- weightarr[i]] + valuearr[i]);
			}
		}
	}
	cout << dp[K] << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> weightarr[i] >> valuearr[i];
	}
	dypro();
	return 0;
}

1. 다이나믹 프로그래밍 이란?

- Space(공간)을 더 사용하여 re-computing(중복되는 연산)을 방지하여 

  Speed(속도)를 증가시켜주는 방법입니다..

- solution 테이블을 사용하여 이미 연산된 적이 있다면 그 값은 바로 테이블에서 가져와서 쓰는 것입니다.

- 처음하는 연산의 경우 연산을 수행한 뒤 결과값을 solution table에 저장합니다.

- 일반적으로 최적해(Optimal Solution)을 구하는 데에 많이 사용된다.

2. Divide and Conquer(분할정복)과 차이점?

- 분할정복 역시 큰 문제를 작은 문제로 쪼개서 해결한다.

- 차이점은 DP에서는 부분(작은) 문제의 해가 중복되는 부분이 있어 나중에 또 필요하다는 것.

3.대표적인 예시

 (1) 피보나치 수열

     -피보나치 수열을 모든 연산을 반복적으로 수행하게끔 구현하면 n이 증가함에 따라

       총 연산의 수 가 급격히 높아진다.(중복되는 연산이 매우 많음)

-f(6)만 해도 이렇게 중복되는 연산이 많습니다.

- 빨간색은 연산없이 바로 테이블에서 끌어오는 녀석입니다.

(2) Matrix-Chain Multiplication 문제

- n개의 행렬이 주어졌을 떄 곱셈연산수를 가장 적게 하는 방법을 찾아라.

- (1~n)을 (1~k) * (k~n)으로 나누어야 하는데 어디를 나눌 것인가?

- 점화식과 관련이 깊다.

4. 해결절차

- (1) 최적해를 정의 한다.

- (2) 이를 바탕으로 점화식으로 표현한다

- (3) 바텀업방식이나 탑다운방식으로 이를 계산해 나간다.

5.구현방식

-(1) 바텀업 방식(Bottom-Up Approach)

     : 반복문 사용

       문제의 전체적인 구조를 파악하고 있어야 한다.

       재귀를 사용할 때의 오버헤드를 줄일 수 있다.

-(2) 탑다운 방식(Top-Down Approach)

     : 점화식의 구조를 직관적으로 파악하기 편하다.

       재귀함수 사용