반응형 코딩테스트 준비/백준 C#167 백준 C# - 1107 +) 풀이 먼저 시간 복잡도를 살펴보자시간 제한: 2초일반적으로 1초에 약 1억 번 연산이 가능하다고 본다.이 문제에서 탐색할 채널 범위는 0 ~ 1000000 (약 100만 개) 그러므로 각 채널에 대해 최대 6자리의 숫자를 확인하는 작업이 필요하다. 따라서 전체적인 경우의 수는 100만 × 6 = 600만이므로 충분히 통과 가능하다.→ 완전탐색(Brute Force)으로 접근해도 문제 없음! 왜 1000000까지 탐색할까?단순히 N = 500000이라면 500000까지 탐색하면 되는거 아니야?→ 그렇지 않다!만약 고장난 버튼 때문에 500000부터 999999까지 전부 누를 수 없다면 입력 가능한 수는 훨씬 멀리 떨어진 곳일 수 있다. 숫자 버튼만으로 누를 수 있는 가장 큰 채널은 999999 → 6자리이다. .. 2025. 6. 11. 백준 C# - 2225 +) 풀이 문제0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제이다.여기서 중요한 부분은 "0"부터 포함된다는 것이다. 그러므로 정수 1개로 0을 만드는 경우의 수도 1가지 존재한다. k = 사용할 정수의 개수n = 목표 합계 점화식 생각1. dp[k,n] 배열에 어떤 값을 넣을까?dp[k,n] = 정수 k개로 합이 n이 되는 경우의 수이다.2. i를 만들기 위해 바로 전 단계는 뭘까?1) 마지막 수가 0인 경우 2) 마지막 수가 1이상인 경우점화식dp[k,n] = dp[k-1,n] + dp[k,n-1];1) dp[k-1,n]정수 k개 중 하나가 0일때 나머지 k-1개로 n을 만들어야한다.2) dp[k,n-1]합이 n이 되도록 정수 k개를 만드려면 합이 n-1인 경우에 +1씩 해서 .. 2025. 4. 16. 백준 C# - 1699 +) 풀이 문제정수 n이 주어졌을때 n을 제곱수들의 합으로 표현하는 방법 중에서 항의 개수가 최소인 경우의 수를 구해야한다.예시12 = 4 + 4 + 413 = 9 + 4 점화식 생각01 dp[] 배열에 어떤 값을 넣을까?i를 만들기 위한 최소 제곱수들의 합으로 표현할 때 필요한 항의 수02 i를 만들기 위해 바로 전 단계는 뭘까?이미 dp[i-j*j]값을 알고있음 그래서 이번 값에서 + 1그래서 나온 점화식dp[i] = min(dp[i-j²]+1) (단 j²예시) n = 5- dp[1]가능한 j: 1 (1²)dp[1] = min(dp[1], dp[1 - 1] + 1) = min(∞, dp[0] + 1) = 1dp[1] = 1- dp[2]가능한 j: 1 (1²)j=1: dp[2] = min(dp[2], dp[1] .. 2025. 4. 16. 백준 C# - 14002 +) 풀이 문제를 읽어보면입력이 1000이니까 1000*1000 = 1000000(백만)이므로 O(N²) 알고리즘으로도 이 문제는 충분히 통과 가능하다. 알고리즘01 문제 분석가장 긴 증가하는 부분수열 거의 동일하지만 한 가지 추가된 조건이 있다.단순히 수열의 길이만 구하는 것이 아니라 그 실제 수열의 내용도 출력해야한다. 02 경로 복원(Path Reconstruction)그 값을 만들기 위해 어떤 선택을 했는지를 저장해서 실제해를 구성할 수 있게 하는 방법이다. 경로 복원에 대한 정보 저장 - prev 배열prev[i] = dp[i]를 만들기 위해 선택된 이전 인덱스, 즉 dp[i]가 dp[j]+1로 갱신되었으면 prev[i] = j를 저장하는 것이다.10 20 10 30 20 50ilist[i] dp[i]pr.. 2025. 4. 11. 백준 C# - 15990 +) 풀이 문제 설명정수 N을 1,2,3 합으로 표현하는 방법의 수 조건 : 같은 수를 연속으로 두 번 이상 사용하면 안된다."1 + 1 + 2" ❌"1 + 2 + 1" ✅조건이 없는 경우 (연속된 숫자가 올 수 있는 경우) 백준 C# - 9095 +)풀이DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작code-piggy.tistory.com점화식dp[n] = dp[n-1] + dp[n-2] + dp[n-3]조건이 있는 경우(연속된 숫자가 올 수 없는 경우)마지막 숫자만 확인하여 겹치게만 안하면 된다는 것이다. 다른말로 마지막 숫자만 체크하면 된다. dp[n][1] .. 2025. 4. 10. 백준 C# - 11053+) 풀이 문제풀이에 앞서 문제에서 제시된 시간복잡도를 분석해보자 제한 시간이 1초 → 일반적으로 연산량 1억 이내 가능하므로 입력에서 N의 크기가 1000이므로 O(N²)까지 허용된다.이 문제를 풀기 앞서 LIS 개념을 알고 풀이를 진행하자LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)란?수열에서 일부 원소를 "순서를 유지한 채"골라서 값이 점점 증가하도록 만든 부분 수열 중 가장 긴 길이의 구하는 문제이다.단 연손된 값일 필요는 없고, 앞에 선택된 값보다 커지기만 하면 된다. 예시[10, 20, 10, 30, 20, 50]→ 가장 긴 증가하는 부분 수열: 10 20 30 50 (길이 4) LIS은 전형적인 DP 문제이다.dp의 배열안에는 dp[i] : i번째 원소를.. 2025. 4. 9. 이전 1 2 3 4 5 ··· 28 다음 반응형
