dynamicprogramming5 [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] 백준 11055번 (가장 큰 증가 부분 수열) 요구능력 : DP에대한 이해 코드설명 : 이 문제는 가장 큰 증가 부분수열로 이전에 풀었던 가장 긴 증가 부분수열이랑 비슷하다. 우선 dp를 구하는 방법부터 알아보자 10 1 100 2 50 60 3 5 6 7 8 위와 같이 예제가 있을 때 dp[1] = 1 dp[2] = 101 dp[3] = 3 . . . 이렇게 될것이다. dp[x] = y라고 했을 때 x번 인덱스까지 가장 큰 증가하는 부분수열은 y라는 의미이다. 이제 점화식을 구하면 되는데 dp[1]도 함께 처리하기 위해 dp[i]에 arr의 값을 전부 넣어준다. 그리고 arr을 비교하면서 dp[i]의 값을 정해준다. 점화식 dp[i] = max(dp[j] + arr[i - 1], dp[i]) arr에서 i - 1을 해준건 arr의 인덱스는 0부터.. 2021. 11. 10. [Swift][DP] 백준 1932번 (정수삼각형) 요구능력 : DP에 대한 이해 코드설명 : 문제를 읽고 우선적으로 생각해볼 수 있는건 dp[i]를 구하려면 이전에 어떤 값을 골랐는지가 중요하다는것이다. 삼각형에서 한줄을 i줄이라고 한다면 몇번째 수를 선택했는지가 중요한것이다. 이것을 보고 dp는 2차원 배열로 이루어지겠구나를 생각했다. 조건은 왼쪽대각선 혹은 오른쪽대각선으로만 선택할 수 있는것이다. 문제의 예제를 보고 8, 1, 0이 있는 줄을 dp[i]라고 생각해보면 이전 줄에 3, 8이 있다. 우선 8을 선택했을 때의 최대값을 구하기 위해서는 3에서 내려오는 방법밖에는 없다. 왼쪽 대각선으로 내려오는 것 밖에 없는것이다. 다음으로 1을 생각해보자. dp[i][1]을 구하는것인데 1은 왼쪽대각선과 오른쪽대각선 2가지가 모두에서 내려올 수 있다. 다.. 2021. 11. 9. [Swift][DP] 백준 1912번 (연속합) 요구능력 : DP에 대한 이해 코드설명 : 이 문제에서 만들어 놓은 함정에 빠지고 문제를 풀 수 없었다.. 함정은 바로 음수를 빼는 조건을 거는것이다. 음수포함해서도 연속값이 큰값이 나올 수 있다. 만약 음수를 빼는 조건을 거셨다면, 2번째 예제에서 14가 안나올것이다. 일단, 이 문제는 문제이름대로 dp에 연속적으로 합을 누적시킨다고 생각하면 된다. dp[0] = arr[0] 을 해준 이유는 dp[0]에는 arr[0]만 누적된거다. dp[1] = max(arr[1], dp[0] + arr[1]) dp[2] = max(arr[2], dp[1] + arr[2]) . . 이런식으로 값을 계속해서 누적 시킨다. max를 쓰는 이유는 값의 누적이 쓸모없어졌을 순간, 바로 현재 값이 이전에 (누적된 값 + 현재값.. 2021. 10. 5. 이전 1 2 다음