1. 재귀함수 (스택 프레임)
<hide/>
public class Main {
public void DFS(int n){
if(n == 0) return;
else{
System.out.println(n);
DFS(n-1);
}
}
public static void main(String[] args){
Main T = new Main();
T.DFS(5);
return ;
}
}Note)
- 실행 결과: 5 4 3 2 1 츨력
2. 이진수 출력 (재귀)
<hide/>
import java.util.Scanner;
public class Main {
public void DFS(int n){
if(n == 0) return;
else{
System.out.print(n + " ");
DFS(n / 2);
}
}
public static void main(String[] args){
Main T = new Main();
T.DFS(11);
return ;
}
}Note) 실행결과
3. 팩토리얼
<hide/>
import java.util.Scanner;
public 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();
System.out.println(T.DFS(5));
return ;
}
}Note) 실행 결과 : 120
- 5! = 5 * 4 * 3 * 2 * 1의 결과인 120이 출력된다.
4. 피보나치 재귀 (메모이제이션)
<hide/>
import java.util.Scanner;
public class Main {
static int [] fibo;
public int fibonacci(int n){
if(n == 1 || n == 2) return fibo[n] = 1;
else return fibo[n] = fibonacci(n - 2) + fibonacci(n - 1);
}
public static void main(String[] args){
Main T = new Main();
int n = 10;
fibo = new int[n + 1];
T.fibonacci(n);
for(int i = 1; i <= n ; ++i){
System.out.print(fibo[i] + " ");
}
return ;
}
}Note) 실행 결과: 1 1 2 3 5 8 13 21 34 55
- 배열과 for문으로 짜는 것이 재귀함수로 돌리는 것보다 성능이 좋다. (재귀를 돌리기에는 무겁다.)
-> 재귀는 호출될 때마다 스택에 프레임이 생기기 때문이다.
- 중소기업의 코딩테스트 질문으로 많이 나오기도 한다.
- static int 배열을 만들어 배열에 기록해두고 출력할 수 있다.
- 기록해두는 것을 "메모이제이션"이라고 한다.
- 메모이제이션을 활용하면 시간 복잡도가 확 줄어든다.
5. 이진트리순회(DFS : Depth-First Search)
Note)
- 전위 순회: 부모 -> 왼쪽 자식 -> 오른쪽 자식
- 중위 순회: 왼쪽 자식 -> 부모 -> 오른쪽 자식
- 후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 부모
(1) 전위순회
<hide/>
import java.util.*;
class Node{
int data;
Node lt, rt;
public Node(int val){
data = val;
lt = rt = null; //객체가 생성되는 순간 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);
}
}
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);
}
}Note) 전위순회 실행 결과 : 1 2 4 5 3 6 7
(2) 중위 순회
<hide/>
import java.util.*;
class Node{
int data;
Node lt, rt;
public Node(int val){
data = val;
lt = rt = null; //객체가 생성되는 순간 null 값
}
}
public class Main {
Node root;
public void DFS(Node root){
if(root == null) return;
else{
DFS(root.lt);
System.out.print(root.data + " ");
DFS(root.rt);
}
}
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);
}
}Note) 중위순회 실행 결과 : 4 2 5 1 6 3 7
(3) 후위순회
<hide/>
import java.util.*;
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{
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);
}
}Note) 후위순회 실행 결과 : 4 5 2 6 7 3 1
6. 부분집합 구하기 (DFS)
<hide/>
import java.util.*;
public class Main {
static int n;
static int[] ch;
public void DFS(int L){
if(L == n + 1){
String tmp = "";
for(int i = 1; i <= n; ++i){
if(ch[i] == 1) tmp += (i + " ");
// 자동으로 string형 변환
}
if(tmp.length() > 0) System.out.println(tmp);
}else{
ch[L] = 1; // 사용한다는 의미로 '1'표시
DFS(L + 1); // 왼쪽으로 뻗는다.
ch[L] = 0;
DFS(L + 1); // 오른쪽으로 뻗는다.
}
}
public static void main(String[] args){
Main T = new Main();
n = 3;
ch = new int[n + 1];
T.DFS(1);
}
}Note) 실행 결과
- 재귀함수, back tracking, BFS 코딩 테스트에 자주 나오니 꼭 해봐야한다.
????
7. 이진트리 레벨탐색(BFS : Breadth-First Search)
<hide/>
import java.util.*;
class Node{
int data;
Node lt, rt;
public Node(int val){
data = val;
lt = rt = null;
}
}
public class Main {
Node root;
public void BFS(Node root){
Queue<Node> Q = new LinkedList<>();
Q.offer(root);
int L = 0; // level
while(!Q.isEmpty()){
int len = Q.size();
System.out.print(L + " : ");
for(int i = 0 ; i < len; ++i){
Node cur = Q.poll();
System.out.print(cur.data + " ");
if(cur.lt != null) Q.offer(cur.lt);
if(cur.rt != null) Q.offer(cur.rt);
}
L++; // 레벨 증가
System.out.println();
}
}
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.BFS(tree.root);
}
}
Note) 실행 결과
- 너비 우선 탐색 (BFS)
- 0 레벨 : 1 ( root) / 1레벨 : 2 3 (root에서 한 번에 이동 가능) / 3레벨: 4 5 6 7 (root에서 두 번 만에 간다.)
-> 즉, root로부터의 거리라고 볼 수 있다.
- 다음 문제인 송아지 찾기 이해하려면 꼭 알아야한다.
8. 송아지 찾기1(BFS - 상태 트리 탐색)
<hide/>
import java.util.*;
public class Main {
int answer = 0;
int [] dis = {1, -1, 5}; // 전진, 후진
int[] ch; //방문 여부 체크 배열 , 0이면 방문하지 않은 곳
Queue<Integer> Q = new LinkedList<>();
public int BFS(int s, int e){
ch = new int[10001]; // 직선 좌표의 최댓값 10000
ch[s] = 1;
Q.offer(s);
int L = 0; // root node는 level이 0
while(!Q.isEmpty()){
int len = Q.size(); // level에 있는 원소의 개수
for(int i = 0; i < len; ++i){
int x = Q.poll();
for(int j = 0; j < 3; ++j){ //
int nx = x + dis[j]; // x의 자식노드를 찾는다.
if(nx == e) return L + 1;
// 자식 노드니까 1 더하기
if(1 <= nx && nx <= 10000 && ch[nx] == 0 ){
ch[nx] = 1; // 방문 체크
Q.offer(nx); // 체크 후 Q에 넣는다.
}
}
}
L++; // level 증가
}
return 0;
}
public static void main(String[] args){
Main T = new Main();
Scanner in=new Scanner(System.in);
int s = in.nextInt(); // 현수의 위치
int e = in.nextInt(); // 송아지의 위치
System.out.println(T.BFS(s, e));
return ;
}
}Note)
- 레벨은 점프 횟수라고 볼 수 있다.
- 최초로 발견되는 것이 최단거리
- 중복되는 수는 없다.
- 3level에서 최초로 14가 발견된다.
9. Tree 말단 노드까지의 가장 짧은 경로 (DFS)
<hide/>
import java.util.*;
class Node{
int data;
Node lt, rt;
public Node(int val){
data = val;
lt = rt = null; //객체가 생성되는 순간 null 값
}
}
public class Main {
Node root;
public int DFS(int L, Node root){
// root가 가리키는 말단 노드, level, 이동거리
if(root.lt == null && root.rt == null) return L;
//root가 말단 노드인지 확인
else return Math.min(DFS(L + 1, root.lt), DFS(L + 1, root.rt));
// 말단 노드가 아닐 때
}
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);
System.out.println(tree.DFS(0, tree.root));
}
}Note) 실행 결과: 1
- 경로의 길이 : 루트 -> 말단 노드까지 가는데 이동하는 횟수, (간선의 개수)
- 최단거리문제 -> BFS로 푼다.
-> DFS로 풀 수는 있지만 제약이 있다. (자식 노드가 하나만 있을 때 에러가 나기 때문이다.)
10. Tree 말단 노드까지의 가장 짧은 경로 (BFS)
<hide/>
import java.util.*;
class Node{
int data;
Node lt, rt;
public Node(int val){
data = val;
lt = rt = null; //객체가 생성되는 순간 null 값
}
}
public class Main {
Node root;
public int BFS(int L, Node root){
Queue<Node> Q = new LinkedList<>();
Q.offer(root);
int L = 0;
while(!Q.isEmpty()){
int len = 0;
for(int i = 0; i < len; ++i){
Node cur = Q.poll();
if(cur.lt == null && cur.rt == null )return L;
if(cur.lt != null) Q.offer(cur.lt); // 왼쪽 자식이 있을 때 넣어준다.
if(cur.rt != null) Q.add(cur.rt); //add offer 상관없음
}
++L;
}
return 0;
}
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);
System.out.println(tree.BFS(0, tree.root));
}
}Note) 실행 결과 : 1
11. 그래프와 인접행렬
- G(V, E) : G:그래프, V: vertax, E: edge
- 인접행렬: 연결된 노드에 대해 1로 표시, 연결되있지 않으면 0으로 표시한다.
1) 무방향 그래프
- 방향 개념이 없다.
- graph[a][b]와 graph[b][a] 에 모두 1 표시한다.
2) 방향 그래프
- 이동하는 방향이 정해져 있다.
- 행 -> 열로 해석한다.
-
3) 가중지 방향 그래프
- 간선에 가중치 까지 있다. (ex) 비용)
- graph[a][b] = 3 : a -> b로 가는데 가중치는 3이다.
12. 경로 탐색 (DFS) - 방향그래프가 주어지면 1번 -> N번 정점으로 가는 모든 경우의 수 출력
- 1번 노드 -> 5번까지 가는 경로
- 12345
- 125
- 13425
- 1345
- 1425
- 145
<hide/>
import java.util.*;
public class Main {
static int n, m , answer = 0;
static int[][] graph;
static int[] ch; // 방문 여부 체크
public void DFS(int v){
if (v == n) answer++;
else{ // 가능한 곳으로 계속 뻗어 나간다.
for(int i = 1; i <= n ; ++i){
if(graph[v][i] == 1 && ch[i] == 0){
ch[i] = 1;
DFS(i);
ch[i] = 0; // 취소 (체크를 풀어준다.)
}
}
}
}
public static void main(String[] args){
Main T = new Main();
Scanner in=new Scanner(System.in);
n = in.nextInt();
m = in.nextInt();
graph = new int[n+1][n+1]; // 인덱스 1 ~ n까지 쓰려고
ch = new int[n+1];
for(int i = 0; i < m; ++i){
int a = in.nextInt();
int b = in.nextInt();
graph[a][b] = 1; // 방향 그래프
}
ch[1] = 1; // 1번 노드 출발점 표시
T.DFS(1); //
System.out.println(answer);
}
}Note) 실행 결과
- 경로에서 방문 했던 곳은 방문하지 않는다.
- 노드 개수만큼 for문이 돈다.
- back할 때는 체크를 하나씩 풀어준다.
13. 경로탐색 (인접리스트, ArrayList)
- 1번 노드 -> 5번까지 가는 경로
- 12345
- 125
- 13425
- 1345
- 1425
- 145
// 오류
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5
<hide/>
package first;
import java.util.*;
public class Main3 {
static int n, m, answer=0;
static ArrayList<ArrayList<Integer>> graph;
static int[] ch;
public void DFS(int v){
if(v==n) answer++;
else{
for(int nv : graph.get(v)){
if(ch[nv]==0){
ch[nv]=1;
DFS(nv);
ch[nv]=0;
}
}
}
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
n=kb.nextInt();
m=kb.nextInt();
graph = new ArrayList<ArrayList<Integer>>();
for(int i=0; i<=n; i++){
graph.add(new ArrayList<Integer>());
}
ch=new int[n+1];
for(int i=0; i<m; i++){
int a=kb.nextInt();
int b=kb.nextInt();
graph.get(a).add(b);
}
ch[1]=1;
T.DFS(1);
System.out.println(answer);
}
}
Note)
- 정점의 개수가 많으면 ArrayList<>를 이용한다.
14. 그래프 최단거리(BFS) - 그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간건 수를 출력
<hide/>
import java.util.*;
class Main {
static int n, m, answer=0;
static ArrayList<ArrayList<Integer>> graph;
static int[] ch, dis;
public void BFS(int v){
ch[v]=1; // 1번에서 시작
dis[v]=0; // 출발 지점: 0
Queue<Integer> queue=new LinkedList<>();
queue.offer(v);
while(!queue.isEmpty()){
int cv=queue.poll(); //cv: current vertax (현재 지점)
for(int nv : graph.get(cv)){
if(ch[nv]==0){ // 방문 안 했으면
ch[nv]=1;
queue.offer(nv);
dis[nv]=dis[cv]+1;
}
}
}
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
n=kb.nextInt(); // 정점 개수
m=kb.nextInt(); // 간선 개수
graph=new ArrayList<ArrayList<Integer>>();
for(int i=0; i<=n; i++){
graph.add(new ArrayList<Integer>());
}
ch=new int[n+1];
dis=new int[n+1];
for(int i=0; i<m; i++){ // 인접 list 만든다.
int a=kb.nextInt();
int b=kb.nextInt();
graph.get(a).add(b);
}
T.BFS(1); // 1번 부터 시작한다.
for(int i=2; i<=n; i++){ // 2번 부터 출력
System.out.println(i+" : "+dis[i]);
}
}
}- 최단거리 = BFS문제 라고 본다.
- dis[v]: v까지 가는 최소 거리
- dis[nv] = dis[v] + 1
-입력
6 9
1 3
1 4
2 1
2 5
3 4
4 5
4 6
6 2
6 5
-출력
2 : 3
3 : 1
4 : 1
5 : 2
6 : 2
-> 2 : 3 => 3 ( 1 -> 4 -> 6 -> 2)
-> 3 : 1 => 1 (1 -> 3)
-> 4 : 1 => 1 (1 -> 4)
-> 5 : 1 (1 ->4 -> 5 )
'자료구조와 알고리듬 With Java > [인프런] Algorithm' 카테고리의 다른 글
| Chapter 08. DFS, BFS 활용 (0) | 2022.04.18 |
|---|---|
| Chapter 06. Sorting and Searching (정렬, 이분검색과 결정알고리즘) (0) | 2022.04.14 |
| Chapter 05. Stack, Queue (자료구조) (0) | 2022.04.13 |
| Chapter 04. HashMap, TreeSet (해쉬, 정렬지원 Set) (0) | 2022.04.12 |
| Chapter 03. Two pointers, Sliding window (0) | 2022.04.12 |