DP
-
[Programmers] 스티커 모으기(2)Algorithm/Programmers 2021. 10. 24. 14:45
출처: https://programmers.co.kr/learn/courses/30/lessons/12971 분류: dp 접근 배열의 길이도 100,000 으로 크고 이 스티커를 뗄지 안 뗄지, 앞에껄 땠는지 안 땠는지 등등의 경우를 고려해줘야 하니 DP로 문제로 접근을 했어요. 그냥 배열의 첫 번째를 기준으로 잡으면, 이 스티커를 땔 경우 DP vs 떼지 않을 경우 DP 두 번의 DP를 구해서 최대를 구하면 되는 문제였네요 처음에 저도 이렇게 접근은 했는데 첫 번째 인덱스부터 DP, 마지막 인덱스부터 거꾸로 DP 라는 엉뚱한 풀이로 해서.. 꽤나 삽질을 했습니다 😰 풀이 일단 각 케이스의 0, 1번 기저 사례를 구해주고 2번 인덱스부터 점화식으로 적용해주면 됩니다. (사실 n이 3일 때는 하나밖에 땔 ..
-
백준 2169 로봇 조종하기Algorithm/BOJ 2021. 6. 2. 15:30
출처: https://www.acmicpc.net/problem/2169 분류: DP 접근방식 백트래킹 문제 같이 보이지만, n, m이 최대 1000이기 때문에 백트래킹으로 접근하면 시간초과가 납니다. 백트래킹에 복잡도를 생각해봤는데, 한 번 이동마다 최대 3가지 경로로 가지가 쳐지고 위로 이동은 없으니 거꾸로 경우를 줄여 2가지로 잡아도 2^1000 하면 시간초과를 면치 못한다고 생각이 드는데요, 제대로 판단한건지는 잘 모르겠네요... 정확히 아시는 분은 답글 부탁드립니다 🙇🏻♂️ 이 문제는 DP로 접근해서 해결할 수 있는데요, 위로 이동하는 경우는 없으니 맨 윗줄은 1, 1지점부터 오른쪽으로 이동하는 경우가 최선의 경우입니다. for col in 1..
-
백준 7579 앱Algorithm/BOJ 2021. 6. 2. 13:37
출처: https://www.acmicpc.net/problem/7579 분류: DP 접근방식 어떤 걸 기준으로 DP를 만들건지 어려웠던 문제였습니다... 결국 다른 블로그의 풀이를 참고하여 해결했습니다. 비용으로 확보할 수 있는 최대 메모리를 만들어가는 방식으로 해결했습니다. 점화식은 아래와 같습니다. DP[cost] = max( DP[cost] , DP[cost - inActiveCost[app] + activeMemory[app] ) 여기서 DP[cost]는 cost를 사용하여 확보할 수 있는 최대 메모리인데요, DP[ cost - inActiveCost[app] ] 은 app을 아직 제거하기 전의 비용으로 확보할 수 있는 최대 메모리로 여기에 지금 앱을 제거해서 얻을 수 있는 비용을 더해주면 이게..
-
백준 5557 1학년Algorithm/BOJ 2021. 6. 2. 11:01
출처: https://www.acmicpc.net/problem/5557 분류: DP 접근방식 만들 수 있는 가능한 연산의 경우의 수를 구하는 문제였습니다! 중간 중에 나올 수 있는 수는 0 ~ 20 밖에 없기 때문에 0~20까지 배열을 만들어두고 개수를 카운트 해주는 방식으로 해결했습니다. 이전 연산의 개수에 계산한 결과가 그대로 다음 연산으로 넘어가는데, 이때 이전 결과는 남아있으면 안되기 때문에 배열을 2개 두고 돌려가며 사용했습니다. 말이 조금 어려운데.. 가령 어떻게 어떻게 해서 중간에 연산 결과가 8이 된 경우가 3개 있다고 생각하고 다음의 숫자는 3이라고 생각해보겠습니다. 그러면 +, - 연산을 사용해 8과 3으로 만들 수 있는 결과는 8 + 3 = 11 8 - 3 = 5 이렇게 두 가지가 ..
-
백준 1958 LCS 3Algorithm/BOJ 2021. 4. 22. 12:30
출처: www.acmicpc.net/problem/1958 분류: LCS, 문자열, DP 접근방식 이번엔 3개 문자열의 LCS를 구하는 문제였습니다. 기존 LCS와 원리는 동일하고 이를 3차원 배열로 확장시키면 되는 문제였습니다. func lcs(_ strA: [Character], _ strB: [Character], strC: [Character]) -> Int { var table = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: 0, count: strC.count+1), count: strB.count+1), count: strA.count+1) for a in 1...strA.count { for b in 1...strB.count { f..
-
백준 11049 행렬 곱셈 순서Algorithm/BOJ 2021. 4. 21. 14:08
출처: www.acmicpc.net/problem/11049 분류: DP 접근방식 전체 순서를 유지하면서 특정 연산을 해야할 때 연산 순서를 어떻게 해야 최소가 될까? 에 관한 문제였습니다. 11066 파일합치기 와 유사한 문제였다는 생각이 드네요. 핵심 아이디어는 X ~ Y까지 연산의 최소값을 DP에 계속 저장해나가는데, X ~ Y까지 연산의 최솟값은 (X~K) + (K~Y) 연산들 중 최소를 찾아나가는 것입니다. 문제의 예시를 가지고 생각해보겠습니다. 각 행렬이 배열에 들어있다고 생각하면, (5x3) - 0 (3x2) - 1 (2x6) - 2 0 ~ 1 까지의 최소값은 dp[0][1], 0 ~ 2 까지의 최소값은 dp[0][2] 에 담는 것입니다. 0 ~ 2 까지의 최솟값은 ( [0][1] 을 먼저 ..
-
백준 17070 파이프 옮기기 1Algorithm/BOJ 2021. 4. 20. 12:38
출처: www.acmicpc.net/problem/17070 분류: DP, 백트래킹 접근방식 주어진 요구사항 대로 파이프의 이동 가능 위치를 잘 계산하고 나면 백트래킹으로 도착한 경우의 수를 세주면 되는 문제였습니다. 파이프의 끝 점에서 출발한 경로는 역시 다시 방문해줄 필요가 없으므로 방향을 고려한 3차원 배열에 이를 기록해서 방문 횟수를 줄여줬습니다. 조금 귀찮긴 하지만 크게 어렵지는 않아서 풀이를 보시면 이해가 되실거에요 :) 해결방법 let n = Int(readLine()!)! var map = [[Int]]() for _ in 0.. Direction { if pipe.0.r == pipe.1.r, abs(pipe.0.c - pipe.1.c) == 1 { return .horizontal } ..
-
백준 2096 내려가기Algorithm/BOJ 2021. 4. 20. 09:54
출처: www.acmicpc.net/problem/2096 분류: DP 접근방식 간단한 DP 문제였습니다. 1, 2, 3 각 열에서 가장 최선인 경우를 계속 선택해나가면 됩니다. 행마다 갱신하고 나면 그 이전은 생각할 필요가 없으므로 디피는 각 열을 저장할 행 하나만 있으면 됩니다 :) 저는 맨 밑에서부터 올라왔는데 위에서부터 내려가도 상관은 없을듯 하네요! 해결방법 let n = Int(readLine()!)! var num = [[Int]]() for _ in 0..