Programming/Algorithm
BOJ: #14889 - ์คํํธ์ ๋งํฌ
BOJ: #14889 - ์คํํธ์ ๋งํฌ
2021.06.18์ ํํ ํ ์๊ฐ ๊ฑธ๋ ค์ ํ์๋ค. ์ ๋ต ์ฝ๋ ํ๋จ์ ์๊ฐ ์ด๊ณผ, ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ ์ฝ๋๋ ๊ฐ์ด ์ฒจ๋ถํ๋ค. ์ผ๋จ, ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ๊ฐ ๋ฌ์ ๋๋ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ 2์ฐจ์ ๋ฐฐ์ด๋ก ์ ์ฅํด์ ์๊ธฐ๋ ๋ฌธ์ ์๋ค. ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ๊ฐ ๋ ํ์, ๊ตณ์ด ์ ์ฅํ ํ์๊ฐ ์๋ค๋ ๊ฑธ ๊นจ๋ฌ์์ ์ ์ฅํ์ง ์๊ณ , ๋ฐ๋ก ์ ์ ๊ณ์ฐํ๋ ์์ผ๋ก ๋ณ๊ฒฝํ๋ค. ๊ทธ๋ฆฌ๊ณ ์ด๋ ๊ฒ ๋ณ๊ฒฝํ๋ฉด์, ์ง๋ฌธ ๊ฒ์ํ์ ๋ณด๋ ์ ์ฒด ํ์ ์งํฉ์ผ๋ก ๋ง๋ค์ด ๋๊ณ , n / 2์ ์กฐํฉ์ ๊ตฌํ ํ์, ์ฐจ์งํฉ์ ๊ตฌํ๋ ์์ผ๋ก ๋งํฌ ํ์ ๊ตฌํ๋ผ๋ ์ด์ผ๊ธฐ๊ฐ ์์ด์ ๊ทธ๊ฒ๋ ๋ฐ์ํ๋ค. ์ฌ๊ธฐ๊น์ง๊ฐ ์๊ฐ ์ด๊ณผ ๋ ์ฝ๋์๋ค. ๋๋ฌด์ง ํด๊ฒฐ์ฑ
์ ๋ชจ๋ฅด๊ฒ ์ด์, PyPy3๋ก๋ ์คํํด๋ดค๋๋ฐ ์ญ์๋ ์๊ฐ์ด๊ณผ์๋ค. ๋ค๋ฅธ ๊ธ์ ์ฐพ์๋ณด๋ ๋๊ฒ, ์๊ฐ ์ด๊ณผ ๋ ์ฝ๋๋ค์ ์กฐํฉ ๊ตฌํ๋ ํจ์๊ฐ ๋นํจ์จ์ ์ด๋ผ๋ ๋ต๋ณ์ ๋ดค๋ค. ๊ทธ๋..
LeetCode: Generate Parentheses
LeetCode: Generate Parentheses
2021.06.17๋ฐฑํธ๋ํน + ์คํ๊ดํธ๋ฅผ ์กฐํฉํ ๋ฌธ์ ์๋ค. ๋ ๊ฐ์ง ๋ฉ์๋๋ฅผ ๋ง๋ค์ด์ ์ฒ๋ฆฌํ๋ค. n๊ฐ์ ๋ชจ๋ ๊ดํธ ์กฐํฉ์ ๋ง๋๋ pick(toPick:) ๋ฌธ์์ด ๋ฐฐ์ด์ด ์ฌ๋ฐ๋ฅธ ๊ดํธ ์กฐํฉ์ธ์ง ํ๋ณํ๋ isWell(_:) ์ค๋ณต์ด ์์๊น๋ด Set์ผ๋ก ์ ์ฅํด์, ์ ๋ ฌํด์ ๋ฐํํ๋ ๊ฑธ๋ก ํด๊ฒฐ. ๋ฌธ์ https://leetcode.com/problems/generate-parentheses ๋ด๊ฐ ์์ฑํ ์ฝ๋ Swift class Solution { func generateParenthesis(_ n: Int) -> [String] { let bracket = ["(", ")"] var result = [[String]]() var picked = [String]() func pick(toPick: Int) { if toPick ==..
BOJ: #15663 - N๊ณผ M (9)
BOJ: #15663 - N๊ณผ M (9)
2021.05.18๊ฐ์ ์๋ฅผ ๋ฐ๋ณตํด์ ๋ฐฉ๋ฌธํ์ง ์๊ธฐ ์ํด visited๋ก ์ฒดํฌ ์ค๋ณต ์์ด์ ๊ฑฐ๋ฅด๊ธฐ ์ํด Set ํ์
์ผ๋ก ์ ์ฅ ์ค์: String ๋ฐฐ์ด ์ ๋ ฌ์ ์๊ฐ ์ฆ๊ฐํ๋ ์์๊ฐ ์๋! ๋ฐ๋ผ์ ์๊ฐ ์ฆ๊ฐํ๋ ์์๋ก ์ ๋ ฌํ ์ ์๊ฒ ๋ณ๋์ ์ฒ๋ฆฌ๊ฐ ํ์ํจ let sortedResult = result.sorted(by: { $0.localizedStandardCompare($1) == .orderedAscending}) ๋ฌธ์ https://www.acmicpc.net/problem/15663 ๋ด๊ฐ ์์ฑํ ์ฝ๋ Swift import Foundation var fileio = FileIO() let n = fileio.readInt() let m = fileio.readInt() var nums = [Int]() for _ i..
BOJ: #3048 - ๊ฐ๋ฏธ
BOJ: #3048 - ๊ฐ๋ฏธ
2021.05.16๋ ๊ทธ๋ฃน์ ๋ํ ๋, ํํ์ ์ด์ฉํด์ ๋ฐฉํฅ์ ๊ฐ์ด ์ ์ฅํ๋ค. false๋ ์ผ์ชฝ์์ ์ค๋ฅธ์ชฝ, true๋ ์ค๋ฅธ์ชฝ์์ ์ผ์ชฝ์ผ๋ก ์ด๋ํ๋ ๊ฐ๋ฏธ๋ฅผ ๋ปํ๋ค. ์ฒ์์ ์ด์ค for๋ฌธ์ ์ด์ฉํ๋๋ฐ, ๊ฐ๋ฏธ๋ค์ ์ค์ํ๋ ๊ฒฝ์ฐ i๋ฅผ ํ ๋ฒ ๋ ๊ฑด๋๋ฐ์ด์ผ ํด์ while๋ฌธ์ผ๋ก ๋ณ๊ฒฝํ๋ค. ๊ทธ๋ฆฌ๊ณ ์๋ก ๋ฐฉํฅ์ด ๋ค๋ฅธ ๊ฒฝ์ฐ์ ์ ๋ถ ์ค์ํด์คฌ์๋๋ฐ, 7% ์ฏค์์ ํ๋ ค์ ๋ค๋ฅธ ํ์ด๋ฅผ ์ฐพ์๋ดค๋ค. ์ผ์ชฝ์ผ๋ก ์ด๋ํ๊ณ ์๋ ๊ฐ๋ฏธ๋ ๋ง๋ ๊ฒฝ์ฐ์๋ ๋ฐ๊ฟ์ค ํ์๊ฐ ์๋ค๋ ๊ฑฐ์๋ค. (←, →) ์๋ก ๋ง๋์ง ์์ผ๋๊น! ๊ทธ๋์ ์์ ์๋ ๊ฐ๋ฏธ๊ฐ ์ค๋ฅธ์ชฝ์ ๋ณด๊ณ ์์ ๋ ์กฐ๊ฑด๋ ์ถ๊ฐํ๋ค. ๋ฌธ์ https://www.acmicpc.net/problem/3048 ๋ด๊ฐ ์์ฑํ ์ฝ๋ Swift let n = readLine()!.split(separator: " ")..
BOJ: #1543 - ๋ฌธ์ ๊ฒ์
BOJ: #1543 - ๋ฌธ์ ๊ฒ์
2021.05.16๋ฌธ์์ด์ ์ธ๋ฑ์ค๋ก ์ ๊ทผํ๊ธฐ ์์ subscript๋ฅผ ์ต์คํ
์
์ผ๋ก ๊ตฌํํ๋ค. ํน์ ๋ฌธ์์ด์ ๋ฐฐ์ด๋ก ๋ณํํด์ ํ์ด๋ ๋๋ค. ๋๋ ๋ ๊ฐ์ ์ปค์(๋ฌธ์์ด ์ปค์, ํจํด ์ปค์)๋ฅผ ์ด์ฉํด ํ์๋ค. ๋ฌธ์ https://www.acmicpc.net/problem/1543 ๋ด๊ฐ ์์ฑํ ์ฝ๋ Swift extension String { subscript(offset: Int) -> String { get { let index = String.Index(utf16Offset: offset, in: self) return String(self[index]) } } } let str = readLine()! let pattern = readLine()! let n = str.count let m = pattern.count va..
Programmers: ๋คํธ์ํฌ
Programmers: ๋คํธ์ํฌ
2021.05.14๋ฌธ์ ๋
ํด๋ฅผ ์๋ชปํด์ ํท๊ฐ๋ ธ๋ ๋ฌธ์ . ์ฌํ bfs/dfs ๋ฌธ์ ๋ ๋น์ทํ๊ฒ ํธ๋๋ฐ, ๋ฐ๊นฅ์์ ๋ชจ๋ ์ปดํจํฐ๋ฅผ ์ํํ๋ฉด์ ํ ๋ฒ์ด๋ผ๋ ๋ฐฉ๋ฌธํ ๊ณณ์ visited ๋ณ์์ ๋ด์ ์ฒดํฌํ๋ค. ์ด๋ฏธ ๋ฐฉ๋ฌธํ ๊ณณ์ ์ปดํจํฐ๋ผ๋ฆฌ ์ฐ๊ฒฐ๋์๋ค๋ ๋ป์ด๋๊น ใ
ใ
๋ฌธ์ https://programmers.co.kr/learn/courses/30/lessons/43162 ๋ด๊ฐ ์์ฑํ ์ฝ๋ Swift import Foundation func solution(_ n:Int, _ computers:[[Int]]) -> Int { var graph = [Int: [Int]]() for i in 0..
LeetCode: Letter Combinations of a Phone Number
LeetCode: Letter Combinations of a Phone Number
2021.05.13์
๋ ฅ์ผ๋ก ๋ค์ด์จ digits์ letter์ ์ ๊ทผํ๊ธฐ ์ํ ์ธ๋ฑ์ค๋ก ๋ณํํ๋ค. ๊ทธ๋ฆฌ๊ณ ๋ฐฑํธ๋ํน์ผ๋ก ๋ฌธ์ ์กฐํฉ์ ๊ตฌํ๋ฉด ๋๋ค. ๋ค๋ฅธ ์กฐํฉ ๋ฌธ์ ์ ํฌ๊ฒ ๋ค๋ฅผ ๊ฒ ์์ ๋ฌธ์ https://leetcode.com/problems/letter-combinations-of-a-phone-number/ ๋ด๊ฐ ์์ฑํ ์ฝ๋ Swift class Solution { func letterCombinations(_ digits: String) -> [String] { let letter: [[Character]] = [ ["a", "b", "c"], ["d", "e", "f"], ["g", "h", "i"], ["j", "k", "l"], ["m", "n", "o"], ["p", "q", "r", "s"], ["t", "u"..
KMP ๋ฌธ์์ด ๊ฒ์ ์๊ณ ๋ฆฌ์ฆ
KMP ๋ฌธ์์ด ๊ฒ์ ์๊ณ ๋ฆฌ์ฆ
2021.05.09์ด ๊ธ์ ๋ณดํธ๋์ด ์๊ธฐ ๋๋ฌธ์ ์ด๊ฒ์ ๋ณด๋ ค๋ฉด ์ํธ๊ฐ ํ์ํฉ๋๋ค.
Programmers: ํ๊ฒ ๋๋ฒ
Programmers: ํ๊ฒ ๋๋ฒ
2021.05.08๋ชจ๋ ์กฐํฉ์ ๋ง๋ค์ด์, ์ฐ์ฐ์ ํด๋ณด๊ณ target๊ณผ ๊ฐ์ผ๋ฉด answer๊ฐ์ 1์ฉ ์ฆ๊ฐ์ํจ๋ค. ๋ฌธ์ https://programmers.co.kr/learn/courses/30/lessons/43165 ๋ด๊ฐ ์์ฑํ ์ฝ๋ Swift import Foundation func solution(_ numbers:[Int], _ target:Int) -> Int { var answer = 0 let n = numbers.count var picked = [Bool]() let op = [true, false] func pick(toPick: Int) { if toPick == 0 { var sum = 0 for i in 0..
BOJ: #6603 - ๋ก๋
BOJ: #6603 - ๋ก๋
2021.05.06์ค๋ณต์ ์ฒ๋ฆฌํด์ฃผ๊ธฐ ์ํด์ visited ๋ณ์๋ฅผ ์ด์ฉํด ์ฒดํฌํ๊ณ , ์ฌ์ ์์ผ๋ก ํ์ํ๊ธฐ ์ํด ์ด์ ์ ๊ณ ๋ฅธ ์๊ฐ ํ์ฌ ๊ณ ๋ฅธ ์๋ณด๋ค ํฐ ๊ฒฝ์ฐ์๋ ๊ฑด๋๋ฐ๊ฒ ํ๋ค. ๋ฌธ์ https://www.acmicpc.net/problem/6603 ๋ด๊ฐ ์์ฑํ ์ฝ๋ Swift while let input = readLine() { if input == "0" { break } let nums = Array(input.split(separator: " ").map { Int(String($0))! }) let n = nums.count var picked = [String]() var visited = Array(repeating: false, count: n) func pick(toPick: Int) { if toPick ==..
BOJ: #10974 - ๋ชจ๋ ์์ด
BOJ: #10974 - ๋ชจ๋ ์์ด
2021.05.0404:21 N๊ณผ M ์๋ฆฌ์ฆ ์ค์.. ์ด๋ค ๋ฌธ์ ๋ ๋๊ฐ์ ๋ฌธ์ https://www.acmicpc.net/problem/10974 ๋ด๊ฐ ์์ฑํ ์ฝ๋ Swift let n = Int(readLine()!)! var picked = [Int]() var visited = Array(repeating: false, count: n) func pick(toPick: Int) { if toPick == 0 { print(picked.map { String($0) }.joined(separator: " ")) return } for i in 0..
BOJ: #10819 - ์ฐจ์ด๋ฅผ ์ต๋๋ก
BOJ: #10819 - ์ฐจ์ด๋ฅผ ์ต๋๋ก
2021.05.0405:33 ๋ชจ๋ ์กฐํฉ์ ๋ง๋ค์ด์ ์ต๋๊ฐ ์ฐพ๊ธฐ ๋ฌธ์ https://www.acmicpc.net/problem/10819 ๋ด๊ฐ ์์ฑํ ์ฝ๋ Swift let n = Int(readLine()!)! let nums = readLine()!.split(separator: " ").map { Int(String($0))! } var results = [[Int]]() var picked = [Int]() var visited = Array(repeating: false, count: n) func pick() { if picked.count == n { results.append(picked) return } for i in 0..