우리는 ROCK이라는 단어를 찾고, 그 단어를 포함한 여러 단어에 대한 경우의 수를 구해햐 한다. 이를 위해서는 주어진 문자열을 처음부터 조사하는 것이 아니라 뒤에서부터 살펴봐야 한다. 이때 dp에는 발견한 K, CK, OCK, ROCK의 개수를 dp에 저장하기로 했다. 아래 코드에서 사용한 dp는 입력된 문자열의 길이 n만큼의 길이를 가지며 각 원소는 길이가 5인 리스트로 선언했다. 각 인덱스는 발견한 (0)K, (1)CK, (2)OCK, (3)ROCK의 개수를 저장하고 마지막 인덱스(4)의 칸에는 ROCK을 포함하고 있는 문자열의 개수를 저장했다. 단, ROCK을 포함하고 있는 문자열 중 "ROCK"은 인덱스(3)에 저장되어 있으므로 해당 문자열을 제외한 개수를 저장했다. 즉, "NROCK"이나 "R..
Algorithm/Dynamic Programming
문제에서 주어진 바와 같이 우리는 준서가 버틸 수 있는 무게에 맞추어 최대 가치를 가지도록 배낭에 물건을 담아야 한다. 이를 위해 knapsack 알고리즘을 활용할 수 있다. 만약 다음과 같이 물건과 가치가 주어졌다고 할 때 버틸 수 있는 무게를 10으로 놓고 knapsack 알고리즘이 어떻게 진행되는지 살펴보자. 물건 1 2 3 4 무게 5 6 4 3 가치 20 10 30 40 knapsack 알고리즘을 위해서는 dp table을 생성해야 한다. 이를 위해 (물건의 개수+1) ×(버틸 수 있는 무게+1) 만큼의 크기를 가진 table을 생성한다. 이때 (물건의 개수+1) 만큼의 행을 가지도록 생성한 이유는 knapsack알고리즘을 적용하기 위해서다. 배낭 용량 0 1 2 3 4 5 6 7 8 9 10 ..
해당 문제는 Floyd Warshall 알고리즘을 사용해 풀 수 있는 문제다. Floyd Warshall 알고리즘은 a에서 b도시로 이동하는 최단 거리를 임의의 도시 c를 경유하는 모든 경우를 고려하여 구하는 알고리즘이다. 즉, 총 도시의 개수가 5개인 경우 1에서 2로 이동하는 최단 거리를 찾을 때 아래 경우를 모두 고려한다. 도시 1에서 도시 1로 이동 후 도시 1에서 도시 2로 이동 도시 1에서 도시 2로 이동 후 도시 2에서 도시 2로 이동 도시 1에서 도시 3로 이동 후 도시 3에서 도시 2로 이동 도시 1에서 도시 4로 이동 후 도시 4에서 도시 2로 이동 도시 1에서 도시 5로 이동 후 도시 5에서 도시 2로 이동 해당 알고리즘은 DP을 활용하여 다음과 같이 구현할 수 있다. import s..
11049번: 행렬 곱셈 순서첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같www.acmicpc.net 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 이때 행렬 N개를 곱하는데 필요한 곱셈의 연산 수는 행렬을 곱하는 순서에 따라 따라지게 된다. 즉, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우 A, B를 먼저 곱하거나 B, C를 먼저 곱하는 경우 각각 90번, 126번으로 곱 횟수가 다르다. 이때 행렬 N개의 크기가 주어지고, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값..
