📌 백준 [1699]: 제곱수의 합🔗 문제 링크문제 설명 📄자연수 n이 주어졌을 때, 자연수들의 제곱수의 합으로 표현할 때 필요한 최소 개수를 구하시오.예를 들어 n=7일 때, 4+1+1+1로 4개의 제곱수의 합으로 표현할 수 있고, 이는 최소값이다.문제 접근 방식 💡동적 프로그래밍(DP)을 활용하여 최소 제곱수 개수를 계산.dp[i]를 자연수 i를 제곱수의 합으로 표현할 때 필요한 최소 개수로 정의.점화식:dp[i] = min(dp[i], dp[i - j*j] + 1) (j*j 초기값:dp[0] = 0.Solution 💻n = int(input())dp = [float('inf')] * (n + 1)dp[0] = 0for i in range(1, n + 1): j = 1 while ..
분류 전체보기
📌 백준 [11048]: 이동하기🔗 문제 링크문제 설명 📄N×M 크기의 미로가 주어진다. 각각의 칸에는 아이템의 개수가 적혀 있다.왼쪽 위에서 시작하여 오른쪽 아래까지 이동하려고 한다.이때, 한 번에 오른쪽, 아래쪽, 또는 대각선 아래로만 이동할 수 있다.아이템을 최대한 많이 줍기 위해 가져올 수 있는 아이템의 최대 개수를 구하시오.문제 접근 방식 💡동적 프로그래밍(DP) 배열 dp[i][j]를 사용하여 (i, j)까지 이동했을 때의 최대 아이템 개수를 저장.초기값: dp[0][0] = miro[0][0].점화식:dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + miro[i][j] (단, 경계를 벗어나지 않도록 조건 추가).Solution 💻n, ..
📌 백준 [11726]: 2×n 타일링🔗 문제 링크문제 설명 📄2×n 크기의 직사각형을 1×2와 2×1 타일로 채우는 방법의 수를 구하시오.결과를 10007로 나눈 나머지를 출력하시오.문제 접근 방식 💡동적 프로그래밍(DP)을 사용하여 타일 채우는 방법의 수를 계산.dp[i]를 2×i 크기의 직사각형을 채우는 방법의 수로 정의.점화식:dp[i] = dp[i-1] + dp[i-2]초기값:dp[1] = 1dp[2] = 2Solution 💻n = int(input())dp = [1] * nfor i in range(2, n): dp[i] = dp[i - 1] + dp[i - 2]print(dp[-1])시간 복잡도 분석 ⏲️시간 복잡도: O(n)1부터 n까지 반복문을 통해 DP 배열을 채움.공간 ..
📌 백준 [11057]: 오르막 수🔗 문제 링크문제 설명 📄수의 자릿수가 N이고, 각 자릿수가 0부터 9까지 증가하는 수를 오르막 수라고 한다.N이 주어졌을 때, 오르막 수의 개수를 10007로 나눈 나머지를 구하시오.문제 접근 방식 💡DP 테이블 dp[i][j]를 정의:i: 자리 수j: 마지막 자릿값이 j인 오르막 수의 개수점화식:dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + ... + dp[i-1][9]최종 결과:sum(dp[n-1]) % 10007Solution 💻n = int(input())dp = [[1] * 10 for _ in range(n)]for i in range(1, n): for j in range(10): dp[i][j] = sum..
📌 백준 [11727]: 2×n 타일링 2🔗 문제 링크문제 설명 📄2×n 크기의 직사각형을 1×2, 2×1, 2×2 크기의 타일로 채우는 방법의 수를 구하시오.결과를 10007로 나눈 나머지를 출력하시오.문제 접근 방식 💡동적 프로그래밍(DP)을 사용하여 타일 채우는 방법의 수를 계산.dp[i]를 2×i 크기의 직사각형을 채우는 방법의 수로 정의.점화식:dp[i] = dp[i-1] + dp[i-2] * 2초기값:dp[1] = 1dp[2] = 3Solution 💻n = int(input())dp = [0] * (n + 1)if n == 1: print(1)elif n == 2: print(3)else: dp[1] = 1 dp[2] = 3 for i in range(3, ..
📌 백준 [2579]: 계단 오르기🔗 문제 링크문제 설명 📄계단을 오를 때 다음 규칙을 따라야 한다:계단은 한 번에 한 계단 또는 두 계단씩 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다.마지막 계단은 반드시 밟아야 한다.각 계단에는 점수가 있으며, 계단을 밟을 때 그 점수가 더해진다. 계단의 점수가 주어질 때, 얻을 수 있는 총 점수의 최댓값을 구하시오.문제 접근 방식 💡동적 프로그래밍(DP)을 사용하여 최댓값을 계산.각 계단에서 얻을 수 있는 점수를 dp[i]로 정의.규칙을 만족하며 마지막 계단을 밟는 경우를 고려해 점수를 누적.Solution 💻stairs = [int(input()) for _ in range(int(input()))]if len(stairs) == 1: ..
📌 백준 [9095]: 1, 2, 3 더하기🔗 문제 링크문제 설명 📄정수 n이 주어졌을 때, 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.예를 들어, n=4라면 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1과 같이 7가지 방법이 있다.문제 접근 방식 💡재귀를 사용해 숫자를 1, 2, 3을 더해가며 n에 도달하는 모든 경우의 수를 계산.주어진 숫자를 초과하는 경우 탐색을 종료.최적화를 위해 재귀를 반복적으로 호출.Solution 💻count = int(input())def func(num): global answer global target if num == target: answer += 1 r..
📌 백준 [1463]: 1로 만들기🔗 문제 링크문제 설명 📄양의 정수 X가 주어질 때, 정수 X에 사용할 수 있는 연산은 다음과 같다:X가 3으로 나누어떨어지면, 3으로 나눈다.X가 2로 나누어떨어지면, 2로 나눈다.1을 뺀다.정수 X를 1로 만들기 위해 필요한 최소 연산 횟수를 구하라.문제 접근 방식 💡BFS(너비 우선 탐색)를 사용하여 최단 경로를 탐색.큐를 활용해 상태를 저장하고, 방문 여부를 체크하여 중복 계산 방지.Solution 💻from collections import dequeinput = int(input())q = deque()pattern = {}q.append((input,0))while q: p,count = q.popleft() if p in pattern..
