통합 요약노트
Ch.2 배열과 문자열
Two Pointer, Sliding Window, Prefix Sum — 배열 문제의 핵심 패턴
이 챕터의 내용
배열의 메모리 구조 — 연속 메모리와 O(1) 접근
연속 메모리 할당이 O(1) 접근의 비밀입니다. 메모리 주소 계산 한 번이면 끝!
사물함 100개가 일렬로 나란히 있다고 상상해보세요. 37번 사물함을 찾으러 갈 때 1번부터 셀 필요가 있나요?
배열도 마찬가지입니다. 연속된 메모리 공간에 데이터가 나란히 저장되기 때문에 위치를 계산 한 번으로 바로 접근합니다
배열의 i번째 요소 주소는 한 줄 공식으로 구할 수 있습니다
- 배열은 연속 메모리에 저장 → 인덱스 접근 O(1)
- 주소 계산: base + i × element_size
- Python list는 동적 배열 (amortized O(1) append)
- 배열 = 읽기 특화 / 연결 리스트 = 삽입·삭제 특화
Two Pointer 기법 — 양 끝에서 좁혀오기
정렬된 배열 또는 양 끝 비교 문제에서 Two Pointer는 강력한 무기입니다.
복도 양 끝에서 두 사람이 걸어옵니다. 만날 때까지 각자 방을 하나씩 확인하죠
두 포인터가 만나면 탐색 종료! 전체 배열을 한 번만 순회합니다
정렬된 배열에서 합이 target인 두 수를 찾는 문제를 풀어봅시다
- Two Pointer = 양 끝에서 좁혀오기 → O(n)
- 정렬 배열 Two Sum: 합 비교로 포인터 이동
- Container With Most Water: 낮은 쪽 이동
- 면접에서 O(n²) → O(n) 최적화 설명 필수
Sliding Window — 윈도우를 밀며 최적해 찾기
윈도우를 한 칸 밀 때마다 빠지는 원소를 빼고 새 원소를 더하면 O(1)에 갱신됩니다!
기차 창문을 떠올려보세요. 풍경이 슬라이드하듯 지나갑니다
가장 간단한 슬라이딩 윈도우: 연속 k개 원소의 최대합 구하기
매번 k개를 다시 더하면 O(n×k), 슬라이딩으로 갱신하면 O(n)!
- Fixed Window: 크기 고정, O(1) 갱신
- Variable Window: set/dict로 조건 추적
- Longest Substring Without Repeating → O(n)
- Brute force O(n²/n³) → Sliding Window O(n)
문자열 조작 — Reverse, Palindrome, Anagram
문자열 = 문자 배열입니다. 배열 기법(Two Pointer, 해시)을 그대로 적용할 수 있습니다!
프로그래밍에서 문자열은 문자(char)의 배열입니다
Two Pointer로 문자열을 제자리에서 뒤집어봅시다. 추가 메모리 없이 O(n)!
Palindrome 판별도 Two Pointer! 양 끝에서 좁혀오며 비교합니다
- 문자열 = 문자 배열, 배열 기법 그대로 적용
- Reverse: Two Pointer in-place O(n)
- Palindrome: 양 끝 비교 O(n)
- Anagram: Counter 해시맵 O(n)
Prefix Sum — 구간 합을 O(1)에 구하기
Prefix Sum 배열을 한 번 만들면 모든 구간 합을 O(1)에 구할 수 있습니다!
가우스의 비밀처럼 미리 계산한 누적 합으로 구간 합을 O(1)에!
prefix[0] = 0으로 시작하면 경계 조건이 깔끔해집니다
구간 합 = prefix[j+1] - prefix[i] 뺄셈 한 번이면 끝!
- Prefix Sum: 누적 합 배열로 구간 합 O(1)
- prefix[0] = 0 더미로 경계 조건 깔끔
- Subarray Sum = K: prefix + 해시맵 콤보
- 전처리 O(n), 쿼리 O(1), Q개 쿼리 → O(n + Q)
면접 실전: Top 5 배열 문제
해시맵, Kadane, Prefix Product 등 핵심 패턴을 하나씩 정복합시다!
LeetCode #1번, 면접 단골 중의 단골! Two Sum을 해시맵으로 O(n)에 풀어봅시다
핵심: 해시맵으로 complement 조회 O(1) → 전체 O(n)
주식 한 번 사고 한 번 팔아서 최대 이익을 구하라!
- Two Sum: 해시맵 O(n)
- Buy & Sell Stock: 최소값 추적 O(n)
- Product Except Self: 좌우 누적곱 O(n)
- Contains Duplicate: set O(n)
- Maximum Subarray: Kadane O(n)
챕터 2 종합 퀴즈 — Array & String 총정리
총 15문제로 완벽하게 점검합시다!
챕터 2에서 배운 모든 것을 확인합니다! 자신감을 가지고 도전해보세요
배열에서 인덱스 접근이 O(1)인 이유는?
Sliding Window 기법의 전체 시간복잡도는?
- 배열: 연속 메모리 → O(1) 접근
- Two Pointer: 양 끝 좁히기 → O(n)
- Sliding Window: 윈도우 밀기 → O(n)
- 문자열 = 문자 배열 → 배열 기법 적용
- Prefix Sum: 전처리 O(n) + 쿼리 O(1)
- Top 5: Two Sum, Stock, Product, Duplicate, Kadane
핵심 용어 모음
배열(Array)
같은 타입 데이터를 연속 메모리에 저장하는 자료구조
인덱스(Index)
배열 내 위치를 나타내는 정수 (0부터 시작)
Base Address
배열의 시작 메모리 주소
인덱스 접근
배열 O(1) / 연결 리스트 O(n)
맨 앞 삽입
배열 O(n) / 연결 리스트 O(1)
맨 뒤 삽입
배열 O(1)* / 연결 리스트 O(1)
중간 삭제
배열 O(n) / 연결 리스트 O(1)
Left Pointer
배열의 왼쪽 끝에서 시작하여 오른쪽으로 이동
Right Pointer
배열의 오른쪽 끝에서 시작하여 왼쪽으로 이동
핵심 원리
매 단계 한 쪽을 이동 → 총 이동 O(n)
Fixed Window
크기 고정 — 연속 k개의 최대합 등
Variable Window
크기 가변 — 조건 만족하는 최소/최대 구간
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 코스 시작하기