02-array

섹션 2. 배열 (Array)

배열 문제는 정렬되어 있는가와 추가 공간을 써도 되는가를 먼저 확인한다.

이 단원에서 꺼낼 도구

• 정렬된 배열 + 합/쌍 → 투 포인터
• 정렬된(혹은 회전된) 배열에서 탐색 → 이분 탐색, 불변식을 반드시 말로 정의
• 존재 여부·빈도 → HashSet / HashMap (O(n) 시간을 공간과 맞바꾸기)
• '자기 자신 제외' 누적값 → prefix / suffix 곱·합
• O(1) 공간 요구 → 배열 자체를 해시 테이블처럼 쓰기 (인덱스 = 값)
• K번째 원소 → 힙 O(n log k) 또는 QuickSelect 평균 O(n)

문제

#	문제	난이도	노트	1회독	2회독	3회독
1	217. Contains Duplicate	Easy	노트	⬜	⬜	⬜
2	1. Two Sum	Easy	노트	⬜	⬜	⬜
3	167. Two Sum II - Input Array Is Sorted	Medium	노트	⬜	⬜	⬜
4	283. Move Zeroes	Easy	노트	⬜	⬜	⬜
5	121. Best Time to Buy and Sell Stock	Easy	노트	⬜	⬜	⬜
6	153. Find Minimum in Rotated Sorted Array	Medium	노트	⬜	⬜	⬜
7	238. Product of Array Except Self	Medium	노트	⬜	⬜	⬜
8	41. First Missing Positive	Hard	노트	⬜	⬜	⬜
9	31. Next Permutation	Medium	노트	⬜	⬜	⬜
10	704. Binary Search	Easy	노트	⬜	⬜	⬜
11	33. Search in Rotated Sorted Array	Medium	노트	⬜	⬜	⬜
12	11. Container With Most Water	Medium	노트	⬜	⬜	⬜
13	15. 3Sum	Medium	노트	⬜	⬜	⬜
14	215. Kth Largest Element in an Array	Medium	노트	⬜	⬜	⬜
15	204. Count Primes	Medium	노트	⬜	⬜	⬜

---

⬅ 전체 목록으로