코린이의 소소한 공부노트

1. Input 1) int[] height - height[i] == i번째 위치의 벽의 높이 - 벽의 간격과 두께는 모두 1이다. 2. Output 1) 두 벽을 골라 물을 채울 때 가장 많이 채울 수 있는 물의 양을 반환 3. Constraint 1) n == height.length 2) 2

1. 입력 - 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) - 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다. 2. 출력 - 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다. 3. 예제 4. 코드 import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer token = new StringTokenizer(br.readLine())..

DNA란 어떤 유전물질을 구성하는 분자이다. 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오티드의 첫글자 A, T, C, G를 따서 표현한다. 그리고 Hamming Distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클오티드 문자가 다른 것의 개수이다. 만약에 “AGCAT"와 ”GGAAT"는 첫 번째 글자와 세 번째 글자가 다르므로 Hamming Distance는 2이다. 우리가 할 일은 다음과 같다. N개의 길이 M인 DNA s1, s2, ..., sn가 주어져 있을 때 Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 s1의 Hamming Distance + s와 s2의 Hamming Distance + ... + s와 sn의 ..

병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다. - 2칸 위로, 1칸 오른쪽 - 1칸 위로, 2칸 오른쪽 - 1칸 아래로, 2칸 오른쪽 - 2칸 아래로, 1칸 오른쪽 병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다. 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자. 1. 입력 - 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이..

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다. 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오. 1. 입력 - 첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. - 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다. 2. 출력 - 첫째 줄에 주어진 추들로 측정할 수 ..

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오. 1. 입력 - 첫째..

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 1. 입력 - N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 2. 출력 - 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. - 그 수가 존재하지 않는다면, -1을 출력하라. 3. 예제 4. 코드 import java.util.*; class Main{ public static void main(String[] args){ char[] nums = new Scanner(System.in..

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 1. 입력 - 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. - 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. - 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 2. 출력 - 첫째 줄에 정답을 출력한다. 3. 예제 4. 코드 import java.io.*; class Main{ pub..

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다. 어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다. 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다. 각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오. 1. 입력 - 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. - 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. - i번째 수..

1. Problem - 그리디 알고리즘을 이용하여 거스름돈으로 지급할 동전의 최소한의 개수를 구해보자. - 그리디 알고리즘은 가장 큰 것부터 또는 가장 작은 것부터 선택하며 최적의 답을 찾아가는 알고리즘으로, 탐욕법이라고도 불린다. - 그리디 알고리즘은 정렬, 다이나믹 프로그래밍과 함께 사용되는 경우가 대다수이다. - 그리디 알고리즘이 항상 최적의 답을 도출하지는 않는다. 2. Input 1) 거스름돈 액수 3. Output 1) 거스름돈을 500원, 100원, 50원, 10원짜리 동전을 이용해서 지급할 때 필요한 동전의 최소 개수 4. Example 거스름돈으로 지급해야 하는 금액: 947원 // 500 < 947 < 1000 500원: 1 // 남은 금액: 447원 // 400 < 447 < 500 ..