커뮤니케이션 스터디 발표 자료(재귀함수)

재귀함수의 개념

• 문제를 해결하는 알고리즘을 구현할 때 사용
• 함수가 자기 자신을 호출하는 방식으로 동작
• 전체 문제를 작은 부분의 문제로 나누고 반복 호출을 통해 모든 부분을 해결

재귀함수의 특징

• 기본 조건 : 재귀함수를 통해 해결하고자 하는 작은 부분 문제들은 해답이 존재해야 한다.
  • 기본 조건이 충족되면 재귀 호출을 중단하고 결과를 반환한다.
  • 부분 기본 조건의 합인 최종 기본 조건을 충족하면 전체 문제의 결과를 얻을 수 있다.
• 종료 조건 : 기본 조건을 충족한 재귀함수를 종료하기 위한 조건을 설정한다.
• 재귀함수 내부에서 자기 자신을 호출한다.
• 기본적으로 반복문보다 직관적이지 않은 구조를 띄고 있으나, 일부 알고리즘에서는 보다 직관적이고 간편한 구현이 가능하다.
  • 예시 : Factorial 계산, Fibonacci 수열, 이진 트리 순회 등
• 호출할 때마다 추가 메모리를 사용하므로, 반복문에 비해 공간 복잡도 측면에서 불리하다.
  • 극단적인 경우 Stack Overflow가 발생할 위험이 존재한다.
  • 기본 조건과 종료조건을 중요하게 다뤄야 한다.

재귀함수 작성

• 재귀함수를 작성하고, 적절한 기본 조건과 종료 조건을 설정한다.
• 재귀 호출이 반드시 종료 조건에 수렴하도록 한다(무한 loop에 주의).
• 함수 내부에서 자신의 함수를 반복 호출한다.
  • 이 호출 함수는 동시에 여러 개가 될 수 있으며, 이에 따라 각 함수의 경로가 나뉘게 된다.
    • 각 경로의 함수들은 종료 조건에 이르러 연쇄적인 호출의 반환이 이루어지며, 모든 함수들이 원래의 함수로 응답한 후에 재귀함수는 종료에 이르게 된다.

재귀함수의 활용

재귀함수를 이용하여 순열 목록을 구하는 코딩 테스트 문제 예시(DFS)

발표 순서 정하기

문제 설명

스터디원들은 제비 뽑기를 통해 발표 인원과 순서를 정하려 합니다. 스터디원들의 이름이 담긴 배열 participants와 발표할 인원의 수 r이 주어집니다. 제비 뽑기를 할 수 있는 모든 순서 목록이 담긴 배열을 오름차순으로 return하도록 solution 함수를 완성해 주세요.

입출력 예

participants	r	result
[나, 다, 가]	2	[[가, 나], [가, 다], [나, 가], [나, 다], [다, 가], [다, 나]]

Test code

import java.util.Arrays;
import java.util.Scanner;

public class Test {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int r = sc.nextInt();
        String[] participants = new String[n];

        for (int i = 0; i < n; i++) {
            participants[i] = sc.next();
        }

        Solution sol = new Solution();
        String[][] answer = sol.solution(participants, r);

        for (String[] ans : answer) {
            System.out.println(Arrays.toString(ans));
        }

    }

}

Solution

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

    private int n;
    private int r;
    String[] participants;
    boolean[] visited;
    String[] out;
    private List<String[]> permutatedList;

    public String[][] solution(String[] participants, int r) {

        n = participants.length;
        this.r = r;

        Arrays.sort(participants);
        this.participants = participants;

        visited = new boolean[n];
        out = new String[r];
        permutatedList = new ArrayList<>();

        generatePermutation(0);

        return (permutatedList.toArray(new String[permutatedList.size()][r]));

    }

    private void generatePermutation(int depth) {

        if (depth == r) {
            permutatedList.add(out.clone());
            return;
        }

        for (int i = 0; i < n; i++) {

            if (!visited[i]) {

                visited[i] = true;
                out[depth] = participants[i];
                generatePermutation(depth + 1);
                visited[i] = false;

            }

        }

    }

}

유사 문제 : 백준 실버3 15649번 N과 M (1)

15649번: N과 M (1)

조합 문제 예시

발표 인원 정하기

문제 설명

스터디원들은 제비 뽑기를 통해 발표 인원을 정하려 합니다. 스터디원들의 이름이 담긴 배열 participants와 발표할 인원의 수 r이 주어집니다. 제비 뽑기를 할 수 있는 스터디원 목록이 담긴 배열을 오름차순으로 return하도록 solution 함수를 완성해 주세요.

입출력 예

participants	r	result
[나, 다, 가]	2	[[가, 나], [가, 다], [나, 다]

Test code

import java.util.Arrays;
import java.util.Scanner;

public class Test {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int r = sc.nextInt();
        String[] participants = new String[n];

        for (int i = 0; i < n; i++) {
            participants[i] = sc.next();
        }

        Solution sol = new Solution();
        String[][] answer = sol.solution(participants, r);

        for (String[] ans : answer) {
            System.out.println(Arrays.toString(ans));
        }

    }

}

Solution

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

    private int n;
    private int r;
    String[] participants;
    boolean[] visited;
    String[] out;
    private List<String[]> combinatedList;

    public String[][] solution(String[] participants, int r) {

        n = participants.length;
        this.r = r;

        Arrays.sort(participants);
        this.participants = participants;

        visited = new boolean[n];
        out = new String[r];
        combinatedList = new ArrayList<>();

        generatecombination(0, 0);

        return (combinatedList.toArray(new String[combinatedList.size()][r]));

    }

    private void generatecombination(int depth, int start) {

        if (depth == r) {
            combinatedList.add(out.clone());
            return;
        }

        for (int i = start; i < n; i++) {

            if (!visited[i]) {

                visited[i] = true;
                out[depth] = participants[i];
                generatecombination(depth + 1, i + 1);
                visited[i] = false;

            }

        }

    }

}