재귀함수란?

  • 재귀함수 : 자기자신을 호출하는 것
  • stack을 이용

1. 재귀함수를 이용하여 1,2,3을 출력하라

  • dfs는 종료 조건을 명시해주면 된다
  • dfs는 호출하는 순서에 따라 나오는 값이 다르다.
    dfs (5)  // 출력하고 dfs(4)를 호출하는지, dfs(4)를 호출하고 출력하는지 확인하자.
    	dfs(4)
    		dfs(3)
            		dfs(2)
                   			dfs(1)
    // 재귀함수
    public void dfs(int n) {
        // 종료 조건
        if (n==0) return;
        else {
            // dfs 위치에 따라 -> 출력되는 순서가 다르다.
    
//            1.  1-2-3-4-5 출력 (출력 후 호출)
//            dfs(n-1);
//            System.out.print(n+" ");
            
//           2. 5-4-3-2-1 출력  (선 출력 후 호출)
            System.out.println(n+" ");
            dfs(n-1);

            System.out.print(n+" ");
            dfs(n-1);

        }
    }

2. 재귀함수로 2진수 구하기

  • 종료 조건 명시하기
  • dfs로 돌고 어느라인으로 돌아가는지 확인하기
  • 출력문의 위치에 따라 나오는 값이 달라진다.
  • 만약 출력문이 위에 있다면 반대로 나오고, 다 돌고 나서 출력을 하면 다음 라인으로 복귀하는 (출력문)을 만난다.
    public void dfs(int n) {
        // 종료 조건
        if (n==0) return;

        else {
            dfs(n/2);
            System.out.print(n%2+" ");
        }

    }

    public int solution(int n) {

        dfs(n);

        int answer=0;
        return answer;

    }

3. 재귀함수로 팩토리얼 구하기

  • 종료 조건을 명시한다.
  • 최종적으로 뭐가 호출되는지 확인하다
dfs(5)
	5*dfs(4)
    		4*dfs(3)
            		3*dfs(2)
                    		2*dfs(1) 
                            		dfs(1)은 1: return 
                                    
	public int dfs(n) {
    		if n==1: return 1;
            	else {
            		return n*dfs(n-1)
            	}
    
    	}

4. 재귀함수로 피보나치 수열 구하기

  • 종료 조건 1,2에서 끝나는거 명시하기
    -결과값 return 확인하기
    public int dfs(int n) {
        // 종료 조건
        if (n==1 || n==2) return 1;
        else {
            return dfs(n-1)+dfs(n-2);
        }

    }


    public int solution(int n) {
        int answer=0;

//        System.out.println(dfs(n));
        // 하나씩 출력
        for (int i=1;i<=n;i++) {
            System.out.print(dfs(i)+" ");
        }
        return answer;
    }
  • 개선된 피보나치 수열
    - 메모제이션을 이용, 배열에 저장하고 이미 계산된 것은 재사용한다.
public class Main4 {
    static int arr[]; // class 밑에 전역변수로 배열 생성

...

    // 개선된 dfs
    // 이미 나온 값을 배열에 기록하면서, 기록된값은 다시 계산 안하게 하기
    public int dfs2(int n) {
        //
        if (arr[n]!=0) {
            return arr[n];
        }

        // 종료 조건
        if (n==1 || n==2) return arr[n]=1;
        else {
            arr[n]=dfs(n-1)+dfs(n-2);
            return arr[n];
        }
    }

...
// Main함수에서는 전역변수로 만든거를 배열에 넣기, 이때 배열+1로 만들기
		arr=new int[n+1]

5. DFS로 부분집합 구하기

해결 방법

  • DFS로 깊이 우선 탐색 -> 재귀함수를 이용하여 노드 끝까지 파고들기
  • 배열 만들기 (n+1)
  • 사용했으면 배열의 값을 1로 변경하기 (사용한다)
  • 사용안했으면 배열의 값을 0으로 변경하기 (사용안한다)
  • 종료조건에서 출력하기
  • n이 3이라면 2X2X2 =8 (공집합 제외) -> 7
package inflearn.section7_dfs;
// 부분 집합 구하기
// 있다. 없다로 구분하기 (가지치기)
// 필요한 개수 +1 만큼 배열로 만들고 값 넣기


import java.util.*;

public class Main5 {

    // static 전역변수
    static int n;
    static int arr[];

    public void dfs(int k) {
        // 종료
        if (k==n+1) {
            // 출력
            String temp="";
            for (int i=1;i<=n;i++) {
                // 1인것만 temp에 넣는다.
                if (arr[i]==1) {
                    temp+=i+" ";
                }
            }

            // 공집합은 제외
            if (temp.length()>0) {
                System.out.println(temp);
            }
        }
        else {
            // 있다.
            arr[k]=1;
            dfs(k+1);
            // 없다.
            arr[k]=0;
            dfs(k+1);
        }
    }
    public void solution() {
        dfs(1);
    }
    public static void main(String[] args) {
        Main5 main=new Main5();
        Scanner scan=new Scanner(System.in);
        n=scan.nextInt();
        arr=new int[n+1];
        main.solution();
    }
}

6. DFS로 이진트리 순회 (깊이우선탐색)

해결방법

  • 전위, 중위, 후위 순회란?
    - 부모의 방문 위치에 따라 달라짐

    • 전위 순회 : 부모 -> 왼쪽 -> 오른쪽
    • 중위 순회 : 왼쪽 -> 부모 -> 오른쪽
    • 후위 순회 : 왼쪽 -> 오른쪽 -> 부모
  • 노드 그리기

class Node {
    int data;
    Node lt,rt;

    public Node(int val) {
        data=val;
        lt=rt=null;
    }
}

// Node 넣기
public class Main6 {
    Node root;

    public int solution() {
        int answer=0;
        return answer;

    }


    public static void main(String[] args) {
        Main6 main=new Main6();
        
        main.root=new Node(1);
        main.root.lt=new Node(2);
        main.root.rt=new Node(3);
        main.root.lt.lt=new Node(4);
        main.root.lt.rt=new Node(5);
        main.root.rt.lt=new Node(6);
        main.root.rt.rt=new Node(7);
        
        Scanner scan=new Scanner(System.in);

    }
}

전체 코드

package inflearn.section7_dfs;

import java.util.*;

class Node {
    int data;
    Node lt,rt;

    public Node(int val) {
        data=val;
        lt=rt=null;
    }

}

public class Main6 {
    Node root;

    public void dfs(Node root) {
        if (root==null) return; // 종료조건
        else {
            // 전위 순회 - 먼저 중간에 있는거 출력하고 왼쪽부터 끝까지 재귀로 호출한다음에 null 값이면 스택에서 pop
            System.out.println(root.data);
            dfs(root.lt);
            dfs(root.rt);

            // 중위 순회 - 왼쪽부터 쭉 들어가다가 null이면 종료하고 데이터 출력 후 
            dfs(root.lt);
            System.out.println(root.data);
            dfs(root.rt);
            
            // 후위 순회 
            dfs(root.lt);
            dfs(root.rt);
            System.out.println(root.data);
            
        }


    }

    public static void main(String[] args) {
        Main6 main=new Main6();

        main.root=new Node(1);
        main.root.lt=new Node(2);
        main.root.rt=new Node(3);
        main.root.lt.lt=new Node(4);
        main.root.lt.rt=new Node(5);
        main.root.rt.lt=new Node(6);
        main.root.rt.rt=new Node(7);

        Scanner scan=new Scanner(System.in);

    }
}
profile
BackEnd Developer

0개의 댓글