본문 바로가기
백준 #10844. 쉬운 계단 수 (Dynamic Programming) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP를 활용해 풀 수 있다. n이 1일 경우, 1 2 3 4 5 6 7 8 9 이렇게 예제를 통해 계단 수가 9개임을 알 수 있다. 그렇다면 n이 2일 경우에는 10, 12, 21, 23 ... 87, 89, 98 이렇게 자리수의 차이가 1이 나는 수를 만들 수 있다. 즉, n이 1일 경우의 9가지 숫자에서 뻗어나와 n이 2일 경우의 계단 수를 만드는 것이다. 1 -> 10, 12 2 -> 21, 23 3 -> 32, 34 4 -> 43, 45 5 -> 54, 56 6 -> 65, 67 7 -> 76, 78 8..
백준 #12865. 평범한 배낭 -Knapsack Algorithm(DP) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net Knapsack 알고리즘에 대해 처음 알게 되었는데, 배낭에 담을 수 있는 아이템의 가치를 최대화해주는, 재미있으면서 아주 실용적인 알고리즘이다. 재귀를 이용한 DP와 이중 for loop을 이용한 DP 두 가지 방법으로 풀어보았다. 기본 로직은 같다. i번째 아이템을 담을 경우와..
백준 #2579. 계단 오르기 다이나믹 프로그래밍을 활용해 풀 수 있는 문제이다. 우선 입력된 계단의 비용을 stair[] 배열에 저장하고, 이와 똑같은 사이즈의 계단의 최대 비용을 저장하는 배열을 DP[]라고 해보자. 그럼 n번째 계단의 최대 비용 DP[n]은 1) DP[n-3] + stair[n-1] + stair[n] 이거나 2) DP[n-2] + stair[n] 이다. 1) 조건에서 왜 DP[n-3]을 더하는지 의문을 가질 수 있을 것이다. 계단은 3개를 연속해서 밟을 수 없으므로, 바로 직전의 계단, 즉, n-1번째 계단을 밟기 위해서는 n-2번째 계단을 밟으면 안 된다. 따라서, n-3번째 계단까지의 최대 비용에 n-1, n번째 계단을 더해준다. 저 식은 n이 3 보다 작을 경우 index를 벗어나므로, 초기값들에 대한 최..
백준 #11053. 가장 긴 증가하는 부분 수열 다이나믹 프로그래밍을 이용해 풀 수 있다! 입력 배열과 같은 크기의 cost 배열(DP 실행결과 저장)을 하나 만든다. 배열의 현재 위치(i) 입장에서 자신보다 크거나 같은 값은 패스하고, 자신보다 작은 값(j)의 cost에서 1을 더한 값이 n의 cost가 된다. 하지만, 탐색을 수행하면서 이미 max값을 갖고 있을수도 있으므로, cost[i]과 cost[j]+1 중 큰 값을 채택한다. 최대로 증가하는 값을 찾아야 하므로, STL sort()를 이용해 cost 배열을 정렬한다. 그리고 제일 마지막에 있는 값, 즉 제일 큰 값이 답이 된다. #include #include using namespace std; #define max_size 1001 int main() { int n; //size of a..
백준 #1149. RGB거리 이웃 간에는 같은 색을 칠할 수 없다는 것이 특징이고, 가장 최소 비용을 묻는 문제이다. n번째 집이 R, G, B로 칠하는 경우를 나눠봤을 때, R로 칠할 경우 : n-1번째 집이 G, B 중 하나의 색을 갖고 있음. G로 칠할 경우 : n-1번째 집이 R, B 중 하나의 색을 갖고 있음. B로 칠할 경우 : n-1번째 집이 R, G 중 하나의 색을 갖고 있음. R로 칠할 경우의 최소 비용은 n-1 집(G, B 중 하나)까지의 최소 비용 + 현재 집의 R 비용이다. 즉, n번째 집을 R로 칠하는 경우의 비용을 cost[n][0]이라고 했을 때, cost[n][0] = min(cost[n-1][1], cost[n-1][2]) + cost[n][0] 이렇게 일반화가 가능하다. ([0]은 R, [1]은 G,..
백준 #1932. 정수 삼각형 경로의 최대 합을 구하는 문제. 현재 층에서 위를 바라봤을 때, 나에게 올 수 있는 값들 중 제일 큰 값을 나에게 더해주면 된다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 가령 여기서 7로 올 수 있는 값은 위에 있는 8과 1이다. 따라서 8과 1중 더 큰 값인 8을 7에 더해 15를 만들어준다. 이렇게 하면 위의 삼각형이 7 10 15 18 16 15 20 25 20 19 24 30 27 26 24 다음과 같이 바뀐다. 주의할 점은, 행의 시작과 끝(0번째, i번째 인덱스)에 위치한 원소일 경우, 위 층의 값들을 비교할 필요 없이 각각 이전 층의 0번째, i-1번째 원소들만이 자신에게 올 수 있으므로, 이 값을 더해주면 된다. 여기서 마지막 행을 sort() 함수로 정렬해준 다음, 마지막 ..
백준 #11047. 동전 0 그리디 알고리즘을 이용해 풀었다. K원을 만드는 데 필요한 동전들은 K원보다 작은 동전들이다. coin 배열을 n-1번째 인덱스부터 0번째 인덱스로 거꾸로 받고, 0번째 인덱스부터 차례대로 K원을 만족시킬 수 있는지 알아본다. 만약 i번째 인덱스가 K원보다 크다면, 다음 인덱스를 탐색한다. 만족하는 인덱스의 숫자(동전 숫자)는 K원보다 작을 때까지 더해준다. 가령, K원을 4200원이라고 했을 때, 50000원, 10000원, 5000원으로는 절대 4200원을 만들 수 없다. 그러니 스킵하고, 1000원을 만나면 그걸 4만큼 반복해서 더해준다. 그럼 4000원이 된다. 그 다음 500원을 더하면 4500원이 되므로, 500원을 낄 수 없다. 얘도 스킵! 그 다음은 100원이다. 4100원 n >> res..
백준 #2178. 미로 탐색 (1, 1)에서 (n, m)까지의 최단 경로를 구하면 된다. 4 6 110110 110110 111111 111101 이런 input이 들어왔을 때, (1, 2)와 (2, 1)까지의 경로는 아래처럼 2가 되는 것을 알 수 있다. (1번 index부터 시작) 120110 210110 111111 111101 즉, 현재 있는 칸에서 +1 한 값이 인접 칸까지의 최단경로이다. 나의 인접 칸들을 모두 훑고 인접 칸들의 인접 칸을 훑어보는 방식이므로, BFS를 이용해 풀어보았다. 현재 있는 칸을 큐에 넣어주고, 방문처리한다. 그리고 큐가 빌 때까지 인접 노드들을 탐색하며 큐에 넣는다. 단, 인접 노드 값이 0이면 그 칸을 지나갈 수 없으므로 탐색하지 않는다. 더 이상 방문할 인접노드가 없다면 큐에서 pop해주고,..

티스토리툴바