https://www.acmicpc.net/problem/18352 18352๋ฒ: ํน์ ๊ฑฐ๋ฆฌ์ ๋์ ์ฐพ๊ธฐ ์ฒซ์งธ ์ค์ ๋์์ ๊ฐ์ N, ๋๋ก์ ๊ฐ์ M, ๊ฑฐ๋ฆฌ ์ ๋ณด K, ์ถ๋ฐ ๋์์ ๋ฒํธ X๊ฐ ์ฃผ์ด์ง๋ค. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) ๋์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์ ๊ฑธ์ณ์ ๋ ๊ฐ www.acmicpc.net ๊ทธ๋ํ, ๋ค์ต์คํธ๋ผ ์ฐ์ต์ ํ๋ ค๊ณ ์๋ํ๋ ๋ฌธ์ ์ด๋ค. ๊ธฐ์กด์ ๊ทธ๋ํ๋ฅผ ์ํํ ๋ ์๋์ฒ๋ผ ๋ง์ด ์ฌ์ฉํ์๋๋ฐ, ์๊ฐ์ด๊ณผ๊ฐ ๋์ idx๋ก ํ์ ์ ๊ทผํ๋ ๋ฐฉ๋ฒ์ผ๋ก ์์ ํ๋ค. while let q = queue.isEmpty() ? nil : queue.removeFirst() X๋ถํฐ ํ(์ผ๋ฐ ๋ฐฐ์ด)์ ๋ฃ์ (๊ฑฐ๋ฆฌ๋ฐฐ์ดdist๋ ma..
๐ Algorithm
์ฒ์์ ์๊ฐํ๋ ํ์ด 1. ๋์
๋๋ฆฌ ์์ฑ = "์์์ ์ข
๋ฅ":["์์์ด๋ฆ"] 2. ๋ฒ์ (1...์์์ ์ข
๋ฅ ์) dp ํ
์ด๋ธ ๋ง๋ค๊ธฐ 3. dp ํ
์ด๋ธ ๊ฒฐ๊ณผ ๋ฐํ ์ด ์์๋๋ก ๊ทธ๋ฆผ์ ๊ทธ๋ฆฌ๊ณ ๊ท์น์ ์ฐพ์ dp ํ
์ด๋ธ์ ๋ง๋ค์ด ํด๊ฒฐํ๋ ค ํ์๋ค.. ๊ท์น์ ์ฐพ๊ณ ์ถ์๋๋ฐ, ๊ฐ๋ง ์ค๊ณ .. ์๊ฐํ๋ ๋๋ก ํด๊ฒฐ๋์ง ์์์ "ํ๋ก๊ทธ๋๋จธ์ค์ ์ง๋ฌธํ๊ธฐ"๋ฅผ ํ์ธํด๋ดค๋๋ฐ ๋ช
์พํ ์ํ์ ํ์ด๊ฐ ์์ด์ ๊ธฐ๋กํด๋๊ณ ์ ํ๋ค. ๊ณ ๋ฑํ์ ๋ ์ด ๋ฌธ์ ๋ฅผ ๋ดค์ผ๋ฉด ์ข ๋ ๋น ๋ฅด๊ฒ ํด๊ฒฐ๋ฐฉ์์ ์์๋์ ๋ฏ ํ๋ค,,ใ
.ใ
ํด๊ฒฐ ๋ฐฉ์ ์์์ ์ข
๋ฅ 1๊ฐ์ง ์์์ผ ๊ฒฝ์ฐ ๋ฐํ๊ฐ = ์์ ๊ฐ์ (์๋๋ถํด ํธ์์ "๊ฐ์" ์๋ต) ์์์ ์ข
๋ฅ 2๊ฐ์ง ์์, ํ์์ผ ๊ฒฝ์ฐ ๋ฐํ๊ฐ = ์์ + ํ์ + ์์ * ํ์ ์์์ ์ข
๋ฅ 3๊ฐ์ง ์์, ํ์, ์ ๋ฐ์ผ ๊ฒฝ์ฐ ๋ฐ..
์๊ณ ๋ฆฌ์ฆ ์คํฐ๋ํ๋ฉด์ ์ฌ๊ท์ ๋ํด ์ ์ดํดํ๊ณ ์ฐ์ง ๋ชปํ๋ ๊ฒฝํ์ด ์๋ค. ํผ๋ณด๋์น๋ ํฉํ ๋ฆฌ์ผ ๋ฌธ์ ์ ๋๋ ๊ด์ฐฎ์๋ฐ, ์ดํด๋๊ฐ ์กฐ๊ธ ๋ถ์กฑํ์ด์ ๊ทธ ์ด์์ ์ฒดํ๋์ง ์์, ์ฝ๊ฒ ์ฌ๊ท๋ฅผ ๋ ์ฌ๋ ค ์ฌ์ฉํ์ง ๋ชปํ์๋ค. ์ด๋ฒ์ ์ฝํ
๋ฅผ ์ค๋นํ๋ฉด์, ์ฌ๋ฌ ๋ฌธ์ ๋ฅผ ํ๊ธฐ๋ณด๋จ ๋ถ์กฑํ๋ ๊ธฐ๋ณธ ๊ฐ๋
์ ๋ํด ๋ค์ ์ดํดํ๊ณ ๋์ด๊ฐ๋ณด์!๋ผ๋ ๋ง์์ผ๋ก ์์ด๊ณผ ์กฐํฉ์ ๋ค์ฌ๋ค๋ณด์๊ณ , ์์ด๊ณผ ์กฐํฉ์ ์์๊ฐ๋ฉด์ ์ฌ๊ท์ ๋ํด์๋ ์์ฐ์ค๋ ์ฒดํํ ์ ์์๋ค-!!! ์์ด (permutation) ์์ด์ด๋ ์๋ก ๋ค๋ฅธ n๊ฐ์ ์์์์ r๊ฐ๋ฅผ ์ค๋ณต ์์ด ์์๋ฅผ ๊ณ ๋ คํ์ฌ ์ ํํ๊ฑฐ๋ ๋์ดํ๋ ๊ฒ์ ์๋ฏธํฉ๋๋ค.(๋จ, 0 ์กฐํฉ func ์กฐํฉ(_ depth: Int, _ start: Int) { if ๋์ค๊ฐ M๊น์ง ๋๋ฌํ๋ค๋ฉด { ๊ฒฐ๊ณผ๋ฐฐ์ด ์ถ๋ ฅ } else { ์ธ..
BFS(๋๋น์ฐ์ ํ์) 1. removeFirst() ์ฌ์ฉ func bfs(graph: [[Int]], startX: Int, startY: Int) -> [Int] { var visited = Array(repeating: Array(repeating: false, count: n), count: n) var queue = [(startX, startY)] var result = [Int]() visited[startX][startY] = true while let node = queue.isEmpty ? nil : queue.removeFirst() { let x = node.0 let y = node.1 result.append(graph[x][y]) let dx = [0, 0, 1, -1] let ..
import Foundation func checkLowerCase(_ input: String) -> Bool { let lowercaseSet = CharacterSet.lowercaseLetters return input.rangeOfCharacter(from: lowercaseSet.inverted) == nil } let st = ["ss", "s1", "11", "SS", "d-"] for s in st { if checkLowerCase(s) { print(s) } } // ss https://developer.apple.com/documentation/foundation/characterset
https://www.acmicpc.net/problem/11659 11659๋ฒ: ๊ตฌ๊ฐ ํฉ ๊ตฌํ๊ธฐ 4 ์ฒซ์งธ ์ค์ ์์ ๊ฐ์ N๊ณผ ํฉ์ ๊ตฌํด์ผ ํ๋ ํ์ M์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ N๊ฐ์ ์๊ฐ ์ฃผ์ด์ง๋ค. ์๋ 1,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ์
์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์๋ ํฉ์ ๊ตฌํด์ผ ํ๋ ๊ตฌ๊ฐ i์ j www.acmicpc.net ํด๋น ๋ฌธ์ ๋ฅผ ํ๋ฉด์ ๋์ ํฉ์ ์ฒ์ ์ ํ๋ค. ๋ฌธ์ ๋ฅผ ๋ณด๊ณ ๊ฐ์ ๊ณ์ฐํด์ ์ ์ฅํด์ ๊บผ๋ด์ ์ฌ์ฉํ๋ฉด ๋ ๊ฒ ๊ฐ๋ค๋ ์๊ฐ์ ๋ค์๋๋ฐ, ์ ํํ ํด๊ฒฐ๋ฐฉ๋ฒ์ด ๋์ ํฉ!์ธ์ง๋ ๋ชฐ๋๋ค..! ๋์ ํฉ์ ๋ํด ์์๋ณด์! ๋์ ํฉ ํน์ ๊ตฌ๊ฐ์ ํฉ์ ์ฐพ๋๋ฐ ์ ์ฉํ ์๊ณ ๋ฆฌ์ฆ ๋์ ํฉ ์๊ณ ๋ฆฌ์ฆ์ ์ฐ์๋ ์์๋ค์ ํฉ์ ๋น ๋ฅด๊ฒ ๊ณ์ฐํ๋ ์๊ณ ๋ฆฌ์ฆ์
๋๋ค. ๋ฐฐ์ด๊ณผ ๊ฐ์ ์ํ์ค ๋ฐ์ดํฐ์์ ์ผ๋ถ ๊ตฌ๊ฐ์ ํฉ์ ์ฐพ๋ ๋ฐ ์ฌ..