자바 - 탐색 알고리즘, 그래프 알고리즘

탐색 알고리즘(Search Algorithms)

자바에서 사용되는 대표적인 탐색 알고리즘에는 선형 탐색(Linear Search)과 이진 탐색(Binary Search)이 있습니다.

두 알고리즘은 데이터 구조나 문제의 특성에 따라 각각의 장단점을 가지며, 적절히 사용해야 최적의 성능을 발휘할 수 있습니다.

 

선형 탐색(Linear Search)

특징:

• 배열이나 리스트에 있는 모든 요소를 처음부터 끝까지 순차적으로 탐색합니다.
• 탐색 대상이 없는 경우, 리스트의 끝까지 탐색을 계속합니다.
• 정렬되지 않은 데이터에도 사용할 수 있습니다.

시간 복잡도:

• 최악의 경우: O(n) (탐색해야 하는 리스트의 모든 요소를 검사해야 하기 때문)

장점:

• 구현이 간단하고, 데이터가 정렬되어 있을 필요가 없습니다.
• 데이터의 크기나 구조에 구애받지 않고 언제나 사용 가능합니다.

단점:

• 리스트의 크기가 커질수록 탐색 시간이 오래 걸립니다.
• 불필요한 비교가 많아 성능이 떨어질 수 있습니다.

예제

package algorithm.search;

public class LinearSearch {

    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // 타겟을 찾으면 인덱스 반환
            }
        }
        return -1; // 타겟을 찾지 못하면 -1 반환
    }

    public static void main(String[] args) {
        int[] nums = {4, 2, 7, 1, 3, 9};
        int target = 7;
        int index = linearSearch(nums, target);
        if (index != -1) {
            System.out.println("Target의 인덱스: " + index);
        } else {
            System.out.println("Target은 없습니다.");
        }
    }
}

 

알고리즘 동작 구조

• 시작부터 끝까지 하나씩 모든 요소를 비교하여 타겟 값을 찾습니다.
• 모든 요소를 확인해야 하기 때문에, 시간 복잡도가 O(n)입니다.

 

이진 탐색(Binary Search)

특징

• 데이터가 정렬된 상태에서만 사용할 수 있는 알고리즘입니다.
• 탐색 범위를 절반씩 줄여가며 타겟을 찾습니다.
• 중간 값을 기준으로 타겟이 있을 만한 위치를 결정하여 탐색합니다.

시간 복잡도

• 최악의 경우: O(log n) (탐색 범위가 계속 절반으로 줄어들기 때문)

장점

• 큰 데이터 집합에서도 빠른 탐색이 가능합니다.
• 데이터가 정렬되어 있을 경우 매우 효율적인 탐색이 가능합니다.

단점

• 반드시 데이터가 정렬되어 있어야 합니다.
• 데이터가 정렬되지 않은 경우, 이진 탐색을 사용하기 전에 정렬을 해야하는 추가 작업이 필요합니다.

예제

package algorithm.search;

public class BinarySearch {

    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // 타겟이 중간 값과 같은 경우
            if (arr[mid] == target) {
                return mid;
            }

            // 타겟이 중간 값보다 큰 경우, 오른쪽 반쪽을 탐색
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1; // 타겟을 찾지 못하면 -1 반환
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 7;
        int index = binarySearch(nums, target);
        if (index != -1) {
            System.out.println("Target의 인덱스: " + index);
        } else {
            System.out.println("Target은 없습니다.");
        }
    }
}

 

알고리즘 동작 구조

• 정렬된 배열에서 중간 값을 기준으로 타겟이 있는 반쪽만을 선택하여 탐색을 계속합니다.
• 반복적으로 탐색 범위를 절반으로 줄여 나가므로, 시간 복잡도가 O(log n)입니다.

 

결론

• 선형 탐색은 단순한 구조로 정렬되지 않은 데이터에서도 언제든지 사용할 수 있지만, 큰 데이터셋에서는 비효율적일 수 있습니다.
• 이진 탐색은 정렬된 데이터에서 매우 효율적이며, 큰 데이터셋에서도 성능이 뛰어납니다. 하지만 데이터가 정렬되어 있어야함 사용할 수 있는 제한이 있습니다.

 

그래프 알고리즘(Graph Algorithms)

자바에서 구현할 수 있는 대표적인 그래프 알고리즘에는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 다익스트라 알고리즘, 최소 신장 트리 알고리즘(크루스칼 알고리즘), 프림 알고리즘 등이 있습니다.

