개발 다이어리

코드

//각 정점으로 가는 최소 이동 간선수
class 그래프최단거리BFS {
    static int n, m, answer=0;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    static int[] ch, dis;
    
    public void BFS2(int v){
        LinkedList<Integer> q = new LinkedList<Integer>();
        ch[v] = 1;
        dis[v] = 0;
        
        q.offer(v);
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            
            for(Integer next : graph.get(cur)) {
                if(ch[next] == 0) {
                    ch[next] = 1;
                    dis[next] = dis[cur]+1;
                    q.add(next);
                }
            }
        }
    }

    
    public static void main(String[] args){
        그래프최단거리BFS T = new 그래프최단거리BFS();
        n=6;//최대 노드
        ch=new int[n+1];
        dis=new int[n+1];
        int[] aArr= {1,1,2,2,3,4,4,6,6};
        int[] bArr= {3,4,1,5,4,5,6,2,5};
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for(int i=0; i<bArr.length; i++){
            int a= aArr[i];
            int b= bArr[i];
            graph.get(a).add(b);
        }
        T.BFS2(1);
        for(int i=1; i<=n; i++){
            System.out.println(i+" : "+dis[i]);
        }
        System.out.println(Arrays.toString(dis));
    }   
}

결과

1 : 0
2 : 3
3 : 1
4 : 1
5 : 2
6 : 2
[0, 0, 3, 1, 1, 2, 2]

시작 정점에서 각 정점으로 가는 최소 횟수

간선 시각화

ch체크를 적용한 상태 트리, 각 레벨 별 횡단은 Q에 저장된 노드다.

브레이크 포인트를 지정하고 디버깅 해보면, 확실히 알 수 있다.

코드

import java.util.*;

class 경로탐색인접리스트 {
    static int n, m, answer=0;
    static List<List<Integer>> graph = new ArrayList<List<Integer>>();
    static int[] ch;
    static Stack<Integer> s = new Stack<Integer>();
    
    public void DFS2(int v){
        if(v == n) {
            System.out.println(s);
            answer++;
        } else {
            for(Integer nx : graph.get(v)) {
                if(ch[nx]==0) {//첫방문
                    ch[nx] = 1;//방문함
                    s.push(nx);//로그용
                    DFS2(nx);
                    s.pop();
                    ch[nx] = 0;
                }
            }
        }
    }
    
    
    public static void main(String[] args){
        경로탐색인접리스트 T = new 경로탐색인접리스트();
        n=5; // 목표 목적지 노드
        ch=new int[n+1];
        // aArr와 bArr를 조합
        // 1->2  , 1->3  , 1->4 이렇게 내가 갈 경로 배열
        int[] aArr= {1,1,1,2,2,2,3,4,4};
        int[] bArr= {2,3,4,1,3,5,4,2,5};
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for(int i=0; i<bArr.length; i++){
            int a= aArr[i];
            int b= bArr[i];
            graph.get(a).add(b);
        }
        ch[1]=1;
        s.push(1);
        T.DFS2(1);
        System.out.println(answer);
    }   
}

결과

[1, 2, 3, 4, 5]
[1, 2, 5]
[1, 3, 4, 2, 5]
[1, 3, 4, 5]
[1, 4, 2, 5]
[1, 4, 5]
6

간선 정보 시각화

List<List<Integer>>  는 리스트 속에 리스트이다. 배열로 치환하면 int[][] 와 같은 2차원 배열 형태다.

ArrayList를 사용한 이유는 크기가 가변인 배열이기 때문이다.

최대 경로좌표가 10000*10000 라면 2차원 배열을 사용하면 메모리 낭비가 심하다.

반면에 ArrayList의 경우 크기가 부족하면 현재 크기에 1.5배에 해당하는 크기 배열을 새로 생성해서 사용한다.

즉, 필요한 크기 만큼만 사용한다.

코드

import java.util.*;

