모나오랭의 개발일지

https://www.acmicpc.net/problem/20303  유니온 파인드(Union-Find)와 다이내믹 프로그래밍(DP)을 이용하는 것이 큰 틀입니다. 처음에 DP를 사용하지 않고 문제를 풀어갔는데, 친구 그룹이 꼭 하나란 보장이 없기에 DP를 사용해야 되는 것을 깨달았습니다.. (ex. K = 8, 각각 3명, 4명씩 친구인 그룹의 총 사탕 합이 최대일 수 있음) 1. 아이들이 가지는 사탕 개수 배열, 유니온 파인드의 부모 배열, 루트를 중심으로 그룹에 속한 아이들의 수를 저장하는 사이즈 배열, 최대 사탕 수를 저장하는 dp 배열을 생성합니다. 2. 친구 관계를 입력받을 때마다 유니온 파인드를 통해 아이들의 관계를 정리합니다. 이때 하위 그룹을 귀속할 때 상위 그룹의 루트에 하위 그룹의 사..

https://www.acmicpc.net/problem/17404   문제와 흡사하게 다이나믹 프로그래밍(DP)을 사용하는 문제입니다.근접한 집들끼린 같은 색으로 칠하지 않아야 하는데, 추가로 처음 집과 마지막 집의 색도 달라야 합니다. 처음에 문제를 풀 때 첫번째 집의 색의 정보를 저장한 배열을 따로 만들어 DP를 실행할 때마다 새로 저장을 했습니다.  너무 복잡하고 연산이 뜻대로 되지 않았습니다. 다시 문제를 풀 때 dp[n - 1][i]의 처음 집 색을 구하고 n번째 집의 색을 다른 두 가지 중 cost가 낮은 색을 택하려고 했습니다. 하지만 처음 시도와 달리 첫 집의 색을 저장하지 않아 답이 안 나왔습니다. 그래서 처음부터 집 색을 하나 정하고, 그다음에 DP를 진행하여 마지막 집의 색을 처음 ..

https://www.acmicpc.net/problem/17626  문제를 잘 읽어야 하는 게, 처음에 자연수 4개 이하로 합을 표현할 수 있다는 점을 보지 않고 혼자 "7개 8개 이상으로 숫자가 많으면 경우의 수가 너무 많은데 어떻게 표현하지?" 생각하며 끙끙댔습니다. 그러고 문제를 다시 보니 4개 이하로 표현한다는 부분을 읽었습니다...ㅎㅎㅎ 문제는 DP를 이용해 풀면 됩니다.  1. 인덱스에 해당하는 숫자가 몇 개로 표현이 가능한 지 개수를 저장하는 배열 dp[50001]을 생성합니다. 2. dp[0] = 0, dp[1] = 1 로 dp 배열을 초기화합니다. (0은 경우의 수가 없고, 1은 1*1 로 표현 가능) 3. 제곱수인 경우를 비교합니다. 즉 dp[i + j]의 값을 구할 때 j가 제곱수인..

https://www.acmicpc.net/problem/2579  DP를 통해 문제를 풀어나갑니다. 그러기 위해선 규칙을 찾아야 하는데, 늘 DP 문제는 규칙을 찾는게 일인 것 같습니다.연속으로 2번까지만 오를 수 있고, 두 칸을 오르는 것은 언제든 가능합니다. 그럼 n번째 계단까지 올랐을 때의 점수는 다음 두 가지가 나옵니다. 1. stair[n] + stair[n - 1] + stair[n - 3] : 계단을 연속으로 오르는 경우, i - 3번째 계단을 더하는 이유는 연속으로 한 칸 씩 올랐다는 점을 구분짓기 위함! 2. star[n] + stait[n - 2] : 계단을 두 칸 오르는 경우 위의 규칙을 이용하여 DP 방식으로 문제를 풀어나가면 됩니다.  #include int n;int stair..

https://www.acmicpc.net/problem/2096  단순히 다이나믹 프로그래밍을 생으로 두 번 돌리니까 메모리 초과가 떴습니다. (항상 문제를 제대로 확인합시다)슬라이딩 윈도우 알고리즘을 이용하면 해결됩니다. 코드 가독성도 좋던데, 진작에 이 알고리즘을 사용할걸 그랬습니다.  1. 최댓값을 저장하는 dp 배열과 최솟값을 저장하는 dp 배열을 저장합니다. 2. 이전 dp 값을 저장하는 pre_dp 배열을 생성합니다. 3. 다이나믹 프로그래밍을 이용하여 점수를 합합니다. 이 때 pre_dp 의 값을 비교하여 현재 dp 값을 구합니다. 4. 현재 dp 값을 구하면 pre_dp 값에 복사합니다.  #include int num[100000][3];int max_pre[3], max_cur[3];..

https://www.acmicpc.net/problem/1932  배낭 문제와 원리가 같은 다이나믹 프로그래밍(DP) 문제입니다. 최댓값을 구하는게 그나마 다른 점...?밑으로 진행할 수록 경우의 수가 하나씩 증가하는데, N번째 줄에서 연산하는 인덱스가 N - 1 을 넘지 않으므로 따로 초기화할 필요 없이 N * N 크기의 배열을 이용하면 됩니다.  1. 문제에서 입력받는 숫자들을 저장하는 2차원 배열과 합의 경우의 수를 줄마다 저장하는 2차원 배열 dp[][] 를 생성합니다. 2. 경우의 수를 저장하는 2차원 배열에 합을 저장할 건데, 이 때 저장하는 방법으로 이전 줄의 왼쪽과 오른쪽 숫자 중 그동안 누적 합이 더 큰 부분을 고른 후 현재 줄의 숫자를 더합니다. 다시 말해 더 큰 숫자를 고르는 것이 ..

https://www.acmicpc.net/problem/15989  이 문제의 다행(?)인 점이라면 순서를 포함하지 않는다는 것입니다. 세 가지의 숫자만으로 조합을 완성하기에 숫자 3을 기준으로 방법의 수를 구할 수 있습니다.   1. 1만으로 이루어진 방법의 수는 1가지입니다. 2. 2가 포함된 방법의 수는 n / 2(몫) 가지입니다. 예를 들어 n = 5인 경우, (2+1+1+1, 2+2+1)과 같이 2의 개수를 1부터 n으로 나눌 때 몫까지로 구분할 수 있습니다. 3. 3을 포함한 경우의 수는 n에 3을 연속적으로 빼고, 1번째 단계와 2번째 단계를 반복하여 구할 수 있습니다. 예를 들어 n = 5인 경우, 숫자 1과 2만으로 경우를 구해보면 (1+1+1+1+1, 2+1+1+1, 2+2+1) 세 ..