[JAVA] 알고리즘 문제풀이 입문 7-4, 7-5

강의: https://inf.run/w779

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의

 

7-4번 (재귀함수로 피보나치 수열 출력)

import java.util.Scanner;

public class Main{
  public void solution(int n, int pre1, int pre2){
    if(n == 0) return;
    else{
      System.out.print(pre2+" ");
      solution(--n, pre2, pre1 + pre2);
    }
  }

  public static void main(String args[]){
    Main T = new Main();
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    in.close();

    T.solution(n, 0, 1);
  }
}

(내가 짠 코드.)

 

 

for문과 재귀함수로 피보나치 수열을 구현할 때, 재귀함수는 stack Frame이 돌아가고 메모리 낭비가 심하기 때문에 성능은 for문으로 구현했을 때가 훨씬 뛰어남.

 

강사님이 짠 코드. n번째의 피보나치 수열을 출력하는데, 같은 번째의 피보나치 숫자를 반복적으로 구하게 되는 것을 피하기 위해 배열에 피보나치 수를 저장하고 값이 구해져 있으면 하위 피보나치 숫자를 구하지 않고 바로 해당 값을 리턴하게끔 만들었다.

import java.util.Scanner;

public class Main{
  static int[] fibo;

  public int solution(int n){
    if(fibo[n]>0) return fibo[n];   //배열에 n번째 피보나치 수가 있는지 확인. 있으면 해당 수 리턴
    if(n == 1 || n == 2) return fibo[n] = 1;  //첫번째, 두번째 수는 1 리턴
    else return fibo[n] = solution(n-2) + solution(n-1);    //배열에 n번째 수가 저장되어 있지 않으면 재귀함수로 구하기
  }

  public static void main(String args[]){
    Main T = new Main();
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    in.close();

    fibo = new int[n+1];
    T.solution(n);

    for(int i = 1; i <= n; i++){
      System.out.print(fibo[i] + " ");
      }
  }
}

 

 

7-5번(재귀함수로 이진트리 순회)

전위순회

class Node{
  int data;
  Node lt, rt;
  public Node(int val){
    data = val;
    lt = rt = null;
  }
}
public class Main{
  Node root;
  public void DFS(Node root){
    System.out.print(root.data + " ");
    if(root.lt!=null) DFS(root.lt);
    else return;
    if(root.rt!=null) DFS(root.rt);
    else return;
  }
  public static void main(String args[]){
    Main tree = new Main();
    tree.root = new Node(1);
    tree.root.lt = new Node(2);
    tree.root.rt = new Node(3);
    tree.root.lt.lt = new Node(4);
    tree.root.lt.rt = new Node(5);
    tree.root.rt.lt = new Node(6);
    tree.root.rt.rt = new Node(7);
    tree.DFS(tree.root);
  }
}

후위순회

class Node{
  int data;
  Node lt, rt;
  public Node(int val){
    data = val;
    lt = rt = null;
  }
}
public class Main{
  Node root;
  public void DFS(Node root){
    if(root.lt!=null) DFS(root.lt);
    else System.out.print(root.data + " ");
    if(root.rt!=null) DFS(root.rt);
    else return;
    System.out.print(root.data + " ");
  }
  public static void main(String args[]){
    Main tree = new Main();
    tree.root = new Node(1);
    tree.root.lt = new Node(2);
    tree.root.rt = new Node(3);
    tree.root.lt.lt = new Node(4);
    tree.root.lt.rt = new Node(5);
    tree.root.rt.lt = new Node(6);
    tree.root.rt.rt = new Node(7);
    tree.DFS(tree.root);
  }
}

 

강사님 코드로 하면 중위순회도 가능함

class Node{
  int data;
  Node lt, rt;
  public Node(int val){
    data = val;
    lt = rt = null;
  }
}
public class Main{
  Node root;
  public void DFS(Node root){
    if(root==null) return;
    else{
    //전위순회
      System.out.print(root.data + " ");
      DFS(root.lt);
      DFS(root.rt);
    //중위순회
      DFS(root.lt);
      System.out.print(root.data + " ");
      DFS(root.rt);
    //후위순회
      DFS(root.lt);
      DFS(root.rt);
      System.out.print(root.data + " ");
    }
  }
  public static void main(String args[]){
    Main tree = new Main();
    tree.root = new Node(1);
    tree.root.lt = new Node(2);
    tree.root.rt = new Node(3);
    tree.root.lt.lt = new Node(4);
    tree.root.lt.rt = new Node(5);
    tree.root.rt.lt = new Node(6);
    tree.root.rt.rt = new Node(7);
    tree.DFS(tree.root);
  }
}