DP29 [Swift][DP] 백준 1699번 (제곱수의 합) 요구능력 : DP에 대한 이해 코드설명 : 우리는 여기서 최소개수를 구해야한다. 모든 경우의수를 비교해서 최소개수를 구하면 된다. 11은 최소 3개항의 제곱수로 표현 가능하다고 한다. 1부터 8까지만 찾아보자. 1 1의제곱 2 1의제곱 + 1의제곱 3 1의제곱 + 1의제곱 + 1의제곱 4 1) 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 2) 2의제곱 5 1) 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 2) 1의제곱 + 2의제곱 6 1) 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 2) 1의제곱 + 1의제곱 + 2의제곱 7 1) 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 2) 1의제곱 + 1의제곱 + 1의제곱 + 2의제.. 2021. 10. 7. [Swift][DP] 백준 14002 (가장 긴 증가하는 부분 수열4) 요구능력 : DP에 대한 이해 코드설명 : 첫번째로 가장 긴 증가하는 부분수열의 크기를 구해야하는데, 먼저 풀고오는 것을 추천한다. 이 문제에서 추가된 부분은 수열을 출력해주는것이다. dp에 우리가 저장한 수열 크기의 순서는 arr에 저장된 수열의 순서와 동일하다. 이게 무슨소린고 하면 아래 그림과 같다. 이거 처음에 나도 뭔소린가 했는데 밑에 var order = dp.max()! 부분부터 손디버깅 해보면서 써봐야 안다. 직접 생각하면서 써봐라. 참고로 아래 코드에서는 인덱스를 의도적으로 맞추지는 않았는데, dp값을 처음에 1로 초기화해놔서 정답이된다. (참고 : 어차피 배열의 뒤쪽에 있는 수가 큰 수 이므로 배열의 뒤쪽부터 찾아주는것이다.) 이제 이 인덱스가 같은점을 이용해서 문제를 푸는데, dp값이.. 2021. 10. 6. [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. [Swift][DP] 백준 11053번 (가장 긴 증가하는 부분수열) 요구능력 : DP의 응용 코드설명 : 이 문제는 앞에있는 숫자가 자기자신보다 작은 숫자의 갯수를 세는것이다. 1. 배열에서 현재 i가 위치한 배열의 앞부분에 현재 arr[i]의 수보다 작은게 있으면 그 자리의 dp는 dp[i]와 dp[j] + 1 중 큰 수를 dp[i]에 넣는다. 그 이유는 디버깅해보면 알겠지만, [10, 20, 10, 30]과 같은 경우에 10일 때는 dp[0] = 1 20일 때는 dp[1] = 2 10일 때는 dp[2] = 1 30일 때는 dp[3] = 3 이 된다. 후기 : 증가하는 부분수열의 점화식은 처음에 구했는데 왜 답이 안나왔었는지 멀리돌아서 왔다. let a = Int(readLine()!)! var arr = readLine()!.split(separator: " ").m.. 2021. 9. 22. 이전 1 ··· 4 5 6 7 8 다음
