dp

👩🏻‍💻 문제링크 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net ✍️ 아이디어 1. 문제 이해 저점에서 올라갔다가 최고점 찍고 내려오는 최대 긴 수열의 항의 갯수를 구하는것임 (∧ 이런 크기로 수열이 정렬되어야함) 2. 나는 2차원 배열을 이용하여 배열의 한 요소가 내려가는 중인 경우와 올라가는 중인 경우를 나눠서 1) 올라가는 중인 경우 : 자신 보다 작은 수랑만 비교 할수 있음 2) 내려가는 중인 경우 : 자신보다 작고 큰수 둘다 비교 할수 있음 ✍️소스코드..

👩🏻‍💻 문제링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net ✍️ 아이디어 1. 문제 이해 포도주 n개가 일렬로 정렬되어 있고 각 잔에 들어있는 포도주의 양을 입력받을때 포도주를 가장 많이 먹을때 얼마나 먹는가 조건 : 인접한 포도주 3잔을 연속으로 들이키면 안됨 2. 나는 조건을 2개로 생각해 3차원 배열을 만듬 (2번째는 바로 전 포도주를 마신여부, 3번째는 전전 포도주를 마신 여부) 3. 생각보다 케이스가 복잡함 첫 잔을 안마시는 경우..

👩🏻‍💻 문제링크 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ✍️ 아이디어 1. 문제 이해 0~N까지 정수 K개를 더해서 그 합이 N이 나오는 경우의 수를 구하자 2. 점화식 D[N][K] = 0~N까지 정수 K개를 더해서 그 합이 N이 나오는 경우의 수 3. ex) 6까지 정수 4개를 더해서 합이 6 = 6까지 정수 3개를 더해서 + 5까지 정수 3개를 더해서 + 4까지 정수 3개를 더해서 .....+ 0까지 정수 3개를 더해서 (이 아이디어는 내가 직접 떠올림 !) 4. 처음에 n=0, k=0~200 의 값이 1이라는 점을 간과함 ✍️소스코드 내 코드 #incl..

👩🏻‍💻 문제링크 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ✍️ 아이디어 (처음에 아이디어 자체가 생각 안나서 강의 봄) 1. 문제 이해 부분 수열중에서 증가하고 가장 긴것을 찾는 문제 2. 이 문제의 특이한 점은 지금 까지 문제는 맨 마지막에 D[N]이 문제의 답이 되었다면 이 문제는 마지막 D[N]이 답이 아니라 점화식에서 가장 max 값이 답이라는 것이다..

👩🏻‍💻 문제링크 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ✍️ 아이디어 1. 문제 이해 문제를 해석하던 도중 단순화 해보니까 n을 1과 2의 합으로 나타낼수 있는 경우의 수였다 그리고 n을 1부터 6까지 나열하여 이게 피보나치 수열과 같은 형태라는것을 알게되었다 -> 하지만 이것이 왜 피보나치 수열과 같은 형태가 나오는지는 이해하지 못했다 2. 점화식 : 직접 써보면 나옴 = 피보나치 수열 ✍️소스코드 (A + B) % M = (A%M + B%M) % M ..

큰 문제를 작은 문제로 나눠서 푸는 알고리즘 더보기 이름에 의미부여 하지 말자.... 다이나믹 = 아무 의미 없음 목차 다이나믹 프로그래밍을 이용해 풀 수 있는 문제의 특징 다이나믹 프로그래밍 구현 방법 다이나믹 프로그래밍 문제 풀이법 다이나믹 프로그래밍 문제 유형 ▶ 다이나믹 프로그래밍을 이용해 풀 수 있는 문제의 특징 1. 중복되는 부분 문제 → 동일한 작은 문제를 반복적으로 해결해야함 ex) 피보나치 수 F0 = 0 F1 = 1 Fn(큰문제) = Fn-1(작은문제) + Fn-2(작은문제) // 점화식을 반복적으로 해결해야 함 2. 최적 부분 구조 → 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다 ex) 피보나치 수 F0 = 0 F1 = 1 Fn(큰문제) ..