본문 바로가기
반응형

코딩테스트 준비/백준 C#161

백준 C# - 9465 +) 풀이 DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작은 부분 문제로 나누어 해결하며 이미 계산된 작은 문제의 결과를 점화식 구하기 처음에 점화식을 구하고 풀었는데 틀렸다. 1칸이 떨어진 경우와 2칸이 떨어진 경우 두가지 경우를 생각해야 했다. 예제를 예시로 보면 100에서 60사이에는 두 칸이 떨어져 있는 것을 확인할 수 있다. 점화식을 세워보자 1칸 , 2칸을 비교해서 큰 값을 dp에 넣으면 된다. 점화식 코드 전문 using System; namespace baek2 { class Program { public static void Main() { int n.. 2023. 12. 7.
백준 C# - 11057 DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작은 부분 문제로 나누어 해결하며 이미 계산된 작은 문제의 결과를 점화식 구하기 이번 문제는 점화식을 쉽게 구할 수 있다. 한번 1일 경우와 2일경우를 쭉 쓰다보면 0에서는 1-9까지 1에서는 2-8까지 이런식으로 더해지는 것을 확인할 수있다. 그래서 아래와 같이 점화식을 구해서 제출했는데 바로 통과했다! dp[i, 0] = (dp[i - 1, 0] + dp[i-1, 1]+ dp[i - 1, 2] + dp[i - 1, 3] + dp[i - 1, 4] + dp[i - 1, 5] + dp[i - 1, 6] + dp[.. 2023. 12. 7.
백준 C# - 1309 +) 풀이 DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작은 부분 문제로 나누어 해결하며 이미 계산된 작은 문제의 결 점화식 구하기 01 일단 적어보자 N = 1,2,3이였을 경우의 수를 다 적어보자 그러면 아래와 같이 나온다. 02 표로 정리 표를 확인해보면 관계성을 구할 수 있으므로 아래와 같은 점화식이 나온다. 02 % 9901 모듈려 연산 C# - 모듈러 연산(나머지 분배 법칙) 백준에서 DP관련 문제를 풀때 출력 부분에 큰 수로 나눈 나머지를 구하라는 부분이 계속 있어서 이부분이 왜 필요한지 자세히 알고 싶어졌다. 모듈러(Modulo) 나눗셈의 나머지를 계산.. 2023. 12. 4.
백준 C# - 1149 +) 풀이 DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작은 부분 문제로 나누어 해결하며 이미 계산된 작은 문제의 결과를 점화식 구하기 01 일단 작성해보자 예제 1번을 가지고 한 번 적어본 후에 관계성을 구해보았다. N = 1, N = 2, N = 3 차근차근 최솟값을 구하면서 다음 N을 구하면 되는 것을 밑에 오른쪽표에서 확인할 수 있다. 02 점화식 구하기 위의 관계성을 통해 아래와 같이 점화식을 구할 수 있다. 코드 전문 using System; namespace baek2 { class Program { public static void Main() { in.. 2023. 12. 4.
백준 C# - 15988 +) 풀이 이 문제를 풀기 앞서 아래 문제를 먼저 풀고 오는 것을 추천한다. 백준 C# - 9095 백준 C# - 9095 +)풀이 DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작 code-piggy.tistory.com 점화식 부분은 9095와 동일하다. 01 케이스 T 다른 부분이 있다면 케이스 T가 추가되었다. while (T > 0) { int N = int.Parse(Console.ReadLine()); Console.WriteLine(dp[N-1] % 1000000009); T--; } 02 % 1000000009 모듈려 연산 C# - 모듈러 연산(나머지 .. 2023. 12. 4.
백준 C# - 10844 +)풀이 DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작은 부분 문제로 나누어 해결하며 이미 계산된 작은 문제의 결과를 문제를 풀기 앞서 문제를 먼저 이해해보자 (문제 이해하기가 제일 어렵다..) N = 자릿수 문제에서 N이 주어질때 길이가 N인 계단수라고 했는데 이 말이 무슨말인지 이해가 안갔다. 결과적으로 자릿수였다. 점화식 구하기 01 일단 써보자 DP문제는 점화식을 구하기 위해 일단 써보는 수 밖에 없다. N = 1일때는 한 자릿수 숫자인 계단수를 구하고 N = 2일때는 두 자릿수 숫자인 계단수를 구해보면 아래 왼쪽 사진과 같이 나타낼 수 있다. 그리고 이를.. 2023. 12. 2.
반응형

티스토리툴바