Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 리버싱
- 철학
- 사회적 사실
- 코드엔진 베이직
- CodeEngn Basic 01
- codeengn basic rce 01
- 디지털 포렌식 트랙
- h4ckinggame
- 사회분업론
- 코드엔진 basic 5
- 코드엔진
- BoB 12기
- CodeEngn Basic 5
- Best of the Best
- 논문리뷰
- malware
- 자살론
- BoB 12기 최종합격 후기
- bob
- 에밀 뒤르켐
- CodeEngn
Archives
- Today
- Total
woonadz :)
동적 프로그래밍(Dynamic Programming) 본문
반응형
동적 프로그래밍(Dynamic Programming)이란?
동적 프로그래밍(Dynamic Programming)은 작은 하위 문제로 나누어 그 결과를 저장해가며, 전체 문제를 해결하는 알고리즘 설계 기법입니다. 이를 통해 중복 계산을 줄여 계산 속도를 높이고 효율적으로 계산할 수 있습니다.
DP 기법을 적용시킬 수 있는 조건
1. 중복되는 부분 문제(Overlapping Subproblems)
동일한 작은 문제들이 반복하여 나타나는 경우, 반복적으로 같은 문제를 해결하는 성질입니다.
2. 최적 부분 구조(Optimal Substructure)
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 성질로, 작은 문제의 최적해를 통해 큰 문제의 최적해를 구할 수 있습니다.
DP 문제 풀이 방법
1. 하위 문제
하위 문제로 분할하여 하위 문제를 재귀적으로 해결합니다.
2. 결과 저장
하위 문제의 결과를 저장하고 이를 이용하여 큰 문제를 해결합니다.
DP 문제 해결 방식
- Bottom-Up (Tabulation 방식) - 반복문 사용 / 최적 부분 구조
Bottom-Up 방식은 작은 부분 문제부터 차례대로 해결하여 전체 문제를 해결하는 방식입니다. 작은 문제들의 결과값을 저장함으로써 동일한 계산을 반복하지 않아 시간 복잡도가 감소합니다. 일반적으로 더 직관적이고 이해하기 쉽지만 결과값을 임의로 저장해 둘 공간이 필요합니다. - Top-Down (Memoization 방식) - 재귀 사용
큰 문제를 작은 부분 문제로 나누어 해결하는 방식입니다. 중복 계산을 피하기 위해 이전에 계산한 값을 저장하는 Memoization을 활용하며, 시간 복잡도가 감소합니다. 하지만 초기값 설정 및 작은 문제들의 결과값을 저장해둘 공간이 필요합니다.
DP 장단점
장점
- 중복 계산을 줄일 수 있습니다.
- 효율적인 시간 복잡도를 가질 수 있습니다.
단점
- 메모리 사용량이 큽니다. DP는 중간 결과를 저장하기 위해 추가적인 메모리를 사용합니다. 따라서 문제의 크기가 커질수록 필요한 메모리도 증가할 수 있습니다.
최장 증가 부분 수열(Longest Increasing Subsequence, LIS)이란?
주어진 수열에서 일부 항목을 선택하여 만들 수 있는 부분 수열 중에서, ‘원소의 크기가 증가하는 순서대로 정렬’되어 있는 가장 긴 수열을 찾는 문제
https://chanhuiseok.github.io/posts/algo-49/
알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘
컴퓨터/IT/알고리즘 정리 블로그
chanhuiseok.github.io
반응형
'IT > 자료구조 및 알고리즘' 카테고리의 다른 글
[개념정리] 정렬 _1(버블 정렬, 단순 선택 정렬, 단순 삽입 정렬) (0) | 2022.02.23 |
---|---|
[개념정리] 재귀 알고리즘 (0) | 2022.02.12 |
[개념정리] 스택과 큐 (0) | 2022.02.04 |
[개념정리] 검색 (0) | 2022.01.30 |
[개념정리] 기본 자료구조 (0) | 2022.01.23 |