2

1

10

3

풀이

해당 문제또한 마찬가지로 다이나믹 프로그래밍을 활용하여 풀이하는 문제이다.

해당 문제에서 제시하는 기본 조건은 3가지로, 가장 신경써야할것은 X를 최소한의 횟수로 1을 만들어야한다는 것이다.

예로, 제시된 예제가 10을 입력했을때 3을 반환해야한다는 것인데, 아무런 생각 없이 구현한다면 4의 결과값이 나오게 된다.

        int[] dp = new int[N+1];
        dp[0] =0;
        dp[1] =0;

마찬가지로 배열을 생성해 N까지 경우의수를 탐색한다.

그리고 이미 제시가 되어있는 값은 입력한다. 0과 1을 입력하면 어떠한 연산도 하지 않기때문에 횟수는 0이 된다.

        for(int i=2; i<=N;i++){
            dp[i] = dp[i-1]+1;
            if(i%2==0){
            dp[i]= Math.min(dp[i],dp[i/2]+1);
            }if(i%3==0){
                dp[i] = Math.min(dp[i],dp[i/3]+1);
            }
        }

그리고 마찬가지로 2부터 문제를 풀어나가기 위해 반복문을 선언한다.

단순히 10까지의 최소 연산 횟수를 구한다고 치면,

• 0 = 0
• 1 = 0
• 2 = 1 (2-1)
• 3 = 1 (3/3)
• 4 = 2 (4/2/2)
• 5 = 3 ((5-1)/2/2)
• 6 = 2 (6/3/2)
• 7 = 3 ((7-1)/3/2)
• 8 = 3 (8/2/2/2)
• 9 = 2 (9/3/3)
• 10 = 3 ((10-1)/3/3)

이렇게 봤을때 느낄 수 있는건, 원래 단순히 최저 횟수를 생각하지 않고 계산을 했을때 , 생각하고 계산했을때의 횟수를 비교해야 된다는 것이다.

위의 연산을 배열로 표현해본다면

• dp[2] = dp[2-1]+1 혹은 dp[2] = dp[2/2]+1
• dp[3] = dp[3/3]+1
• dp[4] = dp[4-1]+1 혹은 dp[4/2]+1 
• dp[5] = dp[5-1]+1 
• dp[6] = dp[6/3]+1 
• dp[7]= dp[7-1]+1 
• dp[8] = dp[8/2]+1
• dp[9] = dp[9/3]+1
• dp[10] = dp[10-1]+1 혹은 dp[10/2]+1

이렇게 구할 수 있다.

혹은 <이 한번씩 등장한다.

그래서 기본 횟수로 dp[i-1]+1 를 값으로 넣어주고, 비교를 해서 더 작은 값을 넣어주는것이다.

다이나믹 프로그래밍을 구현할때는 어떠한 값을 구한다기 보다는 정말 구해야되는 답을 위해서 편법을 쓴다는 생각으로 풀이해야하는것 같다..

package baekjoon.a1463;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class a1463 {
    public static int count =0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N+1];
        dp[0] =0;
        dp[1] =0;
        for(int i=2; i<=N;i++){
            dp[i] = dp[i-1]+1;
            if(i%2==0){
            dp[i]= Math.min(dp[i],dp[i/2]+1);
            }if(i%3==0){
                dp[i] = Math.min(dp[i],dp[i/3]+1);
            }
        }
        System.out.println(dp[N]);
    }
}

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

3
0
1
3

1 0
0 1
1 2

2
6
22

5 8
10946 17711

풀이

해당 문제는 다이나믹 프로그래밍으로 풀이하는 문제이다.

다이나믹 프로그래밍은 재귀용법과 관련지어서 생각해볼수 있는데,

재귀용법은 단순히 매 문제마다 더이상 풀 수 없을때까지 풀이하고 넘어간다면

다이나믹 프로그래밍은 메모이제이션 기법을 활용해서 매 문제의 답을 기억해두고 다음 문제를 풀이할때 그 답을 참고하여 풀이한다는 것이다.

기본적인 풀이에는 배열을 생성해 사용하는데,

해당 문제또한 마찬가지로 배열을 사용해 풀이할 수 있다.

그리고 작은 단계부터 점점 풀어나가서 답을 찾는 방식으로 풀이하면 된다.

일단 단순히 바로 답을 구할 수 있는 것들은 답을 저장해둔다.

값이 0이 들어오면 0을 반환하고, 1이 들어오면 1을 반환한다고 문제에 친절하게 힌트가 적혀있다.

