ย ์นด์ด์คํธ์์ ์งํ๋๋ SW์ ๊ธ ์ปค๋ฆฌํ๋ผ์ ๋ฐํ์ผ๋ก ์์ฑํ์์ต๋๋ค. ๋์ค์ ๋ณต์ตํ ๋ ์ฐพ์๋ณด๊ธฐ ์ํด ๋ฐ๋ก ์ ๋ฆฌ๋ฅผ ํ์ต๋๋ค. ํํธ๋ง๋ค ์ ์ ์ฌ์กฑ์ด ๋ฌ๋ ค์๋๋ฐ ์ฐธ๊ณ ํ์ค ๋ถ๋ค์ ์ํด ์ ์ ์ํฉ์ ๋ง์๋๋ฆฌ์๋ฉด, python์ผ๋ก ํ์ต์ ์งํํ์๊ณ ์ฝ 4์ฃผ๊ฐ ๋งค์ผ ํ๊ท 5~6๋ฌธ์ ์ ๋ ํ์์ต๋๋ค.(ํ์๋ค๋ ๋ง์ด ๋ถ๋๋ฝ๊ฒ ๋ง์ด ํด๋ต์ ์ฐพ์๋ณด๊ธดํ๋๋ฐ..) ์ ๊ธ์ ์
์ํ๊ธฐ ์ ์ฝ๋ฉ ๊ณต๋ถ๋ ๊ตญ๋น๊ต์ก์ ์ด์ํ ๊ฒ์ด ์ ๋ถ์
๋๋ค. ๋ฌธ๊ณผ ๋ํ ์ถ์ ์ด๋ผ ์ฝ๋ฉ์ ๋ํด ์ ํ ๋ชจ๋ฅด๋ ์ํฉ์ด์๊ณ ์๊ณ ๋ฆฌ์ฆ ๊ณต๋ถ์ ์์ด์๋ ๋ฐ๋ฅ์์ ์ถ๋ฐํ ๊ฒ ๊ฐ์ต๋๋ค.
ย ์ด๋ก ๊ณต๋ถ๋ ์๋ ์ฑ
์ผ๋ก ์งํํ์์ต๋๋ค!!
์๋ ํํธ๋ ์ฑ ์ ํํธ๊ฐ ์๋ ์ ๊ธ์์ ๋๋ ์ฃผ์ ํํธ์ ๋๋ค.
ํต์ฌ ํค์๋ :
๋ฐฐ์ด, ๋ฌธ์์ด, ๋ฐ๋ณต๋ฌธ๊ณผ ์ฌ๊ทํจ์, ๊ณ์ฐ๋ณต์ก๋, ์ ๋ ฌ, ์์ ํ์, ์ ์๋ก
์ถ์ฒ : ๋ด๊ฐ ํ์ฌ ์ฌ์ฉํ๋ ์ธ์ด(์๋ฅผ ๋ค์ด, Python, C ๋ฑ)์ ๊ธฐ๋ณธ์ ์ธ ์ ์ถ๋ ฅ ๋ฐฉ์์ ๋ชจ๋ฅธ๋ค๊ฑฐ๋, ์๋ฃํ, ์ ๋ ฌ ๋ฐฉ์ ๋ฑ์ ์ ํํ ์์ง ๋ชป ํ๋ค๋ฉด ๋ฐ๋์ ์ตํ๊ณ ๋์ด๊ฐ์ผํ ํํธ.
๋ฌธ์ ๋ฒํธ | ์ฃผ์ | ๋ฌธ์ ์ ๋ชฉ | ๊ณต๋ถํฌ์ธํธ |
---|---|---|---|
2557 | ์ ์ถ๋ ฅ | Hello World | ์ผ๋จ ๋ง์ผ๋ฉด ๊ธฐ๋ถ ์ข์ |
10869 | ์ ์ถ๋ ฅ | ์ฌ์น์ฐ์ฐ | /, //์ ์ฐจ์ด๋? |
2588 | ์ ์ถ๋ ฅ | ๊ณฑ์ | ์๋ฃํ, ์๋ฆฟ์๋ณ ์ถ๋ ฅ |
2753 | ์กฐ๊ฑด๋ฌธ | ์ค๋ | if else |
10871 | ๋ฐ๋ณต๋ฌธ | X๋ณด๋ค ์์ ์ | ๋ฐ๋ณต๋ฌธ(end์sep์ ๋ค) |
8958 | ๋ฐฐ์ด | OXํด์ฆ | ์ธ๋ฑ์ค , ์ด์คfor๋ฌธ |
4344 | ๋ฐฐ์ด | ํ๊ท ์๋๊ฒ ์ง | ์์์ ์ถ๋ ฅ |
11654 | ๋ฌธ์์ด | ์์คํค ์ฝ๋ | ์์คํค ์ฝ๋๋ ๋ ๋ ํ ๊ตญ๋ฐฅ |
1152 | ๋ฌธ์์ด | ๋จ์ด์ ๊ฐ์ | split, remove |
2869 | ์ํ | ๋ฌํฝ์ด๋ ์ฌ๋ผ๊ฐ๊ณ ์ถ๋ค | ๋๋ ์ง ๊ฐ๊ณ ์ถ๋ค(import math) |
1978 | ์ํ | ์์ ์ฐพ๊ธฐ | ์ปดํจํ ์ฌ๊ณ |
10872 | ์ฌ๊ทํจ์ | ํฉํ ๋ฆฌ์ผ | ๊ณตํฌ์ ์ฌ๊ท ์์ |
1914 | ์ฌ๊ทํจ์ | ํ๋ ธ์ด ํ | print๋ฅผ ์ด๋์ ๋๊น? |
9663 | ์ฌ๊ทํจ์ | N-Queen | ๋ฐฉ๋ฌธํ ์ง์ญ ์ฒดํฌ, ์ฌ๊ท |
2750 | ์ ๋ ฌ | ์ ์ ๋ ฌํ๊ธฐ | ๋ญ์ผ ์ฝ๋ค(์ง์ฅ์ 3์ฐ๋ฒ ์์) |
2751 | ์ ๋ ฌ | ์ ์ ๋ ฌํ๊ธฐ2 | ์ด? ์๊ฐ์ด๊ณผ?(sys.stdin.readline) |
10989 | ์ ๋ ฌ | ์ ์ ๋ ฌํ๊ธฐ3 | ์ด? ๋ฉ๋ชจ๋ฆฌ์ด๊ณผ?(๋์์ ๋ ฌ) |
1181 | ์ ๋ ฌ | ๋จ์ด ์ ๋ ฌ | ๊ธ์ ํฌ๊ธฐ ์ ์ ๋ ฌ, ์ค๋ณต์ ๊ฑฐ |
2390 | ์์ ํ์ | ์ผ๊ณฑ ๋์์ด | permutation, combination |
10819 | ์์ ํ์ | ์ฐจ์ด๋ฅผ ์ต๋๋ก | max, abs, itertools ์ข ํฉ์ ๋ฌผ์ ํธ |
ย ํํธ1 ์ค ๋๋ฅผ ๊ฐ์ฅ ๊ณจ์น ์ํ๊ฒ ํ ์น๊ตฌ๋ ๋ค๋ฆ ์๋ ์ฌ๊ท(recursion).. ํํธ1 ํน์ฑ์ ์ฌ๊ธฐ ๋์จ ๊ฐ๋ ์ด๋ ํ์ด ๋ฐฉ์์ ํํธ4๊น์ง ์ญ์ฑ ์ด์ด์ง๋๋ฐ ์ฌ๊ท๋ ์๋ฌด๋ฆฌ ์ ํด๋ ์ฝ์ง๊ฐ ์์๋ค. ๊ทธ๋๋ ํํธ4๊น์ง ๊ณต๋ถ๋ฅผ ๋ง์น๊ณ ๋ค์ ๋์์์ ํ์ด๋ณด๋ ์๋ก์ด ๋๋์ด์๋ค. ํนํ, N-Queen์ ์ฒ์ ํ ๋๋ง ํด๋ DFS๋ฅผ ๋ชจ๋ฅด๋ค๋ณด๋๊น ๋๋ฌด ์ด๋ ค์ ๋๋ฐ DFS๋ฅผ ํ์ตํ๊ณ ์์ ๋ค์ ๋ณด๋ ์ด๋ฐ ๊ฑฐ์๊ตฌ๋!! ํ๊ฒ ๋๋ ๊ทธ๋ฐ ์ฆ๊ฑฐ์์ด ์๋ค.
ํต์ฌ ํค์๋ :
์ด๋ถํ์, ๋ถํ ์ ๋ณต, ์คํ, ํ, ์ฐ์ ์์ ํ
ย ์ถ์ฒ : ๋ด๊ฐ ์ค๊ณํ ๋ ผ๋ฆฌ๋ ๋ง์ผ๋, ๋ฌธ์ ๋ฅผ ํธ๋๋ฐ ์๊ฐ์ด๊ณผ๊ฐ ๋ง์ด ๋๋ค๋ฉด ๊ผญ ์ตํ์ผ ํ ํํธ. ์ปดํจํ ์ฌ๊ณ ๋ก์ ์ ํ์์ ๊ฐ์ฅ ์ค์ํ ํํธ๊ฐ ์๋๊ฐ ์ถ์. ์๊ฐ๋ณต์ก๋(time complexity)๋ฅผ ๋ฐ์ง์ง ์๊ณ ์ฝ๋๋ฅผ ์ง๋ ๊ฑด ์ปดํจํฐ๊ณผํ์์ ์ง์๋์ด์ผ ํ ๋ฐฉํฅ์์ ์ ์คํ ํ์ธ.
๋ฌธ์ ๋ฒํธ | ์ฃผ์ | ๋ฌธ์ ์ ๋ชฉ | ๊ณต๋ถํฌ์ธํธ |
---|---|---|---|
2805 | ์ด๋ถํ์ | ๋๋ฌด ์๋ฅด๊ธฐ | ์ค๋ฆ์ฐจ์ ์ ๋ ฌ ํ, start, end๊ฐ์ผ๋ก mid๋ฅผ ์ฐพ์ |
2110 | ์ด๋ถํ์ | ๊ณต์ ๊ธฐ ์ค์น | ์ฝ๋๊ฐ ์งํ๋๋ ๊ณผ์ ์ ์๋ฒฝํ ์ดํดํด์ผ ํ ์ ์์ |
16564 | ์ด๋ถํ์ | ํ์ค์ค ํ๋ก๊ฒ์ด๋จธ | start, end๋ฅผ ๋ญ๋ก ์ก์๋? |
1629 | ๋ถํ ์ ๋ณต | ๊ณฑ์ | ๋ถํ ์ ๋ณต์ ์ฌ๊ท๊ฐ ํ์, ๋๋จธ์ง๋ถ๋ฐฐ์ฐ์ฐ๋ฒ์น |
2630 | ๋ถํ ์ ๋ณต | ์์ข ์ด ๋ง๋ค๊ธฐ | ์ด๋๋ฅผ ๊ธฐ์ค์ผ๋ก ๋๋ ์ง ๋ณด์ด๋์? |
2261 | ๋ถํ ์ ๋ณต | ๊ฐ์ฅ ๊ฐ๊น์ด ๋์ | ๋ ผ๋ฆฌ๊ตฌ์กฐ ์ง๊ธฐ๊ฐ ๊น๋ค๋กญ์ง๋ง ์ง๊ณ ๋ณด๋ฉด ์ฌ์ด. |
10828 | ์คํ | ์คํ | Last In First Out |
9012 | ์คํ | ๊ดํธ | ์ด ๋ฌธ์ ๋ฅผ ๋ณด๊ณ ์คํ์ ๋ชป ๋ ์ฌ๋ฆฐ๋ค๋ฉด..? |
2504 | ์คํ | ๊ดํธ์ ๊ฐ | ์ปดํจํ ์ฌ๊ณ ์ ํ์ด ํ์ํด |
2493 | ์คํ | ํ | ์๊ฐ ๋น๊ฒ์ด์ธ ๋ ํฌ๊ธฐํ ๋ด ํ์ด(์์ ํ์) |
2164 | ํ | ์นด๋2 | popleft()๋ ์ผ๋จ ์ฐ๋ฉด ํ์ด๋๊ฐ |
11866 | ํ | ์์ธํธ์ค ๋ฌธ์ 0 | deque๋ฅผ ํ์ฉํ ์ปดํจํ ์ฌ๊ณ |
3190 | ํ | ๋ฑ | ๋ฐฉํฅ ๋ฌธ์ , bfs๋ฅผ ์๊ณ ๋๋ ๋ค๋ฅธ ๋ฌธ์ ๋ก ๋ณด์ธ๋ค! |
11279 | ์ฐ์ ์์ ํ | ์ต๋ ํ | heappop์ ๊ฐ์ด ๊ฐ์ฅ ๋ฎ์ ๊ฑธ ๋ฑ๋๋ค. ๊ทธ๋ ๋ค๋ฉด? |
1655 | ์ฐ์ ์์ ํ | ๊ฐ์ด๋ฐ๋ฅผ ๋งํด์ | ๊ฐ์ด๋ฐ๋ฅผ ๋งํ๋ tree๊ฐ ์๋ค? |
13334 | ์ฐ์ ์์ ํ | ์ฒ ๋ก | ์ ๋ ฌ๋ง ์ ํ๋ค๋ฉด ์ฌ์ด ๋ฌธ์ . |
ย ํํธ2์ ํต์ฌ์, binary search, divide and conquer ๋ฑ์ ์ ํ์ฉํ์ฌ ์๊ฐ ๋ณต์ก๋๋ฅผ ๋ฎ์ถ๋ ๊ฑฐ ๊ฐ๋ค. ์ฒ์ ๊ณต๋ถํ ๋๋ ์๊ฐ๋ณต์ก๋๊ฐ ๋ญ์ง ๋ชฐ๋ผ์ ๊ณ ์ํ๋ค. ๋ถ๋ช ์ด๋ ๊ฒ ํ๋ฉด ๋ต์ด ๋์ค๊ณ ๋ด ๋น์ฃผ์ผ ์คํ๋์ค์์๋ ์ฌ๋ฐ๋ฅธ ๋ต์ด ์ถ๋ ฅ๋๋๋ฐ ์ ์ถ๋ง ํ๋ฉด ์๊ฐ์ด๊ณผ๋๋ค. ์ด์ ๋ ๋ฌธ์ ๋ฅผ ๋ฐ์ผ๋ฉด, n, m ๊ฐ์ ๋ฒ์๋ถํฐ ํ์ธํ๊ฒ ๋๋ค. ๋ฌผ๋ก ๊ทธ๋ ๋ค๊ณ ํ์ฌ ์๊ฐ๋ณต์ก๋๋ฅผ ์ ๋ฐํ ๊ณ์ฐํ๋ ๊ฑด ์๋์ง๋ง, ๋์ถฉ ์์ ํ์์ ํ๋ฉด ์๊ฐ์ด๊ณผ๊ฐ ๋จ๊ฒ ๊ตฌ๋ ์ ๋๋ ํ์ ํ ์ ์๋ค. ์ปดํจํฐ์๊ฒ ๋๊ฒจ์ค ๋ ๋ถํ์ํ ๋ถ๋ถ์ ์ณ๋ด๊ณ ๋ด๊ฐ ์ํ๋ ๋ต์ ๋น ๋ฅด๊ฒ ์ป์ ์ ์๋ ๊ทธ๋ฐ ์ด์ ์ฝ๋๋ฅผ ์งค ์ ์๋๋ก ์ด์ฌํ ๊ณต๋ถํด๋ณด์!
ํต์ฌ ํค์๋ :
๊ทธ๋ํ(vertex, edge, node, arc), BFS, DFS, ์์์ ๋ ฌ
์ถ์ฒ : ์ฃผ์ด์ง๋ ๋ฐ์ดํฐ ๊ฐ์ ๊ด๊ณ๊ฐ ๋ณด์ธ๋ค๋ฉด, ๊ทธ๋ํ๋ฅผ ๊ทธ๋ฆด ์ ์๋ค. ๋ ธ๋ ๊ฐ ์ฐ๊ฒฐ์ ๋ค ํ๋๋ฐ ๊ทธ ๋ค์์ ๋ชจ๋ฅด๊ฒ ๋ค๋ฉด ๋ฐ๋์ ์ตํ์ผ ํ ํํธ.
๋ฌธ์ ๋ฒํธ | ์ฃผ์ | ๋ฌธ์ ์ ๋ชฉ | ๊ณต๋ถํฌ์ธํธ |
---|---|---|---|
1991 | ๊ทธ๋ํํ์๊ธฐ๋ณธ | ํธ๋ฆฌ์ํ | ์ ์์ํ, ์ค์์ํ, ํ์์ํ |
1260 | ๊ทธ๋ํํ์๊ธฐ๋ณธ | DFS์ BFS | DFS์ BFS๋ฅผ ๋ฐฐ์ฐ๊ณ ์ถ๋ค๋ฉด ์ด๊ฑธ ๊ผญ ๋จผ์ |
5639 | ๊ทธ๋ํํ์๊ธฐ๋ณธ | ์ด์ง ๊ฒ์ ํธ๋ฆฌ | ์ด์งํ์์ ์ํํํฉ์๋ค! |
1197 | ๊ทธ๋ํํ์๊ธฐ๋ณธ | ์ต์์คํจ๋ํธ๋ฆฌ | Kruskal, Prim ์๊ณ ๋ฆฌ์ฆ |
11725 | DFS | ํธ๋ฆฌ์ ๋ถ๋ชจ์ฐพ๊ธฐ | ์ฌ๊ท ๊ตฌ์กฐ๋ฅผ ์๋ฒฝํ ์ดํดํ๋ค๋ฉด ์ฌ์ |
1707 | DFS | ์ด๋ถ ๊ทธ๋ํ | -+-+-+๊ฐ ํต์ฌ |
21606 | DFS | ์์นจ ์ฐ์ฑ | DFS๊ฐ ์ด๋ค ๊ฐ์ returnํ๋ ์ง๊ฐ ํฌ์ธํธ |
14888 | DFS | ์ฐ์ฐ์ ๋ผ์๋ฃ๊ธฐ | DFS๋ ์ฌ๊ท๋ค!(์กฐํฉํ์ด๋ ์๊ฐ ๋น๊ต) |
2573 | DFS | ๋น์ฐ | ๋ถํ ์ ๋ณต, DFS, ๋ฐฉํฅ ์ผ์์ผ์ฒด |
2178 | BFS | ๋ฏธ๋ก ํ์ | BFS๋ deque์ ์ฐ๋ฉด ํธ๋ฆฌํด |
18352 | BFS | ํน์ ๊ฑฐ๋ฆฌ์๋์์ฐพ๊ธฐ | ์ด ๋๋ ๋ชฐ๋์ง BFS+DP๋ผ๋ ๊ฑธ |
1916 | BFS | ์ต์๋น์ฉ๊ตฌํ๊ธฐ | ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ(heapq๋ง ์ผ์ ๋ฟ์ธ๋ฐ!) |
7569 | BFS | ํ ๋งํ | 3์ฐจ์ BFS |
3055 | BFS | ํ์ถ | BFS๊ฐ ๋์์ 2๊ฐ๊ฐ ๋๋ค๋ฉด? |
2252 | ์์์ ๋ ฌ | ์ค์ธ์ฐ๊ธฐ | ์ง์ ์ฐจ์๊ฐ 0์ธ ๋ ธ๋๋ถํฐ ์์ |
2637 | ์์์ ๋ ฌ | ์ฅ๋๊ฐ์กฐ๋ฆฝ | ์์์ ๋ ฌ ๊ตฌ์กฐ ์ก๊ธฐ ์ข์ ๋ฌธ์ |
ย ์๊ณ ๋ฆฌ์ฆ ๊ณต๋ถ์ ์ฌ๋ฏธ๋ฅผ ๋๋ผ๊ธฐ ์์ํ ํํธ. ๋ฌธ์ ๋ ์ด์ ํํธ๋ค์ ๋นํด ์ด๋ ค์ ์ง์ ํ์ง ๋ชป ํ ๋ฌธ์ ๊ฐ ๋ง์ง๋ง, DFS์ BFS ๋ฐฉ์์ ๋ํ ๊ธฐ์ด๊ฐ ์กํ๊ณ ๋๋ ๋ค๋ฅธ ์ฌ๋์ด ์์ฑํ ์ฝ๋๋ฅผ ๋ด๋ ์ดํดํ๊ธฐ ์์ํ์๋ค. ํํธ3๋ถํฐ ํ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ๋ฌธ์ ๋ฅผ ํธ๋ ๊ฒ๋ณด๋ค ์ด์ ์ ๋ฐฐ์ ๋ ๊ฒ์ ํ์ฉํ๋ฉด ์๊ฐ์ ๋จ์ถํ๊ธฐ๊ฐ ์ข์๋ค. ์ฌ๋ด์ผ๋ก ์ด์ง๊ฒ์ํธ๋ฆฌ(5639)๋ฅผ ํ ๋, ์ค๊ฐ mid๊ฐ์ ์ฐพ๋ ๊ณผ์ ์ด ๋์ค๋๋ฐ ๋๋ ์์ ํ์์ ํตํด mid๊ฐ์ ์ฐพ์๋๋ ์๊ฐโฐ์ด 3700ms์ด๋ ๋์จ ๋ฐ๋ฉด, ์ด์งํ์์ ์ํํ ์ฝ๋๋ 100ms๋ฐ์ ๋์ค์ง ์์๋ค. ์๊ฐ์ ์ค์ผ ์์๊ฐ ๋ณด์ธ๋ค๋ฉด ์ต๋ํ ์ค์ฌ๋ณด์!!
ํต์ฌ ํค์๋ :
๋์ ํ๋ก๊ทธ๋๋ฐ(DP), ๊ทธ๋ฆฌ๋
์ถ์ฒ : ์ฌ๊ท, ๋ถํ ์ ๋ณต์ ์ด๋ ์ ๋ ์ดํดํ๊ณ ์์ง๋ง ํ์ด ์ ์๊ฐ์ด๊ณผ ํน์ ๋ฉ๋ชจ๋ฆฌ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค๋ฉด ๊ณต๋ถํ๊ธฐ ์ข์ ํํธ. ํนํ, ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋ฉด ๋๋ถ๋ถ ์์ ๋ฐ์ํ ๋ฌธ์ ๊ฐ ํด๊ฒฐ๋ ์ ์์ผ๋ ์ ์ฌ์ ์์ ์ฌ์ฉํ์ง ์๋๋ค๋ฉด 'ํ๋ ธ์ต๋๋ค'๋ฅผ ๋ง์ดํ ์ ์์ผ๋ ์ฃผ์!
๋ฌธ์ ๋ฒํธ | ์ฃผ์ | ๋ฌธ์ ์ ๋ชฉ | ๊ณต๋ถํฌ์ธํธ |
---|---|---|---|
2748 | DP | ํผ๋ณด๋์น ์2 | ๋ฐํ ์ , ํ๋ค์ด 2๊ฐ์ง ๋ชจ๋ ํ์ตํด๋ณด์ |
1904 | DP | 01ํ์ผ | ์ ํ์์ ์ฐพ๋ ๊ฒ ์ค์ํ๋ค! |
9084 | DP | ๋์ | DPํ ์ด๋ธ ๋ง๋ค๊ธฐ, ์ฌ๊ทํด ๊ตฌ์ํ๊ธฐ |
9251 | DP | LCS | DPํ ์ด๋ธ x์ถ,y์ถ ์ก๊ธฐ |
12865 | DP | ์์ฃผ ํ๋ฒํ ๋ฐฐ๋ญ | Knapsack ์๊ณ ๋ฆฌ์ฆ(๊ตญ๋ฐฅ ๋ฌธ์ ) |
11053 | DP | ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด | ์๊ฐ๋ณต์ก๋๋ฅผ ๊ณ ๋ คํ ์๊ณ ๋ฆฌ์ฆ ์ค๊ณ |
2098 | DP | ์ธํ์ ์ํ | ๋นํธ๋ง์คํน, ๋ ๋ฑ์ฅํ DFS+DP |
2253 | DP | ์ ํ | DP๋ ๋ชจ๋ ํ ์ด๋ธ์ ์ฑ์์ผํ๋ค. |
11047 | ๊ทธ๋ฆฌ๋ | ๋์ 0 | ์์ ์ ํ์ด ๋ค์ ์ํฅ์ ์ฃผ๋ฉด ์๋๋ค |
1541 | ๊ทธ๋ฆฌ๋ | ์์ด๋ฒ๋ฆฐ ๊ดํธ | ํ์ด๋ฅผ ๋ณด๊ณ ์ ์ผ ์ถฉ๊ฒฉ๋ฐ์ ์ปดํจํ ์ฌ๊ณ (Thinking) |
1931 | ๊ทธ๋ฆฌ๋ | ํ์์ค ๋ฐฐ์ | ๊ทธ๋ฆฌ๋๋ ์ ๋ ฌ์ด ํต์ฌ |
1700 | ๊ทธ๋ฆฌ๋ | ๋ฉํฐํญ ์ค์ผ์ค๋ง | ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ ์ฌ์ฉ ํ๋จ ๊ทผ๊ฑฐ๋ฅผ ์ฐพ๊ธฐ |
ย DP์ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ ๋ชจ๋ ์ฃผ์ด์ง ์ํฉ์ด ์ต์ ๋ถ๋ถ๊ตฌ์กฐ(Optimal substructure)๋ฅผ ๋ง์กฑํด์ผ ์ฌ์ฉ๊ฐ๋ฅํ๋ฉฐ, ์ฌ๊ทํด๋ฅผ ๊ฐ์ ธ์ผํ๋ค. ์ต์ ๋ถ๋ถ๊ตฌ์กฐ๋ผ๋ ๋ง์ด ์ฝ๊ฒ ์๋ฟ์ง ์์์ผ๋, CLRS ์ฑ ์์ LCS ๋ฌธ์ ๋ฅผ ์น์ ํ ์ค๋ช ํด์ฃผ๋ ๋ถ๋ถ์ด ๋์ค๋๋ฐ ๊ทธ ๋ถ๋ถ์ ํ์ตํ๋ฉฐ ์ต์ ๋ถ๋ถ๊ตฌ์กฐ์ ๋ํด ์ดํดํ ์ ์์๋ค. ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๊ฒฝ์ฐ, ์์ ์ ํ์ด ์ดํ ์ ํ์ ์ํฅ์ ์ฃผ์ง ์์์ผํ๋ค๋ ์กฐ๊ฑด์ด ๊น๋ค๋ก์ ๋ค.
ย ์๊ณ ๋ฆฌ์ฆ ๋ง์ง๋ง ํํธ๋ฅผ ํ๋ ์ค์ธ๋ฐ๋ ์ฌ์ ํ ์ปดํจํ ์ฌ๊ณ ๋ก์ ์ ํ์ ์ฝ์ง ์์ ๊ฒ ๊ฐ๋ค. ์ ๊ธ ์ด์์ง ๋ถ๋ค๊ณผ ํฐํ์์ ๊ฐ๋ ์๊ฐ์ด ์์ด ํฌ๋ํํค ์ฅ๋ณ๊ท ์์ฅ๋๊ป ์ง๋ฌธ์ ๋๋ ธ๋ค. ์ปดํจํฐ๋ ๊ฒฐ๊ตญ ์ธ๊ฐ์ด ์ฌ๊ณ ํ ๊ฑธ ์ํํ๋ ๊ธฐ๊ณ์ธ๋ฐ ๋น ๋ฅธ ์ํ์๊ฐ์ ๋ณด์ด๋ ์ฝ๋๋ค์ ๋ณด๋ฉด ์ ํ ์ดํด๊ฐ ๊ฐ์ง์๋๋ฐ ๊ทธ ์ฝ๋๋ฅผ ๋ณด๊ณ ๊ณต๋ถํ๋๊ฒ ๋ง๋ ์ง ์ฌ์ญค๋ณด์๋ค. ์ด๋ ์ ๋ ๋๋ ๋ด๊ฐ ๋ง๋ค๋ ์๊ฐ์ ๋๋ฆฐ ์ง๋ฌธ์ด์์ผ๋ ์์ฅ๋์ ๋๋ต์ ์ถฉ๊ฒฉ์ ์ด์๋ค.
๊ทธ๊ฒ ์ปดํจํฐ์ ์ ํฉํ ์ฝ๋์ด๋ฉฐ, ์ดํด๊ฐ ๋์ง ์๋๋ค๋ฉด ๊ณต๋ถํ๋ ์ด๊ธฐ์๋ ๊ทธ ์ฝ๋๋ฅผ ํต์งธ๋ก ์ธ์ฐ๋ ๊ฒ ํ์ํ๋ค
1541 ๋ฌธ์ ๊ฐ ๋ฑ ์ข์ ์์์ธ ๊ฑฐ ๊ฐ๋ค. ๋์ ์ฌ๊ณ ๋ก๋ int๋ก ์ ํํ์ฌ ์์์๋ถํฐ ์ฐจ๊ทผ์ฐจ๊ทผ ๊ณ์ฐ์ ํ๋ ๊ฒ ๋ง๋ค๊ณ ์๊ฐํ์๊ณ ์๊ฐ์ด ์ค๋ ๊ฑธ๋ ธ์ง๋ง 40์ค์ด ๋์ด๊ฐ๋ ์ฝ๋๋ฅผ ์์ฑํ์๋ค. ๋ค๋ฅธ ์ฌ๋๋ค์ ์ฝ๋๋ฅผ ๋ณด๋๋ฐ, ๋จ 10์ค๋ ์๋๋ ์ฝ๋๋ก ๋๋ฌด๋ ์ฝ๊ฒ ๋ต์ ์ฐพ๋๊ฒ ๋๋ผ์ ๋ค. ์ด๋ฐ ๋ถ๋ถ๋ค์ด ์์ง ๋ง์ด ๋ถ์กฑํ ๊ฑฐ ๊ฐ์ง๋ง ๋ฐฐ์ฐ๋ ์ฌ๋ฏธ๊ฐ ์์ด ์์ผ๋ก ๋ฌ๋ ค๊ฐ ๋๋ ๋๊ตฐ๊ฐ ๊ฐํํ ์ ์๋ ๊ทธ๋ฐ ์ฝ๋๋ฅผ ์์ฑํ๊ณ ์ถ๋ค.
ํ์ต์ค์ธ ์ธ์ด๊ฐ ์๊ณ ๋ฆฌ์ฆ ๊ฐ์๊ฐ ์๋ ์ธ์ด๊ฐ ์๋๋ผ์ ์๊ณ ๋ฆฌ์ฆ ๊ณต๋ถ ์์๋ฅผ ์ฐพ๊ณ ์์๋๋ฐ, ๋ฐฑ์ค ๋ฌธ์ ๋ ๊ฐ์ด ์ ๋ฆฌ ํด์ฃผ์ ๊ฒ ๋งค์ฐ ๋์์ด ๋์ต๋๋ค! ๊ฐ์ฌํฉ๋๋ค!
์ ๋ง ๊ฐ์ฌํฉ๋๋ค ํญ์ ์์์ ์์ด์ ๊ณ ๋ฏผํ๊ณ ์์๋๋ฐ ์ ์ ๊ณ ๋ฏผ์ ๋ฑ ๋ง๋ ๊ธ์ด๋ค์ ํ๋ณตํ ํ๋ฃจ ๋์ธ์
๋งจ ์ฒซ๋ฒ์งธ ๋ฐฑ์ค ๋งํฌ์ธ HelloWorld๊ฐ ์๋ชป๋์ด 404 ์๋ฌ๋น๋๋ค..
Your writing is really informative, especially because it's so meaningful and updated. Thanks for sharing this wonderful post!
Your writing is really great. Iโm so glad I read it. It kept me hooked the whole way through.
Thanks for this information. I really appreciate the information that you have provided.
๋ฌธ์ ๋ฒํธ ๋๋ฅด๋ฉด ๋ฐ๋ก ์ด๋๋๋ ๋ํ ์ผ๊น์ง..... ๐
์ ๋ฆฌ๊ฐ ์์ฃผ ๊ตฟ์ ๋๋ค :)