🚀 두 수의 합(Two Sum) 알고리즘 문제 풀이 | 알고리즘 & 영어 공부

기본 알고리즘 문제 중 하나인 "Two Sum" 문제를 해결하는 방법을 정리했습니다.
앞으로 올릴 게시물을 통해 알고리즘 사고력과 영어 문제 해석 능력을 동시에 키워보려고 합니다.

 

많은 관심 부탁드립니다.

---

1️⃣ 문제 설명 (Problem Statement)

📌 영어 지문 (Original Problem Statement)

Given an array of integers nums and an integer target,
return indices of the two numbers such that they add up to target.

🔹 you may not use the same element twice.
🔹 You may assume that each input would have exactly one solution.
🔹 You can return the answer in any order.

---

📌 한글 번역 (Korean Translation)

정수 배열 nums 와 정수 target 이 주어졌을 때,
배열 내에서 두 숫자의 합이 target이 되는 두 숫자의 인덱스를 반환하세요.

💡 유의할 점:
🔹  같은 숫자를 두 번 사용할 수 없습니다.
🔹 정답은 반드시 하나만 존재합니다.
🔹  정답의 반환 순서는 상관없습니다.

---

2️⃣ 예제 (Example)

Example	입력 (nums, target)	출력 (indices)	설명
1	[2, 7, 11, 15], 9	[0, 1]	nums[0] + nums[1] = 2 + 7 = 9
2	[3, 2, 4], 6	[1, 2]	nums[1] + nums[2] = 2 + 4 = 6
3	[3, 3], 6	[0, 1]	nums[0] + nums[1] = 3 + 3 = 6

---

🚀 문제 해결 전략 (How to Solve This Problem Efficiently?)

이 문제를 해결하는 방법은 여러 가지가 있지만, 중요한 점은 최대한 효율적으로 푸는 것입니다.

일반적으로 두 숫자의 합을 찾는 문제를 해결하는 방식은 두 가지가 있습니다:

1️⃣ Brute Force (완전 탐색)

• 모든 숫자 쌍을 비교하며 target과 일치하는지를 확인하는 방법
• 간단하지만, 배열 크기가 커지면 O(n²)의 시간 복잡도로 인해 비효율적임

2️⃣ HashMap (해시맵) 활용

• 보완값(complement)을 저장하고 빠르게 조회하여 O(n)의 시간 복잡도로 해결
• 검색 속도가 빠르므로 대규모 데이터에서도 성능이 뛰어남

💡 왜 해시맵을 써야 할까?

• Brute Force는 모든 요소를 비교하므로 시간이 오래 걸림
• 해시맵을 사용하면 숫자를 한 번만 탐색하면서도 보완값을 O(1) 시간에 빠르게 찾을 수 있음

---

✨ 풀이 방법 1: Brute Force (비효율적인 방식)

❌ 시간 복잡도: O(n²)

• 이중 루프를 사용하여 모든 두 숫자 조합을 확인하며 target과 일치하는 경우를 찾는 방식입니다.
• 숫자가 많아지면 시간이 급격히 증가하는 비효율적인 방법입니다.

/**
 * @param nums - 숫자로 이루어진 배열
 * @param target - 찾고자 하는 두 숫자의 합
 * @returns 두 숫자의 인덱스를 담은 배열 (없는 경우 빈 배열 반환)
 */
function twoSum(nums: number[], target: number): number[] {
    
    // 첫 번째 숫자의 인덱스를 순회
    for (let i = 0; i < nums.length; i++) {
        // 현재 선택한 숫자 다음부터 순회하며 두 번째 숫자 찾기
        for (let j = i + 1; j < nums.length; j++) {
            // 두 숫자의 합이 목표값과 일치하면 해당 인덱스 반환
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    // 목표값을 만족하는 조합이 없으면 빈 배열 반환
    return [];
}

단점:

• 시간 복잡도가 O(n²) 이므로 배열 크기가 커지면 성능 저하가 심합니다.
• 비효율적이며, 면접에서 사용하기엔 부족한 코드입니다.

---

✨ 풀이 방법 2: HashMap (효율적인 방식)

✅ 시간 복잡도: O(n)

1. Map 자료구조를 이용하여 숫자의 보완값(complement)과 인덱스를 저장합니다.
2. 배열을 한 번만 순회하면서, target - 현재 숫자 값이 Map에 있는지 확인합니다.
3. 있다면, 그 인덱스와 현재 인덱스를 반환합니다.
4. 없다면, 현재 숫자를 Map에 저장하고 계속 진행합니다.

/**
 * @param nums - 숫자로 이루어진 배열
 * @param target - 찾고자 하는 두 숫자의 합
 * @returns 두 숫자의 인덱스를 담은 배열 (없는 경우 빈 배열 반환)
 */
function twoSum(nums: number[], target: number): number[] {
    // 숫자를 저장할 해시맵 (key: 숫자, value: 인덱스)
    const numMap = new Map<number, number>();

    // 배열을 순회하면서 목표값을 만족하는 두 숫자 찾기
    for (let i = 0; i < nums.length; i++) {
        let complement = target - nums[i]; // 목표값에서 현재 숫자를 뺀 보완값

        // 해시맵에 보완값이 존재하면, 두 숫자의 인덱스를 반환
        if (numMap.has(complement)) {
            return [numMap.get(complement)!, i];
        }

        // 해시맵에 현재 숫자와 해당 인덱스를 저장
        numMap.set(nums[i], i);
    }

    // 목표값을 만족하는 조합이 없으면 빈 배열 반환
    return [];
}

---

✅

HashMap  장점

• 한 번만 루프를 돌기 때문에 O(n) 으로 효율적입니다.
• 빠른 조회가 가능하여 대규모 데이터에서도 성능이 좋습니다.

---

📌 이 글에서는 두 가지 방법을 모두 설명하지만, 더 효율적인 해시맵을 추천합니다!

4️⃣🚀 영어 표현 정리

이 문제를 풀면서 배울 수 있는 알고리즘 관련 영어 표현을 정리해 보았습니다.

영어 표현	뜻
indices of the two numbers	두 숫자의 인덱스
you may not use the same element twice	같은 요소를 두 번 사용할 수 없음
You can return the answer in any order	정답은 어떤 순서로 반환해도 됨
assume that each input would have exactly one solution	각 입력에는 하나의 정답만 존재함