반응형 [PCCP] 알고리즘 - 동적계획법 1. 이론- Dynamic Programming은 전체 문제를 한 번에 해결하는 것이 아닌 작은 부분 문제들을 해결하여 이를 활용하여 전체 문제를 해결하는 것- DP 활용 조건 - Optimal Substructure(최적부분구조): 큰 문제를 작은 문제로 나누었을 떄 동일한 작은 문제 반복 등장 - Overlapping Subproblem(중복부분문제): 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성- 해결과정 1) 점화식 세우기 2) 메모이제이션 저장소 생성 3) 재귀함수 정의 && 종료조건- 최장증가부분수열(Long Increasing Subsequence) - 부분수열: 주어진 수열 중 전후 관계를 유지하며 일부를 뽑아 새로 만든 수열 - LIS: 부분.. 2024. 12. 15. [C++로 배우는 알고리즘과 자료구조] Day 28: 동적 계획법 (DP) 기초 동적 계획법 (Dynamic Programming, DP)동적 계획법(DP)은 복잡한 문제를 해결하기 위해 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 전체 문제의 해를 구하는 알고리즘 설계 기법입니다. DP는 주로 재귀적 구조를 가지며, 중복되는 부분 문제를 해결하여 효율성을 높입니다.DP의 주요 특징:중복된 부분 문제 (Overlapping Subproblems): 문제를 해결하는 과정에서 동일한 부분 문제가 여러 번 재계산됩니다.최적 부분 구조 (Optimal Substructure): 문제의 최적 해는 부분 문제의 최적 해로 구성될 수 있습니다.DP의 접근 방식:탑다운 (Top-Down): 재귀 + 메모이제이션바텀업 (Bottom-Up): 반복문 + 테이블피보나치 수열 (Fibonacc.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 21: 문자열 동적 계획법 (Edit Distance, Longest Common Subsequence) 문자열 동적 계획법문자열 관련 문제는 많은 응용 분야에서 중요합니다. 오늘은 두 가지 주요 문제인 편집 거리(Edit Distance)와 최장 공통 부분 수열(Longest Common Subsequence, LCS)에 대해 학습하겠습니다.편집 거리 (Edit Distance)편집 거리(Edit Distance)는 두 문자열을 같게 만들기 위해 필요한 최소 편집 연산 횟수를 의미합니다. 가능한 편집 연산은 삽입, 삭제, 교체입니다.문제 정의두 문자열 ( s1 )과 ( s2 )가 주어졌을 때, ( s1 )을 ( s2 )로 변환하는 데 필요한 최소 편집 연산 횟수를 계산합니다.편집 거리 구현다음은 C++로 편집 거리 문제를 해결하는 예제입니다.#include #include #include #include .. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 18: 트리 동적 계획법 (Tree DP) 트리 동적 계획법 (Tree DP)트리 동적 계획법(Tree DP)은 트리 구조를 가진 문제를 해결하기 위한 효율적인 방법입니다. 이는 주로 트리의 정점이나 간선을 따라 상태를 정의하고, 하위 트리에서의 정보를 이용하여 전체 문제를 해결하는 기법입니다.문제 예시: 트리의 최대 독립 집합 (Maximum Independent Set of a Tree)주어진 트리에서 서로 인접하지 않은 정점의 최대 집합을 찾는 문제입니다. 이는 트리 DP를 사용하여 효율적으로 해결할 수 있습니다.문제 정의주어진 트리의 정점 수 (n)트리의 간선 정보최대 독립 집합의 크기 계산트리 DP 구현다음은 C++로 트리의 최대 독립 집합 문제를 해결하는 예제입니다.#include #include #include const int MA.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 19: 스테이트 컴프레션 동적 계획법 (State Compression DP) 스테이트 컴프레션 동적 계획법 (State Compression DP)스테이트 컴프레션 동적 계획법(State Compression DP)은 상태를 비트마스크로 표현하여 동적 계획법을 적용하는 기법입니다. 이는 주로 부분 집합 문제나 조합 최적화 문제에 사용됩니다. 이 기법은 상태를 효율적으로 관리하고, 메모리 사용량을 줄일 수 있습니다.문제 예시: 여행 계획주어진 도시들을 방문하면서 최소 비용으로 여행 계획을 세우는 문제를 해결하기 위해 스테이트 컴프레션 DP를 사용할 수 있습니다. 여기서 dp[mask][i]는 방문한 도시 집합이 mask이고 현재 i 도시에 위치한 경우의 최소 비용을 의미합니다.스테이트 컴프레션 DP 구현다음은 C++로 스테이트 컴프레션 DP를 사용하여 문제를 해결하는 예제입니다.#.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 17: 비트마스크 동적 계획법 (Bitmask DP) 비트마스크 동적 계획법 (Bitmask DP)비트마스크 동적 계획법은 상태를 이진수로 표현하여 여러 상태를 효율적으로 관리하는 기법입니다. 주로 부분 집합 문제나 조합 최적화 문제에 사용됩니다. 상태를 이진수로 표현하면 각 비트가 특정 원소의 포함 여부를 나타내어 간결하게 표현할 수 있습니다.문제 예시: 외판원 문제 (Traveling Salesman Problem, TSP)외판원 문제는 주어진 도시들을 방문하여 모든 도시를 한 번씩 방문하고 시작점으로 돌아올 때, 이동 비용의 합이 최소가 되도록 하는 경로를 찾는 문제입니다. 비트마스크 DP를 사용하여 해결할 수 있습니다.문제 정의주어진 도시 수 (n)각 도시 간의 거리 (dist[i][j])최소 이동 비용을 계산하여 출력비트마스크 DP 구현다음은 C+.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 15: 다차원 동적 계획법 (Multidimensional DP) 다차원 동적 계획법 (Multidimensional DP)다차원 동적 계획법은 상태를 여러 차원으로 정의하여 문제를 해결하는 기법입니다. 이 방법은 주로 상태를 더 구체적으로 나누어 관리할 때 사용됩니다. 예를 들어, 3차원 DP는 dp[i][j][k]와 같이 상태를 표현할 수 있습니다.문제 예시: 3차원 DP를 이용한 여행 계획주어진 도시들을 방문하면서 최소 비용으로 여행 계획을 세우는 문제를 해결하기 위해 3차원 DP를 사용할 수 있습니다. 여기서 dp[i][j][k]는 i번째 도시를 j번째 날에 k번 방문했을 때의 최소 비용을 의미합니다. 다차원 DP 구현다음은 C++로 3차원 DP를 사용하여 문제를 해결하는 예제입니다. 문제 정의주어진 도시들의 방문 비용이 포함된 cost 행렬이 있습니다. 여행자.. 2024. 8. 1. [알고리즘] 5. 동적 계획법 Index 1. 다이나믹 프로그래밍 2. 추천문제 3. 참고자료1. 다이나믹 프로그래밍Dynamic Programming- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않음- 점화식 : 인접한 항들 사이의 관계식- Memoization: 한 번 계산한 결과를 메모리 공간에 메모하는 기법(=Caching), - Top-down(메모이제이션) 방식과 Bottom-up 방식이 존재- Bottom-up 방식을 사용시 결과 저장용 리스트는 DP 테이블 이용- 분할 정복은 부분 문제의 중복이 없음 (조건)1) Optimal Substructure(최적 부분 구조)- 큰 문제를 작은 문제로 나눌 수 있으며 작은.. 2024. 7. 19. 이전 1 다음 반응형