class Node{ 
    int data; 
    Node lt, rt; 
    public Node(int val) { 
        data=val; 
        lt=rt=null; 
    } 
} 
  
public class Tree말단노드까지의가장짧은경로BFS{ 
    Node root; 
    
    public int BFS2(Node root){ 
        Queue<Node> Q=new LinkedList<>();
        Q.offer(root);
        int L = 0 ;
        
        while(!Q.isEmpty()) {
            int len = Q.size();
            
            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.add(cur.lt);
                if(cur.rt != null) Q.add(cur.rt);
            }
            L++;
        }
        return 0;
    } 
    
    
    public int BFS(Node root){ 
        Queue<Node> Q=new LinkedList<>();
        Q.offer(root);
        int L=0;
        while(!Q.isEmpty()){
            int len=Q.size();
            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.offer(cur.rt);
            }
            L++;
        }
        return 0;
    } 
  
    public static void main(String args[]) { 
        Tree말단노드까지의가장짧은경로BFS tree=new Tree말단노드까지의가장짧은경로BFS(); 
        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(tree.root)); 
    } 
}

결과

1

자식 노드가 없으면 당연히 말단이다. 그리고 BFS탐색 특성상 가장 먼저 발견한 것이 가장 최단 거리이므로 바로 리턴한다.

코드

import java.util.*;

class BFS송아지찾기상태트리 {
    int answer=0;
    int[] dis={1, -1, 5};
    int[] ch;
    
    Queue<Integer> Q = new LinkedList<>();
    public int BFS2(int s, int e){
        ch = new int[10001]; // 상태체크 배열
        ch[s]=1; //시작위치 방문 체크
        int L = 0;
        Q.add(s); //시작 
        
        while(!Q.isEmpty()) {
            int length = Q.size();
            for (int i = 0; i < length; i++) {
                int v = Q.poll();
                for(int move : dis) {
                    int nextV = v+ move;
                    if(nextV == e) return L+1;//목적지 찾음
                    if(0<nextV && nextV <=10000 &&ch[nextV]==0) {//ch[nextV]==0 첫방문
                        ch[nextV] =1; //이제 방문 표시
                        Q.add(nextV);
                    }
                }
            }
            L++;
        }
        return 0;
    }
    
    

    public static void main(String[] args){
        BFS송아지찾기상태트리 T = new BFS송아지찾기상태트리();
        int start = 5; // 시작 위치
        int end = 14;  // 목적지 위치
        System.out.println(T.BFS2(start, end));
    }   
}

결과

3

앞 뒤로만 갈 수있다고 가정하고, 시작 위치에서 목적지까지 최소 회수를 찾는 문제다.

1~10000은 주어진 경계값으로 무시해도 된다.

핵심은 주어진 경계값 만큼에 상태값을 측정할 배열을 만들어 내가 방문한 곳인지 아닌지를 체크하는 것이다. 10001로 생성한 것은 배열이 0부터 시작이라 보기 편하게 1부터 사용하려고 한 것

ch 배열이 중요한 이유는 재방문을 줄여 시간복잡도 개선과 무한반복을 방지하기 위함이다.

위 상태트리에선 공간 문제로 5가 왜 큐에 저장이 안됐는지만 표시했다.

끝까지 탐색한다면 위 상태 노드를 만다고 종료할 것이다.

코드

package algorithm07;

import java.util.*;

class Node2{ 
    int data; 
    Node2 lt, rt; 
    public Node2(int val) { 
        data=val; 
        lt=rt=null; 
    } 
} 
  
public class BFS레벨탐색{ 
    Node2 root; 
    public void BFS(Node2 root){ 
        Queue<Node2> Q=new LinkedList<>();
        Q.add(root);
        int L=0;
        while(!Q.isEmpty()){
            // for문에서 Q.size()를 조건식으로 주면 메서드 이기 때문에 상태 변화에 따라 값이 변동된다.
            int len = Q.size(); 
            System.out.print(L+" : ");
            for(int i=0; i<len; i++){
                Node2 cur = Q.poll();
                System.out.print(cur.data+" ");
                if(cur.lt!=null) Q.add(cur.lt);
                if(cur.rt!=null) Q.add(cur.rt);
            }
            L++;
            System.out.println();
        }
    } 
    
