동적 프로그래밍 복잡한 문제를 더 간단한 하위 문제로 분해하여 해결하기 위해 수학과 컴퓨터 과학에서 사용되는 방법입니다. 각 하위 문제를 한 번만 해결하고 결과를 저장함으로써 중복 계산을 방지하여 광범위한 문제에 대한 보다 효율적인 솔루션을 제공합니다. 이 기사에서는 예제를 통해 동적 프로그래밍 개념을 자세히 살펴봅니다.

int를 문자열로 변환 C++

동적 프로그래밍

내용의 테이블

• 동적 프로그래밍이란 무엇입니까?
• 동적 프로그래밍은 어떻게 작동하나요?
• 동적 프로그래밍의 예
• 동적 프로그래밍을 언제 사용해야 합니까?
• 동적 프로그래밍의 접근 방식
• 동적 프로그래밍 알고리즘
• 동적 프로그래밍의 장점
• 동적 프로그래밍의 응용
• 동적 프로그래밍의 기초 배우기
• 동적 프로그래밍의 고급 개념
• 동적 프로그래밍 문제

DP(동적 프로그래밍)란 무엇입니까?

동적 프로그래밍(DP) 복잡한 문제를 더 간단한 하위 문제로 분해하여 해결하기 위해 수학과 컴퓨터 과학에서 사용되는 방법입니다. 각 하위 문제를 한 번만 해결하고 결과를 저장함으로써 중복 계산을 방지하여 광범위한 문제에 대한 보다 효율적인 솔루션을 제공합니다.

DP(동적 프로그래밍)는 어떻게 작동하나요?

• 하위 문제 식별: 주요 문제를 더 작고 독립적인 하위 문제로 나눕니다.
• 매장 솔루션: 각 하위 문제를 해결하고 솔루션을 테이블이나 배열에 저장합니다.
• 구축 솔루션: 저장된 솔루션을 사용하여 주요 문제에 대한 솔루션을 구축하세요.
• 중복 방지: DP는 솔루션을 저장함으로써 각 하위 문제가 한 번만 해결되도록 보장하여 계산 시간을 단축합니다.

동적 프로그래밍(DP)의 예

예시 1: 피보나치 수열을 찾는 문제를 생각해 보세요.

피보나치 수열: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

무차별 접근 방식:

무차별 접근 방식을 사용하여 n번째 피보나치 수를 찾으려면 간단히 다음을 추가하면 됩니다. (n-1)번째 그리고 (n-2)번째 피보나치 수열. 이는 효과가 있지만 큰 값에는 비효율적입니다. N , 이전의 모든 피보나치 수를 계산해야 하기 때문입니다.

동적 프로그래밍 접근 방식:

동적 프로그래밍을 사용한 피보나치 수열

• 하위 문제: F(0), F(1), F(2), F(3), …
• 매장 솔루션: 계산된 F(n) 값을 저장할 테이블을 만듭니다.
• 구축 솔루션: F(n)의 경우, 표에서 F(n-1)과 F(n-2)를 찾아 추가하세요.
• 중복 방지: 이 표는 각 하위 문제(예: F(2))가 한 번만 해결되도록 보장합니다.

DP를 사용하면 하위 문제를 다시 계산하지 않고도 피보나치 수열을 효율적으로 계산할 수 있습니다.

자바 문자열 클래스

예 2: 가장 긴 공통 부분 수열(두 문자열에 공통된 가장 긴 부분 수열 찾기)

예시 3: 그래프의 최단 경로(그래프의 두 노드 사이의 최단 경로 찾기)

예시 4: 배낭 문제(주어진 용량의 배낭에 넣을 수 있는 품목의 최대값 찾기)

동적 프로그래밍(DP)을 언제 사용해야 합니까?

동적 프로그래밍은 다음과 같은 특성으로 구성된 문제를 해결할 때 사용되는 최적화 기술입니다.

1. 최적의 하부 구조:

최적의 하위 구조는 더 큰 문제의 최적 결과를 얻기 위해 하위 문제의 최적 결과를 결합하는 것을 의미합니다.

자바와 비교

예:

