2장: 배열과 연결 리스트
배열과 리스트를 선택하는 실무 기준
배열과 리스트 중 무엇이 더 좋냐는 질문에는 정답이 하나가 없습니다. 우선 확인할 것은 어떤 연산이 자주 발생하는가입니다. 조회가 많으면 배열이 유리하고, 앞/중간 수정이 많으면 리스트 계열이 유리합니다.
여기서는 벤치마크 숫자 암기 대신 선택 절차를 익힙니다. 작은 입력으로 원리를 확인하고, 코테에서 바로 쓸 판단 기준으로 연결하겠습니다.
핵심 패턴 요약: 배열·리스트 선택
구조 선택에서 중요한 건 무엇이 더 좋아 보이는가가 아니라 어떤 연산이 실제로 많이 일어나는가입니다. 지금 문제를 기준으로 조회/삽입/삭제 비율을 간단히 숫자로 적어 두고 읽어 보세요.
읽기 중심(workload)은 조회 연산이 대부분을 차지하는 작업 분포입니다.
정의로 보면 전체 연산에서 조회 비율이 삽입/삭제보다 높은 입력 패턴을 뜻합니다.
Q개의 질의 중 대부분이 arr[i] 조회라면 읽기 중심으로 분류하고 배열 계열을 우선 검토합니다.
수정 중심(workload)은 삽입/삭제가 자주 발생하는 분포입니다. 데이터 이동이나 링크 변경이 반복되어 누적 비용이 커지는 상황을 말합니다. 텍스트 편집기처럼 커서 주변 삽입/삭제가 연속으로 나오면 수정 중심 패턴에 가깝습니다.
연산 비율 기반 선택은 지배 연산을 우선 최적화하는 의사결정 방법입니다. 정확히는 가장 자주 발생하는 연산의 점근 비용을 최소화하도록 자료구조를 고르는 규칙입니다. 조회 80%, 삭제 20%라면 배열을 기본 후보로 두고 삭제 패턴이 문제를 만들지 추가 확인하면 됩니다.
배열/리스트 선택 실패 사례와 연결하기
정답 코드를 작성해도 자료구조 선택이 틀리면 시간 초과가 납니다. 반대로 선택이 맞으면 구현이 조금 투박해도 통과할 가능성이 높아집니다.
코테에서는 특히 연산 패턴이 문제 설명에 숨겨져 있습니다. 입력 크기와 연산 종류를 우선 읽고 구조를 고르면, 이후 알고리즘 선택도 쉬워집니다. 지금 문제 설명에서 연산 동사를 모두 동그라미 쳐서 조회/삽입/삭제로 분류해 보세요.
연산 비율 테스트로 빠르게 검증하기
학습 효율을 높이려면 오답 -> 디버깅 -> 교정 -> 검증 순서로 로그를 남기면서 진행하는 것이 가장 빠릅니다.
아래 두 시나리오를 비교해 봅시다.
- A: 랜덤 조회 80%, 앞삽입 10%, 중간삭제 10%
- B: 랜덤 조회 20%, 앞삽입 40%, 중간삭제 40%
- A는 조회 비율이 높으므로 배열이 기본 선택입니다.
- B는 이동보다 연결 변경이 많으므로 리스트/덱 계열이 더 안전합니다.
- 같은 데이터라도 연산 비율이 바뀌면 정답 구조도 바뀝니다.
앞 삽입 시 이동 비용 비교
문제 의도: 앞 삽입을 반복할 때 배열은 왜 느려지고 덱은 왜 안정적인지 확인합니다.
입력 예시: base=[1,2,3,4,5], inserts=[9,8]
출력 예시: array_shift=11, deque_shift=0
insert(0, x)는 맨 앞 삽입이고, push_front/addFirst/appendleft도 같은 앞 삽입 연산입니다.
앞 삽입에서 배열은 기존 원소를 오른쪽으로 밀어야 합니다. 아래 코드는 실행 시간 대신 이동된 원소 수를 직접 셉니다.
#include <deque>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
pair<long long, long long> simulateFrontInsertCost(const vector<int>& base, const vector<int>& inserts) {
vector<int> arrayLike = base;
deque<int> dequeLike(base.begin(), base.end());
long long arrayShift = 0;
long long dequeShift = 0;
for (int x : inserts) {
arrayShift += static_cast<long long>(arrayLike.size());
arrayLike.insert(arrayLike.begin(), x);
}
for (int x : inserts) {
dequeLike.push_front(x);
}
return {arrayShift, dequeShift};
}
int main() {
pair<long long, long long> result = simulateFrontInsertCost({1, 2, 3, 4, 5}, {9, 8});
long long arrayShift = result.first;
long long dequeShift = result.second;
cout << "array_shift=" << arrayShift << ", deque_shift=" << dequeShift << "\n";
return 0;
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Main {
static long[] simulateFrontInsertCost(List<Integer> base, List<Integer> inserts) {
List<Integer> arrayLike = new ArrayList<>(base);
Deque<Integer> dequeLike = new ArrayDeque<>(base);
long arrayShift = 0;
long dequeShift = 0;
for (int x : inserts) {
arrayShift += arrayLike.size();
arrayLike.add(0, x);
}
for (int x : inserts) {
dequeLike.addFirst(x);
}
return new long[]{arrayShift, dequeShift};
}
public static void main(String[] args) {
long[] result = simulateFrontInsertCost(
List.of(1, 2, 3, 4, 5),
List.of(9, 8)
);
System.out.println("array_shift=" + result[0] + ", deque_shift=" + result[1]);
}
}from collections import deque
def simulate_front_insert_cost(base, inserts):
array_like = list(base)
deque_like = deque(base)
array_shift = 0
deque_shift = 0
for x in inserts:
array_shift += len(array_like)
array_like.insert(0, x)
for x in inserts:
deque_like.appendleft(x)
return array_shift, deque_shift
array_shift, deque_shift = simulate_front_insert_cost([1, 2, 3, 4, 5], [9, 8])
print(f"array_shift={array_shift}, deque_shift={deque_shift}")use std::collections::VecDeque;
fn simulate_front_insert_cost(base: &[i32], inserts: &[i32]) -> (i64, i64) {
let mut array_like = base.to_vec();
let mut deque_like: VecDeque<i32> = VecDeque::new();
for &x in base {
deque_like.push_back(x);
}
let mut array_shift: i64 = 0;
let deque_shift: i64 = 0;
for &x in inserts {
array_shift += array_like.len() as i64;
array_like.insert(0, x);
}
for &x in inserts {
deque_like.push_front(x);
}
(array_shift, deque_shift)
}
fn main() {
let (array_shift, deque_shift) = simulate_front_insert_cost(&[1, 2, 3, 4, 5], &[9, 8]);
println!("array_shift={}, deque_shift={}", array_shift, deque_shift);
}배열/리스트 구조 비교 동작 인덱스 끝점 확인
앞 삽입이 많으면 배열은 매번 이동 비용이 누적됩니다. 덱은 양끝 삽입이 기본 연산이라 이동 비용이 거의 없습니다. 그래서 앞/뒤 삽입 중심 문제에서는 덱 계열이 기본 선택입니다.
- 시간복잡도(배열 앞삽입):
O(M * N)(M번 삽입, 매번 최대 N 이동) - 시간복잡도(덱 앞삽입):
O(M) - 공간복잡도: 둘 다
O(N + M)
임의 인덱스 조회 비용 비교
문제 의도: 같은 결과를 구해도 접근 방식에 따라 연산 횟수가 얼마나 달라지는지 확인합니다.
입력 예시: data=[0,1,2,3,4,5,6,7,8,9], queries=[0,4,9,3]
출력 예시: direct_steps=4, linear_steps=20
data[idx]는 원하는 위치를 한 번에 읽는 접근입니다.
아래 코드는 두 방식으로 합계를 구합니다.
- direct: 배열 인덱스로 바로 접근
- linear: 연결 리스트처럼 앞에서부터 걸어가며 접근
#include <iostream>
#include <vector>
using namespace std;
struct ReadResult {
long long directSum;
long long linearSum;
long long directSteps;
long long linearSteps;
};
int readLinearLikeList(const vector<int>& data, int idx, long long& steps) {
int value = -1;
for (int i = 0; i <= idx; ++i) {
value = data[i];
steps += 1;
}
return value;
}
ReadResult compareReadCost(const vector<int>& data, const vector<int>& queries) {
long long directSum = 0;
long long linearSum = 0;
long long directSteps = 0;
long long linearSteps = 0;
for (int idx : queries) {
directSum += data[idx];
directSteps += 1;
linearSum += readLinearLikeList(data, idx, linearSteps);
}
return {directSum, linearSum, directSteps, linearSteps};
}
int main() {
ReadResult r = compareReadCost(
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
{0, 4, 9, 3}
);
cout << "direct_sum=" << r.directSum << ", linear_sum=" << r.linearSum << "\n";
cout << "direct_steps=" << r.directSteps << ", linear_steps=" << r.linearSteps << "\n";
return 0;
}import java.util.List;
public class Main {
static class ReadResult {
long directSum;
long linearSum;
long directSteps;
long linearSteps;
}
static int readLinearLikeList(List<Integer> data, int idx, ReadResult r) {
int value = -1;
for (int i = 0; i <= idx; i++) {
value = data.get(i);
r.linearSteps += 1;
}
return value;
}
static ReadResult compareReadCost(List<Integer> data, List<Integer> queries) {
ReadResult r = new ReadResult();
for (int idx : queries) {
r.directSum += data.get(idx);
r.directSteps += 1;
r.linearSum += readLinearLikeList(data, idx, r);
}
return r;
}
public static void main(String[] args) {
ReadResult r = compareReadCost(
List.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
List.of(0, 4, 9, 3)
);
System.out.println("direct_sum=" + r.directSum + ", linear_sum=" + r.linearSum);
System.out.println("direct_steps=" + r.directSteps + ", linear_steps=" + r.linearSteps);
}
}def read_linear_like_list(data, idx):
value = -1
steps = 0
for i in range(idx + 1):
value = data[i]
steps += 1
return value, steps
def compare_read_cost(data, queries):
direct_sum = 0
linear_sum = 0
direct_steps = 0
linear_steps = 0
for idx in queries:
direct_sum += data[idx]
direct_steps += 1
value, steps = read_linear_like_list(data, idx)
linear_sum += value
linear_steps += steps
return direct_sum, linear_sum, direct_steps, linear_steps
r = compare_read_cost([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 4, 9, 3])
print(f"direct_sum={r[0]}, linear_sum={r[1]}")
print(f"direct_steps={r[2]}, linear_steps={r[3]}")struct ReadResult {
direct_sum: i64,
linear_sum: i64,
direct_steps: i64,
linear_steps: i64,
}
fn read_linear_like_list(data: &[i32], idx: usize, linear_steps: &mut i64) -> i32 {
let mut value = -1;
for i in 0..=idx {
value = data[i];
*linear_steps += 1;
}
value
}
fn compare_read_cost(data: &[i32], queries: &[usize]) -> ReadResult {
let mut result = ReadResult {
direct_sum: 0,
linear_sum: 0,
direct_steps: 0,
linear_steps: 0,
};
for &idx in queries {
result.direct_sum += data[idx] as i64;
result.direct_steps += 1;
result.linear_sum += read_linear_like_list(data, idx, &mut result.linear_steps) as i64;
}
result
}
fn main() {
let data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
let queries = [0usize, 4usize, 9usize, 3usize];
let r = compare_read_cost(&data, &queries);
println!("direct_sum={}, linear_sum={}", r.direct_sum, r.linear_sum);
println!("direct_steps={}, linear_steps={}", r.direct_steps, r.linear_steps);
}배열/리스트 구조 비교 동작 포인터 흐름 추적
직접 인덱스 접근은 질의 수만큼만 연산합니다. 반면 선형 접근은 질의마다 앞에서 다시 걸어가므로 연산이 빠르게 커집니다. 그래서 임의 인덱스 조회가 많은 문제에서는 배열이 기본 선택입니다.
- 시간복잡도(direct):
O(Q) - 시간복잡도(linear-like):
O(sum(idx_i + 1)), 최악O(Q * N) - 공간복잡도:
O(1)(입력 제외)
연산 비율 기반 구조 선택 함수
문제 의도: 연산 비율을 코드로 고정해 팀 내 판단 축을 통일합니다.
입력 예시: (readOps=80, frontOps=10, middleOps=10, needOrdered=false)
출력 예시: dynamic-array
조건을 if 순서대로 읽으면 왜 이 구조를 선택하는지 설명하기 쉽습니다.
조건이 바뀌면 선택 결과도 바뀌게 만들면, 감(직관) 대신 기준으로 결정할 수 있습니다.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string chooseStructure(int readOps, int frontOps, int middleOps, bool needOrdered) {
if (frontOps > readOps) return "deque-or-linked-list";
if (middleOps * 2 >= readOps) return "linked-list";
if (needOrdered) return "dynamic-array-with-sort-step";
return "dynamic-array";
}
int main() {
vector<int> readOps = {80, 20, 40};
vector<int> frontOps = {10, 50, 10};
vector<int> middleOps = {10, 30, 30};
vector<bool> orderedOps = {false, false, true};
for (int i = 0; i < static_cast<int>(readOps.size()); ++i) {
int r = readOps[i];
int f = frontOps[i];
int m = middleOps[i];
bool ordered = orderedOps[i];
cout << "(" << r << "," << f << "," << m << "," << ordered << ") -> "
<< chooseStructure(r, f, m, ordered) << "\n";
}
return 0;
}public class Main {
static String chooseStructure(int readOps, int frontOps, int middleOps, boolean needOrdered) {
if (frontOps > readOps) return "deque-or-linked-list";
if (middleOps * 2 >= readOps) return "linked-list";
if (needOrdered) return "dynamic-array-with-sort-step";
return "dynamic-array";
}
public static void main(String[] args) {
int[][] tests = {
{80, 10, 10, 0},
{20, 50, 30, 0},
{40, 10, 30, 1}
};
for (int[] t : tests) {
boolean ordered = t[3] == 1;
System.out.println(
"(" + t[0] + "," + t[1] + "," + t[2] + "," + ordered + ") -> " +
chooseStructure(t[0], t[1], t[2], ordered)
);
}
}
}def choose_structure(read_ops, front_ops, middle_ops, need_ordered):
if front_ops > read_ops:
return "deque-or-linked-list"
if middle_ops * 2 >= read_ops:
return "linked-list"
if need_ordered:
return "dynamic-array-with-sort-step"
return "dynamic-array"
tests = [
(80, 10, 10, False),
(20, 50, 30, False),
(40, 10, 30, True),
]
for t in tests:
read_ops = t[0]
front_ops = t[1]
middle_ops = t[2]
need_ordered = t[3]
print(f"{t} -> {choose_structure(read_ops, front_ops, middle_ops, need_ordered)}")fn choose_structure(read_ops: i32, front_ops: i32, middle_ops: i32, need_ordered: bool) -> &'static str {
if front_ops > read_ops {
return "deque-or-linked-list";
}
if middle_ops * 2 >= read_ops {
return "linked-list";
}
if need_ordered {
return "dynamic-array-with-sort-step";
}
"dynamic-array"
}
fn main() {
let read_ops = [80, 20, 40];
let front_ops = [10, 50, 10];
let middle_ops = [10, 30, 30];
let ordered_ops = [false, false, true];
for i in 0..read_ops.len() {
let r = read_ops[i];
let f = front_ops[i];
let m = middle_ops[i];
let ordered = ordered_ops[i];
println!(
"({},{},{},{}) -> {}",
r,
f,
m,
ordered,
choose_structure(r, f, m, ordered)
);
}
}배열/리스트 구조 비교 동작 삽입/삭제 재확인
구조 판단 축을 함수로 만들면 리뷰가 쉬워집니다. 요구사항이 바뀌어도 수정 위치가 명확합니다. 코테에서도 왜 이 구조를 골랐는지를 설명할 때 큰 도움이 됩니다.
- 시간복잡도: 테스트 케이스 수를
T라 할 때O(T) - 공간복잡도:
O(1)(입력 제외)
배열/리스트 구현 단순성과 성능 균형점
배열과 리스트를 고를 때 자주 보는 균형점입니다.
- 배열: 랜덤 조회 강함, 중간 이동 비용 큼
- 리스트/덱: 앞뒤 수정 강함, 임의 조회 약함
- 배열: 구현 단순, 재할당/이동 비용 존재
- 리스트/덱: 구조 유연, 포인터/참조 관리 부담
구조 선택 오답 패턴과 교정 방법
처음 배우는 사람이 자주 놓치는 지점입니다.
- 앞삽입이 많은데 배열만 고집해서 시간 초과
- 인덱스 조회가 많은데 연결 리스트를 사용
- 입력이 작을 때만 테스트하고 큰 입력 반례를 생략
- 선택 이유를 문장으로만 남기고 코드 규칙으로 고정하지 않음
반례 예시:
N=200000, 앞삽입N회 -> 배열은 이동 누적으로 급격히 느려짐N=200000, 랜덤 조회N회 -> 선형 접근 구조는 대부분 시간 초과
연산 분포와 복잡도 판단
같은 정답이라도 입력 분포에 따라 병목 지점이 달라지므로, 판단 축을 시간복잡도 표 하나로 끝내지 말고 분포 가정까지 명시해야 합니다.
| 시나리오 | 배열 | 리스트/덱 계열 | 권장 |
|---|---|---|---|
| 랜덤 조회 중심 | O(1) 접근 강점 | O(N) 접근 약점 | 배열 |
| 앞/뒤 삽입삭제 중심 | 앞쪽은 O(N) | 양끝 O(1) | 덱/리스트 |
| 중간 수정 중심 | 이동 비용 큼 | 연결 변경 강점 | 리스트 |
표는 시작점입니다. 실전에서는 반드시 실제 연산 비율로 다시 확인하세요.
제출 전 구조 선택 체크리스트
- 연산 비율(조회/삽입/삭제)을 숫자로 적었는가
- 최소 2개 구조를 같은 입력으로 비교했는가
- 큰 입력 반례에서 시간 초과 위험을 확인했는가
- 구조 선택 판단 이유를 코드 규칙으로 남겼는가
배열 vs 리스트 최종 판단
배열 vs 리스트 선택은 취향이 아니라 연산 패턴 문제입니다. 문제의 핵심 연산을 우선 찾고, 그 연산에 맞는 구조를 고르면 코테 실전에서도 안정적으로 통과율을 높일 수 있습니다.