자바 알고리즘 인터뷰 22. 분할 정복
분할 정복 알고리즘은 영어로 Divide and Conquer 줄여서 DAC 알고리즘이라고 한다. 분할 정복 알고리즘은 이름에서도 나오듯이 분할 그 다음 정복이라는 단계로 이어진다. 즉 2단계로 구성이 된다. 분할 정복 알고리즘을 수도 코드로 표현한 결과는 아래와 같다. DAC(a, i, j) { if(small(a, i, j)) return(Solution(a, i, j)) //분할정복을 하기 전에 답이 나오는 경우 else mid = divide(a, i, j) b = DAC(a, i, mid) c = DAC(a, mid+1, j) d = combine(b, c) return(d) } 1. 퀵 정렬 2. 병합 정렬 3. Cooley-Tukey FFT 알고리즘 4. Karatsuba 알고리즘 x = x..
2024. 2. 16.
