전체 글 (219) 썸네일형 리스트형 [백준][코틀린][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 으로 꺼내.. [백준][코틀린][1285] 동전 뒤집기 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 문제 풀이 1. 주어진 동전들에 대해서 행/열을 각각 회전할 수 있다. 이때 행을 기준으로만 볼때 N=3 일 경우 다음과 같은 경우의 수로 행을 회전할 수 있다. - 행의 회전 경우의 수 1) 행을 회전하지 않는 경우 : 1가지 2) 하나의 행을 회전하는 경우 : (0행, 1행, 2행) : 3가지 3) 두 개의 행을 회전하는 경우 : (0, 1), (0, 2), (1, 2) : 3가지 4) 세.. [백준][코틀린][2138] 전구와 스위치 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 문제 풀이 1. 현재 전구 상태(currentLamp)와 만들고자 하는 상태(targetLamp) 를 선언한다. 2. lamp1Count, lamp2Count 를 선언하고 각각 스위치를 켠 횟수를 저장한다. 3. lamp1, lamp2 배열을 선언하고 lamp1에는 0번째 전구를 켜지 않은 배열을 저장하고 lamp2에는 0번째 전구를 배열을 저장한다. lamp2Co.. 이전 1 2 3 4 5 6 ··· 28 다음
