코테를 위한 기본 알고리즘: Two Sum

안녕하세요! 저는 개발자이며 알고리즘 블로그를 운영하는데요. 이번 포스트에서는 "Two Sum" 문제를 다뤄보려고 합니다. Two Sum은 주어진 배열에서 두 수의 합이 목표값이 되는 원소의 인덱스를 찾는 문제입니다. 주어진 문제의 풀이 코드를 바탕으로 문제 내용, 문제 이해, 풀이 코드, 풀이 방법, 시간 복잡도를 자세히 알아보도록 하겠습니다.

 

바로 아래 정보에서 공부해봅시다!

 

기본 알고리즘 로고

문제 내용

다음은 제공된 코드의 twoSum 메서드의 기능을 설명하는 문제입니다.

문제: 주어진 정수 배열 nums와 정수 target이 있을 때, nums에서 두 수를 선택하여 그 합이 target이 되는 원소의 인덱스를 반환하는 함수 twoSum을 구현하세요. 단, 정답은 반드시 하나만 존재하며, 같은 원소를 두 번 사용할 수 없습니다.

문제 이해하기

이 문제를 이해하기 위해서는 twoSum 함수의 동작 방식을 파악해야 합니다. 주어진 코드를 분석해보면 다음과 같은 과정을 거칩니다:

1. **nums_map**이라는 빈 딕셔너리를 생성합니다.
2. 주어진 배열 **nums**를 반복하며 각 원소와 인덱스를 **nums_map**에 저장합니다.
3. 다시 한 번 **nums**를 반복하며, target - num 값이 **nums_map**에 존재하고, 현재 인덱스와 다른 인덱스를 가지는 경우 해당 인덱스들을 반환합니다.

풀이 코드

다음은 twoSum 함수의 구현 코드입니다.

pythonCopy code
from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        # 키와 값을 바꿔서 딕셔너리로 저장
        for i, num in enumerate(nums):
            nums_map[num] = i

        # 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
        for i, num in enumerate(nums):
            if target - num in nums_map and i != nums_map[target - num]:
                return [i, nums_map[target - num]]

풀이 방법

이제 주어진 코드를 통해 Two Sum 문제를 해결하는 방법에 대해 자세히 알아보겠습니다. twoSum 함수는 주어진 배열 **nums**를 순회하며 각 원소와 해당 원소의 인덱스를 **nums_map**에 저장합니다. 이때, **nums_map**은 원소를 키로, 인덱스를 값으로 가지는 딕셔너리입니다.

그 후, 다시 한 번 **nums**를 순회하면서 각 원소 **num**에 대해 target - num 값이 **nums_map**에 존재하는지 확인합니다. 이를 통해 현재 원소와 더해서 **target**이 되는 값을 찾을 수 있습니다. 단, 같은 인덱스를 사용하지 않도록 조건문 **i != nums_map[target - num]**을 추가하여 중복 결과를 제외합니다.

해당 조건을 만족하는 경우, 현재 원소의 인덱스 **i**와 **target - num**의 인덱스인 **nums_map[target - num]**를 리스트로 반환합니다.

시간 복잡도

이 풀이의 시간 복잡도는 O(n)입니다. 주어진 배열 **nums**를 두 번 순회하기 때문에 순회하는 데 걸리는 시간은 O(n)입니다. 딕셔너리를 통해 값을 조회하는 시간도 O(1)이므로 전체 시간 복잡도는 O(n)입니다.

이상으로 "Two Sum" 문제의 해결 방법에 대해 알아보았습니다. 추가적인 질문이 있다면 언제든지 물어보세요!

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알고리즘 모음

 

 

백준이 너무 어렵다면 아주 기본 코딩테스트 알고리즘을 먼저 도전해보세요~

 

👉 기본 코딩테스트 문제보기