전체 글 (229) 썸네일형 리스트형 분할 정복(Divide & Conquer) 정의 문제를 나눌 수 없을 때까지 나눈 후 다시 합병하여 결과를 얻는 알고리즘이다. 시간 복잡도는 O(nlong) 를 가진다. 합병 정렬 아래와 같이 주어진 정렬을 합병 정렬을 이용하여 정렬한다. 7 5 3 9 1 6 정렬을 가운데를 기준으로 더 이상 나누어 지지 않을 때 까지 쪼갠다.(Divde) 쪼개질 수 없을 때까지 나눈 후 다시 정렬한다. [백준][KOTLIN] 13305 주유소 - https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 1. 각 입력을 Price, Distance 배열에 저장한다. 2. newPrice field 를 선언하고 Price[0] 값을 저장 한다. 3. Distance 배열 만큼 검색을 하는데 이때 newPrice 값과 현재 index 의 Price 값을 비교하여 작은 값으로 계산을 한다. 4. 3번에서 newPrice 보다 작은 값이 들어 올 경우 newPrice 를 작은 값으.. [백준][KOTLIN] 1541 잃어버린 괄호 - https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 1. 주어진 입력은 "-" 문자열을 기준으로 쪼갠다. 2. 1번에서 쪼개진 문자열을 "+" 기준으로 쪼개고 각 문자열의 합을 구한다. 3. 2번에서 구한 각 합을 빼서 최소 값을 구한다. 코드 import java.util.* fun main(args: Array) { val sc = Scanner(System.`in`) val splitMinus = sc.next().split(".. [백준][KOTLIN] 11399 ATM - https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 1. 입력된 배열을 오름 차순으로 정렬한다. 2. 정렬된 값을 문제의 조건에 맞게 합을 구해 결과에 저장 한다. 코드 import java.util.* fun main(args: Array) { val sc = Scanner(System.`in`) val N = sc.nextInt() val P = Array(N) { sc.nextInt() } Arrays.sort(P) var result = 0 for (i in 0.. [백준][KOTLIN] 1931 회의실 배정 - https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 1. 회의실 시간 정보를 저장하는 배열을 선언한다. 2. 배열을 종료 시간 기준으로 오름 차순 정렬 한다. 3. 2번의 정렬된 배열을 시작 시간 기준으로 오름 차순 정렬 한다. 4. 검색되는 회의의 종료 시간이 다음 회의의 시작 시간보다 작은 경우를 검색 한다. 코드 import java.io.* import java.util.* fun main(args: Array) { val br = BufferedReader(InputStreamReader(System.`in`)) // 회의실 개수 val N = .. [백준][KOTLIN] 11047 동전 0 - https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 코드 import java.io.* import java.util.* fun main(args: Array) { val br = BufferedReader(InputStreamReader(System.`in`)) val st = StringTokenizer(br.readLine()) val N = st.nextToken().toI.. [백준][Kotlin] 12865 평범한 배낭 - https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 1. 입력에 대해서 가질 수 있는 최대 가치에 대해서 모두 검색 한다. 2. 아래의 표를 이용해서 점화식을 구한다. (가로 : 최대 무게 경우의 수(K), 세로 : 물건 순서(N)) 1 2 3 4 5 6 7 1 0 0 0 0 0 13 13 2 0 0 0 8 8 13 13 3 0 0 6 8 8 13 14 4 0 0 6 8 1.. [백준][Kotlin] 1912 연속합 - https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 1. 수열을 저장하는 배열을 선언한다. 2. 수열을 순환하면서 최대값을 저장하는 dp 배열을 선언한다. 3. 현재 입력되는 값과 이전 최대값과 현재 입력 값 중 최대 값을 저장한다. 4. 저장된 dp 배열에서 최대값을 구한다. 코드 import java.util.* fun main(args: Array) { val sc = Scanner(System.`in`) val n = sc.nextInt() .. 이전 1 ··· 19 20 21 22 23 24 25 ··· 29 다음
