DP29 [Swift][DP] 백준 11054번 (가장 긴 바이토닉 부분 수열) 요구능력 : DP에 대한 이해 코드설명 : 바이토닉 부분수열을 오해하고 문제를 풀었다. 증가하다가 가운데가 가장크고 점점 작아지는 수가 나오는줄알고 처음에는 증가하는 부분수열 + 인덱스저장 + 감소하는 부분수열로 풀었는데, 생각보다 간단하게 풀리는 문제였다. 이론적인 부분은 https://st-lab.tistory.com/136 엄청 잘 정리해 놓으셨다. 우선 가장 긴 증가하는 부분수열 dp를 구하고, 가장 긴 감소하는 부분수열 dp를 구해준다. 그리고 두 dp의 각 인덱스를 합쳐주고 1씩 빼주면 그게 두 수열을 합친것이다. 그래서 점점 작아지는 부분과 점점 커지는 부분이 합쳐져서 바이토닉 수열이된다. 내가 이해가 안갔던 부분을 위주로 설명하자면, 두 개를 합친다고 어떻게 하나의 바이토닉 수열이 되는가?.. 2021. 11. 15. [Swift][DP] 백준 2133번 (타일 채우기) 요구능력 : DP에대한 이해 코드설명 : 그림을 보면 n = 2일 때는 3가지 n = 3일 때는 0가지, n = 4일 때는 11가지가 나온다. n이 홀수일때는 0가지라는걸 직접 그리는걸 시도해보면 알것이다. n = 4일 때를 보면 빨간색으로 색칠한 부분 오른쪽을보자. n = 2일 때의 모양들을 가지고 있다. n = 2일 때의 모양이 3번 연속나오니까 dp[i] = dp[i - 2] * 3이라는 식은 쉽게 나온다. 하지만, 여기서 끝이아니고 맨 오른쪽에 기괴한 모양이 있다. 이 문제에서 핵심은 저 모양을 처리해주는 것이다. 기괴한 모양은 그려보면 알겠지만, n = 4일 때부터 2개씩 계속나온다. 그럼 +2를 해주면 되지않는가 싶지만 아쉽게도 저 모양마저 계속 옆에 모양이 달려서 나올 것이다. 그럼 n = .. 2021. 11. 11. [Swift][DP] 백준 11722번 (가장 긴 감소하는 부분 수열) 요구능력 : DP에대한 이해 코드설명 : 가장 긴 증가하는 부분수열 문제와 부등호만 틀리다. 가장 긴 감소하는 부분수열을 구하는 문제이다. 예제를 보자. 10 30 10 20 20 10 여기서 i인덱스(3)가 20을 가리킨다고 가정하고 설명하면 arr[0]부터 arr[2]까지의 수 중에서 arr[3]보다 큰 수가 있으면 dp[i]를 갱신해준다. 감소하는 부분수열이라서 앞에 나보다 큰 수가 있으면 dp[i]를 갱신해주는것이다. 그럼 dp[i]는 dp[0]부터 dp[2]까지 중에 조건을 만족하는 dp[]를 갖고 +1을 해줄것이다. dp[1]도만족하고 dp[2]도 만족하는 경우가 있으면 max()로 그 중 큰 값을 가져온다. 이유는 그 중 큰값은 이전에 더 많은 감소하는 부분수열을 갖고있을 것이기 때문이다. .. 2021. 11. 10. [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. 이전 1 2 3 4 5 6 7 8 다음
