[Algorithm] 재귀 함수

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다

 

✨ 개념

- 재귀 함수 : 자기 자신을 다시 호출하는 함수

- dfs를 실제로 구현할 때 자주 사용하므로 제대로 이해하고 넘어가는게 좋다

- 문제를 풀 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다

---

✨ 문제

24060번: 알고리즘 수업 - 병합 정렬 1

조건

1. N개의 서로 다른 양의 정수가 저장된 배열 A

2. 병합 정렬로 배열 A를 오름차순 정렬

3. 배열 A에 저장되는 K번째 수 구하기

---

✨ 풀이

- 병합 정렬은 아는데 막상 구현하려니 어려웠던 문제... (다른 사람 풀이 참조)

병합 정렬

- 분할 정복 기법 + 재귀함수 => 정렬 알고리즘

- 주어진 배열을 원소가 하나가 될 때까지 쪼개고 크기 순으로 재배열하며 원래 배열 크기로 합친다

 

접근

1. 가운데를 기준으로 쪼개기

2. 왼쪽 정렬

3. 오른쪽 정렬

4. 병합

코드

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

public class Main {

    static int[] A;
    static int[] tmp; // 정렬 후 저장 배열
    static int result = -1; // 결과 저장
    static int count = 0; // 저장 횟수를 저장하는 변수
    static int K; // 저장 횟수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 배열 A의 크기
        K = Integer.parseInt(st.nextToken()); // 저장 횟수

        A = new int[N];
        tmp = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) A[i] = Integer.parseInt(st.nextToken());

        merge_sort(A, 0, N-1);

        System.out.println(result);
    }

    // 배열 쪼개기 (오름차순 정렬)
    private static void merge_sort(int[] A, int p, int r) {
        if (count > K) return; // 저장 횟수가 진행 횟수보다 크면 return
        if (p < r) {
            int q = (p+r) / 2;
            merge_sort(A, p, q);
            merge_sort(A, q+1, r);
            merge(A, p, q, r);
        }
    }

    // 배열 병합
    private static void merge(int[] A, int p, int q, int r) {
        int i = p;
        int j = q+1;
        int t = 0;

        while (i <= q && j <= r) {
            if (A[i] <= A[j]) {
                tmp[t++] = A[i++];
            } else tmp[t++] = A[j++];
        }

        // 다 정렬하고 남은 경우
        while (i<=q) tmp[t++] = A[i++]; // 왼쪽 배열이 남은 경우
        while (j<=r) tmp[t++] = A[j++]; // 오른쪽 배열이 남은 경우

        i = p; t = 0;
        while (i<=r) {
            count++;

            if (count == K) {
                result = tmp[t];
                break;
            }

            A[i++] = tmp[t++];
        }
    }
}

---

✨ 참고 자료

https://velog.io/@gayeong39/%EB%B0%B1%EC%A4%80-24060-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%98%EC%97%85-%EB%B3%91%ED%95%A9-%EC%A0%95%EB%A0%AC-1-JAVA

https://velog.io/@gogumi4502/Java-%EB%B0%B1%EC%A4%80-24060-%EC%9E%AC%EA%B7%80

https://www.daleseo.com/sort-merge