Ch.2 배열과 문자열
챕터 2 종합 퀴즈 — Array & String 총정리
배열과 문자열, 얼마나 마스터했는지 확인해볼까?
지금까지 배운 모든 개념을 한 번에 점검합니다. 시간복잡도, 패턴 매칭, 코드 추적까지!
각 기법이 언제 쓰이는지 정확히 구분할 수 있는가?
총 15문제로 완벽하게 점검합시다!
핵심 내용
챕터 2에서 배운 모든 것을 확인합니다! 자신감을 가지고 도전해보세요
배열에서 인덱스 접근이 O(1)인 이유는?
Sliding Window 기법의 전체 시간복잡도는?
Prefix Sum 배열 구축의 시간복잡도는?
"중복 없는 가장 긴 부분 문자열"에 적합한 기법은?
"정렬된 배열에서 합이 target인 두 수 찾기"에 적합한 기법은?
"연속 부분 배열의 최대 합"에 적합한 알고리즘은?
Python의 list.pop(0)은 O(1)이다
Anagram 판별은 정렬로도 풀 수 있지만 해시맵이 더 효율적이다
Two Pointer는 항상 배열이 정렬되어 있어야 사용할 수 있다
Kadane's Algorithm은 모든 원소가 음수인 배열에서도 작동한다
배열의 주소 공식: address(i) = ____ + i × element_size
배열의 주소 공식: address(i) = ____ + i × element_size
Kadane: current = max(num, ____ + num)
Kadane: current = max(num, ____ + num)
Container With Most Water에서 높이가 ____쪽 포인터를 이동시킨다
Container With Most Water에서 높이가 ____쪽 포인터를 이동시킨다
다음 코드의 출력은? arr = [3, 1, 4, 1, 5] prefix = [0] for x in arr: prefix.append(prefix[-1] + x) print(prefix[4] - prefix[1])
다음 코드의 출력은? def f(s): return s == s[::-1] print(f("level"))
Array & String 마스터!
핵심 용어
배열 메모리
연속 저장, O(1) 인덱스 접근
Two Pointer
양 끝에서 좁혀오기 O(n)
Sliding Window
윈도우 밀기 O(n)
문자열 조작
Reverse, Palindrome, Anagram
Prefix Sum
구간 합 O(1)
Top 5 문제
Two Sum, Stock, Product, Duplicate, Kadane
정리 노트
Array & String 총정리
기법별 시간복잡도
- 인덱스 접근
- O(1) — 주소 계산
- Two Pointer
- O(n) — 양 끝 좁히기
- Sliding Window
- O(n) — 윈도우 밀기
- Prefix Sum 쿼리
- O(1) — 전처리 O(n)
- Kadane
- O(n) — 최대 부분 배열 합
문제 → 패턴 매칭
- 합이 target인 두 수
- 해시맵 또는 Two Pointer (정렬 시)
- 부분 배열/문자열
- Sliding Window
- 구간 합
- Prefix Sum
- 최대 부분 배열 합
- Kadane's Algorithm
- Palindrome/Anagram
- Two Pointer / 해시맵
면접 전략: 문제를 보면 먼저 '어떤 패턴인가?'를 판단하는 것이 가장 중요합니다!
핵심 정리
- 1배열: 연속 메모리 → O(1) 접근
- 2Two Pointer: 양 끝 좁히기 → O(n)
- 3Sliding Window: 윈도우 밀기 → O(n)
- 4문자열 = 문자 배열 → 배열 기법 적용
- 5Prefix Sum: 전처리 O(n) + 쿼리 O(1)
- 6Top 5: Two Sum, Stock, Product, Duplicate, Kadane
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작