재귀함수란?
- 재귀함수 : 자기자신을 호출하는 것
- 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);
}
}
BackEnd Developer