🔗 문제 링크 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr📌 문제 개요피보나치 수열은 다음과 같은 규칙을 가진다. n번째 피보나치 수를 구한 뒤, 1234567로 나눈 나머지를 반환하는 문제이다.F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2)📌 접근 방법처음에는 DP 배열을 사용하여 모든 피보나치 값을 저장할 수 있다.arr[i] = arr[i - 1] + arr[i - 2];하지만 현재 값을 계산할 때 필요한 것은 직전 두 개의 값뿐이다.따라서 배열 대신 두 개의 변수만 사용하여 공간을 절약할 수 있다.또한 피보나치 수는 매우 빠르게 증가하므로 매 계산마다 1234567로 나눈 나..

🔗 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/12983📌 문제 개요주어진 단어 조각들을 이용해 문자열을 완성하는 문제이다.각 단어는 무한히 사용할 수 있으며, 최소 개수로 문자열을 구성해야 한다. 📌 접근 방법문자열을 앞에서부터 구성하는 DP 문제dp[i]를 i까지 문자열을 만들 때 필요한 최소 단어 개수로 정의단어 최대 길이가 5이므로 뒤에서 최대 5글자만 확인📌 핵심 아이디어문자열 최소 분할 문제 = DP점화식 : dp[i] = min(dp[i - len] + 1) 조건 : t.substring(i-len, i) 가 strs 에 포함되어야 함Set을 사용하여 탐색 최적화📌 전체 코드import java.util.*;cla..

🔗 문제 링크https://www.acmicpc.net/problem/9461📌 문제 개요파도반 수열은 특정 규칙을 따르는 수열이다.주어진 N에 대해 N번째 값을 구해야 한다. 여러 개의 테스트 케이스가 주어지며, 각각 결과를 출력한다.📌 접근 방법DP 배열을 이용해 수열을 미리 계산최대 N이 100이므로 한 번만 계산하면 충분이후 입력받은 값에 대해 바로 출력📌 핵심 아이디어점화식 : P[n] = P[n-2] + P[n-3]초기값 : P[1] = 1, P[2] = 1, P[3] = 1값이 커지므로 long 사용📌 전체 코드package no_9461;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStre..

🔗 문제 링크 https://www.acmicpc.net/problem/4008📌 문제 개요병사들을 연속된 구간으로 나누고,각 구간의 합을 x라고 할 때 ax² + bx + c의 점수를 계산하여전체 점수의 최댓값을 구하는 문제 단순하게 모든 구간을 고려하면 시간복잡도가 O(N²)이 되어N = 1,000,000에서 절대 풀 수 없다.📌 접근 방법이 문제의 핵심은 DP + 식 변형 + CHT 최적화입니다.먼저 누적합을 정의합니다.S[i] = x1 + x2 + ... + xi그러면 구간 합은 다음처럼 계산됩니다.구간 합 = S[i] - S[j]이제 DP를 정의합니다.dp[i] = 1 ~ i까지 최대 점수점화식: dp[i] = max(dp[j] + f(S[i] - S[j])) 여기서 그대로 계산하면 O(N..

🔗 문제 링크https://www.acmicpc.net/problem/1149📌 문제 개요백준 1149번 RGB 거리는 각 집을 빨강, 초록, 파랑 중 하나로 칠할 때인접한 집은 같은 색을 사용할 수 없다는 조건에서 전체 비용의 최솟값을 구하는 문제입니다. 📌 접근 방법이 문제는 대표적인 DP 기초 문제입니다.각 집마다 3가지 선택지가 있으므로 이전 상태를 기반으로 누적해 나가면 됩니다. DP 정의 : dp[i][color] = i 번째 집까지 고려했을 때 최소 비용 📌 핵심 아이디어현재 집을 특정 색으로 칠하려면이전 집은 다른 색이어야 합니다.📌 점화식dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + cost[i][0];dp[i][1] = Math.min(dp[..

