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와 연결해 정리했습니다.

/ Enhanced for loop는 iterator를 사용합니다
/ Comparable은 자연 정렬입니다
/ Comparator는 외부 정렬 규칙입니다

Module 0

Big-O와 primitive operations

Big-O는 worst-case growth에 대한 가장 타이트한 upper bound로 사용하고, 상수와 낮은 차수 항은 제거합니다.

/ primitive operation을 셉니다
/ 가능한 가장 타이트한 bound를 씁니다
/ 실무에서는 상수도 체감될 수 있습니다

Module 1

Arrays, ArrayLists, recursion

ArrayList는 backing array를 사용하고, 중간 삽입/삭제에서 원소를 shift하며, 꽉 차면 더 큰 배열로 복사합니다. 재귀는 base case와 base case로 향하는 변화가 필요합니다.

/ addToBack은 amortized O(1)
/ addAtIndex는 오른쪽으로 shift
/ Binary search는 탐색 범위를 절반으로 줄입니다

Module 2

Linked lists

LinkedList는 random access를 포기하는 대신 포인터 갱신으로 데이터를 조작합니다. SLL, DLL, CLL의 edge case와 비용을 비교했습니다.

/ SLL removeFromBack은 O(n)
/ DLL은 tail.prev로 뒤 삭제가 O(1)
/ CLL은 data-swap trick으로 양끝 삽입을 처리합니다

Module 3

Stacks and queues

Stack은 한쪽 끝만 사용하고, Queue는 뒤에 넣고 앞에서 뺍니다. ArrayQueue는 circular array를 쓰며 resize 때 unwrap합니다.

/ Stack은 LIFO
/ Queue는 FIFO
/ ArrayQueue enqueue 위치는 (front + size) % capacity

시각 실험실

Big-O 증가율

선의 모양은 증가율을 보여주고, 커서는 선택한 입력 크기의 값을 읽습니다.

로그 스케일

입력 크기: 32

O(1)

O(log n)

O(n)

O(n log n)

160

O(n²)

1,024

ArrayList backing array

연산을 고른 뒤 적용하면 위치 변화가 보입니다.

연산

인덱스: 2

인덱스 0 유지 A

인덱스 1 유지 B

인덱스 2 유지 C

인덱스 3 유지 D

인덱스 4 비어 있음

인덱스 5 비어 있음

Call stack

factorial(4)를 호출하고 반환을 기다립니다.

1/9

호출 factorial(4)

Binary search

목표값: 19. 19 > 13이므로 mid까지의 왼쪽 절반을 제외합니다.

1/3

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가 가득 차면 더 큰 배열을 만들고 기존 원소를 복사한 뒤 새 데이터를 넣습니다.

m1-arrays-and-arraylists.md

Recursion trace

각 recursive call은 더 작은 call을 기다립니다. base case가 반환되면 call stack이 거꾸로 풀립니다.

m1-recursion.md + refs/m1-recursion-summary.md

Circular queue

ArrayQueue는 front index를 유지합니다. Enqueue는 (front + size) % capacity에 들어가고, dequeue는 front를 modulo로 한 칸 이동합니다.

m3-stacks-and-queues.md

두 번째 노트가 아니라 공개용 projection으로 관리합니다.

/새 주제는 먼저 3B study note에 존재해야 합니다.
/스터디 페이지 변경 전 pnpm study:check를 실행합니다.
/해시가 바뀌면 원본 노트를 검토하고 공개 모델을 의도적으로 갱신합니다.

15개 원본 파일

_index.md 73d4f27c

m0-java-review.md f27c8973

m0-iterable-comparable.md b2821863

m0-big-o-concepts.md 90226695

m1-arrays-and-arraylists.md bfdeb22d

m1-recursion.md f7f47484

m2-linked-lists.md 10e2ac72

m3-stacks-and-queues.md 7ac6c8ec

refs/m0-analysis-of-algorithms-summary.md e5177c16

refs/m0-iterators-summary.md d3af23e0

refs/m1-arrays-arraylist-summary.md c69c36c0

refs/m1-recursion-summary.md 716d4a7b

refs/m2-iterators-summary.md f20d6a73

refs/m2-linked-list-variations-summary.md 1ce8d2a3

refs/m2-singly-linked-lists-summary.md 8b70103d