이 알고리즘들은 그래프의 탐색이나 최단 경로, 최소 신장 트리를 찾는 데 사용됩니다.

 

깊이 우선 탐색(Depth-First Search, DFS)

특징

• 그래프에서 한 노드에서 사용하여 가능한 깊이까지 탐색을 진행한 후, 더 이상 갈 곳이 없으면 되돌아와 다른 경로를 탐색하는 방식입니다.
• 스택 자료구조(재귀 호출이나 명시적 스택)를 이용하여 구현합니다.

시간 복잡도 : O(V + E) (V는 정점의 수, E는 간선의 수)

 

장점

• 메모리 사용이 적고, 재귀 호출을 통해 간단히 구현할 수 있습니다.
• 경로의 존재 여부를 쉽게 확인할 수 있습니다.

단점

• 그래프가 매우 깊거나 넓은 경우, 탐색 속도가 느려질 수 있습니다.
• 무한 루프에 빠질 위험이 있습니다(순환 그래프에서).

예제

package algorithm.graph;

import java.util.*;

public class DFS {
    /* Depth-First Search Algorithms*/
    // 인접 리스트를 사용하여 그래프를 표현
    private Map<Integer, List<Integer>> adjList = new HashMap<>();

    // 간선 추가 메서드
    public void addEdge(int v, int w) {
        // v 정점에 대해 w 정점으로의 간선을 추가
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(w);
    }

