Approach 연결 요소(Component)의 개수를 묻는 문제이다. 배추가 심어져 있는 곳에 대해서 방문하지 않았다면 DFS / BFS를 돌리고 component의 개수를 1 증가시켜 주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; int dx[4] = {0, 0, 1, -1}; int dy[4] = {-1, 1, 0, 0}; int m, n; int edge[51][51]; int visited[51][51]; vector node; void dfs(int x_val, int y_val){ visited[x_val][y..

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 https://viyoung.tistory.com/307 문제와 근본적으로 비슷한 측면이 많다. [백준 8394번] [동적 계획법] 약수 Approach 잘 생각해보면, 해당 사람이 악수를 할 수 있는지 여부는 앞의 사람이 악수를 했는지 여부와 관련이 있다 dp[i][0] : i번째 사람까지 참석했다고 했을 때의 경우의 수 중 i번째 사람이 앞 사 viyoung.tistory.com 1이 나올 수 있는지 여부는, 이전의 숫자가 1인지 아닌지 여부와 관련이 있다. (고등학교때 배운 수형도와 비슷한 측면으로 이해해주면 충분하다) dp[i][0] : i번째 자리까지 고려했을 때 나올 수 있는 총 경우의 수 중, i번째 자리가 1이 아닌 경우 dp[i][0] : i번째 자리까지 고려했을 때 나올..