해당 문제는 0이나 1을 몇번 출력하는지를 알고싶어하고, 40보다 작거나 같은 수라고 하니 0부터 40 , 즉 41개의 공간을 가진 배열을 생성해

미리 0과 1이 들어올때의 답을 배열에 넣어놓는다.

        Integer[][] arr = new Integer[41][2];
        arr[0][0] = 1;
        arr[0][1] = 0;
        arr[1][0] = 0;
        arr[1][1] = 1;

0일때 0이 반환되니 0번째의 0은 1, 1은 출력되지 않으니 0이 된다.

1일때는 0이 반환되지 않고 1만 반환되니 0 , 1 이 되는것이다.

0 과 1 의 답을 제시해주고 있으니 2부터 반복문을 돌려서  N번 반복하는 반복문을 실행하면 된다.

여기서 메소드를 호출하지 않고 배열로만 계산을 진행한다.

        for (int j = 0; j < N; j++) {
        int n = Integer.parseInt(br.readLine());
        for (int i = 2; i <= n; i++) {
            arr[i][0] = arr[i - 1][0] + arr[i - 2][0];
            arr[i][1] = arr[i - 1][1] + arr[i - 2][1];
        }

여기서 엄청 헷갈릴것이다.

피보나치를 머릿속으로 그리는것도 어려운데.. 반복문으로 저렇게 표현하고 있으니..

arr[i][0]  <- 이것은 피보나치(2)를 했을때 0이 출력되는 횟수가 된다.

arr[1][0] 은 아까 위에서 선언했듯이 0이 될것이고, arr[0][0]은 1이 된다.

그렇다.. 이것은 피보나치 함수의 결과값을 제출해야 하는것이 아닌 피보나치 함수(N) 을 실행했을때 1과 0이 몇번 출력되는지를 구하는것이다..!

package baekjoon.a1003;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class a1003 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Integer[][] arr = new Integer[41][2];
        arr[0][0] = 1;
        arr[0][1] = 0;
        arr[1][0] = 0;
        arr[1][1] = 1;
        for (int j = 0; j < N; j++) {
        int n = Integer.parseInt(br.readLine());
        for (int i = 2; i <= n; i++) {
            arr[i][0] = arr[i - 1][0] + arr[i - 2][0];
            arr[i][1] = arr[i - 1][1] + arr[i - 2][1];
        }
            System.out.println(arr[n][0]+" "+arr[n][1]);
    }
    }

}

이렇게만 풀이하면 어렵게 생각하지 않고 풀이할 수 있다.

동적 계획법 / 분할 정복

동적 계획법 (다이내믹 프로그래밍)

• 입력 크기가 작은 부분 문제들을 해결한 후 메모이제이션 기법을 사용해서 (미리 결괏값을 저장하여) 문제를 푸는 것
  • 상향직 접근법 → 해당 문제를 풀기 위해 가장 단순한 형태의 해답을 구한 후 이를 저장 후 해당 결괏값을 가지고 상위 문제를 풀이
  • 메모이제이션 : 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술

분할 정복

• 큰 문제를 풀기 위해 문제를 잘게 쪼개서 풀이한 후 다시 합병하여 문제의 답을 얻는 알고리즘
  • 하향식 접근법 → 상위의 해답을 구하기 위해 하위의 해답을 구하는 방식
    • 일반적으로 재귀함수로 구현한다.

공통점과 차이점

• 공통점
  • 문제를 잘게 쪼개서, 가장 작은 단위로 분할한다
• 차이점
  • 동적 계획법
    • 메모이제이션 기법 사용
    • 상위 문제 해결시 재활용함
  • 분할 정복
    • 부분 문제는 서로 중복되지 않는다.
    • 메모이제이션 기법을 사용하지 않음

동적 계획법 활용하기

• 기존의 재귀함수를 호출할 땐?
  • 팩토리얼을 구현할 때, 각각의 매개값의 결과를 구하기 위해 매번 다시 처음부터 순회하며 값을 구한 후 더해준다.
    • 동적계획법을 이용한다면, 이미 계산한 값들은 저장해놓고 순서를 넘기기 때문에 불필요한 호출을 하지 않는다.

public static int recur(int n){
        if(n<=1){
            return n;
        }
        return recur(n-1)+recur(n-2);
    } //기존의 재귀함수 호출