    public static void main(String args[]) { 
        BFS레벨탐색 tree=new BFS레벨탐색(); 
        tree.root=new Node2(1); 
        tree.root.lt=new Node2(2); 
        tree.root.rt=new Node2(3); 
        tree.root.lt.lt=new Node2(4); 
        tree.root.lt.rt=new Node2(5); 
        tree.root.rt.lt=new Node2(6); 
        tree.root.rt.rt=new Node2(7);
        tree.BFS(tree.root); 
    } 
}

결과

0 : 1 
1 : 2 3 
2 : 4 5 6 7

L 을 기준으로 큐 자료구조를 사용하여 탐색해 나아간다.

DFS와 달리 큐를 사용해 탐색해 나아가므로 재귀호출을 하지 않는다.(큐 특징, FIFO, 선입선출)

위 예제에서 int size = Q.size(); 따로 변수로 빼서 사용한 이유는 Q.size()가 메서드이기 때문이다.

Q가 poll()한다면 Q의 상태가 변화했으므로 size()메서드도 변동된다. 

따라서 L별 최초 너비 탐색 직전에 size() 상태를 저장해 놓고 같은 L에 속하는 모든 노드를 탐색하게 된다.

왜 큐 자료구조와 size() 메서드를 상태 값을 따로 로컬 변수로 저장해 반복문을 더 사용하는지 알아보자

현재 데이터 구조는 위와 같다.

L 이 0일 때는 문제 없어보인다.

L이 1일때 Q는 [2,3]을 저장하고 있고, 우리가 원하는 것은 이 과정에서 다음 탐색 L 2 노드데이터인 4,5는 다음에 처리하고 싶을 것이다.

그렇기에 L 값이 변하고 최초 너비 탐색 시 size()값을 저장하여 사용하는 것이다.

또한 큐 특성상 선입선출이므로 앞자리부터 사용하기에 큐를 사용하는 것이다.

엄밀히 말하면 선입선출은 배열을 기반으로 한 ArrayList로 사용은 가능하지만 빈 공간 메꾸는 작업으로 엄청난 비효율이 발생하게 된다. 따라서 LinkedList를 사용한 것이다.

L1의 노트 3 까지 다 탐색한다면 비로소 for문 조건식이 false가 되며, 다음 L++ 너비를 탐색하게 된다.

코드

class Main {
	static int n;
	//체크 배열
	static boolean[] ch;
	public void DFS(int L){
		if(L==n+1){
			String tmp="";
			for (int i = 1; i < ch.length; i++) {
				tmp += ch[i]==true? i+" " : "";
			}
			System.out.println(tmp);
		}
		else{
			ch[L]=true;
			DFS(L+1);
			ch[L]=false;
			DFS(L+1);
		}
	}

	public static void main(String[] args){
		Main T = new Main();
		n=3;
		//단순히 인덱스 0을 버리기 위한 보정값
		ch= new boolean[n+1];
		T.DFS(1); //breakpoint
	}	
}

결과

1 2 3 
1 2 
1 3 
1 
2 3 
2 
3

전위 순회하는 과정에는 전부 ch를 true로 준다.

전위 순회끝나고 중위순회 부분에서 ch를 false로 준다.

반드시 breakpoint를 지정하고 ch[] 변화를 알아보는 것이 좋다.

코드

import java.util.ArrayList;
import java.util.List;

class Node {
	int data;
	Node lt, rt;

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

public class Main {
	Node root;

	List<Integer> list1 = new ArrayList<Integer>();
	List<Integer> list2 = new ArrayList<Integer>();
	List<Integer> list3 = new ArrayList<Integer>();

