알고리즘 (102) 썸네일형 리스트형 [백준][KOTLIN] 2630 색종이 만들기 - https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 1. 입력된 정보를 저장하는 2차원 배열을 선언하고 값을 저장한다. 2. 배열의 색이 같은 색인지 확인 한다. 3. 2번에서 같은 색일 경우 Blue 혹은 White Count 를 증가 한다. 4. 2번에서 다른 색일 경우 각 사분면에 따라 분할 한다. 5. 2번 ~ 3번 과정을 색종이가 더 이상 나누어 지지 않을 때까지 반복 한다. 코드 import java... 분할 정복(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.. 이전 1 ··· 5 6 7 8 9 10 11 ··· 13 다음
