Algorithm236 [Swift][프로그래머스][DFS] 타겟 넘버 요구능력 : 깊이우선탐색 코드설명 : 일반적인 DFS문제로 노드를 그려가면서 풀면 이해가 쉽다. 후기 : 그냥 DFS로 풀면되는걸.. 계속 순열로 풀려고 하다가 시간이 조금 걸렸다.. 이걸 대체 왜 순열로 접근했을까.. func solution(_ numbers:[Int], _ target:Int) -> Int { var result = 0 func dfs(_ depth: Int, _ sum: Int){ if depth == numbers.count{ if target == sum { result += 1 } return } dfs(depth + 1, sum + numbers[depth]) dfs(depth + 1, sum - numbers[depth]) } dfs(0, 0) return result } 2022. 3. 14. [Swift][DP] 백준 5582번 (공통 부분 문자열) 요구능력 : DP 코드설명 : LCS를 풀고오면 문제가 상당히 쉽게느껴집니다. LCS 풀고오기 LCS문제와 다른점을 예시로 설명해보면 A B C 와 A D C가 있다. LCS라면 길이가 가장 긴건 A와 C라서 2가된다. 이 문제대로라면, 길이는 1이다. A 또는 C의 길이이다. 이 문제는 부분수열이기 때문에 같은 문자가 연속적으로 함께있어야지만, 조건이 성립한다. LCS는 기존에 연속적이지 않아도 중간중간 같은 문자가 나타나면 길이를 더해갔지만, 공통부분문자열의 경우에는 연속해서 같은 문자가 나오지 않으면 거기서 길이를 끊어야한다. 점화식을 설명하면, for문을 돌면서 x[i - 1]의 문자와 y[j - 1]의 문자를 비교하면서 만약 같다면, 부분수열이 하나 같다는 말이므로 dp[i][j]에 dp[i -.. 2022. 3. 14. [Swift][비트마스킹] 백준 11723번 (집합) 요구능력 : 비트연산 코드설명 : 이론적으로 어려운 문제는 아닌데 Swift로는 난이도가 상당한문제이다. 이 문제는 wapas님의 IO을 줄여주는 코드가 없으면 풀 수 없는것같다. 아래 코드의 경우 Int는 그냥 readInt()로 받아주면 되지만, String의 경우에는 Byte의 합으로 출력을 해주므로 "add" -> 297 이런식으로 String -> 10진수로 변환해서 모든 값을 더한 값을 알아내야하는 노가다를 해줘야한다. class FileIO { @inline(__always) private var buffer: [UInt8] = Array(FileHandle.standardInput.readDataToEndOfFile()) + [0], byteIdx = 0 @inline(__always) p.. 2022. 3. 14. [Swift][DP] 백준 9251번 (LCS) 요구능력 : DP 코드설명 : https://www.youtube.com/watch?v=EAXDUxVYquY 이곳에 설명을 아주 잘해주시는 교수님이 계십니다. 후기 : 여태 야매로 풀던 DP를 제대로 푸는방법을 배운것같은 강의였다. let x = readLine()!.map{String($0)} let y = readLine()!.map{String($0)} var dp = Array(repeating: Array(repeating: 0, count: y.count + 1), count: x.count + 1) for i in 1...x.count{ for j in 1...y.count{ if x[i - 1] == y[j - 1]{ dp[i][j] = dp[i - 1][j - 1] + 1 }else{ d.. 2022. 3. 10. 이전 1 ··· 13 14 15 16 17 18 19 ··· 59 다음