본문 바로가기

알고리즘

알고리즘/BOJ 2020. 3. 25. [C++] 백준 9461번 - 파도반 수열 0. 문제 1. 아이디어 1) 순서대로 그림을 따라서 그려보니까, P(5) 이후의 삼각형들은 모두 시계방향으로 도는 규칙을 가지고 있다. 따라서 점화식을 세웠을 때 P(N) = P(N -1) + P(N - 5) 라는 사실을 발견! 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include int main() { int T; long long dp[101]; std::cin >> T; dp[1] = 1; dp[2] = 1; dp[3] = 1; dp[4] = 2; dp[5] = 2; for (int r = 0; r > N; for (int i = 6; i
알고리즘/BOJ 2020. 3. 23. [C++] 백준 1699번 - 제곱수의 합 0. 문제 1. 아이디어 1) 야호!!! 2) 해당 문제에서 내가 사용할 dp[i]의 컨셉은 i의 구성하는 최소항들의 개수이다! 그렇다면 그 이후의 수들은 이전 dp값들을 잘 이용한다면 쉽게 최소 제곱수들의 합으로 나타낼 수 있다. ex) dp[80] = dp[64] + dp[16], dp[96] = dp[80] + dp[16] 3) (핵심) 예를 들어 32의 경우와 같이 해당 숫자 이하의 가장 큰 제곱수가 반드시 포함되어야만 하는 건 아니다. ex) 32 = 16 + 16 (O), 25 + 4 + 2 + 1 (X) 그래서 가장 가까이에 있는 제곱수부터 1까지의 케이스를 확인하며 최솟값을 찾으면 된다! 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2..
알고리즘/BOJ 2020. 3. 23. [C++] 백준 2579번 - 계단 오르기 0. 문제 1. 아이디어 1) 하.. 2) 우선 마지막 계단을 반드시 밟을 수 있게 점화식을 세웠을 때 밟는다 밟지 않는다 밟는다 밟는다 ???? 밟는다 밟지 않는다 밟는다 위와 같은 두가지 경우가 성립한다! 일단 지금 세운 점화식을 이용해서 dp의 값들을 구하기 위해선 최소 3개의 값들이 필요하며 dp[0], dp[1], d[2]는 손쉽게 구할 수 있다. (따라서 반복문은 i = 3부터) 3) max 함수를 통해 위에서 세운 두가지 경우 중 더 큰 값을 가지는 경우를 선택하면 된다! 4) 각 점화식에 필요한 부분 이전은, 어떤 계단들을 밟던지 아무 상관이 없다. 따라서 그냥 최댓값을 저장해둔 dp값을 이용하기만 하면 된다!! 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..
알고리즘/BOJ 2020. 3. 23. [C++] 백준 1912번 - 연속합 0. 문제 1. 아이디어 1) dp[i]에는 i번째 원소가 가지는 최대 연속합이다!!! 2) 연속합이 음수가 되지 않는 선에서는 계속해서 더해도 상관이 없다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include #include int arr[100000]; int dp[100000]; int main() { int N; std::cin >> N; for (int i = 0; i > arr[i]; int result = dp[0] = arr[0]; for (int i = 1; i
알고리즘/BOJ 2020. 3. 22. [C++] 백준 11054번 - 가장 긴 바이토닉 부분 수열 0. 문제 1. 아이디어 1) i번째 원소를 기준으로, (왼쪽) arr[0] ~ arr[i]는 증가수열, (오른쪽) arr[i] ~ arr[N-1]은 감소수열 2) 따라서 각각의 원소가 가질 수 있는 증가수열과 감소수열의 길이를 합했을 때 가장 큰 길이를 구한다! 3) 이때, 주의할 건 감소수열의 길이를 구할 때 반!드!시! i번째 원소를 포함하는 길이여야 한다는 것! 4) 그래서 나는 역으로, arr[N-1] ~ arr[i]까지의 증가수열의 길이를 구하기로 했다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include #include int ..
알고리즘/BOJ 2020. 3. 22. [C++] 백준 11722번 - 가장 긴 감소하는 부분 수열 0. 문제 1. 아이디어 1) 앞의 문제들과 동일한 아이디어! 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include int main() { int N, length=0,arr[1000], dp[1000]; std::cin >> N; for (int i = 0; i > arr[i]; for (int i = 0; i
알고리즘/BOJ 2020. 3. 22. [C++] 백준 11055번 - 가장 큰 증가 부분 수열 0. 문제 1. 아이디어 1) n번째 원소의 dp값 = n-1번까지의 원소들 중 자신보다 작은 값 중에 가장 큰 dp의 값 + 자신의 값 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include int main() { int N, result = 0, arr[1000], dp[1000]; std::cin >> N; for (int i = 0; i > arr[i]; // arr에 수열의 값들 입력 for (int i = 0; i
알고리즘/BOJ 2020. 3. 15. [C++] 백준 11053번 - 가장 긴 증가하는 부분 수열 0. 문제 1. 아이디어 1) bottom-up 방식으로 문제를 풀이한다. 2) N번째 열까지 구할 수 있는 증가하는 가장 긴 부분 수열의 길이는 0번부터 N-1 번열 중 자신보다 작은 원소가 구했던 가장 긴 부분 수열의 길이 +1(본인의 길이)이 된다. 이때, N-1번 열까지 구했던 길이는 dp에 메모이제이션한다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include #include int main() { int N, max = 0, value[1000], dp[1000]; std::cin >> N; for (int i = 0; i > value[i]; for (int i = 0; i min) min = dp[j]; dp[i..

티스토리툴바