찾는 문제를 생각해보세요. 최소 비용 가중치 그래프의 경로 원천 노드를 a로 목적지 마디. 이 문제를 더 작은 하위 문제로 나눌 수 있습니다.

• 찾기 최저한의 비용 에서 경로 원천 각각의 노드 중급 마디.
• 찾기 최저한의 비용 각각의 경로 중급 노드에 목적지 마디.

더 큰 문제에 대한 솔루션(소스 노드에서 대상 노드까지의 최소 비용 경로 찾기)은 이러한 작은 하위 문제에 대한 솔루션에서 구성될 수 있습니다.

2. 중복되는 하위 문제:

동일한 하위 문제가 문제의 다른 부분에서 반복적으로 해결됩니다.

예:

계산 문제를 고려하십시오. 피보나치 수열 . 인덱스에서 피보나치 수를 계산하려면 N , 인덱스에서 피보나치 수를 계산해야 합니다. n-1 그리고 n-2 . 이는 지수에서 피보나치 수를 계산하는 하위 문제를 의미합니다. n-1 지수에서 피보나치 수를 계산하는 더 큰 문제에 대한 솔루션에서 두 번 사용됩니다. N .

동적 프로그래밍(DP)의 접근 방식

동적 프로그래밍은 두 가지 접근 방식을 사용하여 달성할 수 있습니다.

1. 하향식 접근 방식(메모이제이션):

하향식 접근 방식이라고도 합니다. 메모이제이션 , 최종 솔루션부터 시작하여 이를 더 작은 하위 문제로 반복적으로 분해합니다. 중복 계산을 피하기 위해 해결된 하위 문제의 결과를 메모 테이블에 저장합니다.

하향식 접근 방식을 분석해 보겠습니다.

• 최종 솔루션부터 시작하여 이를 더 작은 하위 문제로 반복적으로 나눕니다.
• 중복 계산을 피하기 위해 하위 문제에 대한 솔루션을 테이블에 저장합니다.
• 하위 문제의 수가 많고 그 중 다수가 재사용되는 경우에 적합합니다.

2. 상향식 접근 방식(표):

상향식 접근 방식이라고도 합니다. 표 , 가장 작은 하위 문제부터 시작하여 점차적으로 최종 솔루션을 구축합니다. 중복 계산을 피하기 위해 해결된 하위 문제의 결과를 테이블에 저장합니다.

상향식 접근 방식을 분석해 보겠습니다.

• 가장 작은 하위 문제부터 시작하여 점차적으로 최종 솔루션을 구축합니다.
• 상향식 방식으로 하위 문제에 대한 솔루션으로 테이블을 채웁니다.
• 하위 문제의 수가 적고 더 작은 하위 문제에 대한 솔루션에서 최적의 솔루션을 직접 계산할 수 있는 경우에 적합합니다.

동적 프로그래밍 (DP) 연산

동적 프로그래밍은 복잡한 문제를 더 작은 하위 문제로 나누고 나중에 사용할 수 있도록 해당 솔루션을 저장하여 문제를 해결하는 알고리즘 기술입니다. 다음을 포함하는 문제에 특히 효과적입니다. 중복되는 하위 문제 그리고 최적의 하부 구조.

Java에서 arraylist 정렬

동적 프로그래밍을 사용하는 일반적인 알고리즘:

• 가장 긴 공통 부분 서열(LCS): 두 문자열 사이에서 가장 긴 공통 부분 수열을 찾습니다.
• 그래프의 최단 경로: 그래프에서 두 노드 사이의 최단 경로를 찾습니다.
• 배낭 문제: 주어진 용량의 배낭에 넣을 수 있는 최대 아이템 가치를 결정합니다.
• 매트릭스 체인 곱셈: 연산 수를 최소화하기 위해 행렬 곱셈의 순서를 최적화합니다.
• 피보나치 수열: n번째 피보나치 수를 계산합니다.

동적 프로그래밍의 장점 (DP)

동적 프로그래밍에는 다음과 같은 다양한 장점이 있습니다.

• 동일한 하위 문제를 여러 번 다시 계산하는 것을 방지하여 시간을 크게 절약할 수 있습니다.
• 가능한 모든 조합을 고려하여 최적의 솔루션을 찾도록 보장합니다.
• 복잡한 문제를 더 작고 관리하기 쉬운 하위 문제로 나눕니다.

