ImJay

[BOJ/Java] 11403. 경로 찾기 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해석 이 문제는 주어진 방향 그래프에서 각 정점 𝑖에서 𝑗로 가는 경로가 존재하는지를 파악하는 문제다. 입력으로 주어지는 𝑁×𝑁 행렬에서, 행렬의 각 요소가 1인 경우 해당 정점 간에 직접적인 연결이 있음을 나타내며, 0은 연결이 없음을 나타낸다. 풀이 과정 플로이드-와샬 알고리즘을 사용하여 모든 정점 쌍 간의 가능한 경로를 찾는다. 이 알고리즘은 각 정점을 중간 정점으로 고려하며, 간접적인 경로도 고려하여 연결성을 파악한다. 코드 packag..

[BOJ/Java] 15652. N과 M (4) 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해석 이 문제에서는 1부터 𝑁까지의 수 중에서 중복을 허용하여 𝑀개를 고르는 조합을 모두 찾는다. 선택된 수열은 비내림차순이어야 한다는 조건이 있어, 각 수열의 원소는 이전 원소보다 작아지지 않는다. 풀이 과정 문제의 요구 사항을 충족시키기 위해 재귀 함수를 사용하여 문제를 해결한다. 주어진 문제는 백트래킹 기법을 이용해 풀 수 있다. 재귀적으로 각 위치에 들어갈 수를 결정하고, 이전 선택된 수 이상의 숫자만..

[BOJ/Java] 1463. 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 해석 이 문제는 주어진 수 𝑋X를 1로 만드는 데 필요한 최소 연산 횟수를 찾는다. 연산은 다음 세 가지 중 하나를 선택할 수 있다: 𝑋X가 3으로 나누어 떨어지면, 3으로 나눈다. 𝑋X가 2로 나누어 떨어지면, 2로 나눈다. 𝑋X에서 1을 뺀다. 풀이 과정 이 문제는 동적 계획법(Dynamic Programming, DP)을 사용하여 해결할 수 있다. 각 숫자 𝑖i에 대하여, 𝑖i를 1로 만드는 최소 연산 횟수를 dp[i] 배열에 저장한다. 점화식은 다음과 같다: 𝑑𝑝[𝑖]=𝑑𝑝[𝑖−1]+1 𝑑𝑝[𝑖]=min⁡(𝑑𝑝[𝑖],𝑑𝑝..

[BOJ/Java] 1753. 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 해석 이 문제는 주어진 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 고전적인 다익스트라 알고리즘 문제다. 주어진 그래프는 방향성이 있으며, 각 간선에는 가중치가 존재한다. 풀이 과정 제출된 코드는 다음 단계로 문제를 해결한다: 입력 받기: 각 간선 정보를 입력받아 인접 리스트에 저장한다. 다익스트라 알고리즘 실행: 우선순위 큐를 사용하여 현재 정점에서 가장 ..

[BOJ/Java] 11562. 백양로 브레이크 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 문제 해석 이 문제는 학교의 건물 간 통행로를 양방향으로 통행할 수 있게 만드는 데 필요한 최소 비용을 계산하는 문제이다. 각 통행로는 일방통행 또는 양방향 통행이 가능하며, 일방통행로를 양방향으로 바꾸는 데에는 비용이 든다. 풀이 과정 제출된 코드는 플로이드-와샬 알고리즘을 사용하여 모든 쌍 최단 경로를 계산한다. 각 건물 간의 최소 비용을 담은 그래프에서, 일방통행로의 경우 양방향으로 변경할 때 추가 비용을 고..

[BOJ/Java] 2457. 공주님의 정원 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 문제 해석 본 문제에서는 공주님의 정원을 3월 1일부터 11월 30일까지 꽃으로 가득 채우기 위해 필요한 최소한의 꽃 종류를 선택하는 방법을 찾는다. 각 꽃은 피는 시기와 지는 시기가 정해져 있으며, 이를 효과적으로 선택하여 연속적으로 꽃이 피어있게 해야 한다. 풀이 과정 제출된 코드는 꽃들의 생장 기간을 기반으로 그리디 알고리즘을 사용하여 문제를 해결한다. 모든 꽃들을 피는 시기를 기준으로 정렬하..

[BOJ/Java] 17070. 파이프 옮기기 1 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 해석 이 문제는 주어진 격자 안에서 파이프를 조작하여 시작 위치에서 목표 위치까지 이동하는 경로의 수를 찾는 문제다. 파이프는 가로, 세로, 대각선의 3가지 상태로 움직일 수 있으며, 격자의 범위와 벽(값 1)에 의해 움직임이 제한된다. 파이프는 격자의 한 쪽 끝에서 다른 쪽 끝으로만 연장될 수 있으며, 목적지에 도달할 때마다 가능한 경로의 수를 세어야 한다. 풀이 과정 제출된 코드는..

[SWEA/Java] 5672. 올해의 조련사 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 이 문제는 문자열로 이루어진 배열에서 사전적으로 가장 작은 문자열을 만들기 위해 앞뒤에서 문자를 하나씩 선택하는 시뮬레이션 문제이다. 앞 또는 뒤에서 문자를 선택하여 결과 문자열을 조합할 때, 매 선택에서 앞 또는 뒤 중 사전적으로 더 작은 문자를 선택한다. 만약 앞과 뒤의 문자가 같을 경우, 더 내부의 문자까지 비교하여 결정을 내려야 한다. 풀이 과정 제출된 코드는 주어진 배열의 맨 앞과 맨 뒤 문자를 비교하여 더 작은 문자를 결과 문자열에 추가하는 과정을 반복한다. 만약 두 문자가 같을 경우, check..

[BOJ/Java] 17281. ⚾ 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 문제 해석 이 문제는 야구 게임의 이닝과 플레이어의 타격 결과를 기반으로 최대 점수를 계산하는 문제이다. 각 선수가 타석에 서서 결과를 내는 순서인 타순을 조정하여 가장 많은 점수를 얻을 수 있는 경우를 찾아야 한다. 문제의 주요 요소는 다음과 같다 1번 선수는 항상 4번 타자로 고정. 나머지 선수들의 타순을 조합하여 최대 점수를 계산. 각 선수의 타격 결과에 따라 주자들이 진루하며, 홈을 통과하면 점수를 획득. 풀이 과정 제출된 코..

[SWEA/Java] 6109. 추억의 2048게임 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 이 문제는 2048 게임의 변형으로, 게임 보드에서 주어진 방향으로 블록을 이동시키고 합치는 과정을 시뮬레이션하는 문제이다. 입력으로는 보드의 크기 𝑁N과 이동할 방향 𝑆S가 주어진다. 𝑆S는 'l' (왼쪽), 'r' (오른쪽), 'u' (위쪽), 'd' (아래쪽) 중 하나이다. 보드에는 숫자가 적힌 타일이 있으며, 이 타일들을 𝑆S에 따라 이동시키고 같은 숫자의 타일이 만나면 합쳐진다. 합쳐진 타일은 더 이상 합쳐질 수 없다. 풀이 과정 제출된 코드는 주어진 방향에 따라 타일들을 합치고 이동시키는 로..