	public void DFS(Node root) {
		if (root == null)
			return;
		else {
			list1.add(root.data);// 전위 순회
			DFS(root.lt);
			list2.add(root.data);// 중위 순회
			DFS(root.rt);
			list3.add(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);

		System.out.println(tree.list1);
		System.out.println(tree.list2);
		System.out.println(tree.list3);
	}
}

결과

[1, 2, 4, 5, 3, 6, 7]
[4, 2, 5, 1, 6, 3, 7]
[4, 5, 2, 6, 7, 3, 1]

무조건 위 순서로 순회하게 된다. 

여기서 핵심은 순회 시 어떤 시점에 로직을 넣느냐에 따라 전위-중위-후위 순회가 결정된다.

특히 후위순회는 더욱 중요한 것이 특성상 좌항을 모두 순회하고, 우항을 모두 순회하고 마지막으로 가운데 값으로 돌아온다.  이런 특성을 이용해 머지정렬 같은 것을 구현한다.

코드

import java.util.*;
class Main {
	public static void binarySearch(){
		final int SIZE = 1_000_000; // 사이즈를 가차없이 100배씩 늘려보면, 이분검색의 진가를 알 수 있다.
		long startTime = 0L;
		
		int[] arr = new Random().ints(1,Integer.MAX_VALUE)
			.distinct()
			.limit(SIZE)
			.sorted()  //이분 검색은 반드시 정렬이 필요하다.
			.toArray();
		int target = arr[new Random().nextInt(SIZE-1)];
		startTime = System.nanoTime();
		int key = Arrays.binarySearch(arr, target);
		System.out.println("라이브러리 사용 - key: "+key+", value:"+arr[key]);
		System.out.println("소요시간 : "+(System.nanoTime()-startTime)+"나노초");
		
		int lt = 0;
		int rt = arr.length-1;
		int count = 0;
		
		System.out.println("찾아보자!! - " + target);
		
		startTime = System.nanoTime();
		while(lt<=rt) {
			int mid = (lt+rt)/2;
			count ++;
			System.out.println("lt:"+lt+", rt:"+rt+", mid:"+mid+", arr[mid]:"+arr[mid]);
			if(target == arr[mid]) {
				System.out.println("목표숫자 : "+target+", "+count+"번 만에 찾음!!!");
				System.out.println("소요시간 : "+(System.nanoTime()-startTime)+"나노초");
				break;
			}else if(target < arr[mid]) {
				rt = mid -1;
			}else {
				lt = mid +1;
			}
		}
	}
	
	public static void main(String[] args){
		binarySearch();
	}
}

결과

이분검색은 사이즈가 배로 늘어도 그만큼 검색속도가 느려지지 않는다.

코드

class Main {
	
	static int stackFrame(int n){
		if(n<=2) return 1;
		else return stackFrame(n-2)	+stackFrame(n-1);
	}
	
	
	public static void main(String[] args){
		int n=10;
		
		long start = System.nanoTime();
		for(int i=1; i<=n; i++) System.out.print(Main.stackFrame(i)+" ");
		System.out.println();
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		
		start = System.nanoTime();
		int[] intArr = useArray(n);
		System.out.println(Arrays.toString(intArr));
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		
	}

	private static int[] useArray(int n) {
		int[] intArr = new int[n];
		for(int i=1; i<=n; i++) {
			if(i<=2) {
				intArr[i-1] = 1;
			} else {
				intArr[i-1] = intArr[i-2]+intArr[i-3];
			}
		}
		return intArr;
	}	
}

결과

1 1 2 3 5 8 13 21 34 55 
총 소요 시간 : 242100
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
총 소요 시간 : 48000

단순 재귀 호출로는 값이 클 수록 매번 이전 값을 계산하느라 시간 소요가 기하급수적으로 증가한다.

반면에 배열은 이전 값을 재귀적으로 구하지 않으니 값 계산 속도는 선형적으로 증가한다.

import java.util.Arrays;

class Main {
	static int cnt = 0;
	
