Big-O 증가율
선의 모양은 증가율을 보여주고, 커서는 선택한 입력 크기의 값을 읽습니다.
O(1)
1
O(log n)
5
O(n)
32
O(n log n)
160
O(n²)
1,024
Data Structures & Algorithms
DSA I를 작은 시스템처럼 뜯어봅니다.
이 페이지는 DSA I 노트에 있는 내용만 다룹니다. Java review, Iterator/Comparator, Big-O, ArrayList, Recursion과 Binary Search, LinkedList, Stack, Queue입니다.
worst-case Big-O와 primitive operation 세기
Array, ArrayList, backing array, shifting, resize 비용
재귀 base case, call stack trace, binary search
SLL, DLL, CLL의 포인터 갱신 규칙
Linked/array-backed Stack과 Queue ADT
학습 지도
-
Module 0 · 기초
기초와 Java review
Java 문법, generics, wrapper type, Iterable, Iterator, Comparable, Comparator를 JS/TS와 연결해 정리했습니다.
-
Module 0 · Big-O
Big-O와 primitive operations
Big-O는 worst-case growth에 대한 가장 타이트한 upper bound로 사용하고, 상수와 낮은 차수 항은 제거합니다.
-
Module 1
Arrays, ArrayLists, recursion
ArrayList는 backing array를 사용하고, 중간 삽입/삭제에서 원소를 shift하며, 꽉 차면 더 큰 배열로 복사합니다. 재귀는 base case와 base case로 향하는 변화가 필요합니다.
-
Module 2
Linked lists
LinkedList는 random access를 포기하는 대신 포인터 갱신으로 데이터를 조작합니다. SLL, DLL, CLL의 edge case와 비용을 비교했습니다.
-
Module 3
Stacks and queues
Stack은 한쪽 끝만 사용하고, Queue는 뒤에 넣고 앞에서 뺍니다. ArrayQueue는 circular array를 쓰며 resize 때 unwrap합니다.
시각 실험실
ArrayList backing array
연산을 고른 뒤 적용하면 위치 변화가 보입니다.
인덱스 0 유지 A
인덱스 1 유지 B
인덱스 2 유지 C
인덱스 3 유지 D
인덱스 4 비어 있음
인덱스 5 비어 있음
Call stack
factorial(4)를 호출하고 반환을 기다립니다.
호출 factorial(4)
Binary search
목표값: 19. 19 > 13이므로 mid까지의 왼쪽 절반을 제외합니다.
0 low 2
1 범위 5
2 범위 8
3 mid 13
4 범위 19
5 범위 21
6 high 34
1. low 0, mid 3, high 6: 19 > 13이므로 mid까지의 왼쪽 절반을 제외합니다.
Stack / Queue ADT
Stack은 한쪽 top에서만 변하고, Queue는 back으로 들어가 front에서 나갑니다.
Stack / LIFO
대기 A
대기 B
top C
Queue / FIFO
front A
대기 B
back C
개념 노트
ArrayList resize
backing array가 가득 차면 더 큰 배열을 만들고 기존 원소를 복사한 뒤 새 데이터를 넣습니다.
Module 1 · ArrayList
Recursion trace
각 recursive call은 더 작은 call을 기다립니다. base case가 반환되면 call stack이 거꾸로 풀립니다.
Module 1 · Recursion
Circular queue
ArrayQueue는 front index를 유지합니다. Enqueue는 (front + size) % capacity에 들어가고, dequeue는 front를 modulo로 한 칸 이동합니다.
Module 3 · Stack & Queue
스스로 점검
Module 0 · 기초
기초와 Java review
Enhanced for loop는 내부적으로 무엇을 사용하나요?
Iterator(hasNext/next)를 사용합니다. Iterable을 구현해야 enhanced for loop에서 동작합니다.
Comparable과 Comparator의 차이는?
Comparable은 타입의 자연 정렬(compareTo)을 정의하고, Comparator는 외부에서 교체 가능한 정렬 규칙입니다.
Module 0 · Big-O
Big-O와 primitive operations
Big-O는 정확히 무엇을 나타내나요?
worst-case growth에 대한 가장 타이트한 upper bound입니다. 상수와 낮은 차수 항은 제거합니다.
둘 다 O(n)이면 속도가 같나요?
꼭 그렇지는 않습니다. Big-O에서는 상수와 낮은 차수 항을 버리지만 실무에서는 체감될 수 있습니다.
Module 1
Arrays, ArrayLists, recursion
ArrayList addToBack은 amortized O(1)인데 addAtIndex는 왜 O(n)인가요?
addToBack은 가끔만 resize하지만, addAtIndex는 뒤쪽 원소를 모두 한 칸씩 오른쪽으로 밀어야 합니다.
모든 재귀에 필요한 것과 binary search의 관계는?
base case와 그쪽으로 향하는 진행이 필요합니다. Binary search는 매 단계 탐색 범위를 절반으로 줄입니다.
Module 2
Linked lists
removeFromBack이 SLL에서는 O(n), DLL에서는 O(1)인 이유는?
SLL은 head부터 걸어가 새 tail을 찾아야 하지만, DLL은 tail.prev를 바로 읽습니다.
CLL은 어떻게 양끝 삽입을 O(1)로 처리하나요?
head 포인터 하나만 유지하고 data-swap trick으로 front와 back을 모두 O(1)에 접근합니다.
Module 3
Stacks and queues
Stack과 Queue의 순서 규칙은?
Stack은 LIFO로 한쪽 끝만 쓰고, Queue는 FIFO로 back에 넣고 front에서 뺍니다.
ArrayQueue의 enqueue 위치는?
(front + size) % capacity입니다. circular array이고 resize 때 더 큰 배열로 unwrap합니다.