분류 전체보기 (229) 썸네일형 리스트형 [백준][코틀린][10610] 30 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 문제 풀이 1. 주어진 숫자를 30의 배수 중 가장 큰 수가 되게 하기 위해서 다음과 같은 조건을 찾는다. 2. 30의 배수는 3의 배수와 10의 배수의 최소 공배수이다. 3. 따라서 주어진 숫자는 10의 배수가 되면서 3의 배수도 되어야 한다. 4. 주어진 숫자를 내림 차순으로 정렬한다. 5. 10으로 나누어 떨어지지 않으면 -1을 출력한다. 6. 첫자리 부터 마지막 자리까지 더한 합을 3으로 나.. [백준][코틀린][2875] 대회 or 인턴 https://www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net 문제 풀이 1. 여학생 2명과 남학생 1명이 한팀이 된다. 그리고 K명이 인턴쉽에 참가하고 팀이 될 수 없으므로 이를 이용하여 다음과 같은 식을 구한다. (women + men >= 3 + K) 2. 남은 여학생이 팀이 구성될려면 최소 2명이상 있어야 하고 남학생은 최소 1명이상 있어야 한다. 3. while 문을 반복하여 count 값을 증가 시킨다. 4. count 값을 출력한다. 코드 import java.io.* fun main(args: Array) { v.. [백준][코틀린][1744] 수 묶기 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 풀이 1. 입력을 sequence int 배열에 저장한다. 2. sequence 배열을 내림 차순으로 정렬 한다. 3. 양수에 대해서 index 를 0부터 시작하여 두 수의 곱이 두 수의 합보다 크면 result 에 저장하고 index 를 2 증가 시킨다. 4. 두 수의 합이 더 크면 result 에 현재 index 의 값을 저장하고 index 를 1 증가 시킨다. 5. 음수에 대해서 in.. [백준][코틀린][1541] 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 풀이 1. 입력된 문자열을 "-" 기준으로 나눈다. 2. 나누어진 문자열을 "+" 기준으로 나누고 값을 합하여 list 에 저장한다. 3. result 에 list[0] 값을 넣고 list 를 1 부터 마지막 index 까지 탐색하여 result -= list[index] 로 업데이트 한다. 4. result 를 출력한다. 코드 import java.io.* fun main(args: .. [백준][코틀린][12015] 가장 긴 증가하는 부분 수열2 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 풀이 1. 입력의 개수가 10,000 이하일 경우에는 완전 탐색을 이용하여 LIS 길이를 구한다. 2. 10,000 를 넘을 경우에는 이분 탐색을 이용해서 LIS 를 구해야 한다. 3. LIS 값을 저장하는 seq 배열을 선언하고 초기 값을 Int.MIN_VALUE 로 채운다. 4. A[i] 값이 seq[last index] 값보다 클 경우 seq 에 A[i] 를 저장한다. 5. A[i] 값.. [알고리즘] 가장 긴 증가하는 부분 수열 구하기 수열 A = { 10, 20, 40, 30, 1, 3, 90 } 이 주어졌을 때 가장 긴 증가하는 부분 수열(LIS)을 구하는 알고리즘을 알아본다. LIS 를 구하는 방법은 총 세 가지 정도가 있다. 1. 완전 탐색을 이용하여 LIS 구한다. (시간 복잡도 : O(N^2)) 2. DP 를 이용하여 LIS 구한다. (시간 복잡도 : O(N^2)) 3. 이분탐색을 이용하여 LIS 를 구한다. (시간 복잡도 : O(NlogN)) 문제에서 N 의 개수가 10,000 개까지 일 경우 1번 혹은 2번의 방법으로 구할 경우 1초 내에 결과를 얻을 수 있다. 2번 DP 방법은 아직 완전히 익숙하지 않아 완전 탐색에 대한 알고리즘을 우선 기술 한다. 완전 탐색을 이용한 LIS 구하기 1. 입력으로 주어지는 수열을 A 배.. [백준][코틀린][2109] 순회강연 https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 문제 풀이 1. 입력으로 주어지는 강연 정보를 list 에 저장한다. 2. list 를 강연료를 기준으로 내림 차순 정렬한다. 3. 10001 크기의 lecture int 배열을 선언한다. 강연을 잡을 경우 lecture 배열에 강연료를 업데이트하는 용도로 사용한다. 4. list 를 다음과 같은 기준으로 탐색 한다. 4-1. list 의 d 값을 index 로.. [백준][코틀린][1202] 보석 도둑 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 풀이 1. 보석의 정보를 jewel list 에 (무게, 가격)을 Pair 값으로 저장한다. 2. bag queue 에 가장 무게 정보를 저장한다. 3. jewel list 를 무게를 기준으로 오름 차순으로 정렬한다. 4. bag queue 를 오름 차순으로 정렬한다. 5. bag 의 queue 를 비어질 때 까지 pop 으로 꺼내.. 이전 1 2 3 4 5 6 7 ··· 29 다음