검색,탐색 - moggaa/kotlin-coding-test GitHub Wiki
- 배열 탐색시 O(logN) 보장
fun binarySearch(){
//정렬이 되어있어야 사용 가능 (검색 실패시 -> 인덱스 음수 반환)
val arr = IntArray(100){
it + 1
}
val index = arr.binarySearch(22)
}
- 모든 경로 조회, 한번에 하나탐색
fun dfs(index: Int) {
visited[index] = true
println(index)
if(condition){
}
// 구현
for (next in edges[index]) {
if (!visited[next]) {
dfs(next)
}
}
}
- 최단 경로 고려
fun bfs(start: Int) {
queue.add(start)
visited[start] = true
while (queue.isNotEmpty()) {
val head = queue.poll() // 첫 원소 반환 후 remove
println(head)
if(condition){
}
for (next in edges[head]) {
if (!visited[next]) {
visited[next] = true
queue.add(next)
}
}
}
}
순열 리스트 생성
fun <T> permutation(el: List<T>, fin: List<T> = listOf(), sub: List<T> = el ): List<List<T>> {
return if(sub.isEmpty()) listOf(fin)
else sub.flatMap { permutation(el, fin + it, sub - it) }
}
조합 리스트 생성
fun <T> combination(answer: MutableList<List<T>>, el: List<T>, ck: Array<Boolean>, start: Int, target: Int) {
if(target == 0) {
answer.addAll( listOf(el.filterIndexed { index, t -> ck[index] }) )
} else {
for(i in start until el.size) {
ck[i] = true
combination(answer, el, ck, i + 1, target - 1)
ck[i] = false
}
}
}
fun main(args: Array<String>) {
var arr = listOf(1, 2, 3, 4) // 1. Int
//var arr = "asdf".toList() // 2. String
for(i in 1 .. arr.size) {
val answer = mutableListOf<List<Int>>() // 1. Int
// val answer = mutableListOf<List<Char>>() // 2. String
println("================$i 개====================")
combination(answer, arr, Array<Boolean>(arr.size) { false }, 0, i)
answer.forEach { println(it) }
}
}
reference : https://notepad96.tistory.com/111