배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리
이 글의 핵심
배열과 리스트에 대한 실전 가이드입니다. 코딩 테스트 필수 자료구조 완벽 정리 등을 예제와 함께 상세히 설명합니다.
들어가며: 가장 기본적인 자료구조
”배열만 알면 코딩 테스트 50%는 풀 수 있다”
배열과 리스트는 가장 기본적이면서 가장 많이 쓰이는 자료구조(데이터를 담고 꺼내는 방식·구조)입니다. 코딩 테스트의 절반 이상이 배열 문제입니다.
이 글에서 다루는 것:
- 배열 vs 리스트 차이
- 시간복잡도(입력이 커질 때 실행 시간이 얼마나 늘어나는지) 분석
- 투 포인터(두 개의 인덱스로 배열을 훑는 기법), 슬라이딩 윈도우(고정 크기 구간을 한 칸씩 옮기며 보는 기법)
- 실전 문제 풀이
목차
1. 배열 (Array)
배열이란?
배열(Array)은 연속된 메모리 공간에 같은 타입의 데이터를 저장하는 가장 기본적인 자료구조입니다. 인덱스를 통해 각 요소에 직접 접근할 수 있습니다.
배열의 메모리 구조:
메모리 주소: 1000 1004 1008 1012 1016
배열 값: [1] [2] [3] [4] [5]
인덱스: 0 1 2 3 4
각 요소는 연속된 메모리에 저장됨
→ 인덱스로 주소 계산: 주소 = 시작주소 + (인덱스 × 요소크기)
→ arr[2]의 주소 = 1000 + (2 × 4) = 1008Python에서의 배열
Python의 list는 연속된 메모리에 값을 두고, 인덱스만 알면 O(1)(입력 크기와 거의 무관하게 일정한 시간)로 읽습니다. 책장에 꽂힌 책처럼, 몇 번째 권인지만 알면 바로 집어 드는 방식입니다.
# Python list는 동적 배열 (크기 자동 조절)
arr = [1, 2, 3, 4, 5]
# 인덱스 접근 - O(1) 시간복잡도
print(arr[0]) # 1 (첫 번째 요소)
print(arr[2]) # 3 (세 번째 요소)
print(arr[-1]) # 5 (마지막 요소, 음수 인덱스)
print(arr[-2]) # 4 (뒤에서 두 번째)
# 슬라이싱 - 부분 배열 추출
print(arr[1:4]) # [2, 3, 4] (인덱스 1~3)
print(arr[:3]) # [1, 2, 3] (처음부터 인덱스 2까지)
print(arr[2:]) # [3, 4, 5] (인덱스 2부터 끝까지)
print(arr[::2]) # [1, 3, 5] (2칸씩 건너뛰기)
print(arr[::-1]) # [5, 4, 3, 2, 1] (역순)C++에서의 배열:
// C++ 정적 배열 (크기 고정)
int arr[5] = {1, 2, 3, 4, 5};
cout << arr[0] << endl; // 1
cout << arr[2] << endl; // 3
// 크기 확인 (컴파일 타임 — 코드를 빌드할 때 이미 정해지는 값)
int size = sizeof(arr) / sizeof(arr[0]); // 5
// 범위 초과 시 미정의 동작 (위험!)
// cout << arr[10] << endl; // 쓰레기 값 또는 크래시배열의 특징
장점:
- ✅ 인덱스 접근 O(1):
arr[i]로 즉시 접근 가능 (주소 계산만 하면 됨) - ✅ 캐시 효율 좋음: 연속된 메모리라 CPU 캐시에 한 번에 로드
- ✅ 간단하고 직관적: 가장 기본적인 자료구조로 이해하기 쉬움
- ✅ 메모리 효율: 포인터 오버헤드 없음 (연결 리스트 대비)
단점:
- ❌ 크기 고정 (정적 배열): 생성 후 크기 변경 불가
- ❌ 삽입/삭제 O(n): 중간에 요소를 넣거나 빼면 나머지를 이동해야 함
- ❌ 메모리 낭비 가능: 크기를 미리 크게 잡으면 사용하지 않는 공간 발생
시간복잡도 정리:
| 연산 | 시간복잡도 | 설명 |
|---|---|---|
| 접근 (arr[i]) | O(1) | 인덱스로 직접 접근 |
| 검색 (값 찾기) | O(n) | 모든 요소를 순회해야 함 |
| 앞쪽 삽입 | O(n) | 모든 요소를 오른쪽으로 이동 |
| 뒤쪽 삽입 | O(1) | 동적 배열은 분할상환 O(1) |
| 중간 삽입 | O(n) | 삽입 위치 이후 요소 이동 |
| 삭제 | O(n) | 삭제 위치 이후 요소 이동 |
동적 배열 (Dynamic Array)
동적 배열은 크기가 자동으로 늘어나는 배열입니다. Python의 list, C++의 vector, Java의 ArrayList가 모두 동적 배열입니다.
동적 배열의 동작 원리:
초기 상태: capacity=4, size=0
[_][_][_][_]
append(1): [1][_][_][_] size=1
append(2): [1][2][_][_] size=2
append(3): [1][2][3][_] size=3
append(4): [1][2][3][4] size=4 (capacity 가득 참)
append(5): capacity 부족 → 재할당!
1. 새 메모리 할당 (capacity=8, 보통 2배)
2. 기존 요소 복사: [1][2][3][4][_][_][_][_]
3. 새 요소 추가: [1][2][3][4][5][_][_][_]
4. 기존 메모리 해제분할상환 O(1)의 의미: 대부분의 append는 O(1)이지만, 가끔 재할당으로 O(n)이 발생합니다. 평균적으로는 O(1)입니다.
Python list의 동적 배열 연산:
# Python list (동적 배열)
arr = []
# 뒤쪽 추가 - O(1) 분할상환
arr.append(1)
arr.append(2)
arr.append(3)
print(arr) # [1, 2, 3]
# 여러 요소 추가
arr.extend([4, 5, 6])
print(arr) # [1, 2, 3, 4, 5, 6]
# 중간 삽입 - O(n)
arr.insert(1, 10) # 인덱스 1에 10 삽입
print(arr) # [1, 10, 2, 3, 4, 5, 6]
# 동작: [1, 2, 3, ...] → [1, _, 2, 3, ...] → [1, 10, 2, 3, ...]
# 인덱스 1 이후 모든 요소를 오른쪽으로 이동 (O(n))
# 값으로 삭제 - O(n)
arr.remove(10) # 값 10을 찾아서 삭제
print(arr) # [1, 2, 3, 4, 5, 6]
# 동작: 10을 찾기 위해 순회 (O(n)) + 삭제 후 요소 이동 (O(n))
# 인덱스로 삭제 - O(n)
del arr[0] # 인덱스 0 삭제
print(arr) # [2, 3, 4, 5, 6]
# 뒤쪽 삭제 - O(1)
arr.pop() # 마지막 요소 제거
print(arr) # [2, 3, 4, 5]
# 특정 인덱스 삭제 - O(n)
arr.pop(1) # 인덱스 1 제거
print(arr) # [2, 4, 5]
# 길이 확인 - O(1)
print(len(arr)) # 3
# 값 존재 여부 - O(n)
print(3 in arr) # False (순회하며 찾음)
print(4 in arr) # TrueC++ vector의 동적 배열 연산:
// C++ vector (동적 배열)
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> vec;
// 뒤쪽 추가 - O(1) 분할상환
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
// vec: [1, 2, 3]
// 중간 삽입 - O(n)
vec.insert(vec.begin() + 1, 10);
// vec: [1, 10, 2, 3]
// vec.begin() + 1은 인덱스 1을 가리키는 반복자
// 중간 삭제 - O(n)
vec.erase(vec.begin() + 1);
// vec: [1, 2, 3]
// 뒤쪽 삭제 - O(1)
vec.pop_back();
// vec: [1, 2]
// 크기 확인 - O(1)
cout << vec.size() << endl; // 2
// 용량 확인 (재할당 없이 저장 가능한 요소 수)
cout << vec.capacity() << endl; // 4 (예시)
// 용량 미리 확보 (재할당 방지)
vec.reserve(100); // 100개 요소를 위한 메모리 할당
return 0;
}reserve의 중요성:
# Python에서 reserve 효과 (C++의 reserve와 유사)
import time
# reserve 없이 (재할당 빈번)
start = time.time()
arr1 = []
for i in range(1000000):
arr1.append(i)
print(f"시간: {time.time() - start:.4f}초") # 약 0.15초
# reserve 효과 (Python은 자동 최적화)
# C++에서는 vec.reserve(1000000)로 명시배열의 특징
장점:
- ✅ 인덱스 접근 O(1):
arr[i]로 즉시 접근 (주소 계산: 시작주소 + i × 요소크기) - ✅ 캐시 효율 좋음: 연속된 메모리라 CPU 캐시에 한 번에 로드됨
- ✅ 간단하고 직관적: 가장 기본적인 자료구조로 이해하기 쉬움
- ✅ 메모리 효율: 포인터 오버헤드 없음 (각 요소가 순수 데이터)
단점:
- ❌ 크기 고정 (정적 배열): 생성 시 크기를 정하면 변경 불가 (C++ 배열)
- ❌ 삽입/삭제 O(n): 중간에 요소를 넣거나 빼면 나머지를 모두 이동
- ❌ 메모리 낭비 가능: 동적 배열은 여유 공간을 미리 확보 (capacity > size)
실전 활용 시나리오:
- 로그 저장: 로그를 순서대로 저장하고 나중에 순회 (뒤쪽 추가만)
- 점수 관리: 학생 점수를 저장하고 인덱스로 접근
- 버퍼: 데이터를 임시로 저장했다가 일괄 처리
- 정렬된 데이터: 이진 탐색을 위해 정렬된 배열 유지
2. 리스트 (Linked List)
연결 리스트란?
연결 리스트는 노드(Node)가 next 포인터로 다음 노드를 가리키며 이어진 자료구조입니다. 배열이 한 줄로 붙어 있는 반면, 연결 리스트는 보물찾기 카드처럼 “다음 장소”만 적어 두고 따라가는 형태라고 보면 됩니다.
# Python 구현
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def print_list(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# 사용
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list() # 1 -> 2 -> 3 -> None위 예제에서 append는 마지막 노드를 찾기 위해 head부터 끝까지 따라가므로 한 번 호출당 O(n)입니다. 반면 이미 노드 위치를 알고 있다면 포인터만 바꿔 삽입·삭제를 O(1)로 할 수 있다는 점이 배열과 다른 결입니다.
리스트의 특징
장점:
- ✅ 삽입/삭제 O(1): 포인터만 변경
- ✅ 크기 제한 없음
- ✅ 메모리 효율적 (필요한 만큼만)
단점:
- ❌ 인덱스 접근 O(n): 순차 탐색 필요
- ❌ 캐시 효율 나쁨: 메모리 흩어짐
- ❌ 포인터 오버헤드
3. 시간복잡도 비교
| 연산 | 배열 | 연결 리스트 |
|---|---|---|
| 접근 (인덱스) | O(1) | O(n) |
| 검색 (값) | O(n) | O(n) |
| 앞쪽 삽입 | O(n) | O(1) |
| 뒤쪽 삽입 | O(1) 분할상환 | O(1) |
| 중간 삽입 | O(n) | O(1)* |
| 앞쪽 삭제 | O(n) | O(1) |
| 뒤쪽 삭제 | O(1) | O(n) |
| 중간 삭제 | O(n) | O(1)* |
* 해당 노드 위치를 알고 있을 때
4. 실전 기법
투 포인터 (Two Pointers)
투 포인터는 두 개의 인덱스(포인터)를 사용하여 배열을 효율적으로 탐색하는 기법입니다. O(n²) → O(n)으로 최적화할 수 있습니다.
기본 패턴:
정렬된 배열: [1, 2, 3, 4, 6]
↑ ↑
left right
1. left와 right를 양 끝에서 시작
2. 조건에 따라 left를 오른쪽으로, right를 왼쪽으로 이동
3. left와 right가 만날 때까지 반복예제 1: 정렬된 배열에서 두 수의 합
def two_sum_sorted(arr, target):
"""
정렬된 배열에서 합이 target인 두 수의 인덱스를 찾습니다.
시간복잡도: O(n)
공간복잡도: O(1)
Args:
arr: 정렬된 정수 배열
target: 목표 합
Returns:
[left, right] 인덱스 쌍 또는 빈 리스트
"""
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
# 합이 작으면 왼쪽 포인터를 오른쪽으로 (더 큰 값 필요)
left += 1
else:
# 합이 크면 오른쪽 포인터를 왼쪽으로 (더 작은 값 필요)
right -= 1
return []
# 테스트
arr = [1, 2, 3, 4, 6]
target = 6
result = two_sum_sorted(arr, target)
print(result) # [1, 3] (arr[1]=2, arr[3]=4, 2+4=6)
# 실행 과정:
# left=0, right=4: arr[0]+arr[4] = 1+6 = 7 > 6 → right=3
# left=0, right=3: arr[0]+arr[3] = 1+4 = 5 < 6 → left=1
# left=1, right=3: arr[1]+arr[3] = 2+4 = 6 → 찾음!무차별 대입 vs 투 포인터 비교:
# ❌ 무차별 대입 - O(n²)
def two_sum_brute_force(arr, target):
n = len(arr)
for i in range(n):
for j in range(i + 1, n):
if arr[i] + arr[j] == target:
return [i, j]
return []
# ✅ 투 포인터 - O(n)
# (위의 two_sum_sorted 함수)
# 성능 비교
import time
arr = list(range(1, 10001)) # [1, 2, ..., 10000]
target = 19999 # 마지막 두 수의 합
# 무차별 대입
start = time.time()
two_sum_brute_force(arr, target)
print(f"무차별 대입: {time.time() - start:.4f}초") # 약 0.5초
# 투 포인터
start = time.time()
two_sum_sorted(arr, target)
print(f"투 포인터: {time.time() - start:.4f}초") # 약 0.0001초예제 2: 배열에서 중복 제거 (in-place)
def remove_duplicates_inplace(arr):
"""
정렬된 배열에서 중복을 제거합니다 (in-place).
Args:
arr: 정렬된 배열
Returns:
int: 중복 제거 후 배열의 새 길이
"""
if not arr:
return 0
# write_idx: 고유한 값을 쓸 위치
write_idx = 1
# read_idx: 읽을 위치
for read_idx in range(1, len(arr)):
# 이전 값과 다르면 고유한 값
if arr[read_idx] != arr[read_idx - 1]:
arr[write_idx] = arr[read_idx]
write_idx += 1
return write_idx
# 테스트
arr = [1, 1, 2, 2, 2, 3, 4, 4, 5]
length = remove_duplicates_inplace(arr)
print(arr[:length]) # [1, 2, 3, 4, 5]
# 실행 과정:
# [1, 1, 2, 2, 2, 3, 4, 4, 5]
# w r
# arr[0]=1, arr[1]=1 (같음) → write_idx 그대로
#
# w r
# arr[1]=1, arr[2]=2 (다름) → arr[1]=2, write_idx=2
#
# [1, 2, 2, 2, 2, 3, 4, 4, 5]
# w r
# arr[2]=2, arr[3]=2 (같음) → write_idx 그대로
# ...슬라이딩 윈도우 (Sliding Window)
슬라이딩 윈도우는 고정 크기의 윈도우를 배열 위에서 이동하며 계산하는 기법입니다. O(n×k) → O(n)으로 최적화할 수 있습니다.
기본 원리:
배열: [1, 4, 2, 10, 23, 3, 1, 0, 20]
윈도우 크기: k=4
1단계: [1, 4, 2, 10] 23, 3, 1, 0, 20 → 합: 17
2단계: 1, [4, 2, 10, 23] 3, 1, 0, 20 → 합: 39 (17 - 1 + 23)
3단계: 1, 4, [2, 10, 23, 3] 1, 0, 20 → 합: 38 (39 - 4 + 3)
...
핵심: 이전 합에서 빠지는 값을 빼고, 새로 들어오는 값을 더함예제: 크기 k인 부분 배열의 최대 합
def max_sum_subarray(arr, k):
"""
크기 k인 부분 배열의 최대 합을 찾습니다.
시간복잡도: O(n)
공간복잡도: O(1)
Args:
arr: 정수 배열
k: 윈도우 크기
Returns:
최대 합 또는 None (배열이 k보다 작을 때)
"""
if len(arr) < k:
return None
# 1단계: 첫 윈도우의 합 계산 - O(k)
window_sum = sum(arr[:k])
max_sum = window_sum
print(f"초기 윈도우 {arr[:k]}: 합={window_sum}")
# 2단계: 윈도우를 한 칸씩 이동 - O(n-k)
for i in range(k, len(arr)):
# 윈도우 이동: 왼쪽 요소 제거, 오른쪽 요소 추가
window_sum = window_sum - arr[i - k] + arr[i]
print(f"윈도우 {arr[i-k+1:i+1]}: 합={window_sum}")
max_sum = max(max_sum, window_sum)
return max_sum
# 테스트
arr = [1, 4, 2, 10, 23, 3, 1, 0, 20]
k = 4
result = max_sum_subarray(arr, k)
print(f"\n최대 합: {result}") # 39 (10+23+3+1)
# 출력:
# 초기 윈도우 [1, 4, 2, 10]: 합=17
# 윈도우 [4, 2, 10, 23]: 합=39
# 윈도우 [2, 10, 23, 3]: 합=38
# 윈도우 [10, 23, 3, 1]: 합=37
# 윈도우 [23, 3, 1, 0]: 합=27
# 윈도우 [3, 1, 0, 20]: 합=24
# 최대 합: 39무차별 대입 vs 슬라이딩 윈도우 비교:
# ❌ 무차별 대입 - O(n×k)
def max_sum_brute_force(arr, k):
max_sum = float('-inf')
for i in range(len(arr) - k + 1):
# 매번 k개 요소의 합을 다시 계산
current_sum = sum(arr[i:i+k]) # O(k)
max_sum = max(max_sum, current_sum)
return max_sum
# ✅ 슬라이딩 윈도우 - O(n)
# (위의 max_sum_subarray 함수)
# 성능 비교
arr = list(range(1, 100001)) # 10만 개
k = 1000
import time
start = time.time()
max_sum_brute_force(arr, k)
print(f"무차별 대입: {time.time() - start:.4f}초") # 약 5초
start = time.time()
max_sum_subarray(arr, k)
print(f"슬라이딩 윈도우: {time.time() - start:.4f}초") # 약 0.01초슬라이딩 윈도우 활용 시나리오:
- 연속된 k일 동안의 최대 매출
- 고정 크기 버퍼의 평균값 계산
- 네트워크 패킷의 이동 평균
- 시계열 데이터의 이동 통계
부분 배열 (Subarray)
부분 배열(Subarray)은 배열에서 연속된 요소들의 부분 집합입니다. 부분 수열(Subsequence)과 달리 요소가 연속되어야 합니다.
부분 배열 vs 부분 수열:
arr = [1, 2, 3, 4, 5]
# 부분 배열 (연속)
# [1, 2], [2, 3, 4], [3, 4, 5] 등
# 부분 수열 (비연속 가능)
# [1, 3, 5], [2, 4], [1, 2, 4] 등예제: 최대 부분 배열 합 (Kadane’s Algorithm)
Kadane 알고리즘은 O(n) 시간에 최대 부분 배열 합을 찾는 유명한 알고리즘입니다.
def max_subarray_sum(arr):
"""
최대 부분 배열 합을 찾습니다 (Kadane's Algorithm).
시간복잡도: O(n)
공간복잡도: O(1)
Args:
arr: 정수 배열 (음수 포함 가능)
Returns:
최대 부분 배열 합
"""
if not arr:
return 0
max_sum = current_sum = arr[0]
for num in arr[1:]:
# 핵심 아이디어: 현재까지의 합에 num을 더할지,
# 아니면 num부터 새로 시작할지 선택
current_sum = max(num, current_sum + num)
# 최댓값 갱신
max_sum = max(max_sum, current_sum)
return max_sum
# 테스트
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result = max_subarray_sum(arr)
print(result) # 6 (부분 배열: [4, -1, 2, 1])
# 실행 과정:
# arr[0]=-2: current_sum=-2, max_sum=-2
# arr[1]=1: current_sum=max(1, -2+1)=1, max_sum=1
# arr[2]=-3: current_sum=max(-3, 1-3)=-2, max_sum=1
# arr[3]=4: current_sum=max(4, -2+4)=4, max_sum=4
# arr[4]=-1: current_sum=max(-1, 4-1)=3, max_sum=4
# arr[5]=2: current_sum=max(2, 3+2)=5, max_sum=5
# arr[6]=1: current_sum=max(1, 5+1)=6, max_sum=6
# arr[7]=-5: current_sum=max(-5, 6-5)=1, max_sum=6
# arr[8]=4: current_sum=max(4, 1+4)=5, max_sum=6부분 배열 인덱스까지 찾기:
def max_subarray_with_indices(arr):
"""최대 부분 배열의 합과 시작/끝 인덱스를 반환합니다."""
if not arr:
return 0, -1, -1
max_sum = current_sum = arr[0]
max_start = max_end = 0
current_start = 0
for i in range(1, len(arr)):
if arr[i] > current_sum + arr[i]:
current_sum = arr[i]
current_start = i
else:
current_sum = current_sum + arr[i]
if current_sum > max_sum:
max_sum = current_sum
max_start = current_start
max_end = i
return max_sum, max_start, max_end
# 테스트
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
sum_val, start, end = max_subarray_with_indices(arr)
print(f"최대 합: {sum_val}")
print(f"부분 배열: {arr[start:end+1]}")
# 출력:
# 최대 합: 6
# 부분 배열: [4, -1, 2, 1]5. 문제 풀이
문제 1: 배열 회전
문제: 배열을 오른쪽으로 k칸 회전하세요.
def rotate_array(arr, k):
"""
배열을 오른쪽으로 k칸 회전합니다.
예: [1,2,3,4,5], k=2 → [4,5,1,2,3]
시간복잡도: O(n)
공간복잡도: O(n) (슬라이싱) 또는 O(1) (in-place)
"""
if not arr:
return arr
n = len(arr)
k = k % n # k가 n보다 클 때 처리 (예: k=7, n=5 → k=2)
# 방법 1: 슬라이싱 (간단하지만 O(n) 공간)
return arr[-k:] + arr[:-k]
# arr[-k:]: 뒤에서 k개 요소 [4, 5]
# arr[:-k]: 나머지 요소 [1, 2, 3]
# 결과: [4, 5] + [1, 2, 3] = [4, 5, 1, 2, 3]
# 테스트
arr = [1, 2, 3, 4, 5]
print(rotate_array(arr, 2)) # [4, 5, 1, 2, 3]
print(rotate_array(arr, 7)) # [4, 5, 1, 2, 3] (7 % 5 = 2)
print(rotate_array(arr, 0)) # [1, 2, 3, 4, 5] (회전 없음)방법 2: 3번 뒤집기 (in-place, O(1) 공간)
def rotate_array_inplace(arr, k):
"""
배열을 in-place로 회전합니다 (추가 메모리 사용 없음).
알고리즘:
1. 전체 배열 뒤집기
2. 앞 k개 뒤집기
3. 나머지 뒤집기
"""
n = len(arr)
k = k % n
# 헬퍼 함수: 배열의 일부를 뒤집기
def reverse(start, end):
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start += 1
end -= 1
# 1. 전체 뒤집기: [1,2,3,4,5] → [5,4,3,2,1]
reverse(0, n - 1)
# 2. 앞 k개 뒤집기: [5,4,3,2,1] → [4,5,3,2,1] (k=2)
reverse(0, k - 1)
# 3. 나머지 뒤집기: [4,5,3,2,1] → [4,5,1,2,3]
reverse(k, n - 1)
return arr
# 테스트
arr = [1, 2, 3, 4, 5]
print(rotate_array_inplace(arr.copy(), 2)) # [4, 5, 1, 2, 3]문제 2: 중복 제거 (정렬된 배열)
문제: 정렬된 배열에서 중복을 제거하고 새 길이를 반환하세요 (in-place).
def remove_duplicates(arr):
"""
정렬된 배열에서 중복 제거 (in-place).
예: [1,1,2,2,3] → [1,2,3], 길이 3 반환
시간복잡도: O(n)
공간복잡도: O(1)
"""
if not arr:
return 0
# write_idx: 고유한 값을 쓸 위치
write_idx = 1
# read_idx: 현재 읽는 위치
for read_idx in range(1, len(arr)):
# 이전 값과 다르면 고유한 값
if arr[read_idx] != arr[read_idx - 1]:
arr[write_idx] = arr[read_idx]
write_idx += 1
return write_idx # 새로운 길이
# 테스트
arr = [1, 1, 2, 2, 3, 4, 4, 5]
length = remove_duplicates(arr)
print(f"새 길이: {length}")
print(f"결과: {arr[:length]}")
# 출력:
# 새 길이: 5
# 결과: [1, 2, 3, 4, 5]LeetCode 스타일 문제:
# LeetCode 26. Remove Duplicates from Sorted Array
class Solution:
def removeDuplicates(self, nums: list[int]) -> int:
"""
정렬된 배열 nums를 in-place로 수정하여 중복을 제거합니다.
Returns:
k: 고유한 요소의 개수
nums[:k]는 고유한 요소들
"""
if not nums:
return 0
k = 1
for i in range(1, len(nums)):
if nums[i] != nums[i - 1]:
nums[k] = nums[i]
k += 1
return k
# 테스트
solution = Solution()
nums = [1, 1, 2, 2, 2, 3, 3]
k = solution.removeDuplicates(nums)
print(f"k={k}, nums[:k]={nums[:k]}")
# 출력: k=3, nums[:k]=[1, 2, 3]문제 3: 배열 합병 (Merge Sorted Arrays)
문제: 두 정렬된 배열을 합쳐서 하나의 정렬된 배열을 만드세요.
def merge_sorted_arrays(arr1, arr2):
"""
두 정렬된 배열을 합병합니다 (Merge Sort의 merge 단계).
예: [1,3,5], [2,4,6] → [1,2,3,4,5,6]
시간복잡도: O(n + m)
공간복잡도: O(n + m)
"""
result = []
i, j = 0, 0
# 두 배열을 비교하며 작은 값부터 추가
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
# 남은 요소 추가 (한쪽 배열이 먼저 끝났을 때)
result.extend(arr1[i:])
result.extend(arr2[j:])
return result
# 테스트
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
result = merge_sorted_arrays(arr1, arr2)
print(result) # [1, 2, 3, 4, 5, 6, 7, 8]
# 실행 과정:
# i=0, j=0: arr1[0]=1 < arr2[0]=2 → result=[1], i=1
# i=1, j=0: arr1[1]=3 > arr2[0]=2 → result=[1,2], j=1
# i=1, j=1: arr1[1]=3 < arr2[1]=4 → result=[1,2,3], i=2
# ...실전 응용 - k개의 정렬된 배열 합병:
import heapq
def merge_k_sorted_arrays(arrays):
"""
k개의 정렬된 배열을 하나로 합병합니다.
시간복잡도: O(N log k) (N: 전체 요소 수, k: 배열 개수)
"""
# 최소 힙 사용
heap = []
result = []
# 각 배열의 첫 요소를 힙에 추가
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0)) # (값, 배열 인덱스, 요소 인덱스)
# 힙에서 최솟값을 꺼내고, 다음 요소를 추가
while heap:
val, arr_idx, elem_idx = heapq.heappop(heap)
result.append(val)
# 해당 배열의 다음 요소가 있으면 힙에 추가
if elem_idx + 1 < len(arrays[arr_idx]):
next_val = arrays[arr_idx][elem_idx + 1]
heapq.heappush(heap, (next_val, arr_idx, elem_idx + 1))
return result
# 테스트
arrays = [
[1, 4, 7],
[2, 5, 8],
[3, 6, 9]
]
print(merge_k_sorted_arrays(arrays))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]문제 4: 배열에서 최빈값 찾기
from collections import Counter
def find_most_frequent(arr):
"""
배열에서 가장 자주 나타나는 값을 찾습니다.
시간복잡도: O(n)
공간복잡도: O(n)
"""
if not arr:
return None
# Counter로 빈도 계산
counter = Counter(arr)
# 가장 빈도가 높은 값 반환
most_common = counter.most_common(1)
return most_common[0][0] if most_common else None
# 테스트
arr = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
print(find_most_frequent(arr)) # 4 (4번 등장)
# 수동 구현 (Counter 없이)
def find_most_frequent_manual(arr):
"""Counter 없이 수동으로 구현"""
freq = {}
# 빈도 계산
for num in arr:
freq[num] = freq.get(num, 0) + 1
# 최댓값 찾기
max_count = 0
most_frequent = None
for num, count in freq.items():
if count > max_count:
max_count = count
most_frequent = num
return most_frequent
print(find_most_frequent_manual(arr)) # 4문제 5: 배열 재배치 (짝수/홀수 분리)
def partition_even_odd(arr):
"""
배열을 짝수는 앞, 홀수는 뒤로 재배치합니다 (in-place).
시간복잡도: O(n)
공간복잡도: O(1)
"""
left = 0
right = len(arr) - 1
while left < right:
# 왼쪽에서 홀수 찾기
while left < right and arr[left] % 2 == 0:
left += 1
# 오른쪽에서 짝수 찾기
while left < right and arr[right] % 2 == 1:
right -= 1
# 교환
if left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
return arr
# 테스트
arr = [1, 2, 3, 4, 5, 6, 7, 8]
print(partition_even_odd(arr))
# [8, 2, 6, 4, 5, 3, 7, 1] (순서는 다를 수 있음, 짝수가 앞에만 오면 됨)
# 검증
result = partition_even_odd([1, 2, 3, 4, 5, 6, 7, 8])
even_part = [x for x in result if x % 2 == 0]
odd_part = [x for x in result if x % 2 == 1]
print(f"짝수: {even_part}, 홀수: {odd_part}")문제 6: 배열에서 k번째 큰 수 찾기
import heapq
def find_kth_largest(arr, k):
"""
배열에서 k번째로 큰 수를 찾습니다.
시간복잡도: O(n log k)
공간복잡도: O(k)
"""
# 방법 1: 정렬 (간단하지만 O(n log n))
# return sorted(arr, reverse=True)[k - 1]
# 방법 2: 최소 힙 사용 (O(n log k))
# 크기 k인 최소 힙을 유지
heap = arr[:k]
heapq.heapify(heap) # O(k)
for num in arr[k:]:
if num > heap[0]: # 현재 힙의 최솟값보다 크면
heapq.heapreplace(heap, num) # 최솟값 제거, num 추가
return heap[0] # 힙의 최솟값 = k번째 큰 수
# 테스트
arr = [3, 2, 1, 5, 6, 4]
print(find_kth_largest(arr, 2)) # 5 (두 번째로 큰 수)
print(find_kth_largest(arr, 4)) # 3 (네 번째로 큰 수)
# 실행 과정 (k=2):
# 초기 힙: [3, 2] (최소 힙)
# num=1: 1 < 2 → 무시
# num=5: 5 > 2 → 힙: [3, 5]
# num=6: 6 > 3 → 힙: [5, 6]
# num=4: 4 < 5 → 무시
# 결과: heap[0] = 5실전 팁
코딩 테스트 팁
# ✅ 좋은 습관
# 1. 경계 조건 확인
if not arr or len(arr) == 0:
return []
# 2. 인덱스 범위 체크
if i >= 0 and i < len(arr):
print(arr[i])
# 3. 슬라이싱 활용
arr[:] # 복사
arr[::-1] # 뒤집기
arr[::2] # 짝수 인덱스
# ❌ 피해야 할 실수
# 1. 인덱스 범위 초과
# arr[len(arr)] # IndexError!
# 2. 음수 인덱스 혼동
# arr[-1] # 마지막 요소 (에러 아님)
# 3. 얕은 복사 문제
# arr2 = arr # 같은 객체!
# arr2 = arr[:] # 진짜 복사정리
핵심 요약
- 배열: 연속 메모리, 인덱스 접근 O(1), 삽입/삭제 O(n)
- 리스트: 노드 연결, 삽입/삭제 O(1), 인덱스 접근 O(n)
- 투 포인터: 정렬된 배열에서 O(n) 탐색
- 슬라이딩 윈도우: 부분 배열 문제 최적화
- Python list = 동적 배열 (C++ vector와 동일)
문제 풀이 전략
- 입력 크기 확인: n ≤ 100 → O(n²) 가능, n ≤ 10⁶ → O(n) 필요
- 정렬 여부: 정렬되어 있으면 이진 탐색, 투 포인터 고려
- 공간복잡도: in-place 요구 시 투 포인터, 슬라이딩 윈도우
다음 단계
- 스택과 큐
- 해시 테이블
- 이진 탐색
추천 문제 (난이도별)
입문 (Bronze/Easy)
백준:
- 10818번: 최소, 최대 - 배열 순회 기본
- 2562번: 최댓값 - 최댓값과 인덱스 찾기
- 10807번: 개수 세기 - 특정 값 개수 세기
- 10871번: X보다 작은 수 - 조건 필터링
프로그래머스:
- 두 개 뽑아서 더하기 - 이중 반복문
- K번째수 - 슬라이싱과 정렬
초급 (Silver/Medium)
LeetCode:
- 1. Two Sum - 해시맵 활용
- 26. Remove Duplicates - 투 포인터
- 27. Remove Element - in-place 삭제
- 88. Merge Sorted Array - 배열 합병
백준:
- 1546번: 평균 - 배열 변환
- 3273번: 두 수의 합 - 투 포인터
중급 (Gold/Hard)
LeetCode:
- 53. Maximum Subarray - Kadane 알고리즘
- 121. Best Time to Buy and Sell Stock - 최대 이익
- 238. Product of Array Except Self - 누적곱
- 560. Subarray Sum Equals K - 누적합 + 해시맵
백준:
- 2003번: 수들의 합 2 - 투 포인터
- 1806번: 부분합 - 슬라이딩 윈도우
문제 풀이 전략
1단계: 문제 이해
- 입력 크기 확인 (n ≤ 100 → O(n²) 가능, n ≤ 10⁶ → O(n) 필요)
- 정렬 여부 확인 (정렬되어 있으면 이진 탐색, 투 포인터 고려)
- in-place 요구 여부 (추가 메모리 사용 제한)
2단계: 알고리즘 선택
- 정렬된 배열 + 두 수 찾기 → 투 포인터
- 고정 크기 부분 배열 → 슬라이딩 윈도우
- 최대/최소 부분 배열 → Kadane 알고리즘
- 빈도 계산 → 해시맵 (Counter)
3단계: 시간복잡도 검증
- O(n): 1억 연산 → 약 1초
- O(n log n): 정렬, 이진 탐색
- O(n²): n ≤ 5000까지 가능
4단계: 테스트 케이스
- 빈 배열:
[] - 단일 요소:
[1] - 모두 같은 값:
[5, 5, 5] - 정렬된 배열:
[1, 2, 3] - 역순 배열:
[3, 2, 1] - 음수 포함:
[-1, 0, 1]
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
- 스택과 큐 | LIFO와 FIFO 자료구조 완벽 정리
- 해시 테이블 | O(1) 검색의 비밀
- 이진 탐색 | 정렬된 배열에서 O(log n) 검색
- 투 포인터 | 정렬된 배열 최적화 기법
- 슬라이딩 윈도우 | 부분 배열 문제 해결
이 글에서 다루는 키워드 (관련 검색어)
배열, 리스트, Array, Linked List, 자료구조, 시간복잡도, 투 포인터, Two Pointers, 슬라이딩 윈도우, Sliding Window, Kadane 알고리즘, 부분 배열, Subarray, 동적 배열, Dynamic Array, Python list, C++ vector, 코딩 테스트, 알고리즘 문제 등으로 검색하시면 이 글이 도움이 됩니다.
마치며
배열은 가장 기본적이면서 가장 중요한 자료구조입니다. 코딩 테스트 문제의 50% 이상이 배열 문제이며, 투 포인터와 슬라이딩 윈도우만 잘 익혀도 많은 문제를 효율적으로 풀 수 있습니다. 처음에는 무차별 대입(Brute Force)으로 풀어 보고, 시간 초과가 나면 투 포인터·슬라이딩 윈도우 같은 패턴으로 최적화해 보시면 됩니다. 같은 유형을 반복해 풀다 보면 자연스럽게 익숙해집니다.
학습 로드맵:
- 배열 기본: 인덱스 접근, 슬라이싱, 시간복잡도 이해
- 투 포인터: 정렬된 배열에서 두 수 찾기 연습
- 슬라이딩 윈도우: 고정 크기 부분 배열 문제 풀이
- Kadane 알고리즘: 최대 부분 배열 합 마스터
- 실전 문제: 백준, LeetCode에서 20문제 이상 풀이
다음 단계: 배열을 마스터했다면, 스택과 큐에서 LIFO와 FIFO 자료구조를 배워보세요. 스택과 큐는 배열을 기반으로 구현되며, 괄호 검사, BFS/DFS 등에 필수적입니다!
다른 언어와 비교
- Python 자료형 | 리스트, 딕셔너리, 튜플, 세트 완벽 가이드
관련 글
- 스택과 큐 | 코딩 테스트 필수 자료구조 완벽 정리
- 해시 테이블 | O(1) 탐색 자료구조 완벽 정리
- 트리 자료구조 | 이진 트리, BST, 순회 완벽 정리
- 그래프 자료구조 | 인접 리스트, 인접 행렬, 탐색 완벽 정리
- 정렬 문제 풀이 | 코딩 테스트 정렬 패턴 완벽 정리