기록방

👉 문제링크 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 ..

👉 문제링크 2596번: 비밀편지 병현이는 지은이에게 문자 A, B, C, D, E, F, G, H 로 쓰여진 편지를 날마다 보내는데, 컴퓨터로 보내는 비밀편지로, 한 문자마다 0 또는 1인 숫자 여섯 개를 사용하여 보낸다. 둘 사이의 약속은 다음과 www.acmicpc.net 🔸 문제 분석 🔸 0또는 1로 이루어진 숫자를 문자로 변환한다. 같거나 차이가 1일때는 변환 가능하다 차이가 2 이상이면 변환 불가능 하다. 모두 변환 가능하면, 변환한 문자열을 출력 변환이 불가능하면, 처음 불가능 한 문자의 순서를 출력한다. 🔸 코드 🔸 import java.io.FileNotFoundException; import java.util.Scanner; public class Main { private static..

👉 문제링크 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 🔸 문제 분석 🔸 T개의 테스트 케이스마다 결과를 출력한다. 국가의 수 n과 비행기의 종류 m을 입력 받는다. m개의 비행기 종류 마다 a, b 쌍을 입력 받는다. 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다. 모든 국가를 여행할 때 가장 적은 종류의 비행기로 탄다면 몇 개의 종류인지 출력한다. [연결 그래프] 그래프 이론에서 연결 그래프(connected graph)는 모든 두 꼭짓점 사이에 경로가 존재하..