본문 바로가기
백준 #1010. 다리 놓기 (C++ Dynamic Programming) https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net N개의 서쪽 사이트에서 M개의 동쪽 사이트로 이어지는 다리의 개수를 구하는 문제. 조건 1) N은 M보다 작거나 같다. 조건 2) 다리는 서로 겹처질 수 없다. N*M size의 이차원 배열을 만들고, 각각의 값을 적어보면 패턴이 한눈에 잘 보인다. 우선 쉽게 생각해보면, N과 M이 같을 때에는 경우의 수가 1이다. 더보기 만약 N보다 M이 1 클 때에는, 즉, N + 1 == M일 때는 경우의 ..
백준 #2193. 이친수 / C++ / Dynamic Programming https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net 문제에서 제시한 이친수의 조건 1. 0으로 시작하지 않는다. 2. 1이 두 번 연속해서 나타나지 않는다. N이 1일 경우부터 차례차례 생각..
백준 #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() 함수로 정렬해준 다음, 마지막 ..

티스토리툴바