🔗 문제 링크https://www.acmicpc.net/problem/2748📌 문제 개요피보나치 수열에서 N번째 값을 구하는 문제이다.피보나치 수열은 다음과 같은 규칙을 가진다.F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2)N의 범위가 최대 90이므로 일반적인 재귀 방식은 비효율적📌 접근 방법피보나치 수는 이전 두 값을 이용해 계산할 수 있으므로배열 대신 두 개의 변수만 사용해서 해결할 수 있다. 또한 반복문을 사용하면 시간복잡도를 O(N)으로 줄일 수 있다.📌 핵심 아이디어피보나치는 이전 값 2개만 알면 계산 가능매 반복마다 값 이동이 중요하다temp = one + twoone = twotwo = temp N ≤ 90 이므로 long 타입 사용 가능📌 전체 코드impor..

🔗 문제 링크https://www.acmicpc.net/problem/13301📌 문제 개요정사각형 타일을 이어 붙여 도형을 만들 때,타일의 변 길이가 특정 규칙(피보나치 형태)을 따른다.이때 N번째 도형의 둘레 길이를 구하는 문제이다.📌 접근 방법타일의 변 길이는 피보나치 수열도형의 가로, 세로는 연속된 피보나치 값으로 구성됨최종적으로 직사각형 형태가 되므로둘레 = 2 × (가로 + 세로)📌 핵심 아이디어피보나치 수열을 이용해 변 길이를 계산배열 없이 변수 2개로 최적화a = 이전 값b = 현재 값 반복하면서 갱신📌 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;publi..

🔗 문제 링크https://www.acmicpc.net/problem/9625📌 문제 개요처음 화면에는 A만 1개가 있다.버튼을 한 번 누를 때마다 A는 B로 바뀌고, B는 BA로 바뀐다.이렇게 버튼을 K번 눌렀을 때 화면에 존재하는 A와 B의 개수를 구하는 문제📌 접근 방법처음에는 문자열을 직접 바꿔가며 만들어야 하나 생각할 수 있다. 하지만 버튼을 누를수록 문자열 길이가 계속 늘어나기 때문에,실제 문자열을 생성하는 방식은 비효율적이다. 이 문제는 문자열 자체보다 A와 B의 개수 변화 규칙만 보면 훨씬 쉽게 풀 수 있다. 0번: A → A 1개, B 0개1번: B → A 0개, B 1개2번: BA → A 1개, B 1개3번: BAB → A 1개, B 2개4번: BABBA → A 2개, B 3개여기..

🔗 문제 링크https://www.acmicpc.net/problem/10826📌 문제 개요피보나치 수열의 n번째 값을 구하는 문제하지만 n의 범위가 매우 크기 때문에 일반적인 자료형으로는 해결할 수 없다.📌 접근 방법이 문제는 전형적인 DP(동적 계획법) 문제이전 두 값을 이용하여 다음 값을 계산재귀 대신 반복문 사용 (성능 고려)핵심은 자료형 선택📌 핵심 아이디어피보나치 수는 n이 커질수록 값이 매우 빠르게 증가long 범위를 초과하기 때문에 사용 불가따라서 BigInteger 사용 필수BigInteger temp \= a.add(b); BigInteger는 연산을 메서드로 수행해야 한다📌 전체 코드/*문제-10826 (실버5): 피보나치 수 4- n번째 피보나치 수를 출력하는 문제- n의 ..

🔗 문제 링크https://www.acmicpc.net/problem/10870📌 문제 개요피보나치 수열의 n번째 수를 구하는 문제이다.피보나치 수열은 다음과 같이 정의F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2)입력으로 정수 n이 주어질 때, n번째 피보나치 수를 출력📌 접근 방법피보나치 문제는 보통 재귀로 먼저 떠올리기 쉽다.하지만 재귀 방식은 동일한 계산이 반복되어 **시간 복잡도가 O(2ⁿ)**으로 증가한다.이번 문제는 n ≤ 20으로 범위가 작지만,실전 습관을 위해 반복문(Iterative) 방식으로 풀이이전 두 값을 저장하면서다음 값을 계속 누적 계산하는 방식시간 복잡도는 O(n) 이다.📌 핵심 아이디어피보나치는 직전 두 값만 필요, 그리고 값을 한 칸씩 밀어주면..