pkglog
EN

배열과 연결 리스트: 메모리 구조, 연산별 시간 복잡도, 코딩 테스트 활용

작성 · · 20분 읽기 · 수정 초급 튜토리얼

이 글의 핵심

코딩 테스트 문제 상당수는 결국 배열을 어떻게 훑느냐의 문제입니다. 동적 배열이 끝에 추가할 때 상각 O(1)인 이유와 연결 리스트가 캐시 지역성에서 불리한 이유를 짚고, 무차별 대입으로 시간 초과가 날 때 투 포인터·슬라이딩 윈도우·부분합으로 줄여 가는 과정을 난이도별 추천 문제와 함께 보여 줍니다.

시리즈 안내

#01 | 📋 전체 목차 | 다음: #02 스택과 큐

들어가며: 가장 기본적인 자료구조

배열과 리스트는 가장 기본적이면서 가장 많이 쓰이는 자료구조(데이터를 담고 꺼내는 방식·구조)입니다. 코딩 테스트에서도 입력이 배열로 주어지고, 그 배열을 어떻게 훑느냐가 곧 풀이의 핵심인 문제가 많습니다.

이 글에서 다루는 것:

  • 배열 vs 리스트 차이
  • 시간복잡도(입력이 커질 때 실행 시간이 얼마나 늘어나는지) 분석
  • 투 포인터(두 개의 인덱스로 배열을 훑는 기법), 슬라이딩 윈도우(고정 크기 구간을 한 칸씩 옮기며 보는 기법)
  • 실전 문제 풀이

배열 (Array)

배열이란?

배열(Array)은 연속된 메모리 공간에 같은 타입의 데이터를 저장하는 가장 기본적인 자료구조입니다. 인덱스를 통해 각 요소에 직접 접근할 수 있습니다. 배열의 메모리 구조:

메모리 주소:  1000  1004  1008  1012  1016
배열 값:      [1]   [2]   [3]   [4]   [5]
인덱스:        0     1     2     3     4
각 요소는 연속된 메모리에 저장됨
→ 인덱스로 주소 계산: 주소 = 시작주소 + (인덱스 × 요소크기)
→ arr[2]의 주소 = 1000 + (2 × 4) = 1008

Python에서의 배열 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)  # True

C++ 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) 실전 활용 시나리오:

  • 로그 저장: 로그를 순서대로 저장하고 나중에 순회 (뒤쪽 추가만)

  • 점수 관리: 학생 점수를 저장하고 인덱스로 접근

  • 버퍼: 데이터를 임시로 저장했다가 일괄 처리

  • 정렬된 데이터: 이진 탐색을 위해 정렬된 배열 유지

리스트 (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): 순차 탐색 필요

  • ❌ 캐시 효율 나쁨: 메모리 흩어짐

  • ❌ 포인터 오버헤드

시간복잡도 비교

연산배열연결 리스트
접근 (인덱스)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)*

* 해당 노드 위치를 알고 있을 때

실전 기법

투 포인터 (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]

문제 풀이

문제 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

Python 리스트에서 자주 틀리는 부분

Python에서는 arr[-1]이 에러가 아니라 마지막 요소를 돌려주기 때문에, 투 포인터에서 left - 1 같은 인덱스가 음수로 내려가도 예외 없이 엉뚱한 값을 읽습니다. C++처럼 바로 터지지 않으니 경계 검사를 직접 넣어야 합니다. 반대로 arr[len(arr)]는 IndexError지만 슬라이스 arr[len(arr):]는 빈 리스트를 돌려주므로, 슬라이스로 경계를 넘는 코드는 조용히 통과합니다.

arr2 = arr        # 같은 객체를 가리키는 이름이 하나 더 생길 뿐
arr2 = arr[:]     # 얕은 복사(새 리스트, O(n))
grid2 = [row[:] for row in grid]  # 2차원은 행마다 복사해야 함
bad = [[0] * m] * n               # n개 행이 모두 같은 리스트를 공유

arr[::-1], arr[:]처럼 슬라이스는 항상 새 리스트를 만들기 때문에 O(k) 복사 비용이 듭니다. 루프 안에서 arr[i:]를 반복해 만들면 전체가 O(n²)이 되므로, 인덱스만 넘기는 편이 안전합니다.

입력 크기로 접근법 고르기

배열 문제를 받으면 먼저 n의 범위를 봅니다. n이 수백 정도라면 이중 루프 O(n²)도 통과하지만, n이 10⁵~10⁶이면 한 번의 순회로 끝내야 하므로 투 포인터·슬라이딩 윈도우·해시 중 무엇을 쓸지부터 정해야 합니다. 입력이 정렬되어 있다는 조건이 있으면 이진 탐색이나 양 끝 투 포인터가 먼저 후보가 되고, “추가 메모리 없이(in-place)“라는 조건이 붙으면 해시 대신 포인터 두 개로 원소를 옮기는 방식을 떠올리면 됩니다.

가장 자주 시간 초과를 내는 실수는 Python에서 반복문 안에 list.insert(0, x)나 list.pop(0)을 쓰는 것입니다. 둘 다 뒤 원소를 전부 한 칸씩 옮기는 O(n) 연산이라 루프 전체가 O(n²)이 됩니다. 앞쪽 삽입·삭제가 잦다면 collections.deque로 바꾸는 것이 가장 간단한 해결책입니다. 배열이 익숙해졌다면 스택과 큐로 넘어가면 되는데, 괄호 검사와 BFS가 모두 이 두 자료구조 위에서 동작합니다.

추천 문제 (난이도별)

입문 (Bronze/Easy)

백준:

초급 (Silver/Medium)

LeetCode:

중급 (Gold/Hard)

LeetCode:

문제 풀이 전략

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]

다른 언어와 비교

같이 보면 좋은 글

자주 묻는 질문 (FAQ)

Q. 동적 배열의 append는 가끔 전체를 복사하는데 왜 O(1)이라고 하나요?

A. 용량이 가득 찼을 때만 보통 2배 크기로 새 메모리를 잡고 기존 요소를 복사하므로, 그 한 번은 O(n)이 맞습니다. 하지만 용량을 배수로 늘리면 복사가 드물게 일어나서 n번 append의 총비용이 O(n)에 머물고, 한 번당 평균은 O(1)이 됩니다. 이것을 분할상환(amortized) O(1)이라고 부르며, 중간 삽입처럼 뒤 요소를 밀어야 하는 연산은 여전히 O(n)입니다.