일본 치바현's blog

🔹 백트래킹이란?1. 백트래킹(Backtracking)의 정의백트래킹(Backtracking)은 모든 가능한 경우를 탐색하면서 불필요한 경로는 중단(Pruning)하여 효율적으로 해결하는 기법입니다.✅ 백트래킹의 주요 특징:상태 공간 탐색을 수행하여 최적해를 찾음유망하지 않은 경로는 조기에 차단하여 불필요한 연산을 줄임 (Pruning)DFS(깊이 우선 탐색) 기반의 알고리즘 구조순열, 조합, 그래프 탐색, 최적화 문제 등에 활용📌 백트래킹을 사용하면 완전 탐색보다 효율적으로 해를 구할 수 있습니다.🔹 백트래킹의 동작 과정현재 단계에서 가능한 선택을 수행조건을 만족하는지 확인하고 유망한 경우 탐색 지속조건을 만족하지 않는 경우 되돌아감 (백트래킹 수행)모든 가능한 해를 찾거나 최적해를 도출✔️ 백트..

🔹 탐욕법이란?1. 탐욕법(Greedy Algorithm)의 정의탐욕법(Greedy Algorithm)은 문제를 해결할 때 매 단계에서 가장 최선이라고 판단되는 선택을 반복하여 전체 최적해를 구하는 알고리즘 기법입니다.✅ 탐욕법의 주요 특징:매 단계에서 가장 최적이라고 생각되는 해를 선택선택 후에는 되돌아가지 않음 (백트래킹 없음)빠르고 단순한 계산으로 문제 해결 가능항상 최적해를 보장하지는 않지만, 특정 문제에서는 유효📌 탐욕법은 최적해를 구하는 문제뿐만 아니라 근사 해법(Approximation Algorithm)으로도 많이 사용됩니다.🔹 탐욕법의 동작 과정현재 상태에서 가장 최적의 선택을 결정선택한 해를 확정하고 다음 단계로 진행이 과정을 반복하여 전체 문제를 해결최적해를 도출하거나 근사해를 ..

🔹 분할 정복법이란?1. 분할 정복법(Divide and Conquer)의 정의분할 정복법(Divide and Conquer)은 복잡한 문제를 작은 부분 문제로 나누어 각각을 해결한 후 결합하여 전체 문제를 해결하는 알고리즘 기법입니다.✅ 분할 정복법의 주요 특징:문제를 작은 하위 문제로 나눔 (Divide)하위 문제를 해결 (Conquer)해결된 결과를 결합 (Combine)재귀 호출을 활용하여 구조적으로 문제를 해결📌 분할 정복법을 사용하면 복잡한 문제를 보다 쉽게 해결할 수 있습니다.🔹 분할 정복법의 동작 과정문제를 여러 개의 하위 문제로 분할각 하위 문제를 독립적으로 해결 (재귀 호출 가능)해결된 하위 문제들을 결합하여 최종 해결책을 도출✔️ 분할 정복법을 활용한 합병 정렬(Merge Sor..