	static int stackFrame(int n){
		cnt++;
		if(n<=2) return 1;
		else return stackFrame(n-2)	+stackFrame(n-1);
	}
	
	
	public static void main(String[] args){
		int n=45;
		
		long start = System.nanoTime();
		for(int i=1; i<=n; i++) System.out.print(Main.stackFrame(i)+" ");
		System.out.println();
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		System.out.println("총 호출 수 : "+cnt);
		
		cnt=0;
		start = System.nanoTime();
		int[] intArr = useArray(n);
		System.out.println(Arrays.toString(intArr));
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		System.out.println("총 반복 수 : "+cnt);
		
	}

	private static int[] useArray(int n) {
		int[] intArr = new int[n];
		for(int i=1; i<=n; i++) {
			cnt++;
			if(i<=2) {
				intArr[i-1] = 1;
			} else {
				intArr[i-1] = intArr[i-2]+intArr[i-3];
			}
		}
		return intArr;
	}	
}

몇 번 호출되는지 카운트 해봤다.

재귀 호출로 매 번 계산은 비효율적이니 상태값을 저장할 배열을 생성해 적용해보자

import java.util.Arrays;

class Main {
	static int cnt = 0;
	static int[] stackArr;
	
	static int stackFrame(int n){
		cnt++;
		if(n<=2) return 1;
		else return stackFrame(n-2)	+stackFrame(n-1);
	}
	
	static int stackFramePlusArray(int n){
		cnt++;
		if(stackArr[n]>0) return stackArr[n];
		if(n<=2) return stackArr[n]=1;
		else return stackArr[n]=stackFramePlusArray(n-2)+stackFramePlusArray(n-1);
	}
	
	private static int[] useArray(int n) {
		int[] intArr = new int[n];
		for(int i=1; i<=n; i++) {
			cnt++;
			if(i<=2) {
				intArr[i-1] = 1;
			} else {
				intArr[i-1] = intArr[i-2]+intArr[i-3];
			}
		}
		return intArr;
	}	
	
	public static void main(String[] args){
		int n=45;
		
		long start = System.nanoTime();
		for(int i=1; i<=n; i++) System.out.print(Main.stackFrame(i)+" ");
		System.out.println("\n반복문 + 재귀");
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		System.out.println("총 호출 수 : "+cnt);
		
		cnt=0;
		stackArr = new int[n+1];//인덱스 0자리 쓰기 싫어서 +1
		start = System.nanoTime();
		System.out.println("######################################");
		for(int i=1; i<=n; i++) System.out.print(Main.stackFramePlusArray(i)+" ");
		System.out.println("\n반복문 + 재귀(메모이제이션)");
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		System.out.println("총 호출 수 : "+cnt);
		
		cnt=0;
		Arrays.fill(stackArr, 0);
		start = System.nanoTime();
		Main.stackFramePlusArray(n);
		System.out.println("######################################");
		System.out.print(Arrays.toString(stackArr));
		System.out.println("\n재귀(메모이제이션)");
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		System.out.println("총 호출 수 : "+cnt);
		
		
		cnt=0;
		start = System.nanoTime();
		int[] intArr = useArray(n);
		System.out.println("######################################");
		System.out.println(Arrays.toString(intArr));
		System.out.println("반복문");
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		System.out.println("총 반복 수 : "+cnt);
		
	}

}

배열에 미리 계산된 값이 있다면, 더 이상 계산할 것 없이 그 값을 반환하도록 했다.

코드

class Main {
	public int DFS(int n){
		if(n==1) {
			System.out.print(1 + " = ");
			return 1;
		} else {
			System.out.print(n + " * ");
			return n*DFS(n-1);
		}
	}
	public static void main(String[] args){
		Main T = new Main();
		System.out.println(T.DFS(10));
		int sum = 1;
		for (int i = 1; i <= 10; i++) {
			sum *= i;
			if(i==10) System.out.print(i+" = " + sum);
			else System.out.print(i + " * ");
		}
		
		
	}	
}

결과

10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 = 3628800