Code in

탐욕 알고리즘 Greedy Algorithm 그리디 알고리즘은 동적 프로그래밍을 할 때 지나치게 많은 일을 하는 것을 보다 효율적으로 바꾸기 위해서 생겨난 알고리즘입니다. 따라서 동적 프로그래밍과 함께 쓰였을 때 서로 보완할 수 있습니다. Greedy Algorithm은 탐욕 알고리즘, 욕심쟁이 알고리즘으로 불립니다. 매 순간 최선의 선택을 하여 최종적으로 최선이 되도록 하는 알고리즘입니다. 매 순간 해당 순간을 위한 최선의 선택만을 하기 때문에 미래에 어떤 영향을 줄지는 생각하지 않습니다. 모든 경우에 그리디 알고리즘이 적합하진 않지만, 몇몇 케이스에서는 그리디 알고리즘으로 최종적으로 최선인 답을 보다 효율적으로 구할 수 있습니다. 요약하면, 1. 동적 계획법과 마찬가지로 최적화 문제를 푸는 데 사용되..

완전 탐색 알고리즘 - Brute Force : 모든 경우의 수를 확인하여 답을 찾아내는 알고리즘. BF는, 모든 경우의 수를 확인하기 때문에 성공하면 100% 정확한 답을 찾아낼 수 있다. 만들기가 비교적 쉽고 병렬 작업이 가능하다는 장점을 가지고 있지만, 시간적인 측면에서는 비효율적이라는 단점을 가지고 있다. 탐색해야 할 요소들이 많은 경우에는 보다 효율적인 방법을 찾아서 사용하는 것이 좋겠지만, 개수가 정해져 있거나 적은 경우에는 완전 탐색을 사용하여 보다 쉽고 정확하게 답을 구할 수 있다. 완전 탐색을 구현하기 위해서는, 1. 반복문을 사용하거나 (for, while) 2. 재귀 함수를 사용할 수 있다. (return function / 같은 함수 호출의 반복) 재귀 함수의 경우, 더 이상 함수를..

프로그래머스 탐욕법(Greedy) 큰 수 만들기 문제입니다. IntelliJ에서의 풀이입니다. var k: Int = 4 val number: String = "4177252841" fun solution(number: String, k: Int): String { val str: StringBuilder = StringBuilder(number) // String에 비해서 시간이 대략 1/6으로 감소. var i = 0 var kk = k // k는 val이라서 var로 다시 저장. OOP를 위한 것? var len = str.length - 1 while (i = str[i + 1..

프로그래머스 탐욕법(Greedy) 부분 체육복 문제입니다. IntelliJ에서의 풀이입니다. val n: Int = 5 // 2 ~ 30 val lost: IntArray = intArrayOf(2, 4) // size 1 ~ n val reserve: IntArray = intArrayOf(1, 3, 5) // size 1 ~ n fun solution(n: Int, lost: IntArray, reserve: IntArray): Int { var answer = 0 var current: IntArray = IntArray(n+2){1} // 번호는 1부터 시작 끝 1개는 error 방지 lost.forEach { current[it]-- } reserve.forEach { current[it]++ ..

프로그래머스 완전 탐색 부분 카펫 문제입니다. IntelliJ에서의 풀이입니다. val brown: Int = 24 // 최소 8 val yellow: Int = 24 // 최소 1 fun solution(brown: Int, yellow: Int): IntArray { var answer = intArrayOf() // brown = 2*(가로+세로 - 2) yellow = 가로*세로 - brown // (가로+세로) = brown/2 + 2 // 가로*세로 = brown + yellow val mul: Int = brown + yellow val sum: Int = brown / 2 + 2 // 가로 = mul/세로 // 가로+세로 = sum var height = 3 // 최솟값 while (mul..

프로그래머스 완전 탐색 부분 소수 찾기 문제입니다. IntelliJ에서의 풀이입니다. isPrime 참고: https://www.geeksforgeeks.org/sieve-of-eratosthenes/ Sieve of Eratosthenes - GeeksforGeeks Sieve of Eratosthenes - The sieve of Eratosthenes is one of the efficient ways to find all primes smaller than given n www.geeksforgeeks.org import kotlin.math.log10 import kotlin.math.pow val numbers: String = "011" fun solution(numbers: String):..

프로그래머스 완전탐색 부분 모의고사 문제입니다. IntelliJ에서의 문제 풀이입니다. val operations: IntArray = intArrayOf(1, 3, 2, 4, 2) fun solution(answers: IntArray): IntArray { var answer = intArrayOf() var a: Int = 0 // 맞은 개수 count var b: Int = 0 var c: Int = 0 val aa: IntArray = intArrayOf(1, 2, 3, 4, 5) // 답안지 val bb: IntArray = intArrayOf(2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5) val cc: IntArray = intArrayOf(3, 3, ..

프로그래머스의 힙 부분 이중우선순위큐 문제입니다. IntelliJ에서의 풀이입니다. import java.util.PriorityQueue // Kotlin은 JVM: Java Virtual Machine 을 사용하기 때문에 Java에서 import합니다. val operations: Array = arrayOf("I 7", "I 5", "I -5", "D -1") // "I 7", "I 5", "I -5", "D -1" // 7, 5 // "I 16", "D 1" // 0, 0 fun solution(operations: Array): IntArray { var answer = intArrayOf() val minHeap = PriorityQueue() // min Heap 생성 val maxHeap ..

프로그래머스 힙 부분 디스크 컨트롤러 문제입니다. IntelliJ에서의 문제풀이입니다. import java.util.PriorityQueue // Kotlin은 JVM: Java Virtual Machine 을 사용하기 때문에 Java에서 import합니다. val jobs: Array = arrayOf(intArrayOf(0, 3), intArrayOf(1, 9), intArrayOf(500, 6)) fun solution(jobs: Array): Int { var answer = 0 var timer = 0 // 현재 시간 // 0은 요청 시간, 1은 소요 시간 val waitminHeap = PriorityQueue(compareBy({it[0]}, {it[1]})) // wait 에서는 요청 시..

프로그래머스 큐, 프린터 문제입니다. IntelliJ에서의 풀이입니다. import java.util.Queue import java.util.LinkedList // Kotlin은 JVM: Java Virtual Machine 을 사용하기 때문에 Java의 Queue를 import합니다. var location: Int = 2 val priorities: IntArray = intArrayOf(2, 1, 3, 2) fun solution(priorities: IntArray, location: Int): Int { var answer = 0 data class print(val value: Int, val ff: Boolean) // data class 를 사용하여 print라는 데이터 형식을 선언합니..