์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- php ํ๋ก๊ทธ๋๋ฐ ์ ๋ฌธ ์๋ฃจ์
- programmers
- ๋ฐฐ์ด
- ํ๋ฌํฐ
- spring
- SWEA
- php ํ๋ก๊ทธ๋๋ฐ ์ ๋ฌธ ์ฐ์ต๋ฌธ์
- ํ์ด์ฝ ์ถ์ฒ์ธ
- C
- ํ์ด์ฝ ์ด๋์ฝ๋
- php ํ๋ก๊ทธ๋๋ฐ
- C์ธ์ด
- Java
- php ํ๋ก๊ทธ๋๋ฐ ์ ๋ฌธ ๋ฌธ์ ํ์ด
- php ํ๋ก๊ทธ๋๋ฐ ์ ๋ฌธ 3ํ
- php ํ๋ก๊ทธ๋๋ฐ ์ ๋ฌธ
- Flutter
- ํ์ด์ฌ
- ํ์ด์ฝ ์ถ์ฒ์ธ์ฝ๋
- ์คํ๋ง
- ์๋ฐ ์คํ๋ง
- ๋ฐฑ์ค
- ํ๋ฌํฐ ๊ฐ๋ฐํ๊ฒฝ ์ค์
- php ํ๋ก๊ทธ๋๋ฐ ์ ๋ฌธ ์์
- JAVA SPRING
- php
- ์ต๋จ ๊ฒฝ๋ก
- ํ์ด์ฝ ์น๊ตฌ์ฝ๋
- ํ์ ๋ถ๊ธฐ
- ์๋ฐ
- Today
- Total
๋ชฉ๋กํ์ด์ฌ (13)
์ฌ๋ฅ์ด๐ป
Traveling Salesman Problem(TSP) ์ต๊ณ ์ฐ์ ๊ฒ์ ๊ธฐ๋ฐ ํ์ ๋ถ๊ธฐ(Branch and Bound) ์๋ก Traveling Salesman Problem(TSP) : ์ธํ์์ด ์์ ์ ์ง์ด ์์นํ๊ณ ์๋ ๋์์์ ์ถ๋ฐํ์ฌ ๋ค๋ฅธ ๋์๋ค์ "๊ฐ๊ฐ ํ๋ฒ์ฉ๋ง ๋ฐฉ๋ฌธ"ํ๊ณ , "๋ค์ ์๊ธฐ ๋์๋ก ๋์์ค๋" ๊ฐ์ฅ ์งง์ ์ผ์ฃผ์ฌํ๊ฒฝ๋ก(tour)๋ฅผ ๊ฒฐ์ ํ๋ ๋ฌธ์ ์ต๊ณ ์ฐ์ ๊ฒ์ ๊ธฐ๋ฐ ํ์ ๋ถ๊ธฐ(Branch and Bound) ์ ๋ต - ๊ฐ ๋ ธ๋๋ ์ถ๋ฐ๋ ธ๋๋ก๋ถํฐ์ ์ผ์ฃผ์ฌํ๊ฒฝ๋ก๋ฅผ ๋ํ๋ - ๋จ๋ง๋ ธ๋์ ์๋ ์ผ์ฃผ์ฌํ๊ฒฝ๋ก๋ฅผ ๋ชจ๋ ๊ฒ์ฌํ์ฌ ๊ทธ ์ค์์ ๊ฐ์ฅ ๋น์ฉ์ด ๋ฎ์ ์ผ์ฃผ์ฌํ๊ฒฝ๋ก๋ฅผ ์ฐพ์ผ๋ฉด ๋๋ค. (๋ฌด์์ ์๊ณ ๋ฆฌ์ฆ: Brute Force ์ ๋ต) - ๋ถ๊ธฐํ์ ๊ฐ์ง์น๊ธฐ๋ก ์ต๊ณ ์ฐ์ ๊ฒ์์ ์ฌ์ฉํ๊ธฐ ์ํด์ ๊ฐ ๋ ธ๋์ ํ๊ณ์น..
0-1 Knapsack Problem ์ต๊ณ ์ฐ์ ๊ฒ์์ ์ฌ์ฉํ ํ์ ๋ถ๊ธฐ (Branch and Bound) ์๋ก ํ์ ๋ถ๊ธฐ ์ ๋ต์ ๋๊ธฐ : ๋์ถ์ ์ ๋นํจ์จ๋์ถ์ ์ ํ์ ๊ณผ์ ์์ Valid๊ฐ ์ ์ฉ๋๋๋ผ๋ ์ฌ์ ํ ์๋นํ ๋น์จ์ ์ ์ ์ ๋ฐฉ๋ฌธํ์ง ์์๋ ๋จ์ ๋ฐ๊ฒฌ ๋์ถ์ ์ ๋นํจ์จ ํด๊ฒฐ์ฑ : ๊ฐ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ ๋๋ง๋ค ํ๊ณ์น(bound)๋ฅผ ๊ณ์ฐ ํ๊ณ์น(Bound) : ํด๋น ๋ ธ๋๋ก๋ถํฐ ๊ฐ์ง๋ฅผ ๋ป์ด๋๊ฐ์(branch) ์ป์ ์ ์๋ ํด๋ต์น์ ํ๊ณ ๊ฐ 0/1 Knapsack Problem์ ์ต๊ณ ์ฐ์ ๊ฒ์์ ์ฌ์ฉํ ํ์ ๋ถ๊ธฐ(Branch and Bound) ์ ๋ต 1. ๊ทธ ๋ ธ๋์ profit๊ณผ weight๋ฅผ ๊ณ์ฐํ๋ค. 2. ๊ทธ ๋ ธ๋์ bound๋ฅผ ๊ณ์ฐํ๋ค. 3. ํ์ฌ ๋ ธ๋์ profit์ด maxprofit๋ณด๋ค ํฌ๋ฉด maxpr..
0-1 Knapsack Problem ๋๋น ์ฐ์ ๊ฒ์์ ์ฌ์ฉํ ํ์ ๋ถ๊ธฐ (Branch and Bound) ์๋ก ํ์ ๋ถ๊ธฐ ์ ๋ต์ ๋๊ธฐ : ๋์ถ์ ์ ๋นํจ์จ๋์ถ์ ์ ํ์ ๊ณผ์ ์์ Valid๊ฐ ์ ์ฉ๋๋๋ผ๋ ์ฌ์ ํ ์๋นํ ๋น์จ์ ์ ์ ์ ๋ฐฉ๋ฌธํ์ง ์์๋ ๋จ์ ๋ฐ๊ฒฌ ๋์ถ์ ์ ๋นํจ์จ ํด๊ฒฐ์ฑ : ๊ฐ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ ๋๋ง๋ค ํ๊ณ์น(bound)๋ฅผ ๊ณ์ฐ ํ๊ณ์น(Bound) : ํด๋น ๋ ธ๋๋ก๋ถํฐ ๊ฐ์ง๋ฅผ ๋ป์ด๋๊ฐ์(branch) ์ป์ ์ ์๋ ํด๋ต์น์ ํ๊ณ ๊ฐ ๊ธฐ์กด ๊น์ด ์ฐ์ ๊ฒ์(DFS) ๊ธฐ๋ฐ ์๊ณ ๋ฆฌ์ฆ์ ๋ถ๊ธฐํ์ ์ ํน์ฑ์ ์ ๋๋ก ํ์ฉํ๊ณ ์์ง ๋ชปํจ. ๊ทธ๋ ๋ค๋ฉด… ๋๋น ์ฐ์ ๊ฒ์(BFS)์ ์์ ํ์ฌ ๊ตฌํ 0/1 Knapsack Problem์ ๋๋น ์ฐ์ ๊ฒ์์ ์ฌ์ฉํ ํ์ ๋ถ๊ธฐ(Branch and Bound) ์ ๋ต 1. ๊ทธ ๋ ธ๋์ p..
0-1 Knapsack Problem ๊น์ด ์ฐ์ ๊ฒ์์ ์ฌ์ฉํ ํ์ ๋ถ๊ธฐ (Branch and Bound) ์๋ก ํ์ ๋ถ๊ธฐ ์ ๋ต์ ๋๊ธฐ : ๋์ถ์ ์ ๋นํจ์จ๋์ถ์ ์ ํ์ ๊ณผ์ ์์ Valid๊ฐ ์ ์ฉ๋๋๋ผ๋ ์ฌ์ ํ ์๋นํ ๋น์จ์ ์ ์ ์ ๋ฐฉ๋ฌธํ์ง ์์๋ ๋จ์ ๋ฐ๊ฒฌ ๋์ถ์ ์ ๋นํจ์จ ํด๊ฒฐ์ฑ : ๊ฐ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ ๋๋ง๋ค ํ๊ณ์น(bound)๋ฅผ ๊ณ์ฐ ํ๊ณ์น(Bound) : ํด๋น ๋ ธ๋๋ก๋ถํฐ ๊ฐ์ง๋ฅผ ๋ป์ด๋๊ฐ์(branch) ์ป์ ์ ์๋ ํด๋ต์น์ ํ๊ณ ๊ฐ 0/1 Knapsack Problem์ ๊น์ด ์ฐ์ ๊ฒ์์ ์ฌ์ฉํ ํ์ ๋ถ๊ธฐ(Branch and Bound) ์ ๋ต 1. ๊ทธ ๋ ธ๋์ profit๊ณผ weight๋ฅผ ๊ณ์ฐํ๋ค. 2. ๊ทธ ๋ ธ๋์ bound๋ฅผ ๊ณ์ฐํ๋ค. 3. ํ์ฌ ๋ ธ๋์ profit์ด maxprofit๋ณด๋ค ํฌ๋ฉด maxpr..
์์น ๋ฌธ์ - ๋ฐฑํธ๋ํน(Backtracking) ์ํ ๊ณต๊ฐ ํธ๋ฆฌ์ ์๊ณ ๋ฆฌ์ฆ ์๋ก ์ํ ๊ณต๊ฐ ํธ๋ฆฌ(State Space Tree)๋ ๋ฌธ์ ํด๊ฒฐ ๊ณผ์ ์ ์ค๊ฐ ์ํ๋ฅผ ๊ฐ๊ฐ ํ ๋ ธ๋๋ก ๋ํ๋ธ ํธ๋ฆฌ์ ๋๋ค. ๋ฐฑํธ๋ํน(Backtracking)์ ์ํ ๊ณต๊ฐ ํธ๋ฆฌ์์ ์๋ก์ด ํ์์ด ๋ฌด์๋ฏธํ๋ค๊ณ ํ๋จ๋๋ฉด, ๋ค๋ฅธ ์๋ก์ด ํ์์ด ๊ฐ๋ฅํ ์ ํ ํฌ์ธํธ(choice point)๋ก backtrackํ์ฌ ์๋ก์ด ํ์์ ์๋ํฉ๋๋ค. ๋ ์ด์์ ์ ํ ํฌ์ธํธ๊ฐ ์กด์ฌํ์ง ์์ผ๋ฉด, ํ์์ ์คํจ๋ก ๋๋ฉ๋๋ค. ๋์ถ์ ์ ๊ฐ๋ฆผ๊ธธ์ ํ์๋ฅผ ํด๋๊ณ ๋ง๋ค๋ฅธ ๊ณจ๋ชฉ์ ๋ค๋ค๋ฅด๋ฉด ๊ฐ๋ฆผ๊ธธ๊น์ง ๋๋์๊ฐ์ ๋ค๋ฅธ ๊ณจ๋ชฉ์ผ๋ก ๊ฐ๋ณด๋ ๋ฐฉ๋ฒ์ ๋๋ค. ๊น์ด ์ฐ์ ํ์๊ณผ ๊ด๋ จ ์์ต๋๋ค. ์์น ๋ฌธ์ (Coloring Problem)๋ ์ฃผ์ด์ง ๊ทธ๋ํ์์ ์ธ์ ํ ์ ์ ์ ๊ฐ์ ์์ ์น ํ ์..
ํํ๋ง ์๊ณ ๋ฆฌ์ฆ์ ํตํ ์ต์ ์ด์ง ๋ฌธ์ ์ฝ๋ ๊ตฌ์ถ ๊ณผ์ ๋ถ์ํ๊ธฐ (ํํ๋ง ์ฝ๋) ์๋ก ํํ๋ง ์ฝ๋(Huffman Code)๋ ๋ฌธ์๋ค๋ก ์ด๋ฃจ์ด์ง ๋ฐ์ดํฐ ํ์ผ ํฌ๊ธฐ๋ฅผ ์๊ฒ ๋ง๋ค๊ธฐ ์ํด ๋ฌธ์ ๊ฐ๊ฐ์ ์ฝ๋ํ ํ๋ ๋ฐฉ๋ฒ ์ค ํ๋์ ๋๋ค. ๋ ์์ฃผ ์ถํํ๋ ๋ฌธ์์ ๋ํ์ฌ ๋ ์งง์ ์ฝ๋๋ฅผ ํ ๋นํฉ๋๋ค. ์ต์ ์ด์ง ์ฝ๋ฉ ๋ฌธ์ (Optimal Binary Code)๋ ์ฃผ์ด์ง ํ ์คํธ ํ์ผ์ ์๋ ๋ฌธ์๋ค์ ์ด์ง ์ฝ๋๋ก ํํํ๊ธฐ ์ํด ํ์ํ ๋นํธ์ ๊ฐ์๊ฐ ์ต์๊ฐ ๋๋ ์ด์ง ๋ฌธ์ ์ฝ๋๋ฅผ ์ฐพ๋ ๋ฌธ์ ์ ๋๋ค. ์ฆ, ํํ๋ง ์ฝ๋ฉ ๋ฌธ์ ๋ ์ฃผ์ด์ง ๋ฌธ์ ์งํฉ์ ๋ํด ์ต์ ์ฝ๋์ ํด๋นํ๋ ์ด์ง ํธ๋ฆฌ๋ฅผ ๊ตฌ์ถํ์ฌ ์ต์ ์ด์ง ๋ฌธ์ ์ฝ๋(Huffman code)๋ฅผ ๋ง๋ค์ด ๋ณด๋ ๋ฌธ์ ์ ๋๋ค. ๋ณธ๋ก ํํ๋ง ์ฝ๋ฉ ๋ฌธ์ ์๊ณ ๋ฆฌ์ฆ 1) Priority Queue ..
[ํ์ด์ฌ/Python] ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ ์๋์๋ฆฌ ์ดํดํ๊ธฐ ( Floyd-washall ) ์๋ก [ํ์ด์ฌ/Python] ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ ๊ตฌํํ๊ธฐ ( Dijkstra / Bellman-ford / floyd-warshall ) ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ ๊ตฌํํ๊ธฐ ( Dijkstra / Bellman-ford / floyd-warshall ) ์๋ก ์ต๋จ ๊ฒฝ๋ก(Shortest Paths)๋ ๋ ์ ์ ์ฌ์ด์ ๊ฒฝ๋ก๋ฅผ ๊ตฌ์ฑํ๋ ๋ชจ๋ ๊ฐ์ ์ ๊ฐ์ค์น ํฉ์ด ์ต์์ธ ๊ฒฝ๋ก๋ฅผ ๋งํฉ๋๋ค. ์ต๋จ ๊ฒฝ.. develop247.tistory.com ์ด์ ์๊ฐ ๊ตฌํํ์๋ Floyd-washall ์๊ณ ๋ฆฌ์ฆ์ ์๋์๋ฆฌ์ ๋ํด ๊ฐ๋จํ ์์ ๋ฅผ ํตํด ๊ทธ๋ฆผ์ผ๋ก ์ดํดํด๋ณด๋ ค๊ณ ํฉ๋๋ค. ๋ณธ๋ก ๋ฌธ์ 1. Floyd-washall ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํ์ฌ ์ ๊ทธ..
[ํ์ด์ฌ/Python] ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ ์๋์๋ฆฌ ์ดํดํ๊ธฐ ( Dijkstra ) ์๋ก [ํ์ด์ฌ/Python] ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ ๊ตฌํํ๊ธฐ ( Dijkstra / Bellman-ford / floyd-warshall ) ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ ๊ตฌํํ๊ธฐ ( Dijkstra / Bellman-ford / floyd-warshall ) ์๋ก ์ต๋จ ๊ฒฝ๋ก(Shortest Paths)๋ ๋ ์ ์ ์ฌ์ด์ ๊ฒฝ๋ก๋ฅผ ๊ตฌ์ฑํ๋ ๋ชจ๋ ๊ฐ์ ์ ๊ฐ์ค์น ํฉ์ด ์ต์์ธ ๊ฒฝ๋ก๋ฅผ ๋งํฉ๋๋ค. ์ต๋จ ๊ฒฝ.. develop247.tistory.com ์ด์ ์๊ฐ ๊ตฌํํ์๋ Dijkstra ์๊ณ ๋ฆฌ์ฆ์ ์๋์๋ฆฌ์ ๋ํด ๊ฐ๋จํ ์์ ๋ฅผ ํตํด ๊ทธ๋ฆผ์ผ๋ก ์ดํดํด๋ณด๋ ค๊ณ ํฉ๋๋ค. ๋ณธ๋ก ๋ฌธ์ 1. Dijkstra ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํ์ฌ ์ ๊ทธ๋ํ์ v4๋ฅผ ์์์ผ๋ก ํ๋..
์ต์ ๋น์ฉ ์ ์ฅ ํธ๋ฆฌ ์๊ณ ๋ฆฌ์ฆ ์๋์๋ฆฌ ์ดํดํ๊ธฐ ( Prim / Kruskal ) ์๋ก [ํ์ด์ฌ/Python] ์ต์ ๋น์ฉ ์ ์ฅ ํธ๋ฆฌ ์๊ณ ๋ฆฌ์ฆ ๊ตฌํํ๊ธฐ ( Prim / Kruskal ) ์ต์ ๋น์ฉ ์ ์ฅ ํธ๋ฆฌ ์๊ณ ๋ฆฌ์ฆ ๊ตฌํํ๊ธฐ ์๋ก ์ ์ฅ ํธ๋ฆฌ(Spanning tree)๋ ์ฐ๊ฒฐ๋ ๋น๋ฐฉํฅ์ฑ ๊ทธ๋ํ์์, ๋ ธ๋๋ ๊ทธ๋๋ก ์ ์งํ ์ฑ๋ก, ์ํ๊ฒฝ๋ก(cycle)๊ฐ ์์ด์ง๋๋ก ์ด์์ ์ ์ ๊ฑฐํ์ฌ ๊ตฌ์ฑํ ์ฐ๊ฒฐ๋ develop247.tistory.com ์ด์ ์๊ฐ ๊ตฌํํ์๋ Prim, Kruskal ์๊ณ ๋ฆฌ์ฆ์ ์๋์๋ฆฌ์ ๋ํด ๊ฐ๋จํ ์์ ๋ฅผ ํตํด ๊ทธ๋ฆผ์ผ๋ก ์ดํดํด๋ณด๋ ค๊ณ ํฉ๋๋ค. ๋ณธ๋ก ๋ฌธ์ 1. Prim ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํ์ฌ ์ ๊ทธ๋ํ์ ์ต์๋น์ฉ ์ ์ฅ ํธ๋ฆฌ๋ฅผ ๊ตฌํ๋ ๊ณผ์ ์ ์ ์ํ์์ค. ์ฒ์ start_node = 1์ด๋ฏ๋ก, d[1] =..
๋์ ํ๋ก๊ทธ๋๋ฐ - ํ๋ ฌ ๊ณฑ์ ์์ ๊ณ์ฐํ๊ธฐ ( Brute-Force Algorithm ) ์๋ก ๋์ ํ๋ก๊ทธ๋๋ฐ(Dynamic Programming)์ ์ต์ ๋ถ๋ถ ๊ตฌ์กฐ(Optimal Substructure)๋ฅผ ๊ฐ์ง๊ณ ์๊ณ , ์ฌ๊ท ํธ์ถ ์ ๋นํจ์จ์ ์ธ ์ค๋ณต์ด ๋ฐ์ํ๋ ๊ฒฝ์ฐ(Overlapping Recursive Calls) ์ฌ์ฉํ๋ฉด ํจ๊ณผ์ ์ด๋ค. ์ต์ ๋ถ๋ถ ๊ตฌ์กฐ(Optimal Substructure)๋ ํฐ ๋ฌธ์ ์ ์ต์ ์๋ฃจ์ ์ ์์ ๋ฌธ์ ์ ์ต์ ์๋ฃจ์ ์ด ํฌํจ๋๋ ๊ฒ์ ๋งํ๋ค. ๋์ ํ๋ก๊ทธ๋๋ฐ์ ์ ์ฉํ๊ธฐ ์ํด ํญ์ ์ต์ ๋ถ๋ถ ๊ตฌ์กฐ๋ฅผ ๊ฐ๊ณ ์๋์ง ๋จผ์ ํ์ธํด์ผ ํ๋ค. ๊ทธ๋ ๋ค๋ฉด, ๋ํ์ ์ธ ๋์ ํ๋ก๊ทธ๋๋ฐ ๋ฌธ์ ๋ก ํ๋ ฌ ๊ณฑ์ ์์์ ๋ํด ๋์ ํ๋ก๊ทธ๋๋ฐ์ ์ ์ฉํด๋ณด์. ๋ณธ๋ก i × j ํ๋ ฌ๊ณผ j × ํ๋ ฌ์ ๊ณฑํ๊ธฐ ์ํด์..