📌 문제 제목문제 링크: BOJ 12852🗒️ 문제 설명정수 X에 사용할 수 있는 연산X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.세 개의 연산을 사용해 정수 N을 1로 만들려고 할 때, 연산을 사용하는 횟수의 최솟값을 구하여라.출력에는 연산을 하는 횟수의 최솟값과 N을 1로 만드는데 포함되어있는 수를 공백으로 구분해서 출력시간 제한: 0.5초메모리 제한: 512MB1 💡 문제 해결 아이디어BFS와 DP를 사용하여 해결 가능# BFS 사용dist[i]는 N을 i로 만들려고 할 때, 연산의 최솟값.prev[i]는 N을 i로 만들려고 할 때, i 직전에 들러야 하는 값# DP 사용테이블 정의dp[i]는 1을 i로 만들려고 할 때, 연산의 최솟값prev..

📌 문제 제목문제 링크: BOJ 11659🗒️ 문제 설명수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램시간 제한: 1초메모리 제한 256MB1 1 1 e.g.입력5 3 # N과 M (N: 수의 개수, M: 합을 구해야 하는 횟수)5 4 3 2 1 (수열 N)1 3 (i, j)2 4 (i, j)5 5 (i, j)출력12 (5 + 4 + 3)9 (4 + 3 + 2)1 (1)💡 문제 해결 아이디어N과 M이 최대 100,000이기 때문에 시간 복잡도 O(N log N)의 알고리즘 필요i부터 j까지의 합은 1부터 j까지의 합 - 1부터 i-1 까지의 합테이블 정의dp[i]는 1번째 값부터 i번째 까지의 합점화식 찾기dp[i] = dp[i-1] + seq[i]⌛️ 시간 복잡도O(N+..

📌 문제 제목문제 링크: BOJ 11726🗒️ 문제 설명2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램2xn 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력시간 제한: 1초메모리 제한: 256MB1 💡 문제 해결 아이디어테이블 정의dp[i]는 2xi 크기의 직사각형을 채우는 방법의 수점화식 찾기2xi 크기의 직사각형이 있을 때, 왼쪽 위를 2x1 크기의 직사각형으로 채우는 경우2xi 크기의 직사각형이 있을 때, 왼쪽 위를 1x2 크기의 직사각형으로 채우는 경우※ dp[i] = dp[i-1] + dp[i-2]초기값 정하기dp[1] = 1, dp[2] = 2⌛️ 시간 복잡도O(N)✅ 최종 코드import sysinput = sys.stdin.r..

📌 문제 제목문제 링크: BOJ 1149🗒️ 문제 설명RGB거리에는 N개의 집이 1번부터 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 칠하는 비용이 주어졌을 때, 아래의 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하여라.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2시간 제한: 0.5초메모리 제한: 128MB2 집을 칠하는 비용 💡 문제 해결 아이디어테이블 정의dp[i]는 i번째 집까지 칠할 때의 최소 비용dp[i][0]은 i번째 집이 빨강dp[i][1]은 i번째 집이 초록dp[i][2]는 i번째 집이 파랑점화식 찾기dp[1]dp[1][0] = costs[0][0]dp[1][1] = co..

📌 문제 제목문제 링크: BOJ 2579🗒️ 문제 설명계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다.각 계단에는 점수가 쓰여있고 그 계단을 밟으면 점수를 얻게 된다.다음과 같이 도착점까지 간다면 10 + 20 + 25 + 20 = 75점을 얻게 된다.계단을 오르는데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안된다.마지막 도착 계단은 반드시 밟아야 한다.각 계단에 쓰여있는 점수가 주어질 때, 이 게임에서 얻을 수 있는 점수의 최댓값을 구하여라.시간 제한: 1초메모리 제한: 128MB계단의 개수 계단에 쓰여있는 각 점수 💡 문제 해결 아이디어마지막 계단을 무조건 밟아야 하므로 마지막..

📌 문제 제목문제 링크: BOJ 9095🗒️ 문제 설명정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하여라.e.g. 4를 1, 2, 3으로 나타내는 방법은 총 7가지 이다.1 + 1 + 1 + 11 + 1 + 21 + 2 + 12 + 1 + 12 + 21 + 33 + 1시간 제한: 1초메모리 제한: 512MB1 💡 문제 해결 아이디어테이블 정의d[i]는 i를 1, 2, 3으로 만들 수 있는 방법의 수점화식 찾기d[4]1+1+1+1, 1+2+1, 2+1+1, 3+1 -> d[3]을 만드는 방법 + 11+1+2, 2+2 -> d[2]를 만드는 방법 + 21+3 -> d[1]을 만드는 방법 + 3※ d[4] = d[1] + d[2] + d[3]초기값 정하기d[1] = 1d[..

📌 문제 제목문제 링크: BOJ 1463🗒️ 문제 설명정수 X가 할 수 있는 연산X가 3으로 나누어 떨어지면 3으로 나눈다.X가 2로 나누어 떨어지면 2로 나눈다.1을 뺀다.정수 N을 1로 만들려고 할 때, 연산의 최솟값을 구하여라.시간 제한: 1.5초메모리 제한: 128MB1 💡 문제 해결 아이디어N이 최대 1,000,000이기 때문에 시간복잡도가 O(N)이하의 알고리즘을 사용연산 횟수를 저장할 N+1 길이의 배열을 만들어서 사용BFS와 DP를 사용하면 풀 수 있다.# BFS 사용-1을 가지는 N+1 길이의 dist 배열 정의dist[N] = 0으로 초기화queue에 N을 넣고 BFS 수행queue를 popleft()해서 xp를 구한 후 위의 세 연산을 수행한 값이 integer라면 dist[re..

여러 개의 하위 문제를 먼저 푼 후, 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘문제를 해결하기 위한 점화식을 먼저 찾아낸 후, 점화식의 항을 밑에서부터 차례로 구해나가면서 답을 알아내는 알고리즘풀이 과정테이블 정의하기점화식 찾기초기값 정하기📕 문제 1. 피보나치 수열재귀에서의 피보나치 수열은 중복된 연산이 계속 발생.e.g. fibo(5) = fibo(4) + fibo(3) = fibo(3) + fibo(2) + fibo(3) = ...이미 구했던 값을 계속 연산하기 때문에 O(1.1618^N)의 시간복잡도를 가짐def fibo(n): if n 피보나치 수열 문제를 DP로도 해결할 수 있음.미리 배열을 만들어두고 인덱스를 채워나가는 방식으로 해결 가능시간복잡도 O(N)def fibo(n): a..