public static int dynamicFunc(int n){
		Integer[] cache = new Integer[n+1] //저장용 배열을 생성한다.
		cache[0] = 0; //미리 구할 수 있는 값들은 저장해놓는다.
		cache[1] = 1;
		for(int i=2; i<n+1; i++){
			cache[i] = cache[i-1]+ cache[i-2]; //계산된 값을 저장해가며 올라간다.
		}
		return cache[n]; 
		}
	}

분할 정복을 사용하는 병합 정렬과 퀵 정렬

병합 정렬

• 재귀 용법을 활용한 정렬 알고리즘
  • 리스트를 절반으로 나눠 비슷한 크기의 두 리스트로 나눈다.
  • 각 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  • 두 리스트를 다시 하나의 정렬된 리스트로 병합한다.
  • 리스트를 더 이상 쪼갤 수 없을 때까지 나눠서 정렬을 하며 다시 합친다.
    • 병합 정렬은 크게 두 가지의 단계를 거친다.
      • 끝없이 분할하는 split 단계
      • 분할한 것들을 병합하는 merge단계
      • 병합 시에 매번 각각의 데이터의 최소값의 인덱스를 저장한다.
      • 병합시에 각각의 데이터를 비교해서 작은 것을 앞에, 큰 것을 뒤에 놓게 된다.
      • 각각의 데이터는 매번 병합 시에 정렬이 되어있는 상태이다.
• 항상 데이터가 들어오면 두 단계로 분리한다.
• 분리한 데이터를 단계별로 합친다.
• 합칠 시에는 데이터를 비교해가면서 병합된 데이터는 정렬이 된 상태를 유지하게 한다.

분할 메서드를 선언해 보자.

public static void split(ArrayList<Integer> list){
        if(list.size()<=1){
            return;
        }
        int medium = list.size()/2;
        List<Integer> leftList = new ArrayList<>(list.subList(0,medium));
        List<Integer> rightList = new ArrayList<>(list.subList(medium,list.size()));
        System.out.println(leftList);
        System.out.println(rightList);
    }

subList() 메서드를 사용하여 사이즈 /2 만큼의 리스트를 두개 생성한다.

해당 메소드를 재귀호출하여 나눈 후 병합한다.

public static ArrayList<Integer> mergeSplitFunc(ArrayList<Integer> list){
        if(list.size()<=1){
            return list;
        }
        else{
            int medium = list.size()/2;
            //재귀 호출로 더 이상 나눌 수 없을때까지 나눈다.
            ArrayList<Integer> leftList = mergeSplitFunc(new ArrayList<>(list.subList(0,medium)));
            ArrayList<Integer> rightList = mergeSplitFunc(new ArrayList<>(list.subList(medium,list.size())));
            return mergeFunc(leftList,rightList);
        }
    } //나누는 부분에서 재귀호출을 실행한다.

그리고 병합 메소드를 선언한다.

• 더 이상 쪼갤 수 없을 때까지 분할 후 차례로 들어오는 것이기 때문에 왼쪽 리스트, 오른쪽 리스트 이렇게 값을 비교한다.
• 반복문이 아닌 while 문으로 포인터에 1씩 더해주면서 값을 비교하고 종료시킨다.
• 3개의 케이스를 만들어서 케이스별로 정렬을 시도한다.
  • 왼쪽 리스트와 오른쪽 리스트가 존재할 때, 왼쪽 리스트만 존재할때, 오른쪽 리스트만 존재할 때를 비교한다.
    • 각각 리스트별로 다른 사이즈가 될 수 있기 때문이다.

public static ArrayList<Integer> mergeFunc(ArrayList<Integer> leftList,ArrayList<Integer> rightList){
        ArrayList<Integer> mergedList = new ArrayList<>();
        int leftPoint = 0;
        int rightPoint = 0;

        //CASE1 : left / right 둘 다 존재할 때
        while(leftList.size() > leftPoint && rightList.size()>rightPoint){
            if(leftList.get(leftPoint)> rightList.get(rightPoint)){
                mergedList.add(rightList.get(rightPoint));
                rightPoint++;
            }
            else{
                mergedList.add(leftList.get(leftPoint));
                leftPoint++;
            }
        }
        //CASE2 : right 데이터가 없을 때
        while(leftList.size()>leftPoint){
            mergedList.add(leftList.get(leftPoint));
            leftPoint++;
            //나머지를 다 넣어준다.
        }
        // 왼쪽 데이터가 처리된 상태이지만 오른쪽 데이터가 아직 존재하는 상태라면
        // case3으로 들어올 수가 있다.
        //CASE3 : left 데이터가 없을 때
        while(rightList.size()>rightPoint){
            mergedList.add((rightList.get(rightPoint)));
            rightPoint++;
        }
        return mergedList;
    }

