오늘 알고리즘 공부는 분할 정복 문제들에 대해서 살펴보도록 하자. 분할 정복 알고리즘이란? 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제의 답을 계산하는 방법. 재귀와의 차이점은 재귀는 한조각과 나머지 부분과 분할하지만, 분할 정복은 항상 절반씩으로 나눈다. 분할 정복 알고리즘의 구성요소문제를 더 작은 문제로 분할하는 과정 (divide)문제에 대해 구한 답을 원래 문제에 답으로 병합하는 과정 (merge)더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case)분할 정복의 장점작업을 더 빠르게 처리해 준다. 예제 : 수열의 빠른 합과 행렬의 빠른 제곱 1~n까지의 합fastsum() = 1 + 2 + .... + n 1~n/2 + n/2 ~ n까즤 합으로 바꿀 수 있다..
재귀 함수의 필요성 예제: 중첩 반복문 대체하기 0번부터 차례대로 번호 매겨진 n개의 원수 중 네 개를 고르는 모든 경우의 수를 출력하라 보통 아래와 같이 작성할 수 있다. for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { for (int l = k + 1; l < n; l++) { System.out.println(i + "," + j + "," + k + "," + l); } } } } 만약 다섯개를 골라야 한다면? 6개를 골라야 한다면 ? 7개를 골라야한다면? (5중, 6중, 7중 for문을 쓰면 되지만 코드가 길고 복잡해진다.) 재귀호출을 사용하면 단순한 반복문보다 간결하고..
문제 . 1차원 배열에서 연속된 부분 구간 중 그 합이 최대인 구간을 찾는 문제. 예) 배열 [-7, 4, -3, 6, 3, -8, 3, 4] 에서 최대 합을 갖는 부분 구간은 [4, -3, 6, 3] 으로 합은 10 이다 그냥 생각 같아선 다음과 같이 구할 수 있지만, 반복문이 3개이기 때문에 O(N^3)의 시간 복잡도가 걸리기 때문에 좋지 않다. private int inefficientMacSum(int[] arr) { int N = arr.length; int ret = 0; for(int i =0; i< N ; i++) { for(int j = i; j< N; j++) { // A[i,j] 의 합 int sum = 0; for (int k=i; k