동적 프로그래밍과 반대 개념 프로그래밍
동적 프로그래밍 개요
동적 프로그래밍은 주어진 문제를 더 작은 하위 문제들로 나누어 풀고, 그 결과를 저장하고 재활용하여 문제를 해결하는 알고리즘 설계 기법입니다. 큰 문제를 작은 하위 문제로 쪼개서 해결하면서 중복 계산을 피하고 효율적으로 문제를 해결할 수 있습니다.
핵심 특징:
- 문제 분해: 큰 문제를 작은 하위 문제들로 분해합니다.
- 메모이제이션: 하위 문제의 해결 결과를 저장하고 재사용합니다.
- 최적 해 찾기: 하위 문제들의 최적 해를 조합하여 전체 문제의 최적 해를 찾습니다.
장점:
- 효율성 향상: 중복 계산을 줄여 시간 복잡도를 낮출 수 있습니다.
- 문제 해결 범위 확대: 재귀 호출 없이 큰 규모의 문제를 해결할 수 있습니다.
- 코드 명확성 향상: 재귀 호출 구조를 피해 코드를 더 명확하게 작성할 수 있습니다.
활용 분야:
- 최단 경로 계산: 다익스트라 알고리즘, 벨만-포드 알고리즘
- 문제 시퀀스 계산: 피보나치 수열, 최대 공통 부분 문자열
- 조합 문제: 냅색 문제, 동전 교환 문제
동적 프로그래밍과 반대 개념 프로그래밍
동적 프로그래밍과 반대되는 개념의 프로그래밍 방식은 다음과 같습니다.
1. 재귀 프로그래밍:
- 동일한 문제를 반복적으로 호출하여 해결합니다.
- 중복 계산이 발생하여 비효율적일 수 있습니다.
- 간단한 문제 해결이나 특정 상황에서 유용할 수 있습니다.
2. 완전 탐색:
- 모든 가능한 경우를 하나씩 검사하여 해결합니다.
- 문제 규모가 커질수록 비효율적이게 됩니다.
- 최적 해가 보장되지만, 다른 알고리즘보다 훨씬 많은 시간이 소요됩니다.
3. 분할 정복:
- 문제를 크기가 같은 두 개의 하위 문제로 분할합니다.
- 하위 문제를 재귀적으로 해결하고, 결과를 합쳐 최종 결과를 얻습니다.
- 동적 프로그래밍과 유사하지만, 메모이제이션을 사용하지 않습니다.
4. 탐욕 알고리즘:
- 현재 가장 좋은 선택을 반복적으로 수행하여 해결합니다.
- 항상 최적 해를 보장하지는 않지만, 빠른 속도로 해결 가능합니다.
결론:
- 동적 프로그래밍은 중복 계산을 줄여 효율성을 높이는 알고리즘 설계 기법입니다.
- 재귀 프로그래밍, 완전 탐색, 분할 정복, 탐욕 알고리즘 등은 동적 프로그래밍과 반대되는 개념의 프로그래밍 방식입니다.
- 문제의 특성에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.
도움이 되었기를 바랍니다!
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
[백준] 열 개씩 끊어 출력하기 - 11721번 (0) | 2024.06.01 |
---|---|
[백준] KMP는 왜 KMP일까? - 2902번 (0) | 2024.06.01 |
[백준] 피보나치 수1 - 24416번 (0) | 2024.05.31 |
[백준]알고리즘의 수행 시간 6 - 24267 (0) | 2024.05.31 |
[백준]알고리즘의 수행 시간 2 - 24263번 (0) | 2024.05.31 |