반응형 코딩테스트 준비/백준 C#161 백준 C# - 2193 +) 풀이 DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작은 부분 문제로 나누어 해결하며 이미 계산된 작은 문제의 결과를 점화식 찾기 01 일단 적어보기 DP문제는 점화식을 구해야 하는데 일단 적어보고 어떤식으로 반복되는지 찾아야한다. 02 점화식 찾기 위의 적어 놓은 것을 표로 정리하면 아래와 같다. 각각의 0과 1이 어떻게 나오는지 살펴보면 0의 갯수는 앞의 0과 1의 갯수의 합이고 1의 갯수는 앞의 0의 갯수임을 알 수 있다. 그러므로 점화식은 아래와 같이 표시할 수 있다. 주의! int형을 쓰면 안된다 90자리 이친수의 개수 2,880,067,194,370,8.. 2023. 12. 2. 백준C# - 16194 +) 풀이 이 문제를 풀기 앞서 아래 문제를 먼저 풀어보는 것을 추천한다. 백준 C# - 11052 백준 C# - 11052 +) 풀이 DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작 code-piggy.tistory.com 11052번을 풀었음을 전제로 풀이를 진행 01 Max를 Min으로 바뀌어서 제출 문제에서 최솟값을 구하니까 Max를 Min로 제출하면 되겠다 싶어서 바꿨더니 결과가 0으로만 나왔다. p[i] = Math.Max(dp[i], dp[i - j] + p[j]); 02 기준값을 잡자 1씩 더해지는 경우를 기준으로 잡았다. dp[i] = dp[i-1] .. 2023. 12. 1. 백준 C# - 11052 +) 풀이 DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작은 부분 문제로 나누어 해결하며 이미 계산된 작은 문제의 결과를 풀이 점화식 찾기 01 손으로 적어보자 dp와 Pn과의 관계를 한 번 손으로 적어보면 아래와 같이 나오는 것을 확인할 수 있다. 02 점화식 위의 경우의수들 중 제일 큰 값을 골라서 dp[i]에 넣어주면 된다. 그러므로 점화식을 구해보면 아래와 같이 나온다. 코드 전문 using System; namespace baek2 { class Program { static void Main() { int num = int.Parse(Console.Read.. 2023. 11. 30. 백준 C# - 9095 +)풀이 DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작은 부분 문제로 나누어 해결하며 이미 계산된 작은 문제의 결과를 풀이 01 점화식 찾기 n= 1,2,3,4일때를 직접 그리면 서로의 관계를 찾아 볼 수 있다. 아래 그림을 보면 n = 4에서 n = 1,2,3의 조합으로 만들어지는 것을 확인할 수 있다. 점화식 코드 전문 using System; namespace baek2 { class Program { static void Main() { int num = int.Parse(Console.ReadLine()); while(num>0) { int n = int.. 2023. 11. 30. 백준C# - 11727 +) 풀이 이 문제를 풀기 앞서 아래 문제를 먼저 풀고 오는 것을 추천한다. 백준 C# - 11726 백준 C# - 11726 +) 풀이 DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작 code-piggy.tistory.com 11726을 풀고 나서 아래의 점화식을 얻었다. 2x2와 관련된 부분만 추가해주면 된다. (자세한 설명은 11726페이지 참조) 01 2x2 끝에 부분이 2x2인 경우의 수는 dp[i-2]와 같으므로 원래 있던 점화식에 이 부분만 추가해 주면 된다. 코드 전문 using System; namespace baek2 { class Program {.. 2023. 11. 30. 백준 C# - 11726 +) 풀이 DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작은 부분 문제로 나누어 해결하며 이미 계산된 작은 문제의 결과를 메모 code-piggy.tistory.com 풀이 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제이다. 그림에서 보면 끝에 부분이 2x1인 경우와 2x2인 2가지 경우로 나누어진다는 것을 확인할 수 있다. 01 2x1 2x1로 고정되어 있는 경우 경우의 수는 그 자리를 제외한 (n-1)!과 같다. 하지만 우리는 그 값을 dp[i-1]에 저장해놓았으므로 dp[i]에 그 값을 더해준다. 02 2x2 2x2로 고정되어 .. 2023. 11. 29. 이전 1 ··· 5 6 7 8 9 10 11 ··· 27 다음 반응형
