[재귀] 분할정복 문제 풀기

 

 

https://blog.encrypted.gg/919

실전 알고리즘 강좌 리뉴얼에 대한 안내

모든 알고리즘 공부는 이 사이트에서 하고 있다.

---

공부하게 된 계기

백준 1074 Z라는 문제를 푸는데 분할정복을 사용해서 푸는 거라는 것을 알고 공부하게 되었다.

 

 

정리

분할정복은 재귀를 사용한 알고리즘 기법이다. 따라서 재귀를 공부했다.

 

👩🏻‍💻생각해보자
재귀는 작은 문제로 부분으로 나눠서 내가 할 일과 나머지로 나누는 작업이 필요하다.

1. 메소드 역할(정의)를 명확하게 하자

2. 메소드 구현 : 자신이 해야할 일 + 나머지 작업

 

재귀 (recursion)

하나의 함수에서 자기 자신을 다시 호출해 작업 수행

다시 호출할 때 현재 함수에서의 입력값보다 더 작은 값을 인자로 넘겨주어야함

기저 조건 : 함수의 입력값이 일정 크기 이하일 때는 바로 반환(base condition)

반복문으로 구현했을 때에 비해 메모리/시간에서는 손해

계산한 것을 중복해서 계산해 비효율적

시간복잡도 O(1.618^k) : k번째 값을 구할 때 (k에 대한 지수함수 만큼의 시간이 걸린다.)

base condition 분할정복 풀이를 보면서 나왔던 단어였는데 개념을 공부하면 아는 내용이었네!

z에서는 0으로 나눌 수 없으니까 1사분면에 해당하면 바로 return해주는 부분에 해당하려나

 

재귀 사용시 주의사항

1. 함수가 입력에 대해 어디까지 연산을 수행할지

2. 어떤 입력값을 다시 넘겨주어야 하는지

3. 꼭 재귀를 사용해야하는지 판단 (피보나치 수열X)

4. 깊이 들어가면 스택 메모리에 누적

5. 스택 메모리가 작게 제한된 문제는 반복문으로 풀이

6. 계산 값이 자료형 범위를 벗어나는지도 확인

스택 메모리에 제한이 있으면 20000~40000번 정도의 깊이를 가진 재귀함수가 runtime error 발생시킴

스택 메모리 제한을 없애자

https://blog.encrypted.gg/731?category=773649

[실전 알고리즘] 0x06강 - 재귀_구버전

시간복잡도 구하는 이 강의의 첫번째 강의를 다시 공부해야겠다.

 

예시로 이해하기

하노이탑 : n번째 원판을 이동하려면 n-1번째까지의 원판을 다른 기둥으로 옮겨야해.

a에서 b로 n개의 원판을 옮길 때,

public static void test(int a, int b, int n) {
    if (n == 1) {
      System.out.println(a + " " + b);
      return;
    }
    int c = 6 - a - b;
    test(a, c, n - 1);
    System.out.println(a + " " + b);// n번째 원판 옮기고(옮길때 출력)
    test(c, b, n - 1);
}

1. n-1번째부터 1번째 원판을 c로 옮기기

2. n번째 원판을 b로 옮기고

3. c에 있는 1~n-1까지의 원판을 b로 옮기기

 

1번에서 3번으로 3개의 원판을 옮길때

public static void main(String[] args) {
    test(1, 3, 3);
    System.out.println("done");
}

출력되는 순서 >>

1 3   // 첫번째 원판은 1에서 3으로

1 2   // 두번째 원판은 1에서 2로

3 2  // 3에 있는 첫번째 원판이 2로

1 3  // 세번째 원판이 목적지인 3으로

2 1  // 2에서 위에 있는 첫번째 원판이 1로

2 3 // 2에 있는 두번째 원판이 3으로(세번째 원판 위로)

1 3  // 1에 있는 첫번째 원판이 3으로

done // 끝

 

memoization

어떤 input에 의한 output을 반환하는지 기억해놓자

상태공간트리를 그려보고 중복되는 호출이 많다면 결과를 저장하는 memoi 사용

 

문제번호	백준 주소	발상 난이도	구현 난이도	풀이 날짜
1074	https://www.acmicpc.net/problem/1074	3	1	2020.08.26
2447	https://www.acmicpc.net/problem/2447	3	2
2448	https://www.acmicpc.net/problem/2448	3	3
1992	https://www.acmicpc.net/problem/1992	4	4

16684 문제는 한번 보기만 하라고 하셔서 제외했다. 난이도는 10을 기준으로 한다.