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

목차

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

⭐요약

---

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

 

아래는 문제 링크임.

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

⭐문제 풀이

---

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

 

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

1. 완전탐색 (Brute Force)

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

Two Sum 문제를 완전탐색으로 해결하려면, 배열의 모든 요소를 이중 루프를 통해 순회하면서 두 수의 합이 타겟 값과 일치하는지 확인함.

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)

Two Sum 문제를 재귀로 해결하려면, 호출을 통해 배열을 순회함. 해시맵을 사용하여 이미 검사한 숫자를 저장하여 탐색 시간을 줄일 수 있음.

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^2)

Two Sum 문제를 BFS로 해결하려면 각 숫자를 노드로 생각해 탐색을 진행하여, 가능한 모든 숫자 쌍을 순차적으로 확인함. 큐를 사용하여 현재 인덱스에서 시작해 다른 모든 요소와의 합을 순차적으로 검사함.

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<Pair> 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^2)

Two Sum 문제를 DFS로 해결하려면, 모든 숫자 쌍의 조합을 깊이 우선으로 확인함. 재귀를 사용하여 각 숫자와 가능한 다른 숫자의 조합을 깊이 우선으로 탐색함.

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] + "]");
    }
}

⭐후기

---

• 다양한 알고리즘과 자료구조를 사용하여 어떻게 실제 문제 해결에 적용될 수 있는지 고민하게 됨. 각 방식들의 장단점을 직접 비교해보면서, 어떤 문제에서 어떤 접근 방식을 선택할지에 대해 알 수 있었음.
• 문제 해결 과정에서 발생할 수 있는 예외 상황을 어떻게 처리할지에 대해 고민함. 실제 코딩 테스트에서도 문제를 풀 수 있도록 많이 노력해야겠음.
• 이 문제에서는 재귀 방식으로 해시맵을 사용하는 것이 효율적인 것 같음. 각각의 요소를 한번씩만 검사하면 되기 때문인데, 시간 복잡도 계산하는 것이 아직 어려운 것 같음.

⭐참고자료

---

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

 

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