🔗 문제 링크https://www.acmicpc.net/problem/11444📌 문제 개요N번째 피보나치 수를 구하는 문제하지만 N의 크기가 매우 크기 때문에 일반적인 DP(O(N)) 방식으로는 시간 초과가 발생합니다. 📌 접근 방법이 문제는 피보나치를 행렬 형태로 변환하여 해결 기본 행렬:|1 1||1 0| 이 행렬을 N번 곱하면 다음과 같은 결과가 나옵니다.|F(n+1) F(n) ||F(n) F(n-1)| result[0][1] = F(N) 이 됩니다.📌 핵심 아이디어1. 행렬 거듭제곱A^N을 빠르게 구하기 위해 분할 정복 사용짝수: A^N = A^(N/2) × A^(N/2)홀수: A^N = A^(N/2) × A^(N/2) × A 2. 행렬 곱셈 “가로 × 세로” 방식으로 계..

🔗 문제 링크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/1991📌 문제 개요백준 1991번 트리 순회는 이진 트리의 노드 정보가 주어졌을 때,전위 순회 / 중위 순회 / 후위 순회 결과를 출력하는 문제 각 입력은 부모 왼쪽자식 오른쪽자식 형태로 주어지며,'.' 은 자식이 없다는 뜻 루트 노드는 항상 A 이므로, A부터 시작해서 세 가지 순회📌 접근 방법처음에는 트리를 객체로 직접 연결해야 하나 고민할 수 있지만,이 문제는 노드 개수가 많지 않고 각 노드가 왼쪽 자식 / 오른쪽 자식만 가지는 이진 트리이기 때문에배열 두 개만으로도 충분히 해결할 수 있습니다. 저는 다음과 같이 접근했습니다.left[] : 각 노드의 왼쪽 자식 저장right[] : 각 노드의 오른쪽 자식 저장..

🔗 문제 링크https://www.acmicpc.net/problem/1531📌 문제 개요N개의 색종이를 도화지 위에 붙인다.각 색종이는 직사각형 영역을 덮으며, 특정 칸이 M번 초과로 덮이면 보이지 않는다.보이지 않는 칸의 개수를 구하는 문제이다.📌 접근 방법이 문제는 좌표 범위가 크지 않기 때문에복잡한 알고리즘 없이 2차원 배열을 활용한 완전 탐색으로 해결할 수 있다. 각 칸이 몇 번 덮였는지를 직접 기록한 뒤M보다 큰 칸의 개수를 세면 된다.📌 핵심 아이디어2차원 배열을 사용하여 겹침 횟수를 저장색종이 범위를 돌면서 해당 칸을 +1최종적으로 M 초과인 칸만 카운트“각 칸이 몇 번 덮였는지를 직접 세는 문제”📌 전체 코드import java.io.BufferedReader;import jav..

🔗 문제 링크https://www.acmicpc.net/problem/10431📌 문제 개요백준 10431번은 학생들이 줄을 설 때 발생하는 이동 횟수의 총합을 구하는 문제학생들은 순서대로 줄에 들어오며,자신보다 키가 큰 학생보다 앞에 서야 합니다.이 과정에서 발생하는 이동 횟수를 모두 더하는 것이 목표입니다.📌 접근 방법이 문제는 실제로 학생을 이동시키는 것보다,이동 횟수를 계산하는 것이 핵심 학생이 들어올 때마다:이미 들어온 학생들 중에서자신보다 키가 큰 학생 수를 세면 됨이 값이 곧 이동 횟수📌 핵심 아이디어이동 횟수의 의미현재 학생 기준 : 앞에 있는 학생 중 나보다 큰 학생 수 = 이동 횟수예시입력 : 5 3 4 2 진행:5 → 이동 없음3 → 5보다 작음 → 1칸 이동4 → 5보다 작음..

