코딩테스트 완벽 대비 가이드: 알고리즘 유형부터 문제 풀이 전략까지

입력: nums = [2, 7, 11, 15], target = 9
출력: [0, 1]
설명: nums[0] + nums[1] = 2 + 7 = 9

def two_sum_brute_force(nums, target):
    """
    완전탐색 방식: 이중 루프로 모든 조합 확인
    """
    n = len(nums)

    # 첫 번째 수 선택
    for i in range(n):
        # 두 번째 수 선택 (i 이후부터 시작하여 중복 방지)
        for j in range(i + 1, n):
            # 두 수의 합이 target과 같으면 인덱스 반환
            if nums[i] + nums[j] == target:
                return [i, j]

    return []  # 해답이 없는 경우 (문제 조건상 발생하지 않음)

# 테스트
nums = [2, 7, 11, 15]
target = 9
print(two_sum_brute_force(nums, target))  # [0, 1]

def two_sum_hash(nums, target):
    """
    해시 테이블 방식: 딕셔너리로 O(1) 탐색
    """
    # 값 -> 인덱스 매핑을 저장할 딕셔너리
    num_to_index = {}

    for i, num in enumerate(nums):
        # 현재 수와 더해서 target이 되는 수 계산
        complement = target - num

        # complement가 이미 딕셔너리에 있으면 답 찾음
        if complement in num_to_index:
            return [num_to_index[complement], i]

        # 현재 수를 딕셔너리에 저장 (반드시 확인 후 저장)
        num_to_index[num] = i

    return []

# 테스트
nums = [2, 7, 11, 15]
target = 9
print(two_sum_hash(nums, target))  # [0, 1]

def two_sum_two_pointers(nums, target):
    """
    투 포인터 방식: 정렬 후 양 끝에서 탐색
    주의: 원본 인덱스를 유지해야 하므로 (값, 인덱스) 튜플로 저장
    """
    # 원본 인덱스를 유지하기 위해 (값, 원본 인덱스) 튜플 생성
    nums_with_index = [(num, i) for i, num in enumerate(nums)]

    # 값 기준으로 정렬
    nums_with_index.sort()

    # 양 끝에 포인터 배치
    left = 0
    right = len(nums) - 1

    while left < right:
        current_sum = nums_with_index[left][0] + nums_with_index[right][0]

        if current_sum == target:
            # 원본 인덱스 반환 (작은 인덱스를 먼저)
            idx1 = nums_with_index[left][1]
            idx2 = nums_with_index[right][1]
            return [min(idx1, idx2), max(idx1, idx2)]

        elif current_sum < target:
            # 합이 작으면 왼쪽 포인터를 오른쪽으로
            left += 1
        else:
            # 합이 크면 오른쪽 포인터를 왼쪽으로
            right -= 1

    return []

# 테스트
nums = [2, 7, 11, 15]
target = 9
print(two_sum_two_pointers(nums, target))  # [0, 1]

입력: nums = [2, 7, 11, 15], target = 9

단계 1: i=0, num=2
  complement = 9 - 2 = 7
  딕셔너리: {}
  7이 딕셔너리에 없음 → 2를 저장
  딕셔너리: {2: 0}

단계 2: i=1, num=7
  complement = 9 - 7 = 2
  딕셔너리: {2: 0}
  2가 딕셔너리에 있음! → [0, 1] 반환 ✓

# 잘못된 코드
def wrong_two_sum(nums, target):
    num_to_index = {}
    for i, num in enumerate(nums):
        num_to_index[num] = i  # ❌ 먼저 저장하면 안 됨!

        complement = target - num
        if complement in num_to_index:  # 같은 인덱스를 두 번 사용할 수 있음
            return [num_to_index[complement], i]
    return []

# 문제 발생 예시
print(wrong_two_sum([3, 2, 4], 6))  # [1, 2] (정답)
print(wrong_two_sum([5], 10))  # [0, 0] (오답! 5를 두 번 사용)

# 올바른 순서
if complement in num_to_index:  # 1. 먼저 확인
    return [num_to_index[complement], i]
num_to_index[num] = i  # 2. 그 다음 저장

def three_sum(nums):
    """
    세 수의 합: 첫 번째 수를 고정하고 나머지는 투 포인터
    """
    nums.sort()  # 정렬 필수
    result = []
    n = len(nums)

    for i in range(n - 2):
        # 중복 제거: 같은 값은 건너뛰기
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # 최적화: 가장 작은 수가 0보다 크면 더 이상 합이 0이 될 수 없음
        if nums[i] > 0:
            break

        # 나머지 두 수를 투 포인터로 찾기
        left, right = i + 1, n - 1
        target = -nums[i]  # 세 수의 합이 0이므로 나머지 두 수의 합은 -nums[i]

        while left < right:
            current_sum = nums[left] + nums[right]

            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1

                # 중복 제거
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1

            elif current_sum < target:
                left += 1
            else:
                right -= 1

    return result

# 테스트
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1, -1, 2], [-1, 0, 1]]

def two_sum_sorted(numbers, target):
    """
    정렬된 배열에서 투 포인터 사용 (공간 복잡도 O(1))
    LeetCode 167번 기준으로 1-indexed 반환
    """
    left, right = 0, len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]

        if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed로 반환
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return []

# 테스트
print(two_sum_sorted([2, 7, 11, 15], 9))  # [1, 2]

1. 문제 이해 (5분)
   - 입력/출력 형식 확인
   - 제약 조건 파악 (시간 제한, 데이터 크기)
   - 예제로 문제 동작 이해

2. 접근법 설계 (10분)
   - 브루트포스로 가능한지 판단
   - 최적 알고리즘 선택
   - 시간/공간 복잡도 계산

3. 코드 구현 (20분)
   - 변수명을 명확하게
   - 주석으로 의도 설명
   - 단계별로 구현

4. 테스트 (5분)
   - 예제 입력 확인
   - 엣지 케이스 테스트
   - 경계 조건 확인

# 정렬
nums.sort()  # 제자리 정렬 O(n log n)
sorted(nums)  # 새 리스트 반환
nums.sort(reverse=True)  # 내림차순

# 이진탐색
import bisect
bisect.bisect_left(nums, target)  # target 삽입 위치 (왼쪽)
bisect.bisect_right(nums, target)  # target 삽입 위치 (오른쪽)

# 카운터
from collections import Counter
Counter([1, 1, 2, 3]).most_common(2)  # [(1, 2), (2, 1)]

# 힙 (우선순위 큐)
import heapq
heapq.heappush(heap, item)  # 최소 힙
heapq.heappop(heap)
heapq.heappush(heap, -item)  # 최대 힙 (음수로 저장)

# deque (양방향 큐)
from collections import deque
q = deque([1, 2, 3])
q.appendleft(0)  # O(1) 왼쪽 삽입
q.popleft()  # O(1) 왼쪽 제거

# 순열/조합
from itertools import permutations, combinations
list(permutations([1, 2, 3], 2))  # [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]
list(combinations([1, 2, 3], 2))  # [(1,2), (1,3), (2,3)]

# defaultdict (기본값 있는 딕셔너리)
from collections import defaultdict
graph = defaultdict(list)  # 자동으로 빈 리스트 생성
graph[1].append(2)  # KeyError 없음

# 입력 속도 개선 (백준)
import sys
input = sys.stdin.readline
n = int(input())  # 개행 문자 포함되므로 int() 필수