📌 문제 제목문제 링크: 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 1874🗒️ 문제 설명임의의 수열이 주어졌을 때, 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop연산을 수행해야 하는지 알아내는 프로그램스택에 push 하는 순서는 반드시 오름차순.시간 제한: 2초메모리 제한: 128MB1 같은 정수가 두 번 나오는 일은 없다.💡 문제 해결 아이디어push 하는 값을 저장하는 스택 필요입력된 수열을 순회하며 수열에 push 해야할 값과 비교push 해야할 값이 수열의 i번째 값보다 작거나 같을 때까지 값을 증가push 해야할 값이 수열의 i번째 값보다 크다면 스택의 마지막 원소와 i번째 값 비교같으면 pop다르면 NO⌛️ 시간 복잡도O(N)✅ 최종 코드import sysinput = sys.st..

📌 문제 제목문제 링크: 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..

1차원 배열에서 이중 for문으로 O(N^2)에 처리되는 작업을 2개의 포인터를 사용하여 O(N)에 해결하는 알고리즘연속된 구간의 원소들을 처리하거나 정렬된 배열에서의 작업을 구현할 때 시도📕 문제 1. 다음의 배열에서 원소들의 합이 x인 연속 부분 배열의 개수를 구하라.arr = [1, 3, 6, 5, 2, 7, 9], x = 9시작 시점을 한 칸씩 전진해나가면서 구간의 합을 구해야함. 📕 문제 2. 다음의 배열에서 두 개의 원소의 합이 x와 같은지를 확인하고, 같다면 각 원소의 인덱스를 반환하라.arr = [10, 4, 15, 11, 7, 5], x = 15이전 문제처럼 배열을 그대로 두고 st와 en 두 포인터를 0으로 잡으면 답을 찾을 수 없음.배열이 정렬되어 있지 않으면 다음에 올 값이 이전..