4강. 검색알고리즘

4. 검색 알고리즘

---

4.1 선형 검색

선형 검색(Linear Search)
선형 검색은 1950년대 초기에 처음 사용된 가장 기본적인 검색 알고리즘 중 하나입니다. 배열이나 리스트의 첫 번째 요소부터 마지막 요소까지 순차적으로 비교하여 원하는 값을 찾는 방식입니다.
선형 검색은 정렬되지 않은 배열이나 리스트에서 사용할 수 있는 가장 단순한 검색 방법입니다.

선형 검색의 시간 복잡도:
- 최악의 경우: \(O(n)\)
배열의 마지막 요소까지 탐색해야 하는 경우, 모든 요소를 확인해야 하므로 \(O(n)\)의 시간이 소요됩니다.

자바에서 선형 검색을 구현하려면, 배열과 반복문에 대한 기본적인 이해가 필요합니다. 배열은 연속된 메모리 공간에 요소들을 저장하며, 반복문은 배열의 각 요소를 순차적으로 탐색하는 데 사용됩니다.

// 선형 검색 예시
public class LinearSearch {
    public static int linearSearch(int[] arr, int x) {
        for (int i = 0; i < arr.length; i++) { // 배열의 각 요소를 순차적으로 탐색
            if (arr[i] == x) { // 원하는 값을 찾으면 인덱스를 반환
                return i;
            }
        }
        return -1; // 값을 찾지 못하면 -1 반환
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 10, 40}; // 정수 배열 초기화
        int x = 10; // 찾고자 하는 값
        int result = linearSearch(arr, x); // 선형 검색 수행
        if (result == -1) {
            System.out.println("Element not present"); // 값을 찾지 못한 경우
        } else {
            System.out.println("Element found at index " + result); // 값을 찾은 경우
        }
    }
}

4.2 이진 검색

이진 검색(Binary Search)
이진 검색은 1946년에 존 폰 노이만(John von Neumann)에 의해 개발된 알고리즘입니다. 이진 검색은 정렬된 배열에서 중앙값과 비교하여 검색 범위를 절반으로 줄여가며 원하는 값을 찾는 방식입니다.
이진 검색은 배열이 정렬되어 있을 때만 사용할 수 있으며, 검색 범위를 반으로 줄이는 방식으로 빠르게 원하는 값을 찾을 수 있습니다.

이진 검색의 시간 복잡도:
- 최악의 경우: \(O(\log n)\)
배열을 반으로 나누어 검색 범위를 좁혀가므로, \(O(\log n)\)의 시간이 소요됩니다.

자바에서 이진 검색을 구현하려면, 배열과 반복문, 그리고 조건문에 대한 이해가 필요합니다. 또한, 배열이 미리 정렬되어 있어야 하므로 정렬 알고리즘에 대한 이해도 필요합니다.

// 이진 검색 예시
public class BinarySearch {
    public static int binarySearch(int[] arr, int x) {
        int l = 0, r = arr.length - 1; // 검색 범위 초기화
        while (l <= r) { // 검색 범위가 유효한 동안 반복
            int m = l + (r - l) / 2; // 중앙값 계산

            // 중앙값이 찾는 값인 경우
            if (arr[m] == x)
                return m;

            // 찾는 값이 중앙값보다 큰 경우, 오른쪽 절반을 검색
            if (arr[m] < x)
                l = m + 1;

            // 찾는 값이 중앙값보다 작은 경우, 왼쪽 절반을 검색
            else
                r = m - 1;
        }
        return -1; // 값을 찾지 못하면 -1 반환
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 10, 40}; // 정수 배열 초기화
        int x = 10; // 찾고자 하는 값
        int result = binarySearch(arr, x); // 이진 검색 수행
        if (result == -1) {
            System.out.println("Element not present"); // 값을 찾지 못한 경우
        } else {
            System.out.println("Element found at index " + result); // 값을 찾은 경우
        }
    }
}

4.3 깊이 우선 검색(DFS)

