본문 바로가기
반응형

코딩테스트 준비211

백준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.
백준 C# - 1463 +) 풀이 DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작은 부분 문제로 나누어 해결하며 이미 계산된 작은 문제의 결과를 메모 code-piggy.tistory.com 풀이 DP의 점화식을 구해보자 dp[i] = dp[i - 1] + 1 // 1을 빼는 경우 dp[i] = min(dp[i], dp[i / 2] + 1) // 2로 나누는 경우 dp[i] = min(dp[i], dp[i / 3] + 1) // 3으로 나누는 경우 왜 점화식 끝에 1을 더해요? dp[i]는 i를 1로 만들기 위해 필요한 최소 연산 횟수를 나타내므로 각각의 연산이 수행될때마다 count하는 .. 2023. 11. 27.
C# - 퀵 정렬(Quick Sort) 퀵정렬(Quick Sort) 퀵 정렬에서는 피벗(Pivot)을 기준으로 배열을 분할하고, 각 부분 배열에 대해 정렬 작업을 수행하지만 피벗을 다시 처리하는 부분 문제는 호출하지 않는다. 한 번 피벗의 위치가 정해지면 해당 피벗은 정렬이 완료된 것으로 취급되어 중복 계산이 발생하지 않는다. 핵심 : 키 값을 잡아 더 큰것과 더 작은것 바꾸기 01 피벗 선택 퀵 정렬의 핵심은 피벗(pivot)을 선택하는 것이다. 피벗은 배열의 원소 중에서 하나를 선택한다. 피벗 선택의 효율성이 정렬 속도에 영향을 미친다. 02 분할 선택된 피벗을 기준으로 배열을 두 부분으로 분할한다. 피벗보다 작은 값은 피벗의 왼쪽으로, 큰 값은 피벗의 오른쪽으로 배치된다. 분할 과정 후에는 피벗의 위치가 최종적으로 결정된다. 03 정복 .. 2023. 11. 27.
백준 C# - 11653 소인수 개념만 알면 금방 풀 수 있는 문제이다. 코드 전문 using System; namespace baek2 { class Program { static void Main(string[] args) { int n = int.Parse(Console.ReadLine()); int a = 2; for(int i = 0; i 2023. 11. 27.
백준 C# - 11576 +)풀이 문제를 푸는 시간보다 문제를 이해하는 시간이 더 오래 걸린 문제였다. 예제를 이용해서 문제를 이해해보자 17 8 2 2 16 01 첫 줄 17은 진법 A, 8은 진법 B이다. 02 두번째 줄 입력에 나오는 설명은 A진법으로 나타낸 숫자의 자리수의 개수 m이라고 하는데 무슨 말인지 이해가 안갔다. 그냥 간단하게 변환해야할 숫자의 개수이다. 03 세번째 줄 두번째 줄에서 변화해야할 수의 갯수를 받았으니까 해당 하는 수들이다. 풀이 01 A진법을 10진수로 변환 string[] token = Console.ReadLine().Split(); int a = int.Parse(token[0]); int b = int.Parse(token[1]); int m = int.Parse(Console.ReadLine()).. 2023. 11. 27.
반응형

티스토리툴바