코딩연습이 좋아서/이론이 좋아서

Dynamic Programming(동적 계획법) - 최대점수 구하기(냅색 알고리즘)

설명이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)입력첫 번째 줄에 문제의 개수N(1두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.출력첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.예시 입력 1 5 2010 525 1215 86 37 4예시 출력 141 import java.util.*;class Problem { int score; int ti..

Dynamic Programming(동적 계획법) - 동전교환(냅색 알고리즘)

설명다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?각 단위의 동전은 무한정 쓸 수 있다.입력첫 번째 줄에는 동전의 종류개수 N(1두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1각 동전의 종류는 100원을 넘지 않는다.출력첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.예시 입력 1 31 2 515예시 출력 13힌트출력설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다. import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); ..

Dynamic Programming(동적 계획법) - 가장 높은 탑 쌓기(LIS 응용)

설명밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다.아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.(조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.(조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.(조건3) 벽돌들의 높이는 같을 수도 있다.(조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.(조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.입력입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다.둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽..

Dynamic Programming(동적 계획법) - 최대 부분 증가수열(LIS)

설명N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라.예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어길이가 5인 최대 부분 증가수열을 만들 수 있다.입력첫째 줄은 입력되는 데이터의 수 N(3≤N≤1,000, 자연수)를 의미하고,둘째 줄은 N개의 입력데이터들이 주어진다.출력첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.예시 입력 1 85 3 7 8 6 2 9 4예시 출력 14 import java.util.*;public class Main { static int[] dy; public sta..

Dynamic Programming(동적 계획법) - 돌다리 건너기

설명철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다.철수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다.철수가 개울을 건너는 방법은 몇 가지일까요?입력첫째 줄은 돌의 개수인 자연수 N(3≤N≤35)이 주어집니다.출력첫 번째 줄에 개울을 건너는 방법의 수를 출력합니다.예시 입력 1 7예시 출력 134 import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] dy = new int[n +..

Dynamic Programming(동적 계획법) - 계단 오르기

설명철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?입력첫째 줄은 계단의 개수인 자연수 N(3≤N≤35)이 주어집니다.출력첫 번째 줄에 올라가는 방법의 수를 출력합니다.예시 입력 1 7예시 출력 121 import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[]..

Greedy Algorithm - 원더랜드(최소스패닝트리 - 크루스칼 : Union&Find)

설명원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.아래의 그림은 그 한 예를 설명하는 그림이다.위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다.입력첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다.다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다.출력모든 도시를 연결하면서 드는 최소비용을 출려한다.예시 입력 1 9 121 2 12..

Greedy Algorithm - 친구인가? (Disjoint-Set : Union&Find)

설명오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다. 현수는 각 학생들의 친구관계를 알고 싶다.모든 학생은 1부터 N까지 번호가 부여되어 있고, 현수에게는 각각 두 명의 학생은 친구 관계가 번호로 표현된 숫자쌍이 주어진다.만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다.그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다.학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램을 작성하세요.두 학생이 친구이면 “YES"이고, 아니면 ”NO"를 출력한다.입력첫 번째 줄에 반 학생수인 자연수 N(1다음 M개의 줄..

Greedy Algorithm - 최대 수입 스케줄(PriorityQueue)

설명현수는 유명한 강연자이다. N개이 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다.각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.입력첫 번째 줄에 자연수 N(1출력첫 번째 줄에 최대로 벌 수 있는 수입을 출력한다.예시 입력 1 650 220 140 260 330 330 1예시 출력 1150 import java.util.*;class Lecture implements Comparable { int money; int date; public Lecture(int money, int date) { this...

Greedy Algorithm - 결혼식

설명현수는 다음 달에 결혼을 합니다.현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다.피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다.각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다.현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다. 여러분이 현수를 도와주세요.만약 한 친구가 오는 시간 13, 가는시간 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정합니다.입력첫째 줄에 피로연에 참석할 인원수 N(5두 번째 줄부터 N줄에 걸쳐 각 인원의 오는 시간과 가는 시간이 주어집니다.시간은 첫날 ..