알고리즘(w.KOTLIN)/그리디(Greedy) (16) 썸네일형 리스트형 [백준][코틀린][12904] A와 B https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문제 풀이 1. S 를 문자열을 바꾸는 조건을 이용하여 완전 탐색을 할 경우 시간 초과가 발생한다. 2. 타겟 문자인 T에 대해서 마지막 글자가 'A' 라면 이전의 글자에 'A' 만 더한 것이 된다. 3. 마찬가지로 T의 마지막 글자가 'B'라면 'B' 를 제외한 T를 뒤집는다. 4. S == T 일 경우 1을 출력하고 T의 길이가 1이 될때까지 탐색이 되었다.. [백준][코틀린][12970] AB https://www.acmicpc.net/problem/12970 12970번: AB 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net 문제 풀이 1. 문자열을 N의 길이만큼 Char 배열에 A로 채운다. 2. 문자열의 마지막 인덱스 부터 0번째 인덱스까지 현재 인덱스(i)의 문자를 'B'로 변환하면서 다음과 같이 탐색한다. 3. 0부터 N - 2 까지 j 인덱스를 가지는 for문과 j 부터 N - 1까지 k인덱스를 가지는 이중 for문을 이용하여 조건의 쌍을 이루는 개수를 구한다. 4. 개수의 합이 K보다 크면 i 인덱스의 문자를 'B'로 변환할 수 없으므로.. [백준][코틀린][1783] 병든 나이트 https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 1. 병든 나이트의 이동 조건을 보면 오른쪽으로만 무조건 이동이 가능하고 이동 횟수가 아무리 많아도 4가지의 이동 조건을 만족 시키지 못하면 최대 횟수는 3이 된다. 2. 세로의 경우에 대해서 아래와 같이 최대 이동 회수를 확인 한다. - 세로가 1일 경우 : 위아래 이동이 불가능하므로 최대 이동 회수는 0이므로 방문 칸은 처음 위치만 포함된 1이 된다. O - 세로가 2일 경우 1. 가로가 3일 경우 1회 방문 가능하다. 2. 가로가 5일 경우 2회.. [백준][코틀린][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] 값.. 이전 1 2 다음