본문 바로가기

알고리즘/Problem Solving

[BOJ] DP 11053 가장 긴 증가하는 부분수열 C++ 11053번 가장 긴 증가하는 부분 수열 📝문제링크 : www.acmicpc.net/problem/11053 지금까지 풀었던 DP 중 제일 어려웠다. 정답코드를 보고도 접근 방법이 잘 연상되지 않았다. solved.ac 등급이 silver2 던데, silver1 문제보다 어려운 거 같은데...🤔 가장 긴 증가하는 부분 수열은 LIS 라고도 불리는데, 유명한 개념이니까 확실히 알고 넘어가는게 좋을 것 같다. 접근 과정 1. DP니까 당연하게도(?) memoization으로 접근해봐야지. $dp[i]$ : arr[i]이 배열의 마지막 원소일 때, 가능한 가장 긴 증가하는 부분 수열의 길이가 저장된다. dp[i] 에 저장될 값은, arr[i - 1] 까지의 가장 긴 증가하는 부분 수열에 arr[i] 값을 붙일.. 알고리즘/Problem Solving 2020. 12. 28.
[BOJ] DP 2156 포도주 시식 C++ 2156번 포도주 시식 📝문제링크 : www.acmicpc.net/problem/2156 $dp[i]$ 에는 i 번째 포도주가 마지막일 때, 마실 수 있는 최대 포도주의 양이 저장된다. 3개의 포도주를 연속으로 선택할 수 없다는 제약조건이 있으므로, 아래 그림과 같이 3개의 경우의 수를 생각해 볼 수 있다. ① x, y를 고르고 z는 선택하지 않는 경우 ② x, z를 고르고 y는 선택하지 않는 경우 ③ y, z를 고르고 x는 선택하지 않는 경우 이 세가지 경우의 수 중 max 값이 dp[i] 가 된다. 앞에서 풀었던 문제(9465 스티커)는 arr[i] 값을 선택한다는 걸 가정하고 경우의 수를 찾았는데, 이 문제는 arr[i]를 선택하지 않는 경우까지 고려해야한다는 점을 간과하기 쉬워 배울점이 있는 문제.. 알고리즘/Problem Solving 2020. 12. 27.
[BOJ] DP 9465번 스티커 C++ 9465번 스티커 📝문제링크 : www.acmicpc.net/problem/9465 2차원 배열이 주어져 처음 보는 새로운 유형이라고 생각했는데, 결국 다른 DP 문제와 크게 다르진 않았다. 문제는 내가 혼자 풀이방법을 떠올리지 못한다는 것 ㅠㅠ 처음접근 인접한 스티커를 선택할 수 없으므로, n = 1 일 때 부터 대각선 방향만 고려하며 쌓아나아가 봤다. 그러나 한 칸을 건너 뛰고 다음 칸에서 스티커를 선택하는게 더 유리한 케이스도 있어, 1부터 쌓아나가는 방법으로는 답을 찾을 수 없었다. 정답보고접근 2차원 배열 dp 를 선언한다. $dp[i][j]$ 엔 $i$행 $j$열의 스티커를 선택했을 때 얻을 수 있는 최대값이 저장된다. $[j - 2]$ 인덱스와 $[j - 1]$ 인덱스 값을 비교해 더 큰 값.. 알고리즘/Problem Solving 2020. 12. 24.
[BOJ] DP 11057번 오르막 수 C++ 11057번 오르막 수 📝문제링크 : www.acmicpc.net/problem/11057 이전에 풀었던 쉬운 계단수 문제와 아주 유사하다. 오르막수가 0으로 끝나려면 0의 앞자리엔 0만 올 수 있다. 오르막수가 1로 끝나려면 1의 앞자리엔 0과 1이 올 수 있다. 오르막수가 2로 끝나려면 1의 앞자리엔 0과 1과 2가 올 수 있다. . . . 오르막수의 끝자리가 L 인 경우 L의 앞자리엔 0부터 L까지의 수가 올 수 있다. i 는 2부터 N까지, j는 0부터 9까지, k는 0부터 j까지 3중 for문을 돌면 풀 수 있다. 소스코드 #include using namespace std; int main() { intN; cin >> N; // dp[N][L] : N자리 오르막수에 대해, 끝자리가 L인 수의.. 알고리즘/Problem Solving 2020. 12. 4.
[BOJ] DP 10844번 쉬운 계단 수 C++ 10844번 쉬운 계단 수 📝문제링크 : www.acmicpc.net/problem/10844 케이스들을 조금 나열해보면, 다음을 알 수 있다. 계단수가 0으로 끝나려면 0의 앞자리엔 1밖에 올 수 없다. 계단수가 9로 끝나려면 9의 앞자리엔 8밖에 올 수 없다. 계단수의 끝자리가 L = 1 ~ 8인 경우 L - 1 과 L + 1 이 모두 올 수 있다. 따라서 점화식은 다음과 같다. 그리고 N 자리수 계단수는, N자리 일때 끝자리 수가 0 ~ 9 인 수의 개수(dp[N][0] ~ dp[N][9]) 의 총합이다. 소스코드 #include using namespace std; int main() { intN; cin >> N; // dp[N][L] : N자리 계단수에 대해, 끝자리가 L인 수의 개수 int .. 알고리즘/Problem Solving 2020. 12. 3.
[BOJ] DP 9095번 1, 2, 3 더하기 C++ 9095번 1, 2, 3 더하기 📝문제링크 : www.acmicpc.net/problem/9095 #include #include using namespace std; voidfind_ans(int n, vector &dp) { for (int i = 4; i > T; vector dp; for (int i = 0; i > n; dp.assign(n + 1, 0); dp[1] = 1; dp[2] = 2; dp[3] = 4; find_ans(n, dp); cout 알고리즘/Problem Solving 2020. 11. 24.
[BOJ] DP 11726번 & 11727번 2xn 타일링 C++ 11726번 2xn 타일링 📝문제링크 : www.acmicpc.net/problem/11726 점화식 : $ dp[n] = dp[n - 1] + dp[n - 2] $ 소스코드 #include #include using namespace std; voidfind_ans(int n, vector &dp) { dp[n] = (dp[n - 1] + dp[n - 2]) % 10007; } int main() { intn; cin>> n; vector dp(n + 1); dp[0] = 1; dp[1] = 1; for(int i = 2; i 알고리즘/Problem Solving 2020. 11. 23.
[BOJ] DP 1463번 1로만들기 C++ 처음 접해본 DP 문제. 다이나믹 프로그래밍이란? 점화식을 잘 세워서 한번 한 계산은 다시하지 않도록 효율적인 계산을 하게 만드는 프로그래밍 1463번 1로 만들기 📝문제링크 : www.acmicpc.net/problem/1463 이 문제는 주어진 숫자 n에서부터 top down 방식으로 내려오면 경우의 수가 너무 많아 시간이 오래 걸린다. 1부터 시작해 bottom up 으로 올라가며 해당 숫자에 도달하는 최소의 경우를 계산해야 한다. 원리는, 1에서 2로 가는 최소 경로, 1에서 3으로 가는 최소 경로, 4로 가는 최소 경로 ... 이렇게 작은 문제푸터 풀어가는것이다. 4로 가는 최소 경로도 결국 2로 가는 최소 경로를 포함한다는 것을 이해하면 코드도 쉽게 이해할 수 있다. #include #incl.. 알고리즘/Problem Solving 2020. 11. 1.

티스토리툴바