Dynamic Programming
[백준] 2169. 로봇 조종하기 - C++
[Gold II] https://www.acmicpc.net/problem/2169 풀이 일반적인 Bottom-Up 형식으로 풀어낸 DP 문제. 아래, 오른쪽으로만 갈 수 있는 것이 아닌, 왼쪽으로도 갈 수 있기 때문에 이를 고려해줘야 했으나, "한 번 방문한 곳은 다시 방문하지 않는다" 라는 조건이 있기 때문에, 각 줄에서, 왼쪽부터 DP 배열을 갱신하고 (line 43~45), 또 오른쪽부터 다른 DP배열을 갱신한 후 (line 47~49), 둘 중 더 큰 것(최댓값)을 택하여 DP 배열을 최종적으로 갱신해주는 식으로 모든 줄을 반복하면 된다. 다만 주의할 것은, DP 배열을 초기화할 때, 음수 value값이 있으므로, 최댓값을 구하기 위해서는 0으로 초기화하지 않고, 나올 수 있는 가장 작은 값(-..
[백준] 9095. 1, 2, 3 더하기 - 파이썬
[Silver III] https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 간단한 Dynamic Programming 문제. n이 11보다 작다 는 조건이 걸려 있어, Top-Down 방식으로 재귀를 이용해 풀어도 시간초과나, Recursion 기본 횟수(1000회) 제한에 걸리지 않을 법 한 문제였다. [정수 k를 1, 2, 3의 합으로 나타내는 방법의 수] = [k-1을 나타내는 방법의 수] + [k-2을 나타내는 방법의 수] + [k-3을 나타내는 방법의 수] 라는 것만 캐치한다면, Bottom-Up 방식으로 Memoization 하며..
[백준] 11049. 행렬 곱셈 순서 - 파이썬
[Gold III] https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 풀이 [백준] 10942. 팰린드롬? - 파이썬 [백준] 9252. LCS 2 - 파이썬 [백준] 7579. 앱 - 파이썬 최근 풀었던 위 3개의 DP 문제와 크게 다를 것이 없었던 문제. 근데 DP는 DP인 걸 알아도.. 문제마다 다른 상황에 맞춰서 풀이를 생각해내기 쉽진 않음. 그리고 Line 28의 i += 1 이거 하나 빼먹어서 30분동안 찾았다.........
[백준] 10942. 팰린드롬? - 파이썬
[Gold IV] https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 일단 기본적으로, Palindrome 문제에서 쉽게 생각할 수 있는 풀이라 하면 Stack을 이용한 검증. 하지만, Stack을 이용한다면 Time Complexity가 저 하늘 멀리 날아가 버릴 것이 분명해~ 그렇다면 DP를 이용해서 모든 경우를 이차원 배열에 저장하는 식으로.. 0-1 Knapsack이나, LCS 문제처럼 저장해 놓고 풀이하는 식이 맞겠다. 풀이 설명은 주석으로. 참고로 sys.stdin.re..
[백준] 7579. 앱 - 파이썬
[Gold III] https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 일단 보자마자 생각난 것은 "Greedy로 풀면 참 편하겠다..." 인데, 간단하게 생각해 봐도 그리디로 해결될 문제가 아님. 모든 경우의 수를 파악해봐야 될 것 같은 문제이고, DP로 풀면 되겠다 싶었다. 0-1 Knapsack 문제와 동일한 방법으로 풀이했다. 1
[백준] 2056. 작업 - 파이썬
[Gold IV] https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net [백준] 1005. ACM Craft - 파이썬 과 매우 유사했던 문제. 풀이 [백준] 1005. ACM Craft - 파이썬 과 매우 유사해서 비슷하게 어려움 없이 풀었던 문제. DP와 위상 정렬(Topological Sort) 을 이용해서 풀이했다. from collections import deque N = int(input()) times = [] graph_in..
[백준] 1005. ACM Craft - 파이썬
[Gold III] https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net [위상 정렬(Topological Sort)] 참고. https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html 풀이 1 위상 정렬(Topological Sort)을 이용하여 풀이. 오답이 나왔는데, 잘 생각해보니 각 턴마다 건설 시간이 가장 긴 것을 더하는 것이 총 건설 시간의 합이 최소가 되도록 하지..
[백준] 1463. 1로 만들기 - 파이썬
https://www.acmicpc.net/problem/1463 풀이 1 정말 단순하게 생각하면, "당연히 3으로 나누는게 가장 빨리 숫자를 줄일 수 있고, 그 다음이 2로 나누는 거고, 그 다음에 1을 빼는 것을 택하는 게 제일 유리한 거 아닌가?" 라고 생각할 수 있다. (약간의 Greedy 느낌!) 그러나, 10의 Input 예시만 생각해 봐도, 위와 같은 알고리즘으로는 10은 2로 나눠지므로, 10/2 = 5 5는 3, 2로 나눠지지 않으므로, 5-1=4 4는 2로 나눠지므로, 4/2 = 2 2는 2로 나눠지므로, 2/2 = 1 로 4번의 연산만에 1이 된다. 그러나, 첫 번째 단계에서 1을 빼는 것을 택한다면, 10 - 1 = 9 9 / 3 = 3 3 / 3 = 1 로 3번의 연산만에 1을 만..