Pccp 준비하기 - 2 재귀 풀어보기

알고리즘 문제를 풀때 무조건 알아야하는 재귀 문제 2문제를 풀어보았다

재귀 호출의 깊이를 사실 정확히 생각해본적 없었는데 이번 책을 보며
10000이하로 유지시켜야 StackOverflowError가 나지 않는다는것을 알았다!

너무 많이 재귀 되면 메모리와 시간을 그만큼 사용하니 주의하자!

재귀 정의하기

이제부터 재귀 문제인것 같다면 3가지를 생각해서 정리한 뒤 코드를 작성하자

1. 재귀에서 문제가 나타내는게 무엇인지 정확히 파악하기
   문제에서 원하는 명확한 답과 의도를 파악하는게 중요하다!

2. 종료 조건을 생각하자
   재귀를 하염없이 돌릴 수 없기에 종료조건을 고민하자

3. 점화식을 작성하자
   가장 큰 상태가 어떤 과정을 거쳐 가장 작은 상태인 종료조건에 도달하는지 정의해보자!

---

쿼드 압축 후 개수 세기

문제 해설

0과 1로 이루어진 2의n승 정사각형 배열 arr이 주어질때 쿼드트리 방식으로 압축해보고
마지막에 남아있는 0과 1의 개수를 작성해보자

arr행의 개수는1024가 최대이며 각 행의 값은 0 또는 1입니다

일단 값의 범위 int형, 시간복잡도도 크게 생각 안해도 되는 크기의 정사각형이었습니다

3단계 작성하기 및 해결법

상태

하나의 상태는 정사각형 범위
부분문제 - 해당 상태가 나타내는 정사각형 범위를 압축했을때 남아있는 0과 1의 개수를 구하기

종료조건

가로 세로 사이즈가 주어졌을때 그 내부 값이 모두 0이거나 1일때

점화식

큰 문제를 작은 문제로 나눠야하는데
	(offsetX offsetY size) 를 나눠야한다면
    
	-> (offsetX, offsetY, size/2)
	-> (offsetX + size/2, offsetY, size/2)
	-> (offsetX + size/2, offsetY + size/2, size/2)
	-> (offsetX,  offsetY + size/2, size/2)

코드

class Solution {
    int answer[] = new int[2];
    
    public void quard(int[][] arr, int y, int x, int size) {
        boolean flag = true;
        for(int i = y; i < y + size; i++) {
            for (int j = x; j < x + size; j++) {
                if (arr[y][x] != arr[i][j]) {
                    flag = false;
                    break;
                }
            }
        }
        if (!flag) {
            int half = size / 2;
            //점화식 사용 부분
            quard(arr, y,      x,      half);
            quard(arr, y+half, x,      half);
            quard(arr, y,      x+half, half);
            quard(arr, y+half, x+half, half);
            
        }
        else {
            answer[arr[y][x]] += 1;
        }
        
    }
    public int[] solution(int[][] arr) {
        int x = 0;
        int y = 0;
        int size = arr.length;
        quard(arr, y, x, size);
        return answer;
    }
}

모음 사전

문제 설명 및 무식한(?) 방법

'A', 'E', 'I', 'O', 'U' 를 조합해서 최대 5자인 단어를 만들어 사전 순으로 인덱스 위치를 찾는 문제입니다.

보자마자 무식하게 다 구하기?를 시전하고 싶었는데 총 개수가

5 ** 1 + 5 ** 2 + 5 ** 3 + 5 ** 4 + 5 ** 5 = 3905개여서 빠르게 접었다...

3단계 작성하기 및 해결법

상태

제시된 문제를 상태로 보기 
상태는 현재까지 이어 붙인 단어

종료조건

단어 길이가 5자일때

점화식

word = word + (word + 'A') + (word + 'E') + (word + 'I') + (word + 'O') + (word + 'U')   

코드

import java.util.*;

class Solution {
    char [] CHARS = "AEIOU".toCharArray();
    List<String> list = new ArrayList<>();
    
    private void check(String word) {
        list.add(word);
        
        for (int i = 0; i < 5; i++) {
            String w = word + CHARS[i];
            if (w.length() <= 5) {
                check(w);
            }
        }
    }
    
    public int solution(String word) {
        check("");
        return list.indexOf(word);
    }
}