    // DFS 탐색 메서드
    public void DFS(int v, Set<Integer> visited) {
        // 현재 정점을 방문 표시
        visited.add(v);
        System.out.println(v + " ");

        // 현재 정점과 연결된 모든 정점들에 대해 재귀적으로 DFS 호출
        for (int neighbor : adjList.getOrDefault(v, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                DFS(neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        DFS graph = new DFS();

        // 그래프에 간선 추가
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        // 방문한 노드를 추적하기 위한 Set 사용
        Set<Integer> visited = new HashSet<>();
        System.out.println("DFS starting from vertex 2:");
        graph.DFS(2, visited);
    }
}

 

알고리즘 동작 구조

• 스택을 사용해 최대한 깊이 탐색을 진행한 후, 되돌아와서 다른 경로를 탐색합니다.

 

너비 우선 탐색(Breadth-First Search, BFS)

특징

• 시작 노드에서 인접한 모든 노드를 탐색한 후, 그 다음 단계의 인접 노드를 탐색하는 방식입니다.
• 큐 자료구조를 이용하여 구현합니다.

시간 복잡도: O(V + E)

 

장점

• 최단 경로를 찾을 수 있습니다(비가중치 그래프에서).
• 넓은 그래프에서도 무한 루프에 빠질 가능성이 적습니다.

단점

• 노드와 간선의 수가 많을 경우, 메모리 사용량이 증가할 수 있습니다.
• 깊은 그래프에서는 비효율적일 수 있습니다.

예제

package algorithm.graph;

import java.util.*;

public class BFS {
    /* Breadth-First Search, BFS*/
    // 인접 리스트를 사용하여 그래프를 표현
    private Map<Integer, List<Integer>> adjList = new HashMap<>();

    // 간선 추가 메서드
    public void addEdge(int v, int w) {
        // v 정점에 대해 w 정점으로의 간선을 추가
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(w);
    }

    // BFS 탐색 메서드
    public void BFS(int start) {
        // 큐를 사용하여 BFS를 구현
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        // 시작 정점을 큐에 추가하고 방문 표시
        queue.add(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            // 큐에서 정점을 꺼내어 출력
            int v = queue.poll();
            System.out.println(v + " ");

            // 현재 정점과 인접한 모든 정점을 탐색
            for (int neighbor : adjList.getOrDefault(v, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    // 방문하지 않은 정점을 큐에 추가하고 방문 표시
                    queue.add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        BFS graph = new BFS();

        // 그래프에 간선 추가
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        System.out.println("BFS starting from vertex 2:");
        graph.BFS(2);
    }
}

 

알고리즘 동작 구조

• 큐를 사용해 현재 노드의 인접한 모든 노드를 탐색한 후, 다음 단계로 넘어가 탐색을 계속합니다.

 

다익스트라 알고리즘(Dijkstra's Algorithm)

특징

• 가중치가 있는 그래프에서 시작 정점으로부터 모든 정점까지의 최단 경로를 찾는 알고리즘입니다.
• 우선순위 큐(힙 자료구조)를 이용하여 구현합니다.

시간 복잡도: ((V + E) log V)

 

장점

• 음의 가중치가 없는 그래프에서 최단 경로를 매우 효율적으로 찾을 수 있습니다.

단점

• 음의 가중치를 처리하지 못합니다.
• 복잡한 구현과 많은 메모리 사용을 요구할 수 있습니다.

예제

package algorithm.graph;

import java.util.*;

public class Dijkstra {
    // 우선순위 큐에 저장할 노드 클래스
    private static class Node implements Comparable<Node> {
        int vertex, weight;

        Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        // 우선순위 큐에서 가중치를 기준으로 정렬하기 위한 비교 메서드
        public int compareTo(Node other) {
            return Integer.compare(this.weight, other.weight);
        }
    }

    // 다익스트라 알고리즘 메서드
    public int[] dijkstra(int V, Map<Integer, List<Node>> adjList, int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] distance = new int[V];
        Arrays.fill(distance, Integer.MAX_VALUE); // 초기 거리를 무한대로 설정
        distance[start] = 0; // 시작 정점의 거리는 0
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll(); // 우선순위 큐에서 최소 거리를 가진 노드를 꺼냄
            int u = current.vertex;

            // 인접한 모든 노드에 대해 최단 거리를 갱신
            for (Node neighbor : adjList.getOrDefault(u, new ArrayList<>())) {
                int v = neighbor.vertex;
                int weight = neighbor.weight;

                // 새로운 최단 경로를 발견하면 업데이트하고 큐에 추가
                if (distance[u] + weight < distance[v]) {
                    distance[v] = distance[u] + weight;
                    pq.add(new Node(v, distance[v]));
                }
            }
        }

        return distance; // 각 정점까지의 최단 거리를 반환
    }

    public static void main(String[] args) {
        Dijkstra graph = new Dijkstra();
        Map<Integer, List<Node>> adjList = new HashMap<>();

        // 그래프에 간선 추가 (정점, 가중치)
        adjList.computeIfAbsent(0, k -> new ArrayList<>()).add(new Node(1, 4));
        adjList.computeIfAbsent(0, k -> new ArrayList<>()).add(new Node(2, 1));
        adjList.computeIfAbsent(2, k -> new ArrayList<>()).add(new Node(1, 2));
        adjList.computeIfAbsent(1, k -> new ArrayList<>()).add(new Node(3, 1));
        adjList.computeIfAbsent(2, k -> new ArrayList<>()).add(new Node(3, 5));

        int v = 4; // 정점의 수
        int start = 0; // 시작 정점
        int[] distances = graph.dijkstra(v, adjList, start);

        System.out.println("Shortest distances from vertex " + start + ":");
        for (int i = 0; i < distances.length; i++) {
            System.out.println("Vertex " + i + ": " + distances[i]);
        }
    }
}

 

알고리즘 동작 구조

• 시작 노드에서 모든 노드까지의 최단 경로를 우선순위 큐를 사용해 계산합니다.

 

최소 신장 트리(Minimum Spanning Tree, MST) 알고리즘

크루스칼 알고리즘(Kruskal's Algorithm)

특징

• 모든 간선을 가중치 순으로 정렬한 후, 사이클을 만들지 않는 간선을 하나씩 선택하여 최소 신장 트리를 구성합니다.
• 유니온 파인드(Union-Find) 자료구조를 이용하여 사이클을 검출합니다.

시간 복잡도: O(E log E)

 

장점

• 간선이 적은 희소 그래프에서 효율적입니다.
• 구현이 비교적 간단합니다.

단점

• 간선이 많은 그래프에서는 비효율적일 수 있습니다.

예제

package algorithm.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Kruskal {
    // 간선을 표현하는 클래스
    private static class Edge implements Comparable<Edge> {
        int src, dest, weight;

        Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }

        // 가중치를 기준으로 간선을 정렬하기 위한 비교 메서드
        public int compareTo(Edge other) {
            return Integer.compare(this.weight, other.weight);
        }
    }

    private int[] parent;

    // 유니온 파인드의 'find' 메서드
    private int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]); // 경로 압축 기법 사용
        }
        return parent[i];
    }

    // 유니온 파인드의 'union' 메서드
    private void union(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        parent[xRoot] = yRoot;
    }

    // 크루스칼 알고리즘 메서드
    public List<Edge> kruskal(int V, List<Edge> edges) {
        Collections.sort(edges); // 간선을 가중치 순으로 정렬
        parent = new int[V];
        for (int i = 0; i < V; i++) parent[i] = i; // 초기 부모 노드는 자기 자신

        List<Edge> mst = new ArrayList<>();
        for (Edge edge : edges) {
            int x = find(edge.src);
            int y = find(edge.dest);

            // 사이클이 생기지 않는 경우에만 간선을 추가
            if (x != y) {
                mst.add(edge);
                union(x, y);
            }
        }
        return mst; // 최소 신장 트리 반환
    }

    public static void main(String[] args) {
        List<Edge> edges = Arrays.asList(
                new Edge(0, 1, 10),
                new Edge(0, 2, 6),
                new Edge(0, 3, 5),
                new Edge(1, 3, 15),
                new Edge(2, 3, 4)
        );

        Kruskal graph = new Kruskal();
        List<Edge> mst = graph.kruskal(4, edges);

        System.out.println("Edges in MST:");
        for (Edge edge : mst) {
            System.out.println(edge.src + " - " + edge.dest + ": " + edge.weight);
        }
    }
}

 

알고리즘 동작 구조

• 간선을 가중치 순으로 정렬하여 사이클을 만들지 않도록 선택하면서 최소 신장 트리를 만듭니다.

 

프림 알고리즘(Prim's Algorithm)

특징

• 한 정점에서 시작하여 인접한 간선 중 최소 가중치의 간선을 선택하여 트리를 확장하는 방식입니다.
• 우선순위 큐를 사용하여 가장 작은 가중치의 간선을 선택합니다.

시간 복잡도: O(E log V)

 

장점

• 연결된 그래프에 적합하며, 노드 수가 적은 그래프에서도 효율적입니다.

단점

• 구현이 비교적 복잡합니다.

예제

package algorithm.graph;

import java.util.*;

public class Prim {
    // 우선순위 큐에 저장할 노드 클래스
    private static class Node implements Comparable<Node> {
        int vertex, weight;

        Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        // 우선순위 큐에서 가중치를 기준으로 정렬하기 위한 비교 메서드
        public int compareTo(Node other) {
            return Integer.compare(this.weight, other.weight);
        }
    }

    // 프림 알고리즘 메서드
    public void prim(int V, Map<Integer, List<Node>> adjList, int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] inMST = new boolean[V]; // 최소 신장 트리에 포함 여부를 추적
        pq.add(new Node(start, 0)); // 시작 정점을 큐에 추가

        while (!pq.isEmpty()) {
            Node node = pq.poll(); // 우선순위 큐에서 최소 가중치를 가진 노드를 꺼냄
            int u = node.vertex;

            if (inMST[u]) continue; // 이미 포함된 정점이면 건너뜀
            inMST[u] = true; // 현재 정점을 최소 신장 트리에 포함시킴
            System.out.print(u + " "); // 정점 출력

            // 현재 정점과 인접한 모든 정점을 탐색
            for (Node neighbor : adjList.getOrDefault(u, new ArrayList<>())) {
                if (!inMST[neighbor.vertex]) {
                    pq.add(new Node(neighbor.vertex, neighbor.weight)); // 인접 정점을 큐에 추가
                }
            }
        }
    }

    public static void main(String[] args) {
        Prim graph = new Prim();
        Map<Integer, List<Node>> adjList = new HashMap<>();

        // 그래프에 간선 추가 (정점, 가중치)
        adjList.computeIfAbsent(0, k -> new ArrayList<>()).add(new Node(1, 10));
        adjList.computeIfAbsent(0, k -> new ArrayList<>()).add(new Node(2, 6));
        adjList.computeIfAbsent(0, k -> new ArrayList<>()).add(new Node(3, 5));
        adjList.computeIfAbsent(1, k -> new ArrayList<>()).add(new Node(3, 15));
        adjList.computeIfAbsent(2, k -> new ArrayList<>()).add(new Node(3, 4));

        System.out.println("Prim's MST starting from vertex 0:");
        graph.prim(4, adjList, 0);
    }
}

 

알고리즘 동작 구조

• 하나의 시작 노드에서 인접한 최소 가중치 간선을 선택하며 트리를 확장해 나갑니다.