반응형 코딩테스트 준비211 C# - 완전 탐색(Brute force, 백트래킹,순열 조합,비트 마스크) 완점 탐색 모든 가능한 경우의 수를 탐색하여 최적의 결과를 찾는 방법이다. 01 브루트 포스(Brute force) 모든 가능한 결우를 순차적으로 나열하면서 원하는 결과를 찾는 방법이다. 예시 : 비밀번호 02 순열(Permutation) 선택 순서가 결과에 영향을 미치는 경우에 사용하는 방법이다. 03 조합(Combination) 선택 순서가 결과에 영향을 주지 않는 경우에 사용하는 방법이다. 04 백트래킹(BackTracking) 현재 상태에서 가능한 후부군으로 가지를 치며 탐색하는 알고리즘이다. 해가 될 것 같지 않은 경로는 더 이상 탐색하지 않고 되돌아간다. 예시 : 스도쿠 05 비트 마스크(Bit Mask) 이진수의 각 비트를 사용하여 경우의 수를 줄여가며 탐색하는 방법이다. 예시 : 부분 집합.. 2023. 12. 8. 백준 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. 이전 1 ··· 6 7 8 9 10 11 12 ··· 36 다음 반응형
