백준177 [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. [Swift][DP] 백준 11058번 (크리보드) 요구능력 : DP 코드설명 : 의식의 흐름대로 문제를 풀게됬다. 일단 2번부터 4번조건은 처음에는 세개가 다같이 발동해야한다. 1번부터 6번까지는 그냥 A를 찍는게 수가 훨씬 많다고 생각해서 dp[i]에 i를 넣어주었다. 그리고 i가 7일때 부터는 전체선택, 복사, 붙여넣기 등의 과정이 들어가는게 A를 더 많이 찍게된다. n이 7일 때를 가정해서, 점화식을 구해보면 버튼을 총 7번 누를 수 있는데 이 중에서 전체선택, 복사, 붙여넣기를 하려면 버튼 누르는 수가 3번이 있어야한다. 그럼 우리는 A를 최대한 찍고 저 3번을 눌러야한다. 그렇기 때문에 바로 dp[i - 3]인 곳에서 전체선택,복사,붙여넣기를 하면 버튼은 총 7번 누르게된다. 그리고 붙여넣기를 했기 때문에 dp[i - 3]의 A의 개수에서 2배.. 2022. 3. 2. 이전 1 ··· 6 7 8 9 10 11 12 ··· 45 다음