◀ PREV [1] [2] NEXT ▶ 부분집합 구하기(DFS) 자연수 n을 입력하면 1~n까지 원소를 갖는 부분집합을 출력하기 이진 트리 구조로 간 곳은 체크하면서 n+1에 도달하면 체크된 곳을 출력하기 왼쪽은 해당 인덱스를 체크하고 오른쪽은 체크하지 않으면서 진행한다 먼저 전역변수로 방문할 배열의 크기와 배열 방문 여부를 체크할 배열을 만들고 dfs 함수에서 n+1에 도달하면 방문 체크가 된 곳을 출력하고 아니면 왼쪽은 체크한 후 재귀, 오른쪽은 체크를 하지 않고 순회하게 만들어준다 public void DFS(int L){ //끝까지 왔으면 체크된 원소를 출력 if(L == n+1){ for(int i =1; i < L; i++){ if(ch[i] == 1) System.out.print(i + " "); } System.out.println(); } else .. 2023. 8. 15. 이진트리순회(DFS) 이진트리를 깊이우선탐색으로 돌때 전위, 중위, 후위 순회 3가지가 있다 1 2 3 4 5 6 7 으로 된 7개 노드가 있을떄 전위순회 부 - 왼 - 오 1 2 4 5 3 6 7 중위순회 왼 - 부 - 오 4 2 5 1 6 3 7 후위순회 왼 - 오 - 부 4 5 2 6 7 3 1 이 순서로 돈다 코드로 구현할 때는 Node 클래스와 Node 클래스를 재귀적으로 순회할 함수 2개를 만든다 class Node{ int data; Node lt, rt; //노드 생성자 public Node(int val) { data=val; //처음 생성시 좌우 노드는 null lt=rt=null; } } 데이터와 양쪽에 노드를 가지는 노드 클래스를 만들고 처음에 좌우 노드는 null로 만든다 public void DFS(.. 2023. 8. 15. 피보나치 수열 첫번째와 두번째는 1 세번째부턴 fib(n-1) + fib(n-2) 형태 그냥 재귀로 구현하면 효율이 많이 떨어진다 public int dfs(int n){ if(n == 1) return 1; else if(n == 2) return 1; else return dfs(n-1) + dfs(n-2); } 개선을 위해 메모리제이션(한번 사용한 값을 기억) 해두기 배열을 선언하고 dfs 함수를 사용하면 배열 해당 인덱스에 피보나치의 값이 들어가게 한다, 이미 그 값이 있으면 재귀를 하지 않고 배열 값을 리턴한다 if(fib[n] > 0 ) return fib[n]; if(n == 1) return fib[n] = 1; else if(n == 2) return fib[n] = 1; else{ return fib.. 2023. 8. 14. 팩토리얼 0까지 가면 *0으로 0이나 나와버리니까 1까지 갔을때 1 리턴 1 리턴하고 나서 dfs(2)의 2 리턴해서 1*2*3*4*5 형태로 다 출력된다 import java.util.*; class Main { public int dfs(int n){ if(n == 1) return 1; else { return n*dfs(n-1); } } public static void main(String[] args) { Main T = new Main(); Scanner in = new Scanner(System.in); int n = in.nextInt(); System.out.println(T.dfs(n)); } } 2023. 8. 14. 이진수 출력 10진수를 2진수로 바꾸는 방법 - 10진수를 더 이상 안나눠질때까지 2로 나누고 나머지를 거꾸로 출력하면 된다 11은 2진수로 1011 푸는 방법 재귀로 n/2 하면서 n이 0이 될때까지 탐색하고 n%2를 리턴한다 import java.util.*; class Main { public void dfs(int n){ if (n == 0) return; else { dfs(n / 2); System.out.print(n % 2 + " "); } } public static void main(String[] args) { Main T = new Main(); Scanner in = new Scanner(System.in); int n = in.nextInt(); T.dfs(n); } } 2023. 8. 14. 재귀함수(스택 프레임) n을 입력하면 1부터 n까지 출력해보자 반복문으로 스택에 차곡차곡 쌓아서 출력한다 함수 내부에 if, else로 리턴을 언제할지 잘 정의해두자 먼저 print로 출력하면 3 2 1 순서로 나오고 먼저 재귀를 돌면 3 2 1 0 까지 갓다가 0 리턴 1 리턴 2리턴 3 리턴 하면서 1 2 3 출력한다 if (n == 0) return; else { dfs(n-1); System.out.print(n + " "); } import java.util.*; class Main { public void dfs(int n){ if (n == 0) return; else { dfs(n-1); System.out.print(n + " "); } } public static void main(String[] args) .. 2023. 8. 14. 이전 1 2 다음