퀵정렬

• 퀵정렬이란?
  • 정렬 알고리즘의 꽃이라고 할 수 있다.
  • 속도도 빠르고 코드도 간결하게 쉽게 정렬이 가능하다.
    • 피벗(기준점)을 정해서, 각각의 데이터를 확인하면서 피벗보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 배치한다. ****(위치를 잡는다고 생각하면 좋다. 보통 맨 앞에 있는 값을 피벗으로 정한다.)
    • 각 왼쪽 오른쪽의 데이터들은 재귀용법을 사용해서 위 작업을 반복한다.
    • 함수는 각각 왼쪽 + 피벗 + 오른쪽을 리턴한다.
  • 피벗을 정한 후 데이터를 순회하면서 피벗을 기준으로 양쪽에 데이터를 배치한다.
  • 병합 정렬과 차이점은 병합정렬은 분리 후 정렬, 병합 과정을 거친다면 퀵 소트는 분리 시에 정렬하며 나중에 합친다.

코드로 구현해 보기

• 기본적인 split 함수 구현해 보기
  • 재귀함수를 선언한다.
  • 매개값으로 주어지는 배열의 사이즈가 1이라면 아무 동작도 하지 않은 채 배열을 리턴한다.
  • 사이즈가 1 이상이라면 맨 앞의 데이터를 기준점으로 잡고 왼쪽에 배치할 배열과 오른쪽에 배치할 배열을 생성해 인덱스 1부터 순회하여 값이 작다면 왼쪽, 크다면 오른쪽배열로 데이터를 넣어준다.
  • 순회가 끝난 후 각 배열의 데이터를 담을 mergedArr를 생성해 addAll 메서드로 데이터들을 넣어준다.
    • 이때 재귀함수를 호출한다.
    • 왼쪽데이터를 또다시 split 함수로 나눠서 정렬하고, 오른쪽 데이터 또한 마찬가지로 split 함수로 나눠서 정렬한다.
    • 따라서 addAll 메서드 안에 split 함수를 호출하도록 한다.
    • 기준점 (피벗)은 단건만 add 메서드를 통해 삽입한다.

public static ArrayList<Integer> splitFunc(ArrayList<Integer> dataList) {
            if (dataList.size() <= 1) {
                return dataList;
            }
            int pivot = dataList.get(0);
            ArrayList<Integer> leftArr = new ArrayList<>();
            ArrayList<Integer> rightArr = new ArrayList<>();
            for (int i = 1; i < dataList.size(); i++) {
                if (dataList.get(i) > pivot) {
                    rightArr.add(dataList.get(i));
                } else {
                    leftArr.add(dataList.get(i));
                }
            }
            ArrayList<Integer> mergedArr = new ArrayList<>();
            mergedArr.addAll(splitFunc(leftArr));
            mergedArr.add(pivot);
            mergedArr.addAll(splitFunc(rightArr));
            return mergedArr;
        }

• 내림차순으로 정렬하고 싶다면 반대로 동작하도록 하면 된다.

퀵 정렬의 시간복잡도

• 병합정렬과 유사하다. 시간복잡도는 O(n logn) 이 된다.
  • 최악의 경우에는 이미 정렬된 배열에서 pivot 이 가장 크거나 , 가장 작으면 가장 큰 시간이 소요된다.
  • 모든 데이터를 비교해야 하는 상황이 나올 수 있으므로 O(n^2)가 된다.
    • 1,2,3,4,5의 데이터를 퀵 정렬로 정렬한다면, 1 2345 2 345 3 45 이런 식으로 정렬하기 때문에 비효율적이다.

마무리

• 병합정렬과 퀵 정렬은 어떻게 봤을 때 비슷해 보입니다.
  • 병합 정렬은 더 이상 쪼갤 수 없을 때까지 쪼갠 후 정렬하며 병합한다면, 퀵 정렬은 쪼개면서 정렬을 하고 합치는 느낌입니다.
• 검색을 해보니 Collections의 sort는 병합정렬을 기반으로 한 팀 정렬 방식을 사용하고, Arrays의 sort는 듀얼피벗 퀵정렬 방식으로 정렬한다고 합니다.
  • 정렬 방법에 대해서 공부하면서 자바에서 어떠한 api 가 어떤 알고리즘을 구현해 제공해주는지 알고 각각 맞는 상황에 사용하는 게 관건인 것 같습니다 :D