https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. 처음 값부터 연속해서 합을 구하는데, 이전까지 연속합에 현재 값을 더한 것과 그냥 현재 값을 비교하여 큰 값을 dp 배열에 저장한다. 이렇게 되면 연속하는 수 중에서 가장 큰 합을 구할 수 있다. 예를 들어, n = 10, numbers = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1] 인 경우를 생각해보자. dp 배열은 5번째 인덱스까지 [1..
https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. dp[i]는 카드 i개를 구매하는 최대 비용, Pi[i]는 i개가 들어있는 카드팩 가격이다. 예를 들어, 카드를 1개 구매하는 최대 비용은 dp[0] + Pi[1]이다. 카드를 2개 구매하는 최대 비용은 dp[1] + Pi[1], dp[0] + Pi[2] 이다. 카드를 i개 구매하는 최대 비용은 dp[i-1] + Pi[1], dp[i-2] + Pi[2], .....
https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 일정 높이만큼 비가 내렸을 때, 잠기지 않는 영역의 개수의 최대값을 구하는 문제이다. 높이는 입력받은 높이 값들 중 가장 작은 값부터 시작하여 가장 큰 값까지 bfs 함수를 수행하며 개수를 센다. 가장 작은 값 min_height와 가장 큰 값 max_height는 파이코닉한 방법으로 구할 수 있다는 점을 유의한다. bfs에서는 일정 높이보다 높은, 즉 안전한 높이..
https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 💡IDEA 수학을 사용하는 문제이다. 처음엔 BFS로 푸는 문제인 줄 알았으나 시간초과로 실패했다. 오히려 규칙을 찾아서 수학적으로 접근해야한다. 처음 시작하는 수와 마지막 끝나는 수는 1이어야 한다는 점을 주의한다. 거리(y-x) 방법 최소 횟수 1 1 1 2 11 2 3 111 3 4 121 3 5 1211 4 6 1221 4 7 12211 5 8 ..
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. 동적계획법 문제는 쉽게 동적계획법으로 풀어야 하는 문제라고 판단하기가 어렵다. dp 배열을 0~9까지 길이 10의 배열을 총 N+1번 가지는 이차원 배열로 설정한다. N=1 인 경우는 한 자리 수인 계단 수를 찾는 것으로, [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]로 설정되어 총 9개를 가진다. N=2 인 경우는 두 자리 수인 계단 수를 찾는 것으로, N=1인 경우의 dp를 사용하여 [1, 1, 2, 2, 2, 2, 2, 2, 2, 1]로 총 17개이다. ..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. 입력받은 wines를 사용하여 dp를 구성하는데, 0번째 값과 1번째 값은 초기화 해준 후 2번째 값부터 어떻게 계산해야 할지 점점 복잡해진다. 2번째 값은 0번째+1번째 or 1번째+2번째 or 0번째+2번째 중 가장 큰 값으로 설정해준다. 3번째 값 부터는 앞에서 2번째까지 계산해둔 dp를 사용하여 계산해나간다. 연속해서 3잔을 마실 수는 없으므로, 2..
https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 💡IDEA 수학과 분할 정복을 사용하는 문제이다. 피보나치 수열을 계산할 때 동적 계획법이나 변수 두개를 치환하면서 갱신하는 식으로 풀었었는데, 이 문제는 n이 너무 커서 감당할 수가 없다. 어떻게 풀어야할지 도무지 모르겠어서 https://www.acmicpc.net/blog/view/28 의 도움을 받았다. n이 굉장히 클 때 피보나치 수열을 계산하기 위해서는 행렬 제곱을 사용해야 한다. 아래 코드에서 matmul 함수는 행렬 곱셈 후 1000000007로 나누어주는 연..
https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 💡IDEA 다익스트라 또는 플로이드-워셜 알고리즘을 사용하는 문제이다. 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘(S.S.S.P - Single Source Shortest Path) 이라면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있다. 플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다. 플로이..
https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 💡IDEA 분할 정복과 수학을 사용하는 문제이다. 이 문제를 이해하려면, 일단 모듈로 곱셈 역원에 대해 알아야 한다. 학부 때의 기억을 되살리느라 힘들었다. 문제에서 자세히 설명해주고 있는 것 같지만, 문제만 봐서는 잘 이해가 되지 않을 것이다. 중요한 부분은 다음 내용이다. 어떤 분수가 기약분수로 나타냈을 때 a/b이면, 이 분수는 $a × b^{-1} (mod X)$ (X는 소수)으로 대신 계산하도록 한다. 여기서 $b^{-1}$은 b의 모듈러 ..
https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 💡IDEA 벨만-포드 알고리즘을 사용하는 문제이다. 벨만-포드 알고리즘은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘으로, 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있다. 다익스트라 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구한다. 가중치가 음수인 간선이 없다면 최적의 해를 찾을 수 있다. 우선순위 큐(he..
