์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
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 |
- BFS
- TCA
- SnapKit
- XCTest
- swift
- combine
- CollectionView
- Lv2
- ๋ฐฑ์ค
- arkit
- rxcocoa
- SwiftUI
- Xcode
- UIKit
- RxSwift
- ios
- reactorkit
- Kuring
- MVVM
- visionOS
- ํจ์คํธ์บ ํผ์ค
- Swfit
- realm
- designpattern
- BOJ
- Flutter
- ํ๋ก๊ทธ๋๋จธ์ค
- tableView
- node.js
- raywenderlich
- Today
- Total
๋ชฉ๋ก์ฝ๋ฉํ ์คํธ/๐๏ธ ์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ (6)
lgvv98
ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ๊ณผ ์์์ ๋ ฌ ๋ฐฑ์ค ์๊ณ ๋ฆฌ์ฆ: ์ต์ ์คํจ๋ ํธ๋ฆฌ์์ ์ฐ์ตํ ์ ์์ต๋๋ค. โ ์๋ก์ ์งํฉ 6๊ฐ์ ๋ ธ๋๊ฐ ์ฃผ์ด์ง๋๋ฐ ๊ฐ ์ฐ๊ฒฐ ๊ด๊ณ๋ 6 4 1 4 2 3 2 4 5 6 ์ผ๋ก ์ฃผ์ด์ง๋๋ค. ์ฌ๊ธฐ์ ๊ฐ ๋ ธ๋๋ฅผ ๋น๊ตํ๊ณ , ๋ ธ๋ ๋ฒํธ์ ๋ถ๋ชจ๋ฅผ ์ ๋ฐ์ดํธ ํ๋ฉด์ ๊ฒฐ๊ตญ์ ์ฌ์ดํด์ด ํ์ฑ๋๋์ง ์ฐพ์ ์ ์์ต๋๋ค. ํ์ง๋ง ์ด ๊ฒฝ์ฐ ์๊ฐ ๋ณต์ก๋์ ํฐ ์ํด๊ฐ ๋ฐ์ํ๋๋ฐ, ์ด๋ฅผ ๋จ์ถ์ํค๊ณ ์ ๊ฒฝ๋ก ์์ถ ๊ธฐ๋ฒ์ ์ฌ์ฉํ๊ณค ํฉ๋๋ค. * ๊ฒฝ๋ก ์์ถ ๊ธฐ๋ฒ์ด๋? - find ํจ์๋ฅผ ์ฌ๊ท์ ์ผ๋ก ํธ์ถํ์ฌ ๋ถ๋ชจ ํ ์ด๋ธ ๊ฐ์ ๊ฐฑ์ ํ๋ ๋ฐฉ๋ฒ์ ๋๋ค. ์ค๋ ์ฃผ๋ก ์์ ๋ณผ ๋ด์ฉ์ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ด๋ฏ๋ก ์๋ก์ ์งํฉ์ ๋ํ ๋ด์ฉ์ ์๋ ํฌ์คํ ์ ์ฐธ๊ณ ํด์ฃผ์ธ์! https://velog.io/@syc1013/%EC%95%8C%EA%B3%A0%EB%..
ํ๋ก์ด๋ ์์ ์๊ณ ๋ฆฌ์ฆ โ ํ๋ก์ด๋ ์์ ์๊ณ ๋ฆฌ์ฆ ์ด๋ฒ ์๊ณ ๋ฆฌ์ฆ ์ฝ๋๋ ๋๋๋น ์ฑ ์ ๊ธฐ๋ฐ์ผ๋ก ๊ณต๋ถํ๊ณ , swift๋ก ์ ์ดํด๋ฅผ ๋ฐํ์ผ๋ก ์ง์ ์ฝ๋๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฐ๋ผ์ ์ฑ๋ฅ ๋ฐ ์ฝ๋ ๊ฒ์ฆ์ด ์๋ฒฝํ์ง ์์์ ์ค๋ฅ๊ฐ ์์ ์๋ ์์ต๋๋ค. ์ค๋ฅ๊ฐ ์๋ค๋ฉด ๋๊ธ๋ก ์ ๋ณดํด์ฃผ์ธ์! ๋ค์ต์คํธ๋ผ : ํ ์ง์ ์์ ๋ค๋ฅธ ํน์ ์ง์ ๊น์ง - ๊ทธ๋ฆฌ๋์ ์ํจ ํ๋ก์ด๋ ์์ : ๋ชจ๋ ์ง์ ์์ ๋ค๋ฅธ ๋ชจ๋ ์ง์ ๊น์ง - dp์ ์ํจ ์๊ฐ๋ณต์ก๋๋ O(N^3)์ด๋ค. โ ์ฝ๋ import Foundation /// ์ ์ ๊ฐ์ ์ฐ๊ฒฐ๊ด๊ณ, ๊ฐ์ค๊ฐ, ์ ์ ์ ๊ฐ์ func FloydWarshall(graph: [[Int]], weight: [Int], n: Int) -> [[Int]] { var node = [[Int]](repeating: [In..
Dijkstra ์๊ณ ๋ฆฌ์ฆ โ Dijkstra ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํด๋ณด์. ์ด๋ฒ ํฌ์คํ ์์๋ ์ค์ํํธ ๋ฐ์ดํฐ ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ ์ฑ ๊ณผ ๋๋๋น ํ์ด์ฌ ์๊ณ ๋ฆฌ์ฆ ์ฑ ๊ทธ๋ฆฌ๊ณ ๋ค๋ฅธ ๋ถ์ ํฌ์คํ ์ ์ฐธ๊ณ ํ์ฌ ์์ฑํ์์. ์ด๊ฑฐ ์์ ์ ์์ ํ๋๋ ์ฐธ ์ดํด๋ ์ฝ๊ณ ๊ทธ๋ฌ๋๋ฐ, ์๊ณ ๋ฆฌ์ฆ ๊ณต๋ถ ๋๊ณ ๋ค์ ์์ํ๋ ค๋๊น ์ด๋ ค์ ์. ๊ทผ๋ฐ ๊ทธ๋ฅ ์๋นํ ์ง์ค์ด ์๋๋ ์๊ธฐ์ธ ๊ฒ ๊ฐ๋ค. ์๋์ ๊ทธ๋ํ๋ฅผ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์์ผ๋ก ๋ถ์ํด๋ณด์. ๋๋๋น ์ฑ ์ ๋ฐ๋ฅด๋ฉด ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ๊ณผ ํ๋ก์ด๋ ์์ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐํด์ฃผ๋๋ฐ ๋์ ์ฐจ์ด๋ฅผ ๋ถ์ํด๋ณด์. ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ : ํ ์ง์ ์์ ๊ฐ๊ฐ์ ํน์ ์ง์ ๊น์ง์ ์ต๋จ ๊ฒฝ๋ก - ๊ทธ๋ฆฌ๋์ ์ํจ ํ๋ก์ด๋ ์์ ์๊ณ ๋ฆฌ์ฆ : ๋ชจ๋ ์ง์ ์์ ๋ค๋ฅธ ๋ชจ๋ ์ง์ ๊น์ง์ ์ต๋จ ๊ฒฝ๋ก - dp์ ์ํจ ๊ฐ์ ์ ๊ฐ์ : E ๋ ธ๋์..
chapter 5. DFS/BFS โ DFS/BFS์ ๋ํด์ ์์๋ณด์! DFS/BFS๋ ์ธ๊ณต์ง๋ฅ ์์ ์๊ฐ์ ๊ณต๋ถํ์ด์ ๊ทธ ๊ฐ๋ ์ ์๊ณ ์์์ง๋ง, ์ฝ๋๋ก ์์ฑํด ๋ณธ ๊ฒฝํ์ ์์ ์ ๊ธํ๊ฒ ๋ฌธ์ ๋ฅผ ํ ๋๋ฅผ ์ ์ธํ๊ณค ์์๋ค. ์๊ณ ๋ฆฌ์ฆ์ ํ๋ฉด์ DFS/BFS๋ ์.. ๋ญ๋๊น, ์ฌ๊ท๋ ์์ ํ์ ๋ฑ ๋ค๋ฅธ ๋ฐฉ๋ฒ์ผ๋ก๋ ํ๋ฆฌ๋ ๋ฌธ์ ๋ค๋ ์์๋๋ฐ ๊ฐ๋์ DFS/BFS๊ฐ ์๋๋ฉด ํ ์ ์๊ฒ ๋ ๋ฌธ์ (์๋๋ฉด ๋งค์ฐ ๋ณต์กํ)๊ฐ ๋ง๋๋ผ. ๊ทธ๋์ ๊ณต๋ถํด๋ด โ DFS DFS๋ ๊น์ด ์ฐ์ ํ์ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์ด ์๊ณ ๋ฆฌ์ฆ์ ํน์ ํ ๊ฒฝ๋ก๋ก ํ์ํ๋ค๊ฐ ํน์ ์ํฉ์์๋ ์ต๋ํ ๊น์์ด ๋ค์ด๊ฐ์ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ ํ, ๋ค์ ๋์๊ฐ์ ๋ค๋ฅธ ๊ฒฝ๋ก๋ก ํ์ํ๋ ๊ฒฝ๋ก๋ก ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. import Foundation func DFS (graph: [T: ..
chapter 8. DP โ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ(DP)์ ๋ํด์ ์์๋ณด์! DP๋ ํ๊ต ์์ ์๊ฐ์ ํผ๋ณด๋์น๋ฅผ ๊ณต๋ถํ๋ฉด์ ๊ณ์ฐํ ๋ถ๋ถ์ ๊ณ์ฐํ์ง ์๋ ๊ฒ์ผ๋ก ๋ฐฐ์ ๋๋ฐ, ๊ทธ ๋น์์๋ ๊ทธ๊ฒ DP์ธ์ง ๋ชฐ๋์ ์๊ณ ๋ฆฌ์ฆ์ ํ๋ฉด์ DP์ ๊ฐ์ ๋ฌธ์ ๋ค์ ์ ๋ชปํธ๋๋ฐ, ์ด๋ฒ์ ๊ณต๋ถํด ๋ณด๋๊น ๊ทธ ์ฌ๊ณ ๋ฅผ ์ป์ด์ ์กฐ๊ธ ์์ ๊ฐ๋ ์๊น ์๋ฅ๋๋ ์ ํ์ ๋ฌธ์ ์ ์ ๋ ๋๋ฌด๋๋ ์ฝํ๋๋ฐ, DP๋ ์ ํ์์ด ๊ฑฐ์ ๋ฒ ์ด์ค๋ค..? ์๋ฌดํผ ์ด์ฌํ ํด๋ณด์. โ 1๋ก ๋ง๋ค๊ธฐ ์ ํ์์ ์ด์ฉํ๋๋ฐ, ํน์ ํ ์์ ๊ฐ์ ์ ํด์ ์ง์ ๊ทธ๋ฌ๋ณด๋ฉด ๋ฌธ์ ๋ฅผ ๋ง๋๋๋ฐ ๋์์ด ๋ง์ด ๋๋ค. ๋ํ, ๋ณดํ ์ ๋ฐฉ์์ผ๋ก ๊ณ์ฐํ๋๊ฒ ์กฐ๊ธ ๋ ์ด๋์ด ์๋ค๊ณ ํ๊ณ , ์์ฒญ ์ด๋ ต์ง๋ ์์ผ๋๊น ํ๋ฒ ํด๋ณด์. ๋น์ทํ ๋ฌธ์ ๋ฅผ ๋ฐฑ์ค์์ ์ฐพ์ ํ์ด๋ณด์. ๐ ๋ฐฑ์ค๋ฌธ์ ์๊ณ ๋ฆฌ์ฆ์ ์ ํ์์ ๋ง๋ค์ด..
โ ์ด๋ฒ ์๊ฐ์๋ ๋๋์ด ์ฝ๋ฉ ํ ์คํธ๋ฅผ ์ ๋๋ก ์ค๋นํ๊ธฐ ์ํด์ Swift ์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ ์ฑ ์ ๊ตฌ์ ํ๊ณ ๊ณต๋ถํ ๊ฒ์ ๋ํด์ ๊ธฐ๋กํด ๋ณด๋ ค๊ณ ํด. ์ฐ์ ๋ด๊ฐ C์ธ์ด(C++ ์๋;;) ๋ก ์ฝ๋ฉ ํ ์คํธ๋ฅผ ์ค๋นํ๊ธฐ ๋๋ฌธ์, ์๊ฐ ๋ด์ ๋นจ๋ฆฌ ํ๊ธฐ๊ฐ ๋๋ฌด๋๋ ํ๋ค์์. ๊ทธ๋์ ๋ด๊ฐ python์ผ๋ก ์ค๋น ํ์์ผ๋, ํ ์ค ์ฝ๋ฉ ํ ์คํธ๋ฅผ ๋ณด๋๋ฐ Swift๋ก ์ ํํด ๋ ๊ฒ์ ๋ณด๊ณ ์์ ๋ค์ ๋ง์ ์ก๊ณ ๊ณต๋ถํด๋ณด๊ธฐ๋ก ํจ. ๊ทผ๋ฐ ๋จ์ ์ Swift๋ก ํ์ด๋, ๋ฐํ ๋ฐฉ๋ฒ, ๋ฐฐ์ด์ index ์ฐธ์กฐ ๋ฒ, String์ ๋ค๋ฃจ๋ ๋ฒ ๋ฑ Swift๋ฅผ ๋ค๋ฃจ๊ธฐ๊ฐ ์ด๋ ค์ ์ด. ๋ํ Dictionary๋ฅผ Python์์๋ ์๋นํ ํ๋ค์ด ํ์๋๋ฐ, Swift๋ก๋ ์ฌ์ ํ ํ๋ค์ด์, ์์ ํ๋ํ๋ ์ ๋ ํ๊ธฐ ์ํด์ ์ฑ ์ ๊ตฌ์ ํ๋ค. โ ๊ณต๋ถ ๊ณํ ์ฑํฐ๋ฅผ ..