최적화 (2) 썸네일형 리스트형 [알고리즘 & 문제 해결 패턴] 탐욕 알고리즘(Greedy) 원리 및 활용 사례 [알고리즘] 탐욕 알고리즘(Greedy) 원리 및 활용 사례1. 탐욕 알고리즘(Greedy)이란?탐욕 알고리즘(Greedy Algorithm)은**각 단계에서 최적이라고 판단되는 선택을 반복하여 최종 해답을 찾는 방식**의 알고리즘입니다.일반적으로 전체 최적해를 구하는 것이 아닌,각 단계에서 가장 좋은 선택을 했을 때 최적해를 구할 수 있는 경우에 효과적입니다.2. 탐욕 알고리즘의 특징✔ **지역 최적해(Local Optimal Choice)를 선택하여 전체 최적해(Global Optimal Solution)를 찾음**✔ 항상 최적해를 보장하지는 않지만, **근사 최적해(Approximate Solution)**를 빠르게 구할 수 있음✔ DP(Dynamic Programming)와 다르게, **과거의 선.. [알고리즘 & 문제 해결 패턴] 다이나믹 프로그래밍(DP) 개념과 대표 문제 풀이 [알고리즘] 다이나믹 프로그래밍(DP) 개념과 대표 문제 풀이1. 다이나믹 프로그래밍(DP)이란?다이나믹 프로그래밍(Dynamic Programming, DP)은복잡한 문제를 작은 부분 문제로 나누어 해결하는 최적화 기법입니다.일반적인 분할 정복(Divide and Conquer)과 다르게, 동일한 부분 문제가 반복될 경우중복 계산을 줄이기 위해 결과를 저장(Memoization)하여 성능을 향상시킵니다.2. DP의 핵심 개념✔ **중복되는 부분 문제(Subproblem Overlapping)**큰 문제를 작은 문제로 나누어 해결예: 피보나치 수열✔ **최적 부분 구조(Optimal Substructure)**부분 문제의 최적 해가 전체 문제의 최적 해를 구성예: 최단 경로 문제✔ **메모이제이션(Mem.. 이전 1 다음
