기록방

👉 문제링크 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 🔸 문제 분석 🔸 n x m 크기의 창고에 토마토가 놓여있다. 1 : 익은 토마토, 0 : 덜 익은 토마토, -1 : 빈 공간 익은 토마토는 하루가 지날 때 마다 상하좌우 덜 익은 토마토를 익게 만든다. 며칠이 지나야 토마토가 모두 익는지 출력한다. 모두 익지 못하면 -1 을 출력한다. 익은 토마토 주변에 익을 수 있는 토마토를 큐에 넣고 BFS을 실행한다. 며칠이 지나는지 확인해야 하므로 익을 예정인 토마토들은 같은 큐에 넣지 않고..

👉 문제링크 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 🔸 문제 분석 🔸 문자열을 입력받아 부분 문자열의 종류를 출력한다. 입력받은 문자열s를 1부터 s의 크기까지의 길이로 잘라 부분 문자열을 구한다. 문자열의 중복을 피해 저장하고, 개수를 출력한다. 🔸 코드 🔸 import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Stri..

👉 문제링크 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 🔸 문제 분석 🔸 n개의 수열을 입력받고, 가장 긴 증가하는 부분 수열의 길이를 출력한다. 수열의 인덱스 별 부분 수열 길이의 최대값을 저장하는 dp배열을 만들어 값을 구한다. 각 인덱스의 수가 부분 수열의 마지막 수가 됐을 때를 계산해서 그 중 최대값을 구해야 한다. 각 인덱스의 앞쪽에서 수열 원소값이 더 작은 것들 중 dp배열 값이 가장 큰 값을 구한다. 구한 값에 +1..

👉 문제링크 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 🔸 문제 분석 🔸 n X n 지도에서 붙어있는 집 (1)을 찾아 단지 별로 구분한다. 단지의 수와 각 단지별 집의 수를 오름차순으로 출력한다. BFS로 탐색해 붙어있는 집의 수와 단지 수를 구한다. 🔸 코드 🔸 import java.util.*; public class Main { public static void main(String[] args) { // 1) input Scanner sc = new Scanner(System.in); int n ..

👉 문제링크 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 🔸 문제 분석 🔸 노드 수 n, 시작 노드, 끝 노드, 간선의 수 m과 m개의 간선 정보가 입력된다. 시작 노드부터 끝 노드 까지 몇 개의 간선으로 갈 수 있는지 출력한다. 연결되어있지 않으면 -1을 출력한다. 🔸 코드 🔸 import java.util.ArrayList; import java.util.Scanner; import java.util.Stack; public class Main { public static void ..