๋งค์ผ Python, Java๋ก ํธ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ !
- ํ๋ฃจ์ ์ต์ 1๊ฐ์ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํ๊ธฐ
- ๋ชป ํธ๋ ๋ฌธ์ ๋ผ๋ ์ต๋ํ ๊ณ ๋ฏผํด๋ณด๊ธฐ
- ๋๊ตฌ๋ ๋ณด์๋ ์ดํด ํ ์ ์๋ ์ฝ๋์ ํ์ด๋ฅผ ์์ฑํ๋ ค๊ณ ๋ ธ๋ ฅํ๊ธฐ
- ์คํ / ํ
- ํด์ฌ
- ํ
- ์์ ํ์
- ์ ๋ ฌ
- ๊ทธ๋ฆฌ๋
- DFS/BFS
- ๊ทธ๋ํ
- ์ด์ง ํ์
- DP
- ๊ทธ๋ฆฌ๋
- ํ์
- DFS/BFS
- ํ๋ก์ด๋ ์์ฌ
- DP
-
LEVEL 1
- 2016๋
- ๊ฐ์ ์ซ์๋ ์ซ์ด
- ๊ฐ์ด๋ฐ ๊ธ์ ๊ฐ์ ธ์ค๊ธฐ
- ๋๋์ด ๋จ์ด์ง๋ ์ซ์ ๋ฐฐ์ด
- ๋ ์ ์ ์ฌ์ด์ ํฉ
- ๋ฌธ์์ด ๋ด ๋ง์๋๋ก ์ ๋ ฌํ๊ธฐ
- ์์ ์ฐพ๊ธฐ
- ๋ฌธ์์ด ๋ด p์y์ ๊ฐ์
- ์์ ์ํธ
- ์ด์ํ ๋ฌธ์ ๋ง๋ค๊ธฐ
- ํธ๋ํฐ ๋ฒํธ ๊ฐ๋ฆฌ๊ธฐ
- ์ต๋๊ณต์ฝ์์ ์ต์๊ณต๋ฐฐ์
-
LEVEL 2
-
LEVEL 3
- ๋น๋ฐ ์ง๋
- ๋คํธ ๊ฒ์
- ํ๋ ์ฆ 4๋ธ๋ก
- ๋ด์ค ํด๋ฌ์คํฐ๋ง
- ๋ฐฉ๊ธ ๊ทธ๊ณก
- ์บ์
- ์์ถ
- ํ์ผ๋ช ์ ๋ ฌ
- n์ง์ ๊ฒ์
- ์คํ / ํ
- ํด์ฌ
- ํ
- ์์ ํ์
- ์ ๋ ฌ
- DFS/BFS
- ๊ทธ๋ํ
์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋ฅผ ํ๋ค ๋ณด๋ฉด ์๊ฐ๋ณต์ก๋๋ฅผ ์๊ฐํด์ผ ํ๋ ๊ฒฝ์ฐ๊ฐ ์ข
์ข
์๊ธด๋ค.
์๊ฐ๋ณต์ก๋ ๊ธฐ์ค์ด ์์ด์, ๊ธฐ์ค์ ๋๊ธฐ์ง ๋ชปํ๋ฉด ๋ฌธ์ ๋ฅผ ํ์ด๋ ํ๋ฆฌ๋ ๊ฒฝ์ฐ๊ฐ ์๊ธด๋ค.
| Operation | Example | Big-O | Notes |
|---|---|---|---|
| Index | l[i] | O(1) | ย |
| Store | l[i] = 0 | O(1) | ย |
| Length | len(l) | O(1) | ย |
| Append | l.append(5) | O(1) | ย |
| Pop | l.pop() | O(1) | l.pop(-1) ๊ณผ ๋์ผ |
| Clear | l.clear() | O(1) | l = [] ๊ณผ ์ ์ฌ |
| Slice | l[a:b] | O(b-a) | l[:] : O(len(l)-0) = O(N) |
| Extend | l.extend(โฆ) | O(len(โฆ)) | ํ์ฅ ๊ธธ์ด์ ๋ฐ๋ผ |
| Construction | list(โฆ) | O(len(โฆ)) | ์์ ๊ธธ์ด์ ๋ฐ๋ผ |
| check ==, != | l1 == l2 | O(N) | ๋น๊ต |
| Insert | ใ ฃ.insert(i, v) | O(N) | i ์์น์ v๋ฅผ ์ถ๊ฐ |
| Delete | del l[i] | O(N) | ย |
| Remove | l.remove(โฆ) | O(N) | ย |
| Containment | x in/not in l | O(N) | ๊ฒ์ |
| Copy | l.copy() | O(N) | l[:] ๊ณผ ๋์ผ - O(N) |
| Pop | l.pop(i) | O(N) | l.pop(0):O(N) |
| Extreme value | min(l)/max(l) | O(N) | ๊ฒ์ |
| Reverse | l.reverse() | O(N) | ๊ทธ๋๋ก ๋ฐ๋๋ก |
| Iteration | for v in l: | O(N) | ย |
| Sort | l.sort() | O(N Log N) | ย |
| Multiply | k*l | O(k N) | [1,2,3] * 3ย ยป O(N**2) |
| Operation | Example | Big-O | Notes |
|---|---|---|---|
| Index | d[k] | O(1) | ย |
| Store | d[k] = v | O(1) | ย |
| Length | len(d) | O(1) | ย |
| Delete | del d[k] | O(1) | ย |
| get/setdefault | d.method | O(1) | ย |
| Pop | d.pop(k) | O(1) | ย |
| Pop item | d.popitem() | O(1) | ย |
| Clear | d.clear() | O(1) | s = {} or = dict() ์ ์ฌ |
| View | d.keys() | O(1) | d.values() ๋์ผ |
| Construction | dict(โฆ) | O(len(โฆ)) | ย |
| Iteration | for k in d: | O(N) | ย |
| Class Name | Add | Remove | Get | Contains | Iterator.remove |
|---|---|---|---|---|---|
| ArrayList | O(1) | O(n) | O(1) | O(n) | O(n) |
| LinkedList | O(1) | O(1) | O(n) | O(n) | O(1) |
| Class Name | Add | Contains | Next |
|---|---|---|---|
| HashSet | O(1) | O(1) | O(h/n) - h๋ ํ ์ด๋ธ ์ฉ๋ |
| LinkedHashSet | O(1) | O(1) | O(1) |
| EnumSet | O(1) | O(1) | O(1) |
| TreeSet | O(log n) | O(log n) | O(log n) |
| Class Name | Offer | Peak | Poll | Size |
|---|---|---|---|---|
| PriorityQueue | O(log n) | O(1) | O(log n) | O(1) |
| LinkedList | O(1) | O(1) | O(1) | O(1) |
| ArrayDequeue | O(1) | O(1) | O(1) | O(1) |
| DelayQueue | O(log n) | O(1) | O(log n) | O(1) |
| Class Name | Get | ContainsKey | Next |
|---|---|---|---|
| HashMap | O(1) | O(1) | O(h/n) - h๋ ํ ์ด๋ธ ์ฉ๋ |
| LinkedHashMap | O(1) | O(1) | O(1) |
| EnumMap | O(1) | O(1) | O(1) |
| TreeMap | O(log n) | O(log n) | O(log n) |