🔗 문제 링크https://www.acmicpc.net/problem/11576📌 문제 개요백준 11576번은 A진법으로 표현된 수를 B진법으로 변환하는 문제입니다.입력은 일반적인 문자열 형태가 아니라, 각 자릿수가 공백으로 구분되어 주어진다는 점이 특징즉, 문제의 핵심은 다음 두 단계입니다.A진법 수를 10진수로 바꾸기10진수를 다시 B진법으로 바꾸기진법 변환의 기본 원리를 알고 있으면 어렵지 않게 해결할 수 있는 문제📌 접근 방법이 문제는 한 번에 A진법에서 B진법으로 바로 바꾸려고 하기보다,중간에 10진법으로 변환해서 처리하는 것이 가장 깔끔 1. A진법 → 10진법A진법 수가 자릿수 배열로 주어지므로, 왼쪽부터 하나씩 읽으면서 누적 계산 예를 들어 8진수 1 0 1 이라면:0 * 8 + 1 ..

🔗 문제 링크https://www.acmicpc.net/problem/15688📌 문제 개요N개의 정수가 주어지고 이를 오름차순으로 정렬하는 문제N의 최대값이 1,000,000으로 매우 크기 때문에 입출력 속도가 중요📌 접근 방법배열에 숫자를 입력받는다Arrays.sort()로 정렬한다출력 시 StringBuilder를 사용해 성능을 개선한다📌 핵심 아이디어단순 정렬 문제지만 출력이 핵심System.out.println을 반복하면 시간초과 발생 가능StringBuilder로 모아서 한 번에 출력📌 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util...

🔗 문제 링크🔗 https://www.acmicpc.net/problem/16435📌 문제 개요스네이크버드는 자신의 길이보다 작거나 같은 높이의 과일만 먹을 수 있다.과일을 먹을 때마다 길이는 1씩 증가한다.주어진 과일들을 적절히 먹어 최대 길이를 구하는 문제📌 접근 방법과일을 아무 순서로 먹는 것이 아니라 작은 것부터 먹는 것이 핵심큰 과일부터 먹으면 이후 작은 과일을 못 먹는 경우 발생따라서: 오름차순 정렬 후 순차 탐색📌 핵심 아이디어현재 길이 >= 과일 높이 → 먹기 (길이 +1)현재 길이 한 번 막히면 뒤는 전부 불가능📌 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamRead..

🔗 문제 링크https://www.acmicpc.net/problem/1652📌 문제 개요NxN 크기의 방이 주어지고, .은 빈칸, X는 벽을 의미한다.가로 또는 세로로 연속된 빈칸이 2칸 이상이면 누울 수 있는 자리로 판단- 가로 / 세로 각각 가능한 자리 개수를 구하는 문제📌 접근 방법이 문제는 단순 구현 문제로연속된 '.'의 길이를 세는 방식으로 해결할 수 있다.가로 방향 탐색한 행씩 보면서 '.' 개수 카운트'X'를 만나면 구간 종료세로 방향 탐색동일한 방식으로 열 기준 탐색📌 핵심 아이디어연속된 '.' 구간을 찾는다구간 길이가 2 이상이면 카운트'X'를 기준으로 구간을 나눈다가로와 세로는 완전히 별개로 계산📌 전체 코드import java.io.BufferedReader;import j..

🔗 문제 링크문제 링크: https://www.acmicpc.net/problem/4659📌 문제 개요백준 4659번 비밀번호 발음하기는주어진 문자열이 좋은 비밀번호인지 판별하는 문제모음(a, e, i, o, u)이 최소 1개 이상 포함되어야 한다.모음이 3개 연속으로 오면 안 된다.자음이 3개 연속으로 오면 안 된다.같은 글자가 연속으로 2번 오면 안 된다.단, ee와 oo는 허용된다.입력은 여러 줄로 주어지고, "end"가 입력되면 종료📌 접근 방법문자열을 앞에서부터 한 글자씩 보면서 조건을 검사하면 해결모음이 한 번이라도 등장했는지모음 또는 자음이 3번 연속되는지같은 문자가 연속되는지문자 하나를 볼 때마다 현재 문자가 모음인지 자음인지 구분하고,모음이면 vowelCnt 증가, consonant..