Algorithm/Dynamic Programming(DP, 동적 프로그래밍)
-
[백준 10844번] 쉬운 계단 수 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 5. 30. 15:16
백준알고리즘 10844번 : 쉬운 계단 수 (Solved.ac 난이도 Silver1) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP(Dynamic programming) 문제이다. 초항의 길이별 정답을 통해 규칙을 찾고, 그 규칙들로 길이 N인 계단 수를 찾을 수 있다. 규칙을 찾기위해 자리 길이가 1일때와 2일때를 계산해보았다. N=1일때 경우의수? 1~9 까지 총 9가지(0으로 시작하는 수는 계단 수가 아님) N=2일 경우의 수? 맨 뒤에 9가 붙는 경우(앞에 8이 있는 갯수) - 1 맨 뒤에 8이 붙는 경우 (앞에 7,9가 있는 갯수) 맨 뒤에 ..
-
[백준 2193번] 이친수 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 4. 20. 20:05
백준알고리즘 2193번 : 이친수 (Solved.ac 난이도 Silver3) https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 규칙을 찾고나면 어렵지 않게 풀 수 있는 문제같다. 그리고 규칙을 찾는 방법은 작은 경우에서부터 하나씩 크기를 늘리면서 앞전 경우와 연결되는 연속성을 발견하는 것이다. 예를 들어 3자리 숫자일때와 4자리 숫자일때를통ㅇ해 규칙을 찾아보자. 3자리 숫자일때는 100, 101로 총 2가지 경우의 수가 있다. 4자리 ..
-
[백준 1149번] RGB거리 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 4. 8. 10:43
백준알고리즘 1149번 : RGB거리 (Solved.ac 난이도 Silver1) 집을 빨강, 초록, 파랑색으로 칠할 때, 그 최소비용을 구하는 문제이다. ↑클릭시 문제 link로 이동합니다.😊 집이 N개 있을 때, N번째 집이 나올 수 있는 색깔의 경우의수를 따져보자. 1. N번째 집이 R(Red)일때, N-1번째 집은 G(Green) or B(Blue)여야한다. 2. N번쨰 집이 G일때, N-1번째 집은 R or B여야한다. 3. N번째 집이 B일때, N-1번째 집은 R or G여야한다. 이것을 각각의 배열로 만들어서 매 회마다 N번째 집이 R일때의 최소 비용, G일때의 최소 비용, B일때의 최소 비용만 선택적으로 따오도록 한뒤, 마지막에 R[N-1], G[N-1], B[N-1]의 비용중 가장 작은 수..
-
[백준 2579번] 계단 오르기 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 4. 7. 18:59
백준알고리즘 2579번 : 계단 오르기 (Solved.ac 난이도 Silver3) 계단을 오를 때 얻을 수 있는 점수의 최댓값을 출력하는 문제이다. ↑클릭시 문제 link로 이동합니다.😊 문제를 푼 후기들을 검색해보면 구현자체는 쉬웠다고하는데 나는 동적 프로그래밍이 아직 익지 않아서 그런지 규칙을 찾고 그것을 쪼개는 게 너무 어려웠다. 처음에는 그리디 알고리즘으로 풀어보려고하였으나, 한번 구현해본 뒤 안된다는 것을 알고 포기. 그리디 알고리즘을 적용하기 위해서는 내가 짠 로직의 결과값이 변화가 없어야하는데, 이 문제는 그렇게 되지 않는다. 예를들어서 계단이 다음과 같이 있다면 [1 2 3 4] 내가 밟아야하는 계단은 (1, 3, 4) 로 총 8점이다. 나는 이걸 딴에는 그리디 알고리즘으로 적용하고자하여,..
-
[백준 9095번] 11726번 : 2xn 타일링 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 3. 30. 19:35
백준알고리즘 11726번 : 2xn 타일링 (Solved.ac 난이도 Gold5) 요약 : 피보나치 수열의 규칙이 있는 DP 문제 ↑클릭시 문제 link로 이동합니다.😊 이 문제는 Dynamic Program 알고리즘 중 Top-down 방식으로 풀어보았다. 큰 단위를 작은 단위의 문제로 쪼개서 풀어야하는데, 내가 적절하게 잘 쪼개는지를 검증하기위해 최소 단위를 내가 직접 풀어보았다. 2xN 의 면적을 1x2의 타일과, 2x1의 타일로 채울 수 있는 집합의 개수를 구하는 문제이다. 따지고보면 경우의 수를 구하는 문제인데, 2x3의 타일부터 규칙이 생길것으로 판단되니(타일의 최대길이가 2이므로) 2x1과 2x2의 경우의 수를 구하고, 2x3의 경우의수가 하위 갯수의 집합의 합이 되는 DP로 구성되는지 검증..
-
[백준 9095번] 1, 2, 3 더하기 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 3. 28. 20:50
백준알고리즘 9095번 : 1, 2, 3 더하기 (Solved.ac 난이도 Silver3) ↑클릭시 문제 link로 이동합니다.😊 DP(Dynamic Programming), 동적 프로그래밍의 기본 문제이다. 동적 프로그래밍을 풀이하는데에는 Bottom-up 방식과 Top-down 방식이있다. 이 문제는 Bottom-up 방식으로 풀어보았다. 문제를 작은 단위의 문제로 쪼개서 풀어야하는 만큼, 최소 단위 정도는 내가 직접 풀어보아야한다. 이 문제는 1,2,3의 숫자만 이용하여 만들수 있는 집합의 개수를 구하는 문제이다. 4부터는 '1+ [3으로 만들 수 있는 집합의 개수] / 2 + [2로 만들 수 있는 집합의 개수] / 3 + [1으로 만들 수 있는 집합의 개수]'로 쪼갤 수 있기때문에, 3까지만 내가..