코딩 테스트 문제 정리 - 재귀 (Gold 이하 문제)

재귀(再歸)란?

주어진 문제를 해결하기 위하여 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식. 어떤 루틴이나 프러시저가 자기 자신을 반복적으로 호출하여 문제를 풀어 나가는 알고리즘으로, 이를 이용하기 위해서는 스택을 사용한다. 간단한 루틴을 풀 수 있지만, 처리 속도가 느리고 횟수가 지나치게 많으면 프로그램이 정지하기도 한다.
- 네이버 사전

 

재귀 문제의 대표적인 예로는 피보나치 문제가 있다.

 

위의 인용에서도 언급하고 있지만, 재귀라는 방식 자체가 시간복잡도를 줄여주는 방식은 아니다.

 

그러나 메모이제이션이라는 방식을 통해 중간 결과를 저장해두는 방식으로 처리한다면, 계산 횟수를 많이 줄일 수 있다.

 

또 다른 방법으로는 조건문을 통해서 불필요한 가지를 쳐내는 방식으로도 계산횟수를 줄인다. 

 

이번에는 문제 등급이 낮다보니 메모이제이션 방식보다는 특정 조건을 만족하면 재귀호출을 하는 방식을 주로 사용했다.

 

푼 문제는 다음과 같다.

 

1. 재귀함수가 뭔가요? : https://www.acmicpc.net/problem/17478

2. Z : https://www.acmicpc.net/problem/1074

3. 별찍기 - 10 : https://www.acmicpc.net/problem/2447

4. 별찍기 - 11 : https://www.acmicpc.net/problem/2448

 

재귀함수가 뭔가요? 재귀의 입문으로는 정말 괜찮은 문제라 생각한다.

 

다만 Z와 별찍기는 내가 생각했던 재귀랑은 조금 달랐었는데,

 

재귀를 가지를 뻗어나가며 탐색한다는 느낌보다는 큰 부분부터 작은 부분을 완성하기 위해 사용한다.

 

가지를 뻗어나가면서 찾는건 백 트래킹쪽에 가까운 방식인 것 같다.

 

1. 재귀함수가 뭔가요?

중간 중간 재귀의 횟수를 나타내는 prefix는 언더바다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
        recursive(0, N);
    }

    public static void recursive(int index, int N) {
        String str = "____";
        String padding = repeat(str, index);
        System.out.println(padding +"\"재귀함수가 뭔가요?\"");
        if(index == N) {
            System.out.println(padding + "\"재귀함수는 자기 자신을 호출하는 함수라네\"");
        } else {
            System.out.println(padding + "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.");
            System.out.println(padding + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.");
            System.out.println(padding + "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"");
            recursive(index+1, N);
        }
        System.out.println(padding + "라고 답변하였지.");
    }

    // Java 8 호환 문자열 반복 함수
    public static String repeat(String str, int count) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < count; i++) {
            sb.append(str);
        }
        return sb.toString();
    }
}

2. Z

2^N-1 * 위치마다 곱해지는 값을 알아야 풀 수 있다. 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int r = scanner.nextInt();
        int c = scanner.nextInt();
        scanner.close();

        int ans = findPosition(N, r, c);
        System.out.println(ans);
    }

    public static int findPosition(int N, int r, int c) {
        if (N == 0) return 0;

        int half = (int)Math.pow(2, N-1);
        int areaSize = half * half;

        if (r < half && c < half) {
            return findPosition(N - 1, r, c);
        }
        else if (r < half && c >= half) {
            return areaSize + findPosition(N - 1, r, c - half);
        }
        else if (r >= half && c < half) {
            return 2 * areaSize + findPosition(N - 1, r - half, c);
        }
        else {
            return 3 * areaSize + findPosition(N - 1, r - half, c - half);
        }
    }
}

3. 별찍기 - 10

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

public class Main {
    static char[][] arr = null;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        arr = new char[N][N];
        recursive(0,0, N);

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if (arr[i][j] != '*') {
                    sb.append(' ');
                } else {
                    sb.append(arr[i][j]);
                }
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }

    public static void recursive(int x, int y, int N) {
        if(N == 1) {
            arr[x][y] = '*';
            return;
        }

        recursive(x, y, N/3);
        recursive(x, y + N/3, N/3);
        recursive(x, y + 2 * N/3, N/3);
        recursive(x + N/3, y, N/3);
        recursive(x + 2 * N/3, y, N/3);
        recursive(x + N/3, y + 2 * N/3, N/3);
        recursive(x + 2 * N/3, y + N/3, N/3);
        recursive(x + 2 * N/3, y + 2 * N/3, N/3);
    }
}

4. 별찍기 - 11

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

public class Main {
    static char[][] arr = null;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        arr = new char[N][2 * N - 1]; // 열의 개수를 2*N-1로 수정

        recursive(0, N - 1, N);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 2 * N - 1; j++) { // 열의 범위를 수정
                sb.append(arr[i][j] == '*' ? '*' : ' ');
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }

    public static void recursive(int x, int y, int N) {
        if (N == 3) {
            arr[x][y] = '*';
            arr[x + 1][y - 1] = '*';
            arr[x + 1][y + 1] = '*';
            arr[x + 2][y - 2] = '*';
            arr[x + 2][y - 1] = '*';
            arr[x + 2][y] = '*';
            arr[x + 2][y + 1] = '*';
            arr[x + 2][y + 2] = '*';
            return;
        }

        int nextN = N / 2;
        recursive(x, y, nextN);
        recursive(x + nextN, y - nextN, nextN);
        recursive(x + nextN, y + nextN, nextN);
    }
}

 

재귀 문제는 구현 자체가 어려웠고, 문제를 보고 재귀 인지 떠올리기도 쉽지 않았다.

 

도와 주는 사람이 없었으면 손도 못 댈만한 문제들이 많았다.

 

특히 별 찍기는 알고리즘 자체 구현도 문제였지만 입출력 방식에서도 문제가 있어서 고통받았다.

2024.04.09 - [개발/코딩테스트] - 백준 문제에서 Java의 표준 입출력이 시간 초과가 나는 이유..

 

애초에 재귀가 시간복잡도를 잡기위한 방법이 아니어서 N이 크게 주어지지지 않았다.

 

별 찍기와 같은 경우는 문제를 푸는 접근법을 모르면 손도 못댈만한 문제들이라 주기적으로 와서 복기해야할 것 같다.