[알고리즘] Dynamic Programming (동적 계획법)
Dynamic Programming (동적 계획법)이란? 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것입니다. DP는 왜 사용하는 걸까? 피보나치 수열을 예시로 들 수 있습니다. 피보나치 수열은 아래와 같습니다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... => fibo(n) = fibo(n-1) + fibo(n-2) 이런 알고리즘에서 f(n)을 호출한다고 하면 아래와 같이 중복되는 숫자들이 늘어나게 됩니다. 즉, 시간복잡도가 O(2^n)이 걸리게 됩니다. 하지만 이미 계산했던 값들을 저장한다면 O(n)까지 줄일 수 있습니다. 이것이 DP를 사용하는 이유입니다. DP의 접근방식 기본적..
2023. 2. 12.
[Kotlin] filter, map 호출 순서에 따른 성능 차이
이번에 filter와 map의 호출 순서에 따른 성능차이를 확인해보려고 합니다. map, filter VS filter, map 먼저 사용될 data class를 정의합니다. data class Food( val name: String, val price: Int ) 1. map() 함수를 수행한 뒤, filter() 함수를 수행한다. fun main() { val list = listOf( Food("chicken", 20000), Food("pizza", 25000), Food("sushi", 21000), Food("coffee", 5500), Food("beer", 3800) ) val result = list.map(::mapToName) .filter(::filterByPrice) print(..
2023. 2. 3.
[Kotlin] Collection 관련 함수들 (filter, map, flatmap)
filter 주어진 람다의 조건을 만족하는 원소만 필터링하는 기능입니다. List와 Set을 필터링하는 경우에는 List로, Map을 필터링하는 경우에는 Map으로 반환합니다. filter 함수는 요소의 값만 확인할 수 있습니다. val list = listOf("A", "B", "C") val newList = list.filter { it != "A" } println(newList) // input: [A, B, C] // Result: [B, C] map 각 원소를 원하는 형태로 변환해서 새 컬렉션을 만듭니다. 새로 만들어지는 컬렉션은 원본 컬렉션과 원소의 개수는 같지만 각 원소는 주어진 람다(함수)에 따라 변환됩니다. val list = listOf("A", "B", "C") val newLis..
2023. 2. 3.
