[코테] 순차/이진 탐색과 그래프 이해

순차 탐색 [시간 복잡도 : O(N)]

• 순차적으로 탐색하는 알고리즘

public static boolean sequentialSearch(List<Integer> arr, int findData){
        for (int a : arr){
            if(a == findData){
                return true;
            }
        }
        return false;
    }

이진 탐색 [시간 복잡도 : O(logN)]

• 정렬된 리스트에서 검색 범위를 줄어가며 탐색하는 알고리즘

public static boolean binarySearch(List<Integer> arr, int findData){
        if(arr.size() == 1){
            if(arr.get(0) == findData){
                return true;
            }
            return false;
        }
        int middleData = arr.size()/2;
        if(arr.get(middleData) == findData){
            return true;
        }
        if(arr.get(middleData) > findData){
            return binarySearch(new ArrayList<>(arr.subList(0, middleData)), findData);
        }
        return binarySearch(new ArrayList<>(arr.subList(middleData, arr.size())), findData);
    }

- 참고 : https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

그래프 이해

• A, B, C 는 각각 Node(또는 Vertex) 이다.
• 각각의 노드를 이어주는선은 Edge 이다.
• 인접 Vertex : Edge 로 연결된 인접한 노드 (C의 인접 Vertex는 B)
• Edge 가 화살표가 있다면 방향 그래프, 아래 이미지와 같이 화살표가 없다면 무방향 그래프
• 단순 경로 : 한번 다녀간 Node는 방문하지 않는 경로(예 : C > B > A / C > B > A > B > C 는 단순 경로가 아니다)
• 가중치 그래프 : Edge 에 가중치(숫자)가 부여된 그래프
• 연결 그래프 vs 비연결 그래프 : 모든 노드가 연결되어 있다면 연결 그래프, 연결 안된 노드가 하나라도 있다면 비연결 그래프
• 차수 : 노드의 인접한 노드수