[알고리즘] 분할 정복(Divide and Conquer) 알아보기
개발/DS&Algorithms
/ 2022. 5. 10.
안녕하세요😎 백엔드 개발자 제임스입니다 :) 이번 포스팅은 분할 정복에 대해서 정리하도록 하겠습니다. 저번 시간 정리했던 동적 계획법과 유사하게 어떠한 문제를 해결하는 방법인데요. 아래에서 자세하게 알아보겠습니다. 분할 정복(Divide and Conquer) 알고리즘 분할 정복 알고리즘은 어떠한 문제를 작은 문제로 더 이상 나눌 수 없을 때까지 분할하여 문제를 해결하는 방법입니다. 자세하게는 분할된 작은 단위의 문제들을 각각 풀면서 다시 합병하여 답을 구하는 것입니다. 대표적인 예로는 정렬 알고리즘 중에서 퀵 정렬(Quick sort), 합병 정렬(Merge sort), 이진 탐색(Binary search), 선택 문제, 고속 푸리에 변환(FFT) 문제가 대표적입니다. * 분할 정복과 동적 계획법의 차..
[알고리즘] 분할 정복(Divide and Conquer) 알아보기
개발/DS&Algorithms
/ 2022. 5. 10.
안녕하세요😎 백엔드 개발자 제임스입니다 :) 이번 포스팅은 분할 정복에 대해서 정리하도록 하겠습니다. 저번 시간 정리했던 동적 계획법과 유사하게 어떠한 문제를 해결하는 방법인데요. 아래에서 자세하게 알아보겠습니다. 분할 정복(Divide and Conquer) 알고리즘 분할 정복 알고리즘은 어떠한 문제를 작은 문제로 더 이상 나눌 수 없을 때까지 분할하여 문제를 해결하는 방법입니다. 자세하게는 분할된 작은 단위의 문제들을 각각 풀면서 다시 합병하여 답을 구하는 것입니다. 대표적인 예로는 정렬 알고리즘 중에서 퀵 정렬(Quick sort), 합병 정렬(Merge sort), 이진 탐색(Binary search), 선택 문제, 고속 푸리에 변환(FFT) 문제가 대표적입니다. * 분할 정복과 동적 계획법의 차..