[2026] 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리

· 20분 읽기 · 수정 초급 튜토리얼
[2026] 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리

이 글의 핵심

배열과 리스트: 코딩 테스트 필수 자료구조 가장 기본적인 자료구조·배열 (Array).

🎯 이 글을 읽으면 (읽는 시간: 20분)

TL;DR: 코딩 테스트의 50%를 차지하는 배열과 리스트를 완벽하게 마스터합니다. 투 포인터, 슬라이딩 윈도우 같은 핵심 테크닉으로 O(n²) 문제를 O(n)으로 최적화하는 방법을 배웁니다. 이 글을 읽으면:

  • ✅ 배열 vs 리스트 차이와 선택 기준 완벽 이해
  • ✅ 투 포인터, 슬라이딩 윈도우 패턴 마스터
  • ✅ 시간복잡도 분석 및 최적화 능력 습득 실무 활용:
  • 🔥 코딩 테스트 (LeetCode, 백준)
  • 🔥 알고리즘 면접 대비
  • 🔥 실전 데이터 처리 최적화 난이도: 초급 | 실습 문제: 8개 | Python + C++: 모두 포함

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

”배열만 알면 코딩 테스트 50%는 풀 수 있다”

배열과 리스트는 가장 기본적이면서 가장 많이 쓰이는 자료구조(데이터를 담고 꺼내는 방식·구조)입니다. 코딩 테스트의 절반 이상이 배열 문제입니다. 이 글에서 다루는 것:

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

코딩 테스트 준비하며 깨달은 것

알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.

목차

  1. 배열 (Array)
  2. 리스트 (Linked List)
  3. 시간복잡도 비교
  4. 실전 기법
  5. 문제 풀이
  6. 정리

1. 배열 (Array)

배열이란?

배열(Array)은 연속된 메모리 공간에 같은 타입의 데이터를 저장하는 가장 기본적인 자료구조입니다. 인덱스를 통해 각 요소에 직접 접근할 수 있습니다. 배열의 메모리 구조: 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

// 실행 예제
메모리 주소:  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를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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++에서의 배열: 아래 코드는 cpp를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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가 모두 동적 배열입니다. 동적 배열의 동작 원리: 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

초기 상태: 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를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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의 동적 배열 연산: 다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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를 사용한 구현 예제입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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)*
* 해당 노드 위치를 알고 있을 때

일상 비유로 이해하기: 시간 복잡도는 책에서 원하는 페이지를 찾는 방법으로 비유할 수 있습니다. O(1)은 목차를 보고 바로 찾기, O(log n)은 이진 탐색처럼 중간을 펼쳐 앞뒤 판단하기, O(n)은 첫 페이지부터 하나씩 넘기기, O(n²)은 모든 페이지 조합을 확인하기입니다.

4. 실전 기법

투 포인터 (Two Pointers)

투 포인터는 두 개의 인덱스(포인터)를 사용하여 배열을 효율적으로 탐색하는 기법입니다. O(n²) → O(n)으로 최적화할 수 있습니다. 기본 패턴: 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

정렬된 배열: [1, 2, 3, 4, 6]
             ↑           ↑
           left        right
1. left와 right를 양 끝에서 시작
2. 조건에 따라 left를 오른쪽으로, right를 왼쪽으로 이동
3. left와 right가 만날 때까지 반복

예제 1: 정렬된 배열에서 두 수의 합 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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 투 포인터 비교: 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ❌ 무차별 대입 - 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) 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)으로 최적화할 수 있습니다. 기본 원리: 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

배열: [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 슬라이딩 윈도우 비교: 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ❌ 무차별 대입 - 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 부분 수열: 아래 코드는 python를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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) 시간에 최대 부분 배열 합을 찾는 유명한 알고리즘입니다. 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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) 공간) 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)

문제: 두 정렬된 배열을 합쳐서 하나의 정렬된 배열을 만드세요. 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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개의 정렬된 배열 합병: 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 배열에서 최빈값 찾기

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 배열 재배치 (짝수/홀수 분리)

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ✅ 좋은 습관
# 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[:]  # 진짜 복사

정리

핵심 요약

  1. 배열: 연속 메모리, 인덱스 접근 O(1), 삽입/삭제 O(n)
  2. 리스트: 노드 연결, 삽입/삭제 O(1), 인덱스 접근 O(n)
  3. 투 포인터: 정렬된 배열에서 O(n) 탐색
  4. 슬라이딩 윈도우: 부분 배열 문제 최적화
  5. Python list = 동적 배열 (C++ vector와 동일)

문제 풀이 전략

  1. 입력 크기 확인: n ≤ 100 → O(n²) 가능, n ≤ 10⁶ → O(n) 필요
  2. 정렬 여부: 정렬되어 있으면 이진 탐색, 투 포인터 고려
  3. 공간복잡도: in-place 요구 시 투 포인터, 슬라이딩 윈도우

다음 단계

추천 문제 (난이도별)

입문 (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]

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

이 글에서 다루는 키워드 (관련 검색어)

배열, 리스트, Array, Linked List, 자료구조, 시간복잡도, 투 포인터, Two Pointers, 슬라이딩 윈도우, Sliding Window, Kadane 알고리즘, 부분 배열, Subarray, 동적 배열, Dynamic Array, Python list, C++ vector, 코딩 테스트, 알고리즘 문제 등으로 검색하시면 이 글이 도움이 됩니다.

마치며

배열은 가장 기본적이면서 가장 중요한 자료구조입니다. 코딩 테스트 문제의 50% 이상이 배열 문제이며, 투 포인터와 슬라이딩 윈도우만 잘 익혀도 많은 문제를 효율적으로 풀 수 있습니다. 처음에는 무차별 대입(Brute Force)으로 풀어 보고, 시간 초과가 나면 투 포인터·슬라이딩 윈도우 같은 패턴으로 최적화해 보시면 됩니다. 같은 유형을 반복해 풀다 보면 자연스럽게 익숙해집니다. 학습 로드맵:

  1. 배열 기본: 인덱스 접근, 슬라이싱, 시간복잡도 이해
  2. 투 포인터: 정렬된 배열에서 두 수 찾기 연습
  3. 슬라이딩 윈도우: 고정 크기 부분 배열 문제 풀이
  4. Kadane 알고리즘: 최대 부분 배열 합 마스터
  5. 실전 문제: 백준, LeetCode에서 20문제 이상 풀이 다음 단계: 배열을 마스터했다면, 스택과 큐에서 LIFO와 FIFO 자료구조를 배워보세요. 스택과 큐는 배열을 기반으로 구현되며, 괄호 검사, BFS/DFS 등에 필수적입니다!

다른 언어와 비교

관련 글

... 996 lines not shown ... Token usage: 63706/1000000; 936294 remaining Start-Sleep -Seconds 3