ImJay

[SWEA/Java] 4193. 수영대회 결승전 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com문제 해석삼성이는 수영대회 결승전에 진출했으며, 이번 대회는 N x N 크기의 제한된 바다 공간에서 열린다. 이 경기장은 섬과 같이 지나갈 수 없는 장애물(1로 표시)과 특정 주기로 사라졌다 나타나는 소용돌이(2로 표시)가 포함되어 있다. 소용돌이는 0초, 1초에 생성되고 2초에 사라진다가 3초, 4초에 다시 생성되는 패턴을 가진다. 이 문제에서는 삼성이가 가장 빠른 길을 찾아 결승점에 도달할 수 있는 시간을 계산하는 것이 목표다.풀이 과정경로 찾기와 시간 계산을 요구하는 BFS(너비 우선 탐색)를 이용해 해결할 수 있다..

[BOJ/Java] 12015. 가장 긴 증가하는 부분 수열 2 12015번: 가장 긴 증가하는 부분 수열 2첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)www.acmicpc.net문제 해석주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾는 고전적인 문제의 확장판이다. 이 문제는 수열의 길이가 매우 클 수 있기 때문에 𝑂(𝑁^2)의 시간 복잡도를 갖는 기본적인 동적 프로그래밍 방법으로는 효율적으로 해결할 수 없다. 대신, 이진 탐색을 활용한 𝑂(𝑁log⁡𝑁) 시간 복잡도의 풀이가 필요하다.풀이 과정입력 받기: 수열의 크기 N과 수열 A를 입력 받는다.DP 배열 초기화..

[BOJ/Java] 11055. 가장 큰 증가 부분 수열 11055번: 가장 큰 증가하는 부분 수열수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는www.acmicpc.net문제 해석주어진 수열에서 증가 부분 수열을 찾아 그 합이 최대가 되는 값을 구하는 문제이다. 이는 '가장 긴 증가하는 부분 수열' 문제의 변형으로, 길이가 아닌 수열의 합을 최대화하는 것이 목표이다.풀이 과정입력 받기: 수열의 크기 N과 수열 A를 입력 받는다.동적 프로그래밍(DP) 배열 초기화: DP 배열을 사용하여 각 위치에서 가능한 최대 합을 저장..

[SWEA/Java] 5656. 벽돌 깨기 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com문제 해석특정 구조의 격자에서 N번의 기회로 최대한 많은 벽돌을 깨뜨리는 시뮬레이션 게임이다. 벽돌은 숫자로 표시되며, 숫자는 벽돌이 폭발할 때 영향을 미치는 범위를 의미한다. 사용자는 N번의 기회에 W의 너비 중 하나를 선택해 벽돌을 발사할 수 있으며, 목표는 격자판에 남은 벽돌의 수를 최소화하는 것이다.풀이 과정입력 받기: 테스트 케이스 수와 각 테스트 케이스에 대한 N, W, H, 그리고 격자판 상태를 입력 받는다.시뮬레이션 실행: 각 위치에서 발사 가능한 모든 조합을 시도하면서 최소 벽돌 수를 찾는다.순열 생성: N번의..

[BOJ/Java] 1786. 찾기 1786번: 찾기첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～mwww.acmicpc.net문제 해석문자열에서 특정 패턴을 찾는 문제로, 주어진 텍스트 문자열(T)에서 패턴 문자열(P)이 등장하는 모든 위치를 찾아 그 시작 위치들을 출력하는 것이다. 이 문제는 문자열 검색 알고리즘 중 하나인 KMP(Knuth-Morris-Pratt) 알고리즘을 사용하여 해결할 수 있다. KMP 알고리즘은 불필요한 문자 비교를 최소화하여 빠른 검색을 가능하게 한다.풀이 과정입력 받기: 문자열 T와 패턴 P를 입력 받는다.KMP 실행:..

[BOJ/Java] 9205. 맥주 마시면서 걸어가기 9205번: 맥주 마시면서 걸어가기송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다.www.acmicpc.net문제 해석이 문제는 페스티벌에 참여하기 위해 맥주를 마시면서 여러 장소를 거쳐가는 과정을 모델링한 그래프 탐색 문제이다. 주어진 장소들 사이의 거리를 기반으로 맥주 한 캔으로 갈 수 있는 최대 거리(1000미터)를 고려해, 출발지(집)에서 목적지(페스티벌)까지 도달 가능한지 판단해야 한다.풀이 과정주어진 모든 위치를 Vertex 객체로 저장하고, 각 위치 간의 거리를 계산해 연결 가능..

[SWEA/Java] 1263. 사람 네트워크2 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com문제 해석이 문제는 사회과학 연구에서 사용되는 네트워크 중요도 척도인 'Closeness Centrality' (CC)을 계산하는 문제이다. 네트워크 상의 모든 사용자 간 최단 경로의 합으로 정의된다. 각 사용자에 대해 다른 모든 사용자까지의 최단 경로를 더한 후, 가장 작은 값을 가진 사용자의 CC 값을 찾는 것이 목표다.풀이 과정이 문제의 풀이는 플로이드-와샬 알고리즘을 사용하여 모든 노드 쌍에 대한 최단 거리를 계산하는 것을 기본으로 한다. 주어진 인접 행렬에서 직접 연결되지 않은 노드 간의 ..

[SWEA/Java] 9282. 초콜릿과 건포도 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com문제 해석이 문제는 N x M 크기의 초콜릿을 1x1 크기로 완전히 나누려고 할 때, 최소한의 건포도 수를 포함하여 나누는 전략을 찾는 것이다. 건포도의 수는 각 조각에 미리 할당되어 있으며, 나눌 때마다 해당 영역의 건포도 합이 비용으로 추가된다.풀이 과정동적 프로그래밍(DP) 접근: 이 문제는 4차원 DP 배열 dp[x][y][h][w]을 사용하여 (x, y) 위치에서 시작하고 (h, w) 크기를 가진 영역을 나누는 데 필요한 최소 비용을 저장한다.재귀와 메모이제이션: dfs 함수를 통해 재..

[BOJ/Java] 11726. 2xn 타일링 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 해석 "2xn 타일링" 문제는 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 찾는 문제다. 이 문제는 동적 프로그래밍을 활용하여 풀 수 있다. 크기가 n인 문제를 해결하기 위해, 먼저 n이 1과 2일 때의 해답을 초기값으로 설정하고, n이 3 이상일 때는 점화식 𝑓(𝑛)=𝑓(𝑛−1)+𝑓(𝑛−2)를 사용하여 해를 구한다. 풀이 과정 프로그램은 BufferedReader를 이용해 입력을 받고 BufferedWrite..

[BOJ/Java] 1463. 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 해석 이 문제는 주어진 수 N을 1로 만드는 최소 횟수를 구하는 문제다. 수행할 수 있는 연산은 세 가지로, N을 3으로 나누기, 2로 나누기, 또는 1을 빼는 연산이 있다. 주어진 N에 대해 세 가지 연산을 적절히 조합하여 1로 만드는 데 필요한 최소 연산 횟수를 찾는 것이 목표다. 풀이 과정 본 코드는 동적 계획법을 사용하여 문제를 해결한다. 배열 dp를 사용하여 각 숫자 i를 1로 만들기 위해 필요한 최소 연산 횟수를 저장한다. dp[i]는 i번째 숫자를 1로 만드는 데 필요한 최소 연산 횟수를 나타낸다. 초기화: dp[1..