DP29 [Swift][프로그래머스][DP] N으로 표현 요구능력 DP 문제풀이 이 문제는 N을 이용해서 number를 만드는데 N을 최소개수로 사용해서 number를 만들때 몇개를 써야하는지를 묻는문제이다. DP를 생각하게된 이유? 카테고리가 DP로 분류되어있다. 예제를 보자. 12 = (55 + 5)/5 가 있다. 이게 5를 4번 사용한것이라고한다. 그렇다면 55는 5를 2번사용했다는 말이되는데, (55 + 5)는 5를 3번 사용한것이다. DP문제를 조금 풀어봤으면 감이 올것이다. 현재 이 식은 dp[4] = dp[3] + dp[1]과 같은 형태구나 라는것을.. 사실, dp는 다른 알고리즘 문제들과는 조금다르게 감각(?)이 필요한 문제같다. 그래서 다양한문제를 많이 접해봐야하는데, 만약 이런감이 안잡힌다면, DP문제를 많이 풀어보기를 추천드립니다. 이 문제.. 2022. 5. 2. [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][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 2 3 4 ··· 8 다음