[자료구조/알고리즘] LeetCode Two Sum - 완전탐색, 재귀, BFS, DFS로 풀기 (Java)

목차

📅진행기간: 2024년 2월 5일 ~ 2024년 9월 20일

⭐ 요약

---

이 글에서는 자료구조/알고리즘 강의에서 진행한 LeetCode의 Two Sum 문제를 완전탐색, 재귀, 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)으로 해결한 방법을 설명한다. 모든 코드는 Java로 작성했으며, 해답을 찾지 못한 경우를 고려하여 IllegalArgumentException을 발생시키도록 예외 처리를 적용했다.

 

아래는 문제 링크이다.

https://leetcode.com/problems/two-sum/

⭐ 문제 설명

---

▲ 자료구조/알고리즘 Zoom 강의

 

Two Sum 문제는 주어진 정수 배열 nums에서 두 숫자를 찾아 합이 target과 일치하는지를 확인하고, 일치하는 두 숫자의 인덱스를 반환해야 한다. 고려해야 할 점은 정확히 하나의 해결책이 존재하며, 같은 요소를 두 번 사용할 수 없다는 것이다.

풀이 방법	시간 복잡도	핵심 자료구조
완전탐색 (Brute Force)	O(n²)	이중 루프
재귀 (Recursion)	O(n)	HashMap
BFS (너비 우선 탐색)	O(n²)	Queue
DFS (깊이 우선 탐색)	O(n²)	재귀 스택

⭐ 문제 풀이

---

1. 완전탐색 (Brute Force)

• 가능한 모든 경우의 수를 탐색하여 문제의 해답을 찾는 방법이다.
• 장점: 구현이 간단하며, 모든 가능성을 탐색한다.
• 단점: 데이터셋이 큰 경우에 비효율적이다.
• 시간 복잡도: O(n²)

배열의 모든 요소를 이중 루프로 순회하면서 두 수의 합이 타겟 값과 일치하는지 확인한다.

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = solution.twoSum(nums, target);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }
}

 

2. 재귀 (Recursion)

• 함수가 자기 자신을 호출하여 문제를 해결하는 방법이다. 작은 단위의 문제로 쪼개어 각각을 해결해 나가면서 전체 문제의 해답을 구한다.
• 장점: 복잡한 문제를 간단하고 명확하게 표현할 수 있으며, 코드가 직관적이다.
• 단점: 함수 호출에 따른 오버헤드가 발생하며 메모리 사용이 비효율적이다. 재귀 호출의 깊이가 깊어지면 스택 오버플로우가 발생할 수 있다.
• 시간 복잡도: O(n)

재귀 호출을 통해 배열을 순회한다. HashMap을 사용하여 이미 검사한 숫자를 저장하므로 탐색 시간을 O(n)으로 줄일 수 있다.

import java.util.HashMap;

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        return twoSumRecursive(nums, target, 0, new HashMap<>());
    }

    private int[] twoSumRecursive(int[] nums, int target, int index, HashMap<Integer, Integer> indexMap) {
        if (index == nums.length) {
            throw new IllegalArgumentException();
        }

        int complement = target - nums[index];
        if (indexMap.containsKey(complement)) {
            return new int[] {indexMap.get(complement), index};
        }

        indexMap.put(nums[index], index);

        return twoSumRecursive(nums, target, index + 1, indexMap);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = solution.twoSum(nums, target);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }
}

3. BFS (너비 우선 탐색)

• 그래프의 모든 노드를 너비를 우선으로 탐색하는 방법이다. 시작 노드에서 가까운 노드를 먼저 방문하고, 멀어질수록 나중에 방문한다.
• 장점: 최단 경로를 찾거나 문제의 단계별 해답을 찾는 데 적합하며, 모든 노드를 방문한다.
• 단점: 탐색해야 하는 노드의 수가 많을 경우 많은 메모리가 필요하다.
• 시간 복잡도: O(n²)

