본문 바로가기
반응형

코딩테스트 준비211

C# - 모듈러 연산(나머지 분배 법칙) 백준에서 DP관련 문제를 풀때 출력 부분에 큰 수로 나눈 나머지를 구하라는 부분이 계속 있어서 이부분이 왜 필요한지 자세히 알고 싶어졌다. 모듈러(Modulo) 나눗셈의 나머지를 계산하는 연산이다. 일반적으로 mod 혹은 %기호료 표시된다. a mod b = r a = 나눠지는수, b = 나누는 수, r 나머지 모듈러 연산과 분배법칙 어떤 수 m으로 나누었을 때 나머지는 덧셈에 대해 분배된다. ( a + b ) mod m = (( a mod m )+( b mod m )) mod m 예시 ( 7 + 5 ) mod 3=(( 7 mod 3 )+( 5 mod 3 )) mod 3 12 mod 3 = ( 1 + 2 ) mod 3 0 = 3 mod 3 DP에서 왜 모듈러 연산을 사용할까? 중간에 발생하는 값들이 매우.. 2023. 12. 4.
백준 C# - 10844 +)풀이 DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작은 부분 문제로 나누어 해결하며 이미 계산된 작은 문제의 결과를 문제를 풀기 앞서 문제를 먼저 이해해보자 (문제 이해하기가 제일 어렵다..) N = 자릿수 문제에서 N이 주어질때 길이가 N인 계단수라고 했는데 이 말이 무슨말인지 이해가 안갔다. 결과적으로 자릿수였다. 점화식 구하기 01 일단 써보자 DP문제는 점화식을 구하기 위해 일단 써보는 수 밖에 없다. N = 1일때는 한 자릿수 숫자인 계단수를 구하고 N = 2일때는 두 자릿수 숫자인 계단수를 구해보면 아래 왼쪽 사진과 같이 나타낼 수 있다. 그리고 이를.. 2023. 12. 2.
백준 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.
반응형

티스토리툴바