ImJay

[BOJ/Java] 4485. 녹색 옷 입은 애가 젤다지? 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제 해석 이 문제는 다익스트라 알고리즘을 이용하여 최소 비용 경로를 찾는 문제이다. 각 칸에는 비용이 존재하고, 이 비용을 최소화하면서 오른쪽 아래 구석으로 이동해야 한다. 이 문제는 전형적인 그리드 기반의 최단 경로 문제로, 각 점에서 상하좌우 네 방향으로 이동할 수 있다. 풀이 과정 입력받은 그리드 map에 대하여 다익스트라 알고리즘을 적용하여 해결한다. 우선적으로 weight 배..

[BOJ/Java] 11722. 가장 긴 감소하는 부분 수열 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 문제 해석 이 문제는 주어진 배열에서 가장 긴 감소하는 부분 수열의 길이를 찾는 문제이다. 감소하는 부분 수열이란, 수열의 원소들이 감소하는 순서로 정렬된 수열을 의미한다. 풀이 과정 제출된 코드는 동적 프로그래밍(DP)을 이용한 방식으로 구현되어 있지만, 로직에 오류가 있어 정확히 문제의 요구사항을 충족하지 못하는 부분이 있다...

[BOJ/Java] 1520. 내리막 길 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 해석 "내리막 길" 문제는 지정된 MxN 격자에서 각 셀에는 높이가 주어지며, 항상 상하좌우로만 이동할 수 있는 조건에서, 시작점 (M, N)에서 목표점 (1, 1)까지 내리막길로만 이동하는 경로의 수를 구하는 문제이다. 이동은 오직 더 낮은 높이의 셀로만 가능하다. 풀이 과정 이 문제는 동적 프로그래밍(DP)과 깊이 우선 탐색(DFS)을 활용하여 해결할 수 있다. DP 배열 dp를 사용하여 각 위치에서 목표 위치까지 도..

[BOJ/Java] 19942. 다이어트 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 문제 해석 다이어트 문제(BOJ 19942)는 주어진 영양소의 최소 요구량을 만족하는 식단을 찾는 문제이다. 각 식단은 단백질, 지방, 탄수화물, 비타민을 포함하며, 주어진 요구량을 만족하는 식단 중 최소 비용을 갖는 식단을 찾는 것이 목표이다. 풀이 과정 이 문제는 부분 집합의 속성을 활용하여 모든 가능한 조합을 탐색하는 방법으로 해결할 수 있다. 재귀적 방법으로 각 음식을 선택하거나 선택하지 않는 모든 경우를 고려하며..

[BOJ/Java] 20055. 컨베이어 벨트 위의 로봇 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 문제 해석 컨베이어 벨트와 로봇의 상호작용을 시뮬레이션하는 본 문제에서는 벨트가 원형으로 연결되어 있으며, 로봇이 올라갈 수 있는 위치와 올라갈 수 없는 위치로 구분되어 있다. 각 칸에는 내구도가 존재하며, 로봇이 칸 위로 이동하거나 벨트가 회전할 때마다 내구도가 감소된다. 주어진 조건 하에서 내구도가 0인 칸의 수가 특정 값(K) 이상이 될 때까지의 반복 과정을 통해 진행 단계 수를 ..

[BOJ/Java] 9935. 문자열 폭발 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 해석 "문자열 폭발" 문제는 주어진 문자열에서 특정 "폭발 문자열"이 있을 경우, 그 문자열을 모두 제거하고, 제거 후 남은 문자열에 다시 폭발 문자열이 포함되어 있다면 이를 반복적으로 제거하는 과정을 거쳐 최종적으로 남은 문자열을 반환하는 문제다. 만약 모든 문자가 제거될 경우 "FRULA"를 출력한다. 이 문제는 특히 문자열 처리와 스택을 활용하는 알고리즘 설계 능력을 요구한다. 풀이 과정 이 문..

[BOJ/Java] 17837. 새로운 게임 2 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제 해석 이 문제는 체스판에서 말을 이동시켜서 게임을 진행하는 시뮬레이션 문제다. 체스판의 각 칸은 흰색, 빨간색, 파란색으로 구분되어 있으며, 말은 특정 방향으로만 이동할 수 있다. 말은 다른 말 위에 올라탈 수 있으며, 이동 시 다양한 규칙에 따라 처리가 달라진다. 게임의 목표는 말이 네 개 이상 쌓이면 게임을 종료하는 것이다. 이 문제의 주요 도전은 말의 이동과 위치, 방향 변경 등을 정확히 처리하는 것이..

[BOJ/Java] 9251. LCS (최장 공통 부분 수열) 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 해석 LCS 문제는 두 문자열이 주어졌을 때, 두 문자열 모두의 부분 수열이 되는 가장 긴 수열을 찾는 문제이다. 이 문제를 해결하기 위해 동적 프로그래밍(Dynamic Programming) 방식을 사용하며, 이를 구현하기 위한 점화식을 개발하고 코드로 옮겨야 한다. 풀이 과정 주어진 코드는 두 문자열 a와 b를 입력 받고, 이를 문자 배열로 변환한..

[BOJ/Java] 1938. 통나무 옮기기 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net 문제 해석 NxN 크기의 격자에서 통나무를 이동시켜야 하는 최소 횟수를 구하는 문제다. 통나무는 'B'로, 목표 위치는 'E'로 표현된다. 통나무는 3개의 연속된 칸을 차지하며, 수직이나 수평 방향으로만 움직일 수 있다. 또한, 통나무는 중심을 기준으로 90도 회전할 수 있으며, 각 격자 칸은 비어 있거나('0'), 장애물('1')이 있거나, 통나무의 시작 위치('B'), 혹은 목표 위치('E'..

[BOJ/Java] 17609. 회문 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 해석 문제 "회문"은 문자열이 회문인지, 유사 회문인지, 일반 문자열인지를 판별하는 문제다. 회문은 정방향과 역방향이 같은 문자열을 말하고, 유사 회문은 한 문자를 제거하여 회문이 될 수 있는 문자열을 의미한다. 이 문제를 해결하기 위해서는 각 문자열에 대해 투 포인터 알고리즘을 활용하여 양 끝에서부터 문자를 비교하면서 회문 여부를 확인해야 한다. 풀이 과정 이 코드는 투 포인터를 활용하여 문자열의 시작 인덱스와 끝 인덱스를 가리키는 start와 en..