📅 2023년 12월 29일

[알고리즘 2일차]

33일차: 주요 알고리즘 (2)

완전 탐색 : BFS (넓이 우선 탐색)

public class BFS_ListGraph {
    static List<List<Integer>> list = new ArrayList<>();
    static boolean[] visited;
    public static void main(String[] args) {
        int[][] input = {
                {0,1},
                {0,2},
                {1,3},
                {2,3},
                {2,4},
        };
        visited = new boolean[input.length];
        for(int i = 0; i<input.length; i++){
            list.add(new ArrayList<>());
        }
        for (int[] a : input ){
            addEdge(a[0],a[1]);
        }
        bfs(0);
    }
    static void addEdge(int a , int b){
        list.get(a).add(b);
        list.get(b).add(a);
    }
    static void bfs(int start){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        while (!queue.isEmpty()){
            int next = queue.poll();
            System.out.println(next);
            for(int target : list.get(next)){
                if(!visited[target]){
                    visited[target] = true;
                    queue.add(target);
                }
            }
        }
    }
}

프로그래머스 문제 : 가장 먼 노드
프로그래머스 문제 : 게임 맵 최단거리

이진 탐색

public class Binary_Search {
    public static void main(String[] args) {
        // 정렬이 되어 있어야 이진탐색 가능
        int[] arr = {1,3,5,7,9,11,13,15,17,19};
        System.out.println(binarySearch1(3, 0, arr.length-1, arr));
        System.out.println(binarySearch2(3, 0, arr.length-1, arr));
    }
    static int binarySearch1(int key, int low, int high, int[] arr) {
        if(low <= high) {
            int mid = (low + high) / 2;
            if(key == arr[mid]) {
                return mid;
            } else if(key < arr[mid]) {
                return binarySearch1(key ,low, mid-1, arr);
            } else {
                return binarySearch1(key, mid+1, high, arr);
            }
        }
        return -1;
    }
    static int binarySearch2(int key, int low, int high, int[] arr) {
        while(low <= high) {
            int mid = (low + high) / 2;
            if(key == arr[mid]) {
                return mid;
            } else if(key < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}

프로그래머스 문제 : 입국심사

github java 실습 내용