각 숫자를 노드로 생각하여 탐색을 진행한다. Queue를 사용하여 현재 인덱스에서 시작해 다른 모든 요소와의 합을 순차적으로 검사한다.

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    static class Pair {
        int index;
        int value;

        Pair(int index, int value) {
            this.index = index;
            this.value = value;
        }
    }

    public int[] twoSum(int[] nums, int target) {
        Queue queue = new LinkedList<>();

        for (int i = 0; i < nums.length; i++) {
            queue.add(new Pair(i, nums[i]));
        }

        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            for (int i = current.index + 1; i < nums.length; i++) {
                if (current.value + nums[i] == target) {
                    return new int[]{current.index, i};
                }
            }
        }

        throw new IllegalArgumentException();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = solution.twoSum(nums, target);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }
}

4. DFS (깊이 우선 탐색)

• 그래프의 모든 노드를 깊이를 우선으로 탐색하는 방법이다. 시작 노드에서 가능한 한 깊게 탐색하다가 더 이상 탐색할 수 없는 지점에 도달하면 이전 분기점으로 돌아가 다른 경로를 탐색한다.
• 장점: BFS에 비해 메모리 소비가 적고, 모든 가능한 경로를 탐색하며 해를 찾을 수 있다.
• 단점: 최단 경로를 보장하지 않으며, 탐색 속도가 BFS에 비해 느릴 수 있다. 탐색의 깊이가 깊어질수록 스택 오버플로우가 발생할 수 있다.
• 시간 복잡도: O(n²)

재귀를 사용하여 각 숫자와 가능한 다른 숫자의 조합을 깊이 우선으로 탐색하며, 모든 숫자 쌍의 조합을 확인한다.

public class Solution {

    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            int[] result = dfs(nums, target, i, i + 1);
            if (result != null) {
                return result;
            }
        }
        throw new IllegalArgumentException();
    }

    private int[] dfs(int[] nums, int target, int start, int next) {
        if (next == nums.length) {
            return null;
        }

        if (nums[start] + nums[next] == target) {
            return new int[]{start, next};
        }

        int[] directlyNext = dfs(nums, target, start, next + 1);
        if (directlyNext != null) {
            return directlyNext;
        }

        if (start < nums.length - 1) {
            return dfs(nums, target, start + 1, start + 2);
        }

        return null;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = solution.twoSum(nums, target);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }
}

⭐ 풀이 방법 비교

---

4가지 풀이 방법을 장단점 중심으로 비교하면 아래와 같다.

풀이 방법	시간 복잡도	장점	단점
완전탐색	O(n²)	구현이 단순함	데이터가 크면 비효율적임
재귀 + HashMap	O(n)	가장 효율적. 각 요소를 한 번만 검사함	재귀 깊이가 깊으면 스택 오버플로우 위험
BFS	O(n²)	단계별 탐색에 적합함	메모리 사용이 많음
DFS	O(n²)	BFS보다 메모리 소비가 적음	최단 경로 보장 안됨. 속도가 느릴 수 있음

⭐ 후기

---

• 다양한 알고리즘과 자료구조를 사용하여 동일한 문제를 여러 방식으로 해결해보면서, 각 방식의 장단점을 직접 비교할 수 있었다. 어떤 문제에서 어떤 접근 방식을 선택해야 하는지 판단하는 감각을 조금씩 키울 수 있었다.
• 문제 해결 과정에서 발생할 수 있는 예외 상황을 어떻게 처리할지에 대해 고민했다. 실제 코딩 테스트에서도 예외 케이스를 놓치지 않도록 꾸준히 연습해야겠다고 느꼈다.

⭐ 참고자료

---

1) hyehyes.log, "[알고리즘] 완전탐색", 2022.03.31, https://velog.io/@hyehyes/알고리즘-완전탐색

 

이 글은 패스트캠퍼스의 백엔드 개발 캠프에서 공부한 내용을 작성한 것입니다.