깊이 우선 검색(Depth-First Search, DFS)
깊이 우선 검색은 1950년대에 에드거 다익스트라(Edger Dijkstra)에 의해 소개된 그래프 검색 알고리즘입니다. DFS는 가능한 깊숙이 내려가며 노드를 탐색한 후, 더 이상 갈 수 없으면 백트래킹(backtracking)하여 다음 경로를 탐색합니다.
DFS는 재귀 호출 또는 스택을 사용하여 구현할 수 있습니다. 자바에서는 재귀 호출을 사용하여 간단하게 구현할 수 있습니다.

DFS의 시간 복잡도:
- 그래프가 인접 리스트로 표현된 경우: \(O(V + E)\)
여기서 \(V\)는 정점의 수, \(E\)는 간선의 수입니다.

자바에서 DFS를 구현하려면, 그래프를 표현하는 방법(인접 리스트 또는 인접 행렬)에 대한 이해와 재귀 호출 또는 스택에 대한 이해가 필요합니다.

// 깊이 우선 검색(DFS) 예시
import java.util.*;

public class DFSSearch {
    private LinkedList adjLists[]; // 인접 리스트로 그래프 표현
    private boolean visited[]; // 방문 여부를 저장하는 배열

    // 그래프 초기화
    DFSSearch(int vertices) {
        adjLists = new LinkedList[vertices];
        visited = new boolean[vertices];

        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList();
    }

    // 간선 추가
    void addEdge(int src, int dest) {
        adjLists[src].add(dest);
    }

    // DFS 알고리즘
    void DFS(int vertex) {
        visited[vertex] = true; // 현재 노드를 방문 표시
        System.out.print(vertex + " ");

        Iterator ite = adjLists[vertex].listIterator();
        while (ite.hasNext()) {
            int adj = ite.next();
            if (!visited[adj])
                DFS(adj); // 재귀적으로 인접 노드 방문
        }
    }

    public static void main(String args[]) {
        DFSSearch g = new DFSSearch(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Following is Depth First Traversal (starting from vertex 2)");

        g.DFS(2); // 노드 2에서 시작하는 DFS
    }
}

4.4 너비 우선 검색(BFS)

너비 우선 검색(Breadth-First Search, BFS)
너비 우선 검색은 1945년에 콘래드 즈데릭(Konrad Zuse)에 의해 처음 소개된 그래프 검색 알고리즘입니다. BFS는 시작 정점에서 가까운 정점부터 차례대로 탐색하며, 큐(queue)를 사용하여 탐색합니다.
BFS는 최단 경로를 찾는 문제에서 유용하게 사용됩니다.

BFS의 시간 복잡도:
- 그래프가 인접 리스트로 표현된 경우: \(O(V + E)\)
여기서 \(V\)는 정점의 수, \(E\)는 간선의 수입니다.

자바에서 BFS를 구현하려면, 큐와 그래프를 표현하는 방법(인접 리스트 또는 인접 행렬)에 대한 이해가 필요합니다. 자바의 `LinkedList` 클래스는 큐로 사용될 수 있습니다.

// 너비 우선 검색(BFS) 예시
import java.util.*;

public class BFSSearch {
    private int V; // 정점의 수
    private LinkedList adj[]; // 인접 리스트로 그래프 표현

    // 그래프 초기화
    BFSSearch(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // 간선 추가
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // BFS 알고리즘
    void BFS(int s) {
        boolean visited[] = new boolean[V]; // 방문 여부를 저장하는 배열
        LinkedList queue = new LinkedList(); // 큐 초기화

        visited[s] = true; // 시작 정점을 방문 표시
        queue.add(s); // 시작 정점을 큐에 추가

        while (queue.size() != 0) {
            s = queue.poll(); // 큐에서 정점을 하나 제거
            System.out.print(s + " ");

            Iterator i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true; // 인접 정점을 방문 표시
                    queue.add(n); // 인접 정점을 큐에 추가
                }
            }
        }
    }

    public static void main(String args[]) {
        BFSSearch g = new BFSSearch(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Following is Breadth First Traversal (starting from vertex 2)");

        g.BFS(2); // 노드 2에서 시작하는 BFS
    }
}

---

해시태그: #알고리즘 #Algorithm #프로그래밍 #Programming #컴퓨터과학 #ComputerScience #코딩 #Coding #검색 #Search #선형검색 #LinearSearch #이진검색 #BinarySearch #깊이우선검색 #DFS #너비우선검색 #BFS #Java #자바 #코딩공부 #개발자 #Developer