Approach 기본적인 접근 방법은 https://viyoung.tistory.com/315과 동일하다. [백준 1725번] [스택] 히스토그램 Approach 기본적인 접근 방법은 다음 블로그를 참고하면 된다. https://cocoon1787.tistory.com/315 [C/C++] 백준 1725번 - 히스토그램 (스택 풀이) 문제 히스토그램에 대해서 알고 있는가? 히스토그램은 아래와.. viyoung.tistory.com 다만, 이 문제에서 결과값이 20억 이하라는 보장이 없으므로 출력을 long long 자료형을 사용해야한다는 점에서 차이가 있다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)..

Approach 기본적인 접근 방법은 다음 블로그를 참고하면 된다. https://cocoon1787.tistory.com/315 [C/C++] 백준 1725번 - 히스토그램 (스택 풀이) 문제 히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다. cocoon1787.tistory.com 이 접근방법을 잘 곱씹어보면, 스택이 점점 쌓여감에 따라서 들어있는 숫자들을 index로 가지는 히스토그램 막대의 높이는 계속 증가하거나 같을 수 밖에 없다. 따라서 pop 연산을 계속 수행하게 되면, 나오는 숫자들은 계속 감소하거나 같을 수 밖에 없다. 위 블로그에 나온 예시에..

Approach 완전 탐색으로 이 문제를 처리한다고 하면 비둘기집의 원리에 따라서 중복되는 연산이 매우 많다는 사실을 쉽게 캐치할 수 있다. dp[i] = i번째 수부터 시작하는 LIS 중 합이 가장 큰 값 dp[i] = max(v[i], max{dp[i + j] + v[i]}) for all j s.t v[i] < v[j] Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; vector v; int n; int dp[1001]; int memoi(int k){ int& ret = dp[k]; if(ret != -1) return ret; int cmp = v[k]; fo..

Approach 이 문제를 완전탐색으로 접근해보면, 앞에서부터 모든 문자열에 대해서 되는지를 체크해주면 된다. 다만, 비둘기집의 원리에 의해서 중복되는 계산이 매우 많다는 사실을 캐치할 수 있다. 이 지점에서 Memoization을 활용한 DP를 활용해서 중복되는 계산을 줄일 수 있음을 생각할 수 있다. dp[i] : s의 i 번쨰 index까지는 매핑되었고, 그 이후의 문자열을 매칭지을 수 있는지 여부 (가능하면 1, 아니면 0) dp[i] = max(dp[i + v[j].size()]) for all j s.t s.substr(i, i + v[j].size()) == v[j] (v[j] 는 j번째 문자열) Code #include #define fastio ios_base::sync_with_stdi..

Approach 완전 탐색 기법으로 해당 문제를 푸는 식으로 문제를 접근해보면, 길이가 N - 1인 계단수의 정보를 활용해서 길이가 N인 계단수를 구할 수 있다는 점을 쉽게 파악할 수 있다. 다만, 마지막 수가 1 ~ 8인지 0이나 9인지 여부에 따라서 경향성이 달라지므로 끝나는 숫자에 대한 정보가 필요한데 이를 dp에 저장해두면 쉽게 풀 수 있다. Let dp[i][j] : 마지막 수가 j이면서 길이가 i인 계단 수 (dp[1][0] = 0, dp[1][1 ~9] = 1 : Initial value) dp[i][j] : dp[i - 1][j - 1] + dp[i - 1][j + 1] for j $\in$ {2, 3, 4, 5, 6, 7, 8, 9} dp[i]j] : dp[i - 1][j + 1] for..

Approach 전형적인 냅색 문제에서 표현만 달라진 형태이지, 완벽히 접근방법이 동일하다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int dp[100][10001]; int n, k; vector coin; int memoi(int x, int k){ if(x == n) return (k == 0 ? 0 : 987654321); if(k < 0) return 987654321; int& ret = dp[x][k]; if(ret != -1) return ret; int value = coin[x]; return ret = min(memoi(x + 1, k), ..

Approach path(y, x) : (y, x)ㄱ에서 시작해서 맨 아래줄까지 재려가는 부분 경로의 최대합 이렇게 정의했을 경우, path(y, x)는 y ~ n - 1까지의 아직 해결하지 못한 조각들에 대한 값을 정의하는 부분이므로 이전 입력값에 영향을 받지 않는다. 즉, (y, x)까지 어떤 경로로 도착했건 남은 부분 문제는 항상 최적으로 풀어도 상관이 없다. 이러한 성질을 최적 부분 구조(Optimal substructure)이라고 한다. 이러한 성질 때문에 지금까지의 선택과 관계 없이 각 부분 문제를 최적으로 풀기만 하면 전체 문제의 최적해도 알 수 있게 되는 것이다. 따라서 탑-다운 방식으로 이 문제를 해결할 수 있게 된다. Code #include #define fastio ios_base:..

Approach *에 몇 글자가 대응하는지 여부가 가장 중요하다. 이 문제를 완전탐색을 통해서 해결할 수 있다. 완전탐색을 통해 해결할 수 있으나, 문자열의 길이가 100자리 이하라는 것을 감안할 때 비둘기집 원리를 이용하면 총 101 * 101 가지 이하만 계산해주면 된다는 것을 이해할 수 있다. (즉, 중복되는 계산이 무조건적으로 생기므로 메모이제이션을 활용하면 중복되는 계산을 줄일 수 있다.) Code 1. $0(N^3)$로 푸는 풀이 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; string W; string T; int dp[101][101]; int memoizat..