동적 프로그래밍의 응용 (DP)

동적 프로그래밍에는 다음을 포함하여 광범위한 응용 프로그램이 있습니다.

• 최적화: 배낭 문제, 최단 경로 문제, 최대 부분 배열 문제
• 컴퓨터 과학: 가장 긴 공통 부분 수열, 편집 거리, 문자열 일치
• 운영 연구: 재고관리, 스케줄링, 자원배분

이제 동적 프로그래밍을 마스터하기 위한 포괄적인 로드맵을 살펴보겠습니다.

동적 프로그래밍(DP)의 기초 배우기

• 메모이제이션이란 무엇인가요? 완전한 튜토리얼
• 표 작성과 메모화
• 최적의 하부 구조 특성
• 겹치는 하위 문제 속성
• 동적 프로그래밍 문제를 해결하는 방법은 무엇입니까?

• 피보나치 수열
• n번째 카탈로니아어 번호
• Bell Numbers(세트를 분할하는 방법의 수)
• 이항 계수
• 코인 변경 문제
• 부분합 문제
• nCr %p 계산
• 막대 자르기
• 페인팅 울타리 알고리즘
• 가장 긴 공통 부분 수열
• 가장 긴 증가 부분 수열
• 인접한 것 사이의 차이가 1이 되는 가장 긴 부분 수열
• 모두 1인 최대 크기 정사각형 하위 행렬
• 최소 비용 경로
• 끝까지 도달하기 위한 최소 점프 횟수
• 가장 긴 공통 부분 문자열(공간 최적화 DP 솔루션)
• 1, 2, 3단계를 사용하여 n번째 계단에 도달하는 방법 계산
• mXn 행렬의 왼쪽 위에서 오른쪽 아래까지 가능한 모든 경로를 계산합니다.
• 장애물이 있는 그리드의 고유한 경로

2. 동적 프로그래밍(DP)에 대한 중간 문제

• 플로이드 워샬 알고리즘
• 벨만-포드 알고리즘
• 0-1 배낭 문제
• 0/1 배낭에 아이템 인쇄하기
• 무한한 배낭(반복 아이템 허용)
• 계란 낙하 퍼즐
• 단어 나누기 문제
• 정점 커버 문제
• 타일 ​​쌓기 문제
• 상자 쌓기 문제
• 파티션 문제
• 여행하는 세일즈맨 문제 | 세트 1(순진하고 동적 프로그래밍)
• 가장 긴 회문 부분 수열
• 가장 긴 공통 증가 부분 수열(LCS + LIS)
• 배열의 모든 개별 하위 집합(또는 하위 시퀀스) 합계 찾기
• 가중 작업 스케줄링
• 개수 이상(원래 위치에 요소가 나타나지 않도록 하는 순열)
• 회문을 형성하기 위한 최소 삽입
• 와일드카드 패턴 일치
• 인접한 공이 다른 종류가 되도록 공을 배열하는 방법

3. 동적 프로그래밍(DP)의 어려운 문제

• 회문 파티셔닝
• 줄 바꿈 문제
• 화가의 칸막이 문제
• 브리지 및 토치 문제에 대한 프로그램
• 매트릭스 체인 곱셈
• 행렬 체인 곱셈 문제의 인쇄 괄호
• 2D 매트릭스의 최대 합계 직사각형
• 최대 k번 주식을 사고 팔면 최대 이익을 얻을 수 있습니다.
• 서로 다른 비용의 역순 연산을 사용하여 문자열을 정렬하는 데 드는 최소 비용
• 배열의 AP(산술 진행) 하위 시퀀스 수
• 트리의 동적 프로그래밍 소개
• 임의의 노드가 루트로 간주될 수 있는 경우 트리의 최대 높이
• 가장 긴 반복 및 겹치지 않는 하위 문자열

빠른 링크:

• 데이터 구조와 알고리즘 배우기 | DSA 튜토리얼
• 동적 프로그래밍 인터뷰 질문 상위 20개
• 동적 프로그래밍의 '연습 문제'
• 동적 프로그래밍에 대한 '퀴즈'