이미지 로딩 중...
AI Generated
2025. 11. 21. · 11 Views
Leetcode 알고리즘 문제 해결 전략 완벽 가이드
초급 개발자를 위한 Leetcode 알고리즘 문제 해결 전략을 단계별로 알려드립니다. 문제를 읽고 분석하는 방법부터 최적화된 솔루션을 작성하는 방법까지, 실전에서 바로 활용할 수 있는 구체적인 전략과 팁을 제공합니다.
목차
- 문제_이해하기_입출력_분석
- 브루트_포스_먼저_생각하기
- 시간_복잡도_분석하기
- 적절한_자료구조_선택하기
- 엣지_케이스_테스트하기
- 패턴_인식하고_재사용하기
- 코드_리뷰_및_리팩토링
- 디버깅_전략
- 공간_복잡도_최적화
- 문제_유형별_접근법
1. 문제_이해하기_입출력_분석
시작하며
여러분이 Leetcode 문제를 처음 열었을 때 어디서부터 시작해야 할지 막막했던 적 있나요? 문제를 대충 읽고 바로 코드를 작성하다가 나중에 예외 케이스를 발견하고 처음부터 다시 작성했던 경험이 있으신가요?
이런 문제는 문제를 제대로 이해하지 못한 채 성급하게 코드를 작성하기 때문에 발생합니다. 문제의 핵심 요구사항과 제약조건을 놓치면 아무리 좋은 알고리즘을 알고 있어도 정답을 맞출 수 없습니다.
바로 이럴 때 필요한 것이 체계적인 문제 이해 방법입니다. 문제를 읽고, 입출력 예제를 분석하고, 엣지 케이스를 찾는 과정을 통해 코딩을 시작하기 전에 문제의 전체 그림을 파악할 수 있습니다.
개요
간단히 말해서, 문제 이해 단계는 알고리즘 문제를 풀기 전 가장 중요한 준비 과정입니다. 마치 요리를 시작하기 전에 레시피를 꼼꼼히 읽고 재료를 확인하는 것과 같습니다.
왜 이 단계가 필요한지 생각해볼까요? 실제로 코딩 인터뷰에서 가장 흔한 실수는 문제를 잘못 이해하고 엉뚱한 답을 작성하는 것입니다.
예를 들어, "배열에서 중복을 제거하라"는 문제에서 순서를 유지해야 하는지, 정렬된 배열인지 아닌지에 따라 완전히 다른 접근법이 필요합니다. 전통적인 방법으로는 문제를 한 번 읽고 바로 코딩을 시작했다면, 이제는 문제를 최소 2-3번 읽으며 핵심 키워드를 체크하고, 제약 조건을 메모하고, 예제를 직접 손으로 풀어보며 패턴을 찾아야 합니다.
문제 이해의 핵심 특징은 첫째, 입력과 출력의 형태를 명확히 파악하는 것, 둘째, 제약 조건(시간 복잡도, 공간 복잡도, 입력 크기)을 확인하는 것, 셋째, 특수한 경우(빈 배열, 음수, 중복값 등)를 미리 생각하는 것입니다. 이 세 가지를 확실히 하면 코딩 중 발생할 수 있는 대부분의 실수를 예방할 수 있습니다.
코드 예제
# 문제: 배열에서 두 수의 합이 target이 되는 인덱스 찾기
# 입력: nums = [2, 7, 11, 15], target = 9
# 출력: [0, 1] (nums[0] + nums[1] = 2 + 7 = 9)
def two_sum(nums, target):
# 1. 문제 이해: 두 수의 합 = target, 인덱스 반환
# 2. 제약조건: 각 입력은 정확히 하나의 답, 같은 요소 두 번 사용 불가
# 3. 엣지케이스: 빈 배열? 음수? 중복값?
seen = {} # 이전에 본 숫자와 인덱스 저장
for i, num in enumerate(nums):
complement = target - num # 필요한 나머지 값
if complement in seen:
return [seen[complement], i]
seen[num] = i # 현재 숫자와 인덱스 저장
return [] # 답이 없는 경우 (문제에서는 항상 답이 존재한다고 가정)
설명
이것이 하는 일: 문제를 체계적으로 분석하여 코딩하기 전에 요구사항과 제약조건을 완벽히 이해하는 것입니다. 마치 건물을 짓기 전에 설계도를 그리는 것처럼, 코드를 작성하기 전에 해결 방향을 명확히 합니다.
첫 번째로, 문제 제목과 설명을 2-3번 정독하면서 핵심 키워드에 밑줄을 그어봅니다. "중복 제거", "정렬된", "최대값", "최소 시간" 같은 단어들이 알고리즘 선택의 힌트가 됩니다.
이 단계에서 문제가 무엇을 요구하는지 한 문장으로 요약해보세요. 그 다음으로, 주어진 예제들을 직접 손으로 풀어봅니다.
컴퓨터처럼 생각하며 각 단계를 추적하면 자연스럽게 알고리즘이 떠오릅니다. 예를 들어 Two Sum 문제에서 [2,7,11,15]를 순회하며 "9에서 2를 빼면 7이 필요하네, 이미 본 숫자들을 저장해두면 되겠구나"라는 통찰을 얻을 수 있습니다.
세 번째 단계는 제약조건 확인입니다. "배열의 길이는 최대 10^4"라면 O(n^2) 알고리즘은 시간 초과가 날 수 있으니 O(n) 또는 O(n log n)을 목표로 해야 합니다.
"추가 공간을 사용할 수 없다"는 조건이 있다면 in-place 알고리즘을 고민해야 합니다. 마지막으로 엣지 케이스를 생각합니다.
빈 배열이 입력될 수 있나요? 음수나 0이 포함될 수 있나요?
중복된 값이 있을 때 어떻게 처리해야 하나요? 이런 질문들에 대한 답을 미리 준비하면 코딩 중 당황하지 않고 매끄럽게 처리할 수 있습니다.
여러분이 이 단계를 꼼꼼히 거치면 코딩 시간이 절반으로 줄어들고, 버그가 거의 없는 깔끔한 코드를 작성할 수 있습니다. 또한 면접관에게 "이 사람은 문제 해결 능력이 뛰어나다"는 인상을 줄 수 있습니다.
실전 팁
💡 문제를 읽을 때 형광펜이나 메모장을 사용해 핵심 키워드를 표시하세요. "정렬된", "유일한", "최소/최대" 같은 단어는 알고리즘 선택의 결정적 힌트입니다.
💡 주어진 예제가 2-3개뿐이라면 직접 엣지 케이스를 만들어보세요. 빈 배열, 길이 1인 배열, 모든 요소가 같은 배열 등을 테스트하면 놓친 부분을 발견할 수 있습니다.
💡 제약조건에서 입력 크기를 확인하세요. n ≤ 100이면 O(n^3)도 괜찮지만, n ≤ 10^5면 O(n log n) 이하가 필요합니다. 이것만 알아도 알고리즘 선택 범위가 크게 좁혀집니다.
💡 문제 이해가 잘 안 되면 Discussion 탭에서 다른 사람들의 질문을 읽어보세요. 같은 고민을 한 사람들의 질문과 답변이 문제 이해에 큰 도움이 됩니다.
💡 면접 상황이라면 문제를 이해한 내용을 면접관에게 말로 설명해보세요. "제 이해가 맞다면 이 문제는 X를 Y하는 것이 목표인데 맞나요?"라고 확인하면 잘못된 방향으로 가는 것을 막을 수 있습니다.
2. 브루트_포스_먼저_생각하기
시작하며
여러분이 어려운 알고리즘 문제를 만났을 때 "최적의 솔루션을 바로 찾아야 해"라는 압박감에 아무것도 시작하지 못한 적 있나요? 머릿속이 하얘지고 어디서부터 손을 대야 할지 모르겠는 상황 말이죠.
이런 문제는 처음부터 완벽한 답을 찾으려는 심리적 압박 때문에 발생합니다. 실제로 많은 초보자들이 "O(n)으로 풀어야 하는데 어떻게 하지?"라는 생각에 갇혀 시간만 낭비합니다.
바로 이럴 때 필요한 것이 브루트 포스(무차별 대입) 접근법입니다. 가장 단순하고 직관적인 방법부터 시작하면 문제의 구조를 파악할 수 있고, 이를 기반으로 최적화할 수 있습니다.
마치 초안을 먼저 쓰고 나중에 다듬는 글쓰기와 같습니다.
개요
간단히 말해서, 브루트 포스는 모든 가능한 경우를 다 시도해보는 가장 단순한 접근법입니다. 효율적이지는 않지만 확실하게 작동하는 솔루션을 빠르게 찾을 수 있습니다.
왜 이 방법이 필요한지 설명하자면, 첫째로 문제를 풀 수 있다는 자신감을 얻을 수 있고, 둘째로 최적화의 기준점이 되며, 셋째로 면접에서 "아무 답도 못 쓰는" 최악의 상황을 피할 수 있습니다. 예를 들어, Two Sum 문제에서 "모든 쌍을 다 확인해보면 되겠구나"라는 간단한 생각부터 시작하면 됩니다.
전통적인 학습법에서는 "이 문제는 해시맵으로 O(n)에 풀 수 있다"는 정답만 암기했다면, 이제는 "이중 for 문으로 O(n^2)에 풀 수 있고, 이걸 해시맵으로 개선하면 O(n)이 된다"는 과정을 이해하게 됩니다. 브루트 포스의 핵심 특징은 첫째, 구현이 쉽고 직관적이라는 점, 둘째, 정확성이 보장된다는 점, 셋째, 최적화 아이디어의 출발점이 된다는 점입니다.
많은 최적 알고리즘이 사실 브루트 포스에서 불필요한 반복을 제거한 결과입니다.
코드 예제
# 브루트 포스: 모든 쌍을 확인
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 [] # 답이 없는 경우
# 시간 복잡도: O(n^2) - 이중 반복문
# 공간 복잡도: O(1) - 추가 메모리 사용 안 함
# 장점: 이해하기 쉽고 구현 간단
# 단점: 큰 입력에서 느림
설명
이것이 하는 일: 브루트 포스는 "모든 가능성을 다 해보자"는 단순하지만 확실한 전략입니다. 마치 열쇠 꾸러미에서 맞는 열쇠를 찾을 때 하나하나 다 시도해보는 것과 같습니다.
첫 번째로, 문제를 읽고 "가장 무식하게 풀면 어떻게 풀까?"라고 자문해봅니다. Two Sum 문제라면 "첫 번째 숫자와 나머지 모든 숫자를 더해보고, 두 번째 숫자와 나머지 모든 숫자를 더해보면 되겠네"라는 생각이 자연스럽게 떠오릅니다.
이것이 바로 이중 for 문입니다. 그 다음으로, 이 방법의 시간 복잡도를 계산해봅니다.
n개의 요소에 대해 각각 n-1개를 확인하므로 O(n^2)입니다. n이 100이면 10,000번 연산인데 괜찮지만, n이 10,000이면 1억 번 연산이라 느릴 수 있다는 것을 알 수 있습니다.
이 시점에서 "최적화가 필요하구나"라는 판단을 내릴 수 있습니다. 세 번째 단계는 브루트 포스를 실제로 구현해보는 것입니다.
놀랍게도 많은 경우 브루트 포스만으로도 Leetcode의 Easy 문제는 통과할 수 있습니다. 또한 코드를 작성하면서 "아, 여기서 같은 계산을 반복하고 있네"라는 개선 포인트를 발견하게 됩니다.
마지막으로, 이 솔루션을 바탕으로 최적화를 고민합니다. "매번 배열을 다시 순회하는 대신 이미 본 숫자를 어딘가에 저장해두면 어떨까?"라는 생각이 해시맵 솔루션으로 이어집니다.
이렇게 브루트 포스는 최적 솔루션으로 가는 디딤돌 역할을 합니다. 여러분이 이 접근법을 사용하면 어떤 어려운 문제라도 일단 뭔가 쓸 수 있다는 자신감이 생깁니다.
면접에서도 "일단 브루트 포스로 풀고 최적화하겠습니다"라고 말하면 면접관이 긍정적으로 평가합니다. 또한 브루트 포스 코드를 테스트 케이스로 삼아 최적화된 코드가 같은 결과를 내는지 검증할 수도 있습니다.
실전 팁
💡 면접에서는 "먼저 브루트 포스로 접근하고 최적화하겠습니다"라고 말하세요. 이것만으로도 체계적으로 생각한다는 인상을 줍니다.
💡 브루트 포스의 시간 복잡도를 계산하고 입력 크기와 비교하세요. n ≤ 1000이고 O(n^2)면 통과 가능하지만, n ≤ 10^5면 O(n log n) 이하로 최적화가 필요합니다.
💡 브루트 포스 코드에 주석으로 "TODO: 이 부분에서 중복 계산이 발생함. 메모이제이션 필요"라고 적어두면 최적화 방향이 명확해집니다.
💡 제출 전에 브루트 포스로 작은 테스트 케이스를 풀어보고, 최적화된 코드와 결과가 같은지 확인하세요. 이것이 가장 확실한 검증 방법입니다.
💡 일부 문제는 브루트 포스가 유일한 정답일 수 있습니다. 조합(Combination) 문제처럼 모든 경우를 다 봐야 하는 경우가 그렇습니다. 무조건 최적화할 필요는 없습니다.
3. 시간_복잡도_분석하기
시작하며
여러분이 코드를 완성했는데 Leetcode에서 "Time Limit Exceeded" 오류를 받은 적 있나요? 분명 로직은 맞는데 왜 통과하지 못하는지 답답했던 경험 말이죠.
이런 문제는 알고리즘의 효율성을 고려하지 않고 코드를 작성했기 때문에 발생합니다. 작은 테스트 케이스에서는 잘 작동하지만, 입력 크기가 커지면 기하급수적으로 느려지는 코드는 실무에서 사용할 수 없습니다.
바로 이럴 때 필요한 것이 시간 복잡도 분석입니다. 코드가 얼마나 빠른지 예측하고, 주어진 제약조건 안에서 통과할 수 있는지 미리 판단할 수 있습니다.
개요
간단히 말해서, 시간 복잡도는 입력 크기(n)가 커질 때 프로그램이 실행하는 연산 횟수가 어떻게 증가하는지 나타내는 지표입니다. 마치 자동차의 연비처럼, 알고리즘의 효율성을 측정하는 기준입니다.
왜 이것이 중요한지 생각해볼까요? 컴퓨터는 보통 1초에 약 10^8~10^9번의 연산을 수행할 수 있습니다.
만약 n = 10,000인 배열에 대해 O(n^2) 알고리즘을 사용하면 1억 번 연산이 필요한데, 이는 약 1초 정도 걸립니다. 하지만 n = 100,000이면 100억 번 연산으로 100초가 걸려 시간 초과가 발생합니다.
전통적으로는 코드를 작성한 후 제출해서 시간 초과가 나면 그때 최적화했다면, 이제는 코드를 쓰기 전에 시간 복잡도를 계산하고 "이 접근법이 통과할까?"를 먼저 판단합니다. 이렇게 하면 잘못된 방향으로 시간을 낭비하지 않습니다.
시간 복잡도의 핵심 특징은 첫째, 상수 시간은 무시한다는 것(O(2n) = O(n)), 둘째, 최고차항만 고려한다는 것(O(n^2 + n) = O(n^2)), 셋째, 최악의 경우를 기준으로 한다는 것입니다. 이런 규칙 덕분에 복잡한 코드도 간단한 표기법으로 효율성을 비교할 수 있습니다.
코드 예제
# 다양한 시간 복잡도 예제
# O(1) - 상수 시간: 입력 크기와 무관
def get_first_element(arr):
return arr[0] if arr else None # 항상 1번 연산
# O(n) - 선형 시간: 입력 크기에 비례
def find_max(arr):
max_val = arr[0]
for num in arr: # n번 반복
if num > max_val:
max_val = num
return max_val
# O(n^2) - 이차 시간: 이중 반복문
def has_duplicate_pair(arr):
n = len(arr)
for i in range(n): # n번
for j in range(i+1, n): # 각 i마다 n번
if arr[i] == arr[j]:
return True
return False # 총 n * n = O(n^2)
# O(log n) - 로그 시간: 이진 탐색
def binary_search(sorted_arr, target):
left, right = 0, len(sorted_arr) - 1
while left <= right: # 매번 범위가 절반으로 줄어듦
mid = (left + right) // 2
if sorted_arr[mid] == target:
return mid
elif sorted_arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # log n번 반복
# O(n log n) - 효율적인 정렬
def merge_sort_example(arr):
return sorted(arr) # Python의 Timsort: O(n log n)
설명
이것이 하는 일: 시간 복잡도 분석은 코드를 실행하지 않고도 성능을 예측하는 강력한 도구입니다. 마치 건물 설계도를 보고 건설 비용을 예측하는 것처럼, 코드를 보고 실행 시간을 추정할 수 있습니다.
첫 번째로, 코드에서 반복문을 찾습니다. 한 개의 for 문이 n번 반복하면 O(n), 이중 for 문이면 O(n^2)입니다.
단, 내부 반복문이 매번 절반씩 줄어든다면 O(n log n)이 됩니다. 예를 들어, 이진 탐색은 매 단계마다 검색 범위가 절반이 되므로 O(log n)입니다.
그 다음으로, 문제의 제약조건과 비교합니다. "n ≤ 100"이면 O(n^3)도 괜찮지만(100^3 = 100만), "n ≤ 10^5"면 O(n^2)도 위험합니다(10^5^2 = 100억).
Leetcode에서 일반적으로 1-2초 안에 통과해야 하므로, 약 10^8번 이하의 연산을 목표로 해야 합니다. 세 번째 단계는 공간 복잡도도 함께 고려하는 것입니다.
해시맵을 사용하면 시간은 O(n)으로 줄지만 공간이 O(n) 필요합니다. 문제에서 "추가 공간을 사용하지 않고 풀어라"는 조건이 있다면 O(1) 공간 복잡도인 투 포인터나 제자리 정렬을 사용해야 합니다.
마지막으로, 실전 팁으로 대략적인 규칙을 외워두면 편합니다. n ≤ 10이면 O(n!) 가능, n ≤ 20이면 O(2^n) 가능, n ≤ 500이면 O(n^3) 가능, n ≤ 5000이면 O(n^2) 가능, n ≤ 10^6이면 O(n log n) 가능, n ≤ 10^8이면 O(n) 가능합니다.
여러분이 시간 복잡도를 분석할 수 있게 되면 "이 문제는 정렬을 써야겠구나(O(n log n))", "이 문제는 해시맵을 써야겠구나(O(n))", "이 문제는 투 포인터를 써야겠구나(O(n))"처럼 알고리즘을 선택하는 기준이 생깁니다. 또한 면접에서 "제 솔루션의 시간 복잡도는 O(n log n)입니다"라고 말할 수 있어 전문성을 보여줄 수 있습니다.
실전 팁
💡 반복문의 중첩 깊이를 세세요. 1개면 O(n), 2개면 O(n^2), 3개면 O(n^3)입니다. 단, 범위가 고정이면(예: 항상 26번 반복하는 알파벳) O(1)로 간주합니다.
💡 "매번 절반씩 줄어든다"는 패턴을 발견하면 O(log n)입니다. 이진 탐색, 이진 트리의 높이, 2의 거듭제곱 증가 등이 해당됩니다.
💡 정렬이 필요하면 기본적으로 O(n log n)이 추가됩니다. 따라서 "정렬 + 선형 탐색"은 O(n log n + n) = O(n log n)입니다.
💡 재귀 함수의 시간 복잡도는 "호출 횟수 × 각 호출의 작업량"입니다. 피보나치의 단순 재귀는 O(2^n)이지만, 메모이제이션을 쓰면 O(n)으로 줄어듭니다.
💡 Python의 내장 함수도 시간 복잡도가 있습니다. list.append()는 O(1), list.insert(0, x)는 O(n), x in list는 O(n), x in set는 O(1)입니다. 자주 쓰는 함수들의 복잡도를 외워두세요.
4. 적절한_자료구조_선택하기
시작하며
여러분이 "빠른 검색이 필요한데 뭘 써야 하지?" 또는 "순서를 유지하면서 중복을 제거하려면?"처럼 자료구조 선택에 고민한 적 있나요? 리스트를 써야 할지, 세트를 써야 할지, 딕셔너리를 써야 할지 헷갈렸던 경험 말이죠.
이런 문제는 각 자료구조의 특성과 시간 복잡도를 제대로 이해하지 못해서 발생합니다. 잘못된 자료구조를 선택하면 O(n)으로 풀 수 있는 문제를 O(n^2)로 풀게 되어 시간 초과가 발생합니다.
바로 이럴 때 필요한 것이 문제 유형에 맞는 자료구조 선택 능력입니다. "빠른 검색"이면 해시 세트, "빠른 조회+저장"이면 해시맵, "정렬된 순서 유지"면 힙이나 정렬된 배열처럼 패턴을 알면 즉시 올바른 선택을 할 수 있습니다.
개요
간단히 말해서, 자료구조 선택은 문제 요구사항에 가장 효율적인 데이터 저장 방식을 고르는 것입니다. 마치 요리할 때 적절한 조리 도구를 선택하는 것처럼, 문제에 맞는 자료구조를 쓰면 코드가 간결하고 빨라집니다.
왜 이것이 중요한지 예를 들어볼까요? "배열에 특정 값이 있는지 확인"하는 작업을 리스트로 하면 O(n)이지만 세트로 하면 O(1)입니다.
100만 개 요소에서 1만 번 검색한다면, 리스트는 100억 번 연산(100초), 세트는 1만 번 연산(0.01초)으로 엄청난 차이가 납니다. 전통적으로는 모든 문제를 배열과 리스트로만 풀려고 했다면, 이제는 해시맵(딕셔너리), 해시 세트, 스택, 큐, 힙, 트리 등 다양한 자료구조를 상황에 맞게 활용합니다.
각 자료구조는 특정 작업에 최적화되어 있습니다. 자료구조 선택의 핵심 기준은 첫째, 어떤 연산이 주로 필요한지(검색?
삽입? 삭제?
정렬?), 둘째, 중복을 허용하는지, 셋째, 순서가 중요한지입니다. 이 세 가지 질문에 답하면 자연스럽게 적절한 자료구조가 떠오릅니다.
코드 예제
# 문제별 적절한 자료구조 선택 예제
# 1. 빠른 검색 필요 → Set 사용 (O(1) 검색)
def contains_duplicate(nums):
seen = set() # 해시 세트: 빠른 검색
for num in nums:
if num in seen: # O(1) 검색
return True
seen.add(num) # O(1) 삽입
return False
# 2. 값-키 매핑 필요 → Dictionary 사용
def two_sum(nums, target):
num_to_index = {} # 해시맵: 값 → 인덱스 매핑
for i, num in enumerate(nums):
complement = target - num
if complement in num_to_index: # O(1) 검색
return [num_to_index[complement], i]
num_to_index[num] = i # O(1) 삽입
return []
# 3. 최소/최대값 추적 → Heap 사용
import heapq
def find_kth_largest(nums, k):
min_heap = []
for num in nums:
heapq.heappush(min_heap, num) # O(log n) 삽입
if len(min_heap) > k:
heapq.heappop(min_heap) # 최소값 제거 O(log n)
return min_heap[0] # k번째 큰 값
# 4. LIFO(후입선출) 필요 → Stack 사용
def is_valid_parentheses(s):
stack = [] # 리스트를 스택으로 사용
pairs = {'(': ')', '{': '}', '[': ']'}
for char in s:
if char in pairs:
stack.append(char) # 여는 괄호 푸시
elif not stack or pairs[stack.pop()] != char:
return False # 닫는 괄호 확인
return len(stack) == 0
설명
이것이 하는 일: 자료구조 선택은 알고리즘의 효율성을 결정하는 가장 중요한 결정입니다. 같은 로직이라도 자료구조에 따라 O(n)과 O(n^2)의 차이가 날 수 있습니다.
첫 번째로, 문제에서 요구하는 핵심 연산을 파악합니다. "빠르게 찾아야 한다"면 해시 기반 자료구조(세트, 딕셔너리), "순서대로 처리해야 한다"면 큐, "가장 최근 것을 먼저"라면 스택, "항상 최소/최대값을 알아야 한다"면 힙을 떠올립니다.
그 다음으로, 각 자료구조의 시간 복잡도를 비교합니다. 리스트는 검색 O(n)이지만 인덱스 접근은 O(1), 세트는 검색/삽입/삭제가 모두 O(1)이지만 순서 없음, 힙은 최소값 접근 O(1)이고 삽입/삭제 O(log n)입니다.
문제에서 자주 하는 연산이 효율적인 자료구조를 선택합니다. 세 번째 단계는 제약조건을 고려하는 것입니다.
"중복을 허용하지 않는다"면 세트가 자동으로 중복 제거, "순서가 중요하다"면 리스트나 deque, "키-값 쌍을 저장"한다면 딕셔너리가 적합합니다. 또한 "공간을 최소화해야 한다"면 추가 자료구조 없이 원본 배열을 조작하는 in-place 알고리즘을 고려합니다.
마지막으로, Python의 기본 자료구조 특성을 활용합니다. collections.Counter는 빈도 계산, collections.defaultdict는 키가 없을 때 기본값 제공, collections.deque는 양쪽 끝에서 O(1) 삽입/삭제가 가능합니다.
이런 특화된 자료구조를 알면 코드가 훨씬 간결해집니다. 여러분이 자료구조를 적절히 선택할 수 있게 되면 많은 문제가 놀랍도록 쉬워집니다.
"Two Sum은 해시맵", "Top K Elements는 힙", "Valid Parentheses는 스택"처럼 패턴이 보이기 시작합니다. 또한 면접에서 "이 문제는 빠른 검색이 필요하므로 해시 세트를 사용하겠습니다"라고 설명하면 사고 과정을 명확히 전달할 수 있습니다.
실전 팁
💡 "존재 여부 확인"이 주 작업이면 Set, "값과 연결된 정보 저장"이면 Dict를 사용하세요. 둘 다 O(1) 검색이지만 용도가 다릅니다.
💡 "최근 K개", "sliding window" 문제는 collections.deque를 사용하세요. 양쪽 끝에서 O(1)로 추가/제거할 수 있어 list보다 효율적입니다.
💡 "K번째 큰/작은 값" 문제는 크기 K인 힙을 유지하세요. 전체 정렬(O(n log n))보다 힙(O(n log k))이 빠릅니다.
💡 "빈도 계산" 문제는 collections.Counter를 사용하면 한 줄로 해결됩니다. Counter(nums).most_common(k)로 상위 k개를 쉽게 구할 수 있습니다.
💡 Python의 list는 동적 배열이므로 끝에 추가(append)는 O(1)이지만 앞에 추가(insert(0, x))는 O(n)입니다. 앞뒤 모두 추가/삭제가 필요하면 deque를 쓰세요.
5. 엣지_케이스_테스트하기
시작하며
여러분이 완벽하게 작동한다고 생각한 코드를 제출했는데 "Runtime Error"나 "Wrong Answer"를 받은 적 있나요? 분명 주어진 예제는 다 통과했는데 숨겨진 테스트 케이스에서 실패하는 경우 말이죠.
이런 문제는 일반적인 경우만 고려하고 특수한 상황(엣지 케이스)을 놓쳤기 때문에 발생합니다. 빈 배열, 한 개짜리 배열, 음수, 0, 중복값, 최대/최소 경계값 같은 특수 케이스는 종종 버그를 숨기고 있습니다.
바로 이럴 때 필요한 것이 체계적인 엣지 케이스 테스트입니다. 코드를 제출하기 전에 극단적인 경우들을 미리 확인하면 숨어있는 버그를 발견하고 수정할 수 있습니다.
개요
간단히 말해서, 엣지 케이스는 일반적이지 않은 극단적인 입력 상황을 말합니다. 마치 자동차 안전 테스트에서 극한 상황을 시뮬레이션하는 것처럼, 코드도 비정상적인 입력에서 제대로 작동하는지 확인해야 합니다.
왜 이것이 중요한지 실무 관점에서 설명하자면, Leetcode의 숨겨진 테스트 케이스 대부분이 엣지 케이스입니다. 일반적인 경우는 누구나 맞추지만, 빈 배열에서 IndexError가 나거나, 음수 입력을 처리 못 하거나, 최댓값 오버플로우가 발생하는 등의 문제로 많은 사람들이 실패합니다.
전통적으로는 주어진 예제만 확인하고 제출했다면, 이제는 제출 전에 "최소 입력은?", "최대 입력은?", "특수 문자는?", "중복은?", "경계값은?" 같은 체크리스트를 돌려봅니다. 이 과정만으로도 대부분의 실수를 잡아낼 수 있습니다.
엣지 케이스의 핵심 유형은 첫째, 빈 입력([], "", None), 둘째, 크기 1인 입력, 셋째, 중복된 값, 넷째, 정렬 여부, 다섯째, 음수/0/최댓값, 여섯째, 경계 조건(딱 k개, n-1개 등)입니다. 이 여섯 가지만 확인해도 대부분의 버그를 예방할 수 있습니다.
코드 예제
# 엣지 케이스를 고려한 안전한 코드 예제
def find_median(nums):
"""정렬되지 않은 배열의 중앙값 찾기"""
# 엣지 케이스 1: 빈 배열
if not nums:
return None
# 엣지 케이스 2: 크기 1인 배열
if len(nums) == 1:
return nums[0]
# 일반적인 경우
sorted_nums = sorted(nums) # 정렬
n = len(sorted_nums)
# 엣지 케이스 3: 짝수 vs 홀수 길이
if n % 2 == 0:
# 짝수: 중간 두 값의 평균
mid1 = sorted_nums[n // 2 - 1]
mid2 = sorted_nums[n // 2]
return (mid1 + mid2) / 2
else:
# 홀수: 정확히 중간 값
return sorted_nums[n // 2]
# 테스트: 다양한 엣지 케이스
assert find_median([]) == None # 빈 배열
assert find_median([5]) == 5 # 크기 1
assert find_median([1, 2]) == 1.5 # 짝수 길이
assert find_median([1, 2, 3]) == 2 # 홀수 길이
assert find_median([3, 1, 2]) == 2 # 정렬 안 됨
assert find_median([-1, 0, 1]) == 0 # 음수 포함
assert find_median([1, 1, 1]) == 1 # 중복값
설명
이것이 하는 일: 엣지 케이스 테스트는 코드의 견고성을 보장하는 안전장치입니다. 일반적인 입력뿐 아니라 극단적이고 예외적인 상황에서도 올바르게 작동하는지 검증합니다.
첫 번째로, 빈 입력을 항상 확인합니다. 빈 배열([]), 빈 문자열(""), None 값이 들어왔을 때 어떻게 처리할지 명확히 정의해야 합니다.
많은 버그가 "배열이 비어있을 거라고 생각 못 했어요"에서 발생합니다. nums[0]을 접근하기 전에 if not nums: 체크를 습관화하세요.
그 다음으로, 크기가 1인 입력을 확인합니다. 반복문이나 인덱스 계산이 제대로 작동하는지 보는 좋은 테스트입니다.
예를 들어, nums[i]와 nums[i+1]을 비교하는 코드는 길이가 1이면 IndexError가 발생합니다. 이런 경우 for i in range(len(nums) - 1): 처럼 범위를 조정해야 합니다.
세 번째 단계는 중복값과 경계값을 테스트하는 것입니다. "모든 요소가 같은 배열"([5,5,5,5,5]), "처음과 끝만 같은 배열"([1,2,3,1]), "최솟값과 최댓값"(-10^9, 10^9) 같은 경우를 확인합니다.
특히 정수 오버플로우가 발생할 수 있는 언어(Java, C++)에서는 두 큰 수를 더할 때 주의해야 합니다. 마지막으로, 문제의 제약조건 경계를 테스트합니다.
"1 ≤ k ≤ n"이라는 조건이 있다면 k=1과 k=n인 경우를 확인하고, "배열 길이 ≤ 10^5"라면 정확히 10^5개인 배열로 시간 초과가 나지 않는지 확인합니다. 이런 경계값에서 off-by-one 에러가 자주 발생합니다.
여러분이 엣지 케이스를 체계적으로 테스트하는 습관을 들이면 제출 전에 대부분의 버그를 잡아낼 수 있습니다. Leetcode의 "Run Code" 기능을 활용해 직접 만든 엣지 케이스들을 테스트하세요.
또한 면접에서 "엣지 케이스로 빈 배열과 중복값을 확인하겠습니다"라고 말하면 꼼꼼하다는 인상을 줄 수 있습니다.
실전 팁
💡 엣지 케이스 체크리스트를 만드세요: "빈 입력? 크기 1? 중복? 음수? 0? 최대/최소값?" 이 6가지만 확인해도 대부분의 버그를 잡습니다.
💡 Python에서는 assert 문으로 테스트하세요. assert find_median([]) == None처럼 작성하면 기대값과 다를 때 AssertionError가 발생해 즉시 알 수 있습니다.
💡 배열 인덱스 접근 전에 항상 범위를 확인하세요. nums[i+1]을 쓴다면 i < len(nums)-1 조건을 추가하고, nums[-1]을 쓴다면 if nums: 체크를 먼저 하세요.
💡 나눗셈 연산이 있다면 0으로 나누기를 조심하세요. a / b를 하기 전에 if b != 0: 체크를 추가하거나, 문제 조건에서 b가 0이 아님을 보장하는지 확인하세요.
💡 문자열 문제에서는 빈 문자열(""), 공백만 있는 문자열(" "), 특수문자("#$%"), 대소문자 혼합("AbCd") 등을 테스트하세요. 각각 다른 버그를 드러낼 수 있습니다.
6. 패턴_인식하고_재사용하기
시작하며
여러분이 새로운 문제를 만났을 때 "이 문제 어디선가 본 것 같은데"라는 느낌을 받은 적 있나요? 문제 유형은 다르지만 해결 방법이 비슷해 보이는 경험 말이죠.
이런 현상은 우연이 아닙니다. Leetcode 문제의 70% 이상은 약 15-20개의 핵심 패턴으로 분류할 수 있습니다.
투 포인터, 슬라이딩 윈도우, 백트래킹, 동적 프로그래밍 같은 검증된 패턴을 알면 새로운 문제도 빠르게 풀 수 있습니다. 바로 이럴 때 필요한 것이 패턴 인식 능력입니다.
문제의 특징을 보고 "아, 이건 투 포인터 문제구나" 또는 "이건 BFS로 풀어야겠다"고 즉시 판단할 수 있으면 문제 풀이 시간이 획기적으로 단축됩니다.
개요
간단히 말해서, 알고리즘 패턴은 비슷한 유형의 문제를 푸는 검증된 접근 방법의 템플릿입니다. 마치 요리 레시피처럼, 재료(입력)만 바뀌고 조리법(알고리즘)은 비슷한 경우가 많습니다.
왜 패턴 학습이 중요한지 설명하자면, 처음부터 새로운 알고리즘을 발명할 필요가 없기 때문입니다. "정렬된 배열에서 두 수의 합 찾기", "배열에서 최장 부분 배열 찾기", "섬의 개수 세기" 같은 문제들은 각각 투 포인터, 슬라이딩 윈도우, BFS/DFS라는 정형화된 패턴으로 풀립니다.
전통적으로는 문제를 하나하나 독립적으로 풀었다면, 이제는 "이 문제는 어떤 패턴에 속하지?"를 먼저 생각합니다. 패턴을 파악하면 70-80%의 솔루션 구조가 이미 머릿속에 있고, 나머지 20-30%만 문제에 맞게 커스터마이즈하면 됩니다.
핵심 패턴의 특징은 첫째, 입력 형태로 패턴을 추측할 수 있다는 것(정렬된 배열 → 투 포인터/이진 탐색, 그래프 → BFS/DFS), 둘째, 코드 구조가 매우 유사하다는 것, 셋째, 한 번 배우면 수십 개 문제에 적용할 수 있다는 것입니다.
코드 예제
# 패턴 1: 투 포인터 (정렬된 배열에서 두 수의 합)
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1 # 양 끝에서 시작
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1 # 합을 키우려면 왼쪽 증가
else:
right -= 1 # 합을 줄이려면 오른쪽 감소
return []
# 패턴 2: 슬라이딩 윈도우 (최대 합 부분 배열)
def max_sum_subarray(nums, k):
# 크기 k인 윈도우의 최대 합
window_sum = sum(nums[:k]) # 첫 윈도우
max_sum = window_sum
# 윈도우를 한 칸씩 이동
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k] # 오른쪽 추가, 왼쪽 제거
max_sum = max(max_sum, window_sum)
return max_sum
# 패턴 3: 빠른 검색 (해시맵)
def group_anagrams(strs):
anagram_map = {} # 정렬된 문자 → 원본 단어들
for word in strs:
key = ''.join(sorted(word)) # 정렬해서 키로 사용
if key not in anagram_map:
anagram_map[key] = []
anagram_map[key].append(word)
return list(anagram_map.values())
설명
이것이 하는 일: 패턴 인식은 문제를 보자마자 "이건 저 패턴으로 풀면 되겠다"고 판단하는 능력입니다. 체스 고수가 수천 개의 정석을 외워서 빠르게 다음 수를 결정하는 것처럼, 알고리즘 패턴을 알면 즉시 해결 방향을 잡을 수 있습니다.
첫 번째로, 문제의 특징을 파악해 패턴을 추론합니다. "정렬된 배열 + 두 수"라면 투 포인터, "연속된 부분 배열 + 크기 k"라면 슬라이딩 윈도우, "그래프 + 최단 경로"라면 BFS, "모든 조합 찾기"라면 백트래킹을 떠올립니다.
이런 신호를 인식하는 연습이 중요합니다. 그 다음으로, 해당 패턴의 템플릿 코드를 적용합니다.
예를 들어, 투 포인터 패턴은 항상 "left = 0, right = n-1, while left < right"로 시작하고, 조건에 따라 left를 증가시키거나 right를 감소시킵니다. 이 구조는 "두 수의 합", "팰린드롬 확인", "컨테이너 물 담기" 등 수십 개 문제에 똑같이 적용됩니다.
세 번째 단계는 패턴의 변형을 이해하는 것입니다. 슬라이딩 윈도우는 고정 크기(크기 k)일 수도 있고, 가변 크기(조건을 만족하는 최소/최대 윈도우)일 수도 있습니다.
같은 패턴이지만 세부 구현이 약간 다릅니다. 이런 변형을 알면 응용력이 생깁니다.
마지막으로, 여러 패턴을 조합하는 경우도 있습니다. 예를 들어, "정렬 + 투 포인터", "해시맵 + 슬라이딩 윈도우", "BFS + 메모이제이션"처럼 두 가지 패턴을 섞어 쓰는 문제도 많습니다.
기본 패턴을 확실히 알면 조합도 자연스럽게 이해됩니다. 여러분이 주요 패턴 15-20개를 마스터하면 Leetcode Easy/Medium 문제의 80% 이상을 풀 수 있습니다.
패턴별로 5-10문제씩 풀어보며 템플릿 코드를 체화하세요. 또한 새 문제를 풀 때마다 "이 문제는 어떤 패턴인가?"를 스스로에게 질문하는 습관을 들이면 패턴 인식 능력이 빠르게 향상됩니다.
실전 팁
💡 Leetcode의 "Tag" 기능을 활용하세요. Two Pointers, Sliding Window, Dynamic Programming 같은 태그별로 문제를 모아서 풀면 패턴이 빠르게 익숙해집니다.
💡 각 패턴의 "신호"를 정리해두세요. "정렬됨 → 이진 탐색/투 포인터", "연속 부분 배열 → 슬라이딩 윈도우", "모든 경우 탐색 → 백트래킹/BFS" 같은 치트시트를 만들면 도움이 됩니다.
💡 같은 패턴의 문제를 연속으로 3-5개 풀어보세요. 문제만 바뀌고 코드 구조가 비슷하다는 것을 체감하면 패턴이 확실히 각인됩니다.
💡 패턴별 템플릿 코드를 작성해 보관하세요. 투 포인터, 이진 탐색, BFS, DFS의 기본 뼈대 코드를 저장해두고 새 문제에 복사-붙여넣기해서 커스터마이즈하면 시간이 절약됩니다.
💡 면접에서는 "이 문제는 투 포인터 패턴으로 접근하겠습니다"라고 먼저 말하세요. 패턴을 명시하면 구조화된 사고를 보여줄 수 있고, 면접관도 여러분의 의도를 쉽게 이해합니다.
7. 코드_리뷰_및_리팩토링
시작하며
여러분이 문제를 풀고 "Accept"를 받았는데, 다른 사람들의 솔루션을 보니 훨씬 간결하고 우아한 코드를 발견한 적 있나요? "나도 이렇게 짤 수 있었는데"라고 아쉬워했던 경험 말이죠.
이런 차이는 단순히 실력의 차이가 아니라 코드 개선 과정의 차이입니다. 많은 사람들이 문제를 풀면 바로 다음 문제로 넘어가지만, 고수들은 자신의 코드를 리뷰하고 더 나은 방법을 고민합니다.
바로 이럴 때 필요한 것이 체계적인 코드 리뷰와 리팩토링입니다. "일단 통과"한 코드를 "읽기 쉽고 효율적인" 코드로 개선하는 과정을 통해 실력이 한 단계 성장합니다.
개요
간단히 말해서, 코드 리뷰는 작성한 코드를 비판적으로 재검토하는 과정이고, 리팩토링은 기능은 유지하면서 코드 품질을 개선하는 작업입니다. 마치 글을 쓰고 퇴고하는 것처럼, 코드도 첫 버전에서 끝나는 것이 아닙니다.
왜 이 과정이 중요한지 생각해볼까요? 첫째, 더 효율적인 알고리즘을 발견할 수 있습니다(O(n^2) → O(n)).
둘째, 코드 가독성이 높아져 나중에 다시 봐도 이해하기 쉽습니다. 셋째, 버그를 발견할 수 있습니다(엣지 케이스 누락, 논리적 오류 등).
넷째, 모범 사례를 학습할 수 있습니다. 전통적으로는 "통과했으니 끝"이었다면, 이제는 "통과했으니 개선할 점은 없을까?"를 고민합니다.
Leetcode의 "Discuss" 탭에서 다른 사람들의 우수한 솔루션을 읽어보고, 자신의 코드와 비교하며 배울 점을 찾습니다. 코드 리뷰의 핵심 체크리스트는 첫째, 시간/공간 복잡도를 더 줄일 수 있는가, 둘째, 불필요한 변수나 반복문이 있는가, 셋째, 코드가 명확하고 읽기 쉬운가, 넷째, 엣지 케이스를 모두 처리했는가입니다.
이 네 가지 관점에서 코드를 다시 보면 개선 포인트가 보입니다.
코드 예제
# Before: 비효율적이고 복잡한 코드
def remove_duplicates_v1(nums):
unique = []
for num in nums:
is_duplicate = False
for u in unique: # O(n^2) - 매번 전체 리스트 확인
if u == num:
is_duplicate = True
break
if not is_duplicate:
unique.append(num)
return unique
# After: 효율적이고 간결한 코드
def remove_duplicates_v2(nums):
seen = set() # O(1) 검색을 위한 해시 세트
result = []
for num in nums: # O(n) - 한 번만 순회
if num not in seen:
seen.add(num)
result.append(num)
return result
# Best: Python의 기능 활용 (가장 간결)
def remove_duplicates_v3(nums):
# 순서 유지 필요 없으면
return list(set(nums))
# 순서 유지 필요하면 (Python 3.7+)
# return list(dict.fromkeys(nums))
# 리팩토링 결과:
# - 시간 복잡도: O(n^2) → O(n)
# - 가독성: 15줄 → 1-2줄
# - 의도: "중복 제거"가 명확히 드러남
설명
이것이 하는 일: 코드 리뷰는 작성한 코드를 객관적으로 평가하고 개선하는 과정입니다. 마치 운동선수가 경기 영상을 다시 보며 동작을 교정하는 것처럼, 코드를 다시 읽으며 더 나은 방법을 찾습니다.
첫 번째로, 시간 복잡도와 공간 복잡도를 재검토합니다. "이 반복문이 정말 필요한가?", "이 변수를 저장해둬야 하나?"를 질문하세요.
예를 들어, 위 예제에서 unique 리스트를 매번 순회하는 대신 seen 세트로 O(1) 검색을 하면 O(n^2)에서 O(n)으로 개선됩니다. 그 다음으로, 코드의 중복을 제거합니다.
같은 로직이 여러 곳에 반복되면 함수로 추출하고, 같은 계산이 여러 번 일어나면 변수에 저장해둡니다. DRY(Don't Repeat Yourself) 원칙을 따르면 코드가 짧아지고 버그 가능성도 줄어듭니다.
세 번째 단계는 변수명과 코드 구조를 명확히 합니다. temp, x, arr 같은 모호한 이름 대신 seen_numbers, current_sum, sorted_array 같은 설명적인 이름을 사용하세요.
또한 복잡한 조건문은 중간 변수로 나누어 의도를 명확히 표현합니다(is_valid = x > 0 and x < 10 같이). 마지막으로, Discuss 탭에서 상위 투표를 받은 솔루션을 읽어봅니다.
특히 Python에서는 리스트 컴프리헨션, 람다 함수, 내장 함수(map, filter, zip) 등을 활용한 간결한 코드가 많습니다. 이런 Pythonic한 코드를 학습하면 여러분의 코드 스타일도 발전합니다.
여러분이 매 문제마다 "일단 풀고 → 리뷰하고 → 개선하는" 습관을 들이면 실력이 빠르게 향상됩니다. 같은 문제를 일주일 후 다시 풀어보면 첫 번째보다 훨씬 나은 코드를 작성할 수 있을 것입니다.
또한 면접에서도 "제 코드를 이렇게 개선할 수 있습니다"라고 말하면 성장 마인드셋을 보여줄 수 있습니다.
실전 팁
💡 문제를 풀고 Discuss 탭에서 "Most Votes" 솔루션을 읽어보세요. 다른 사람들이 어떻게 더 효율적으로 풀었는지 비교하며 배울 점을 찾으세요.
💡 자신의 코드에 주석으로 "TODO: 이 부분을 더 효율적으로 개선 가능"이라고 표시해두세요. 나중에 다시 보면 개선 아이디어가 떠오를 수 있습니다.
💡 같은 문제를 일주일 후 다시 풀어보세요. 처음과 다른 접근법이 떠오르거나 더 깔끔한 코드를 작성할 수 있다면 실력이 성장한 증거입니다.
💡 변수명을 의미 있게 바꾸세요. i, j, k는 반복 인덱스로만 쓰고, 비즈니스 로직 변수는 left_pointer, current_sum, max_length처럼 명확히 표현하세요.
💡 Python의 내장 함수를 활용하세요. sum(), max(), min(), any(), all(), sorted(), enumerate(), zip() 같은 함수를 쓰면 반복문을 줄이고 의도를 명확히 할 수 있습니다.
8. 디버깅_전략
시작하며
여러분이 코드를 완성했는데 예상과 다른 결과가 나오거나 "Runtime Error"를 받았을 때 어디가 잘못됐는지 찾느라 한참 헤맨 적 있나요? print()를 여기저기 넣어보거나 코드를 처음부터 다시 읽으며 시간을 낭비했던 경험 말이죠.
이런 문제는 체계적인 디버깅 전략 없이 무작위로 문제를 찾으려고 하기 때문에 발생합니다. 버그는 코드의 어디든 숨어있을 수 있고, 운에 맡겨 찾으려면 시간이 오래 걸립니다.
바로 이럴 때 필요한 것이 효율적인 디버깅 기법입니다. 문제를 빠르게 좁혀가는 방법, 유용한 디버깅 도구, 흔한 버그 패턴을 알면 10분 걸릴 디버깅을 1분 안에 끝낼 수 있습니다.
개요
간단히 말해서, 디버깅은 코드에서 버그(오류)를 찾아 수정하는 과정입니다. 마치 의사가 증상을 보고 병의 원인을 찾아 치료하는 것처럼, 잘못된 출력이나 에러 메시지에서 버그의 위치를 추론합니다.
왜 디버깅 스킬이 중요한지 설명하자면, 실무에서는 코드 작성보다 디버깅에 더 많은 시간을 쓴다는 연구 결과도 있습니다. Leetcode에서도 로직은 맞는데 작은 실수(인덱스 오류, 초기화 실수, 경계 조건 누락) 때문에 통과하지 못하는 경우가 흔합니다.
빠른 디버깅은 곧 시간 절약입니다. 전통적으로는 에러가 나면 당황하며 코드를 처음부터 다시 읽었다면, 이제는 체계적으로 접근합니다.
첫째, 에러 메시지를 읽고 정확히 어디서 무슨 일이 일어났는지 파악합니다. 둘째, 이진 탐색처럼 코드 범위를 절반씩 좁혀가며 버그 위치를 특정합니다.
셋째, 작은 테스트 케이스로 재현합니다. 디버깅의 핵심 전략은 첫째, 에러 메시지와 스택 트레이스를 꼼꼼히 읽기, 둘째, print 문이나 디버거로 중간 값 확인하기, 셋째, 작은 입력으로 단순화하기, 넷째, 한 번에 한 가지만 바꿔보기입니다.
이 네 가지만 따라도 대부분의 버그를 빠르게 찾을 수 있습니다.
코드 예제
# 디버깅 예제: 이진 탐색 버그 찾기
# 버그 있는 코드
def binary_search_buggy(arr, target):
left, right = 0, len(arr) # 버그 1: right는 len(arr) - 1이어야 함
while left <= right:
mid = (left + right) / 2 # 버그 2: 정수 나눗셈 //를 써야 함
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid # 버그 3: mid + 1이어야 함 (무한 루프 가능)
else:
right = mid - 1
return -1
# 디버깅 과정
def binary_search_debug(arr, target):
left, right = 0, len(arr) - 1 # 수정 1
while left <= right:
mid = (left + right) // 2 # 수정 2
print(f"Debug: left={left}, right={right}, mid={mid}, arr[mid]={arr[mid]}") # 디버그 출력
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1 # 수정 3
else:
right = mid - 1
return -1
# 테스트로 버그 확인
arr = [1, 3, 5, 7, 9]
print(binary_search_debug(arr, 7)) # 디버그 출력으로 각 단계 추적
# 흔한 디버깅 패턴
# 1. IndexError → 배열 경계 확인 (i < len(arr) vs i <= len(arr))
# 2. Infinite Loop → 반복 변수가 변하는지 확인
# 3. Wrong Answer → 작은 입력으로 손으로 추적
# 4. Runtime Error → None 체크, 0으로 나누기 확인
설명
이것이 하는 일: 디버깅은 "왜 내 코드가 예상대로 작동하지 않는가?"라는 질문에 답하는 탐정 작업입니다. 증거(에러 메시지, 출력값)를 수집하고, 가설을 세우고, 검증하는 과학적 과정입니다.
첫 번째로, 에러 메시지를 정확히 읽습니다. "IndexError: list index out of range"는 배열 범위를 벗어났다는 뜻이고, "KeyError: 'x'"는 딕셔너리에 'x' 키가 없다는 뜻입니다.
에러 메시지는 보통 정확히 무엇이 잘못됐는지 알려주므로, 당황하지 말고 천천히 읽으세요. 또한 스택 트레이스(에러가 발생한 줄 번호)를 확인해 정확한 위치를 파악합니다.
그 다음으로, print 문으로 중간 값을 확인합니다. "이 시점에서 변수 x는 어떤 값일까?"를 확인하려면 print(f"x = {x}")를 삽입하세요.
특히 반복문 안에서 매 반복마다 변수가 어떻게 변하는지 추적하면 논리적 오류를 발견하기 쉽습니다. 예를 들어, "left가 계속 0이네?
mid + 1로 업데이트 안 되고 있구나"라는 걸 알 수 있습니다. 세 번째 단계는 문제를 단순화하는 것입니다.
큰 입력에서 버그가 나면 작은 입력(배열 길이 1, 2, 3)으로 재현해보세요. 손으로 코드를 한 줄씩 따라가며 "지금 left=0, right=0, mid=0, 다음은..."처럼 추적하면 어디서 잘못됐는지 명확히 보입니다.
복잡한 문제를 간단한 경우로 줄이는 것이 디버깅의 핵심입니다. 마지막으로, 한 번에 한 가지만 바꿔보세요.
"여기도 의심스럽고 저기도 의심스러워"라며 여러 곳을 동시에 수정하면 오히려 더 꼬입니다. 하나씩 바꿔가며 테스트하면 정확히 어느 부분이 문제였는지 알 수 있고, 나중에 같은 실수를 반복하지 않습니다.
여러분이 디버깅 전략을 익히면 "에러가 나면 어떡하지"라는 두려움이 사라집니다. 오히려 에러 메시지는 친절한 힌트이고, print 문은 강력한 도구라는 것을 알게 됩니다.
면접에서도 "버그가 있다면 이렇게 추적하겠습니다"라고 설명하면 문제 해결 능력을 보여줄 수 있습니다.
실전 팁
💡 Python의 pdb 디버거를 사용하세요. import pdb; pdb.set_trace()를 삽입하면 그 지점에서 코드가 멈추고 변수를 대화형으로 확인할 수 있습니다.
💡 에러 메시지를 Google에 검색하세요. "Python IndexError list index out of range" 같이 검색하면 비슷한 문제를 겪은 사람들의 해결책을 찾을 수 있습니다.
💡 이진 탐색처럼 디버깅하세요. 코드 중간에 print("checkpoint 1"), print("checkpoint 2")를 넣어 어디까지 실행됐는지 확인하면 버그 범위를 빠르게 좁힐 수 있습니다.
💡 흔한 버그 패턴을 외워두세요: 배열 인덱스(i < len vs i <= len), 0으로 나누기, None 참조, 무한 루프(업데이트 안 됨), off-by-one 에러 등이 90% 이상을 차지합니다.
💡 Leetcode의 "Custom Testcase"로 작은 입력을 직접 만들어 테스트하세요. [1], [1,2], []처럼 극단적인 경우를 넣어보면 숨은 버그를 발견할 수 있습니다.
9. 공간_복잡도_최적화
시작하며
여러분이 문제를 풀었는데 "Memory Limit Exceeded" 오류를 받거나, 면접관이 "추가 공간을 사용하지 않고 풀 수 있나요?"라고 물었을 때 당황한 적 있나요? 시간 복잡도는 O(n)으로 완벽한데 메모리 사용 때문에 통과하지 못하는 경우 말이죠.
이런 문제는 시간 복잡도만 고려하고 공간 복잡도를 간과했기 때문에 발생합니다. 큰 입력(n = 10^6)에서 O(n) 공간을 쓰면 수백 MB의 메모리가 필요해 제한을 초과할 수 있습니다.
바로 이럴 때 필요한 것이 공간 복잡도 최적화 기법입니다. 추가 메모리를 줄이거나 제자리(in-place) 알고리즘을 사용하면 같은 기능을 더 적은 메모리로 구현할 수 있습니다.
개요
간단히 말해서, 공간 복잡도는 알고리즘이 실행되는 동안 사용하는 추가 메모리의 양입니다. 시간은 빠른데 메모리를 너무 많이 쓰면 실무에서는 서버 비용이 증가하고, Leetcode에서는 메모리 제한 초과로 실패합니다.
왜 공간 최적화가 중요한지 예를 들어볼까요? 배열을 복사하면 O(n) 공간이 필요하지만, 원본 배열을 직접 수정하면 O(1) 공간으로 해결할 수 있습니다.
특히 모바일이나 임베디드 환경에서는 메모리가 제한적이므로 공간 효율성이 매우 중요합니다. 전통적으로는 편의를 위해 여러 개의 임시 배열, 딕셔너리, 세트를 자유롭게 사용했다면, 이제는 "정말 이 추가 공간이 필요한가?", "원본을 수정해도 되는가?", "상수 공간으로 해결할 방법은?"을 고민합니다.
공간 최적화의 핵심 기법은 첫째, in-place 알고리즘(원본 수정), 둘째, 슬라이딩 변수(배열 대신 몇 개 변수로 추적), 셋째, 비트 마스킹(불린 배열 대신 정수의 비트 사용), 넷째, 투 포인터(추가 배열 없이 포인터로 해결)입니다.
코드 예제
# 문제: 배열 뒤집기
# O(n) 공간: 새 배열 생성
def reverse_array_space(nums):
return nums[::-1] # 새 배열을 만들어 반환 - O(n) 공간
# O(1) 공간: in-place 뒤집기
def reverse_array_inplace(nums):
left, right = 0, len(nums) - 1
while left < right:
# 두 요소 교환 (추가 메모리 없이)
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums # 원본 배열 수정 - O(1) 공간
# 문제: 피보나치 수열의 n번째 값
# O(n) 공간: 모든 값 저장
def fib_array(n):
if n <= 1:
return n
fib = [0, 1]
for i in range(2, n + 1):
fib.append(fib[i-1] + fib[i-2]) # 배열에 모두 저장
return fib[n]
# O(1) 공간: 마지막 두 값만 추적
def fib_optimized(n):
if n <= 1:
return n
prev, curr = 0, 1
for _ in range(2, n + 1):
prev, curr = curr, prev + curr # 두 변수만 업데이트
return curr
# 공간 절약: n=100일 때
# fib_array: 100개 요소 배열 (약 800 bytes)
# fib_optimized: 변수 2개 (약 16 bytes)
설명
이것이 하는 일: 공간 복잡도 최적화는 같은 기능을 더 적은 메모리로 구현하는 기술입니다. 마치 여행 짐을 최소화하는 것처럼, 꼭 필요한 데이터만 메모리에 유지합니다.
첫 번째로, in-place 알고리즘을 고려합니다. 새 배열을 만들지 않고 원본 배열을 직접 수정하면 O(n) 공간을 O(1)로 줄일 수 있습니다.
예를 들어, 배열 뒤집기는 양쪽 끝에서 투 포인터로 교환하면 추가 메모리 없이 해결됩니다. 단, 원본 보존이 필요한 경우에는 사용할 수 없습니다.
그 다음으로, 전체 배열 대신 필요한 값만 변수에 저장합니다. 피보나치 예제처럼 모든 값이 필요하지 않고 최근 몇 개만 있으면 되는 경우, 배열 대신 변수 2-3개로 충분합니다.
이를 "슬라이딩 윈도우" 또는 "슬라이딩 변수" 기법이라고 합니다. 세 번째 단계는 자료구조를 더 효율적인 것으로 바꾸는 것입니다.
불린 배열(True/False를 n개 저장)이 필요하다면 비트 마스킹(정수 하나의 비트로 표현)을 쓰면 공간이 1/8로 줄어듭니다. 또한 set 대신 정렬된 배열로 중복을 제거하면 해시 테이블 오버헤드를 줄일 수 있습니다.
마지막으로, 재귀를 반복문으로 바꾸는 것도 공간 최적화입니다. 재귀는 콜 스택에 O(n) 공간을 쓰지만, 반복문은 O(1) 공간만 씁니다.
깊은 재귀(n이 큰 경우)는 스택 오버플로우를 일으킬 수 있으므로 반복문으로 변환하는 것이 안전합니다. 여러분이 공간 최적화 기법을 익히면 "이 문제를 상수 공간으로 풀 수 있을까?"라는 도전적인 질문에 답할 수 있습니다.
면접에서도 "O(n) 솔루션은 이렇고, O(1) 공간으로 최적화하면 이렇습니다"라고 두 가지를 보여주면 깊이 있는 이해를 증명할 수 있습니다.
실전 팁
💡 문제에서 "can you do it in O(1) space?"라고 물으면 in-place 알고리즘이나 투 포인터를 시도하세요. 대부분 추가 배열 없이 풀 수 있다는 힌트입니다.
💡 동적 프로그래밍(DP)에서 전체 테이블이 필요하지 않으면 슬라이딩 배열을 쓰세요. dp[i]가 dp[i-1], dp[i-2]만 참조하면 배열 대신 변수 2개로 충분합니다.
💡 재귀 깊이가 n에 비례하면 O(n) 공간입니다. 꼬리 재귀 최적화나 반복문으로 바꾸면 O(1)로 줄일 수 있습니다.
💡 Python의 제너레이터를 사용하세요. 큰 리스트를 한 번에 만들지 않고 필요할 때마다 하나씩 생성(yield)하면 메모리를 크게 절약할 수 있습니다.
💡 공간과 시간은 트레이드오프 관계입니다. 해시맵을 쓰면 시간 O(1)이지만 공간 O(n), 정렬하면 시간 O(n log n)이지만 공간 O(1)입니다. 문제의 우선순위를 파악하세요.
10. 문제_유형별_접근법
시작하며
여러분이 새로운 문제를 만났을 때 "이게 배열 문제인가, 그래프 문제인가, 트리 문제인가?" 하며 혼란스러웠던 적 있나요? 어떤 알고리즘을 써야 할지 감이 잡히지 않아 시간을 낭비한 경험 말이죠.
이런 문제는 문제 유형을 분류하는 기준을 모르기 때문에 발생합니다. 사실 Leetcode 문제는 크게 10여 개의 카테고리로 나뉘고, 각 카테고리마다 효과적인 알고리즘이 정해져 있습니다.
바로 이럴 때 필요한 것이 문제 유형별 접근법입니다. "배열/문자열 → 투 포인터", "트리 → BFS/DFS", "최적화 → DP"처럼 유형에 따른 전략을 알면 즉시 올바른 방향으로 나아갈 수 있습니다.
개요
간단히 말해서, 문제 유형 분류는 비슷한 특징을 가진 문제들을 그룹화하고, 각 그룹에 맞는 알고리즘을 적용하는 것입니다. 마치 병원에서 증상에 따라 진료과를 나누는 것처럼, 문제의 특징에 따라 접근법이 달라집니다.
왜 이 분류가 중요한지 설명하자면, 문제 유형을 파악하면 "어떤 자료구조와 알고리즘을 써야 하는지"가 자동으로 떠오릅니다. 예를 들어, "그래프에서 최단 경로"라면 BFS, "모든 경로 탐색"이라면 DFS/백트래킹, "최적 부분 구조"라면 DP를 떠올립니다.
전통적으로는 문제를 하나의 독립적인 퍼즐로 봤다면, 이제는 "이 문제는 전형적인 슬라이딩 윈도우 문제구나"라고 즉시 분류합니다. 같은 유형의 문제는 코드 구조가 80% 이상 비슷하므로, 템플릿을 약간만 수정해도 됩니다.
주요 문제 유형은 배열/문자열(투 포인터, 슬라이딩 윈도우), 연결 리스트(투 포인터, 더미 노드), 트리(DFS, BFS, 재귀), 그래프(BFS, DFS, 유니온 파인드), 정렬/검색(이진 탐색, 퀵셀렉트), 동적 프로그래밍(메모이제이션, 상향식), 백트래킹(재귀, 가지치기), 그리디(로컬 최적 → 전역 최적) 등입니다.
코드 예제
# 유형별 대표 패턴 코드
# 1. 배열 - 투 포인터 (Two Sum in Sorted Array)
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return [left, right]
elif total < target:
left += 1
else:
right -= 1
# 2. 트리 - DFS 재귀 (Maximum Depth)
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
# 3. 그래프 - BFS (Level Order Traversal)
from collections import deque
def level_order(root):
if not root:
return []
queue = deque([root])
result = []
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
# 4. DP - 1D (Climbing Stairs)
def climb_stairs(n):
if n <= 2:
return n
prev, curr = 1, 2
for _ in range(3, n + 1):
prev, curr = curr, prev + curr
return curr
# 5. 백트래킹 (Permutations)
def permute(nums):
result = []
def backtrack(path, remaining):
if not remaining:
result.append(path[:])
return
for i in range(len(remaining)):
backtrack(path + [remaining[i]], remaining[:i] + remaining[i+1:])
backtrack([], nums)
return result
설명
이것이 하는 일: 문제 유형 분류는 수천 개의 문제를 10여 개 카테고리로 정리해 학습 효율을 극대화합니다. 각 유형의 특징과 대표 알고리즘을 알면 새 문제도 빠르게 해결할 수 있습니다.
첫 번째로, 문제의 입력 형태를 봅니다. 배열/문자열이면 투 포인터나 슬라이딩 윈도우, 연결 리스트면 투 포인터나 더미 노드, 트리/그래프면 BFS/DFS, 집합 연산이면 유니온 파인드를 떠올립니다.
입력 형태만 봐도 50% 정도 방향이 잡힙니다. 그 다음으로, 문제의 목표를 파악합니다.
"최단 경로"면 BFS, "모든 경우의 수"면 백트래킹, "최댓값/최솟값 최적화"면 DP나 그리디, "정렬된 배열에서 찾기"면 이진 탐색입니다. 목표가 무엇인지에 따라 알고리즘이 달라집니다.
세 번째 단계는 제약조건을 고려합니다. "n ≤ 20"이면 O(2^n) 백트래킹도 가능, "n ≤ 10^5"면 O(n) 또는 O(n log n)이 필요합니다.
또한 "중복 없음", "정렬됨", "음수 없음" 같은 조건은 알고리즘 선택에 영향을 줍니다. 마지막으로, 각 유형의 템플릿 코드를 외워둡니다.
BFS는 항상 "queue + while + for level", DFS는 "재귀 + base case", 백트래킹은 "재귀 + 선택/탐색/복원", DP는 "점화식 + 초기화 + 반복"의 구조입니다. 이 뼈대를 외우면 문제에 맞게 살만 붙이면 됩니다.
여러분이 유형별 접근법을 마스터하면 문제를 보자마자 "아, 이건 전형적인 슬라이딩 윈도우야"라고 즉시 파악할 수 있습니다. Leetcode를 유형별로 묶어서 풀면 패턴이 빠르게 익숙해지고, 같은 유형의 20-30문제를 풀면 그 유형은 완전히 정복할 수 있습니다.
실전 팁
💡 Leetcode의 "Explore" 메뉴에서 카테고리별로 문제를 풀어보세요. Array, Linked List, Tree, Graph, DP 등 유형별로 정리된 학습 경로가 있습니다.
💡 자신만의 "치트시트"를 만드세요. "정렬된 배열 + 타겟 → 이진 탐색", "트리 + 레벨별 → BFS" 같은 패턴을 한 장에 정리해두면 빠르게 참고할 수 있습니다.
💡 비슷한 유형의 문제를 연속으로 5-10개 풀어보세요. 슬라이딩 윈도우 문제만 하루에 10개 풀면 패턴이 완전히 몸에 배게 됩니다.
💡 유형별 대표 문제를 꼭 풀어보세요. Two Sum(해시맵), Binary Tree Level Order(BFS), Climbing Stairs(DP), Permutations(백트래킹) 같은 클래식 문제는 각 유형의 기본기입니다.
💡 한 유형에서 막히면 다른 유형으로 넘어가세요. DP가 어렵다면 배열 문제로 자신감을 회복한 후 다시 도전하는 것이 효율적입니다. 골고루 연습하는 것이 중요합니다.
댓글 (0)
함께 보면 좋은 카드 뉴스
데이터 증강과 정규화 완벽 가이드
머신러닝 모델의 성능을 극대화하는 핵심 기법인 데이터 증강과 정규화에 대해 알아봅니다. 실무에서 바로 활용할 수 있는 다양한 기법과 실전 예제를 통해 과적합을 방지하고 모델 성능을 향상시키는 방법을 배웁니다.
ResNet과 Skip Connection 완벽 가이드
딥러닝 모델이 깊어질수록 성능이 떨어지는 문제를 해결한 혁신적인 기법, ResNet과 Skip Connection을 초급자도 이해할 수 있도록 쉽게 설명합니다. 실제 구현 코드와 함께 배워보세요.
CNN 아키텍처 완벽 가이드 LeNet AlexNet VGGNet
컴퓨터 비전의 기초가 되는 세 가지 핵심 CNN 아키텍처를 배웁니다. 손글씨 인식부터 이미지 분류까지, 딥러닝의 발전 과정을 따라가며 각 모델의 구조와 특징을 실습 코드와 함께 이해합니다.
CNN 기초 Convolution과 Pooling 완벽 가이드
CNN의 핵심인 Convolution과 Pooling을 초급자도 쉽게 이해할 수 있도록 설명합니다. 이미지 인식의 원리부터 실제 코드 구현까지, 실무에서 바로 활용 가능한 내용을 담았습니다.
TensorFlow와 Keras 완벽 입문 가이드
머신러닝과 딥러닝의 세계로 들어가는 첫걸음! TensorFlow와 Keras 프레임워크를 처음 접하는 분들을 위한 친절한 가이드입니다. 실무에서 바로 활용할 수 있는 핵심 개념과 예제를 통해 AI 모델 개발의 기초를 탄탄히 다져보세요.