본문 바로가기
반응형

DP6

[브론즈1]백준 2869번(달팽이는 올라가고 싶다) - 코테공부 37일차(2025.02.27) 문제유형수학풀이 방법 도출 과정1. 땅 위의 달팽이가 V미터인 나무 막대를 올라간다. 달팽이는 낮에 A미터 올라가는데 밤에는 B미터 떨어진다. 달팽이가 나무 막대를 모두 올라가려면, 몇일 걸리는지 구하는 문제2. 입력: A, B, V 3. 예제 분석1일차: (A - B)2일차: (A - B) + (A - B) 3일차: (A - B) + (A - B) + (A - B) 일반화 하면 (A - B) x (n - 1) + A 4. 이식을 변형하면  (A - B) x (n - 1) + A >= V이것을 n에 관하여 정리하면 다음과 같아진다. n >= V-A/A-B + 1 그런데 이가 마지막 날에는 미끌어지지 않기 때문에 +1를 삭제한다.시간 복잡도시간 복잡도는  O(1)이다. 코드 및 간단설명수학을 사용하였다. .. 2025. 2. 27.
[골드5]백준 12865번(평범한 배낭) - 코테공부 36일차(2025.02.26) 문제유형다이나믹 프로그래밍(동적 계획법)풀이 방법 도출 과정1. 물건 N개의 물건이 있다. 각 물건은 무개W와 가치 V를 가지는데 최대 K만큼의 무개만큼 넣는다고 가정했을 때, 가치V가 가장 높을 때의 값을 구하는 문제이다.2. 첫 줄에 입력은 N, K 나머지는 W, V이다. 3. 가장 먼저 일단 가장 W가 채워질 가능성을 찾고 그 뒤로 그 가능성 중에 가장 나은 것을 고르는 방법이 있다. 이 방법은 최악의 경우 100C50이 나오는데 이는 1억을 넘는 것이기에 사용하지 않겠다. 4. 두번째로 그리디 알고리즘을 사용하는 방법이 있는데 이를 위해 가치 대비 무개 비율이 높은 순서대로 정렬한 다음 가능한 한 많은 물건을 선택한다고 해서 정확한 최적해를 보장하기에는 적절하지 않다. 5. 그러므로 동적 계획법을.. 2025. 2. 26.
[골드5]백준 9251번(LCS) - 코테공부 31일차(2025.02.23) 문제유형동적 계획법풀이 방법 도출 과정1. 두 개의 부분 수열이 주어졌을 때, 두 수열 모두에 공통으로 등장하는 부분 수열의 개수를 구하는 문제이다.2. 각 수열의 가능한 부분 수열의 수는 길이가 n일때 약 2에 n 개이다.  에를 들어 길이가 1000인 수열은 2에 1000개의 부분 수열을 갖게 되므로, 모든 경우를 생성해 비교하는 방식은 계산량이 기하급수적으로 증가해 실제로는 불가능하다.3. 그렇다면 그리디 알고리즘으로 접근해보도록 하면 한 수열을 순회하며 특정 패턴(예: 'A', 그 다음 'AC' 등)을 차례로 찾아 나가는 그리디 방식은 일부 경우에는 효과적일 수 있으나. 항상 최적의 해답을 도출하지 못할 뿐 아니라, 최악의 경우 불필요한 중복 연산이 많아져 시간 복잡도가 크게 증가할 수 있다.4... 2025. 2. 23.
[실버2]백준 11053번(가장 긴 증가하는 부분 수열) - 코테공부 30일차(2025.02.21) 문제유형동적 계획법풀이 방법 도출 과정1. 주어진 수열 A에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다.2. 모든 부분 수열을 생성한 뒤, 각 부분 수열이 증가하는지 확인하여 최대 길이를 찾는 방식도 생각할 수 있다. 그러나 수열의 길이가 최대 1000인 경우 가능한 부분 수열의 수가 기하급수적으로 증가하여(실제로는 2^N에 가까운 복잡도를 가진다.) 실행 시간이 매우 비련실적이게 된다. 3. 단순 그리디 알고리즘을 사용한다고 하더라도 매 순간 가장 좋아보이는 선택을 하더라도 전체 최적해를 보장할 수 없으므로 이 문제에는 적합하지 않다. 4. 위 두가장 방법의 한계를 고려할 때, 작은 부분 문제로 나누어 그 결과를 재활용하는 동적 계획법이 적합한 해결이다.이를 위해 먼저 문제를 재귀적인 관점.. 2025. 2. 21.
[실버1]백준 1149번(RGB거리) - 코테공부 29일차(2025.02.20) 문제유형수학풀이 방법 도출 과정1. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하는 것이 문제 - i-1과 i+1 과 i는 각각 색이 같으면 안됨3. 각 비용이 낮은 것을 찾으면 됨 단, 이동하면서 칠하기 때문에 잘생각해야함4. 만약 이렇게 있을 경우5.26 40 8349 60 5713 89 99  1) 26 2) 57 3) 13이렇게 해서 96이렇게 구해나가면 된다.6. 이 문제는 현재 집을 칠하는 비용을 이전 집들의 최소 비용과 연계하여 계산해야 하므로, 재귀 함수를 활용한 해결이 가능하다. 즉, 집 i를 칠하는 비용은 i-1번째 집까지의 최소 비용을 고려한 결과로 나타낼 수 있다. 이를 통해, 각 집을 칠하는 최소 비용.. 2025. 2. 20.
[실버2]백준 11048번(이동하기) - 코테공부 28일차(2025.02.19) 문제유형그리디 알고리즘풀이 방법 도출 과정1. 준규의 이동 경로는 오른쪽, 아래, 대각선 오른쪽 아래로 제한되어 있으므로, 각 위치에서 도달할 수 있는 최대 사탕 개수를 저장하는 DP 테이블을 구상할 수 있다. 2. 구체적으로 각 위치 (r, c)의 값은 이전에 도달할 수 있는 세 위치 (r + 1, c), (r, c + 1), (r + 1, c +1) 중 최대값에 현재 위치의 사탕 수를 더한 값으로 갱신된다.3. DP 테이블을 구성할 때, 아직 방문하지 않은 위치의 값은 0으로 초기화한다. "단, 가장 먼저 숫자가 0인 숫자는 최소화해야한다."라는 표현은 초기 상태나 경로 선택 시 0의 영향을 최소화해야 한다는 의미로 해석할 수 있으며, 이 경우 DP 테이블 초기화 및 경계 처리에 주의한다.4. 모든 .. 2025. 2. 19.
반응형

티스토리툴바