목록Divide and Conquer (1)

Tori의 개발 공부

분할과 정복 내용정리

분할 정복 알고리즘 이란? 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다. 일반적으로 재귀 함수로 구현한다. 설계 단계 Divide (분할) : 문제가 분할이 가능한 경우, 원래 문제를 분할하여 더 작은 하위 문제들로 분할한다. Conquer (정복) : 나누어진 문제가 여전히 분할이 가능하다면, 다시 Divide 수행하고 그렇지 않다면 문제를 해결한다. Combine (합치기): Conquer한 문제들을 통합하여 원래 큰 문제의 답을 얻는다. 장단점 장점 문제를 나눔으로써 어려운 문제를 쉽게 해결할 수 있다. 단점 재귀 함수를 호출한다는 점에서 함수 호출로 인한 오버헤드 발생, 스택에 ..
Algorithm/개념 정리 2021. 9. 13. 23:08
이전 Prev 1 Next 다음