알고리즘 개념 정리

1. 깊이 우선 탐색(DFS)

[재귀호출 풀이]

fun dfs(graph: Array<List<Int>>, v: Int, visited: BooleanArray) {
    visited[v] = true
    println(v) // 처리 로직

    for (neighbor in graph[v]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited)
        }
    }
}

fun main() {
    val graph = arrayOf(
        listOf(),          // 0번 노드 (사용 안 함)
        listOf(2, 3, 4),   // 1번 노드와 연결된 노드
        listOf(1, 5),
        listOf(1),
        listOf(1),
        listOf(2)
    )
    val visited = BooleanArray(graph.size)
    dfs(graph, 1, visited)
}

✅ 언제 재귀 DFS를 선택할까? : 빠르게 구현할 수 있고, 문제 크기가 작을 때 유리

상황	이유
문제 조건이 작거나 노드 수가 적음 (예: ≤ 10⁴)	재귀 호출이 간결하고 빠르게 작성 가능
백트래킹 문제	자연스럽게 "되돌아가는 구조"가 재귀에 잘 맞음
순열, 조합, 부분집합	함수 인자만으로 상태 관리가 쉬움
트리 탐색 (후위/전위 순회 등)	트리는 깊이가 제한적이므로 재귀로 처리하기 좋음

[스택 풀이]

import java.util.Stack

fun dfsStack(graph: Array<List<Int>>, start: Int) {
    val visited = BooleanArray(graph.size)
    val stack = Stack<Int>()

    stack.push(start)

    while (stack.isNotEmpty()) {
        val v = stack.pop()

        if (!visited[v]) {
            visited[v] = true
            println(v) // 처리 로직

            // 인접 노드를 역순으로 넣어야 오름차순으로 방문됨
            for (neighbor in graph[v].reversed()) {
                if (!visited[neighbor]) {
                    stack.push(neighbor)
                }
            }
        }
    }
}

fun main() {
    val graph = arrayOf(
        listOf(),
        listOf(2, 3, 4),
        listOf(1, 5),
        listOf(1),
        listOf(1),
        listOf(2)
    )
    dfsStack(graph, 1)
}

✅ 언제 스택 DFS를 선택할까? : 성능 안정성이 필요하거나, 방문 순서 세밀 제어가 필요할 때

상황	이유
깊은 그래프 (노드 수가 많거나, 깊이 10⁵ 이상 가능성)	코틀린/JVM은 기본 재귀 깊이 제한 있음 (StackOverflow 방지)
방문 순서를 정밀하게 제어해야 함	스택에 넣는 순서 조작 가능 (reversed() 등 활용)
재귀가 금지된 환경 (예: 일부 코딩 테스트 플랫폼)	명시적 스택으로 안전하게 처리 가능
디버깅이 복잡한 문제	상태를 명시적으로 관리하므로 디버깅이 용이함

2. 너비 우선 탐색(BFS)

📌 개념 요약

• 너비 우선 탐색
• 가까운 노드부터 탐색
• 큐 사용

import java.util.LinkedList
import java.util.Queue

fun bfs(graph: Array<List<Int>>, start: Int) {
    val visited = BooleanArray(graph.size)
    val queue: Queue<Int> = LinkedList()

    queue.add(start)
    visited[start] = true

    while (queue.isNotEmpty()) {
        val v = queue.poll()
        println(v) // 처리 로직

        for (neighbor in graph[v]) {
            if (!visited[neighbor]) {
                queue.add(neighbor)
                visited[neighbor] = true
            }
        }
    }
}

fun main() {
    val graph = arrayOf(
        listOf(),
        listOf(2, 3, 4),
        listOf(1, 5),
        listOf(1),
        listOf(1),
        listOf(2)
    )
    bfs(graph, 1)
}

항목	DFS (재귀)	BFS (큐)
구조	재귀 함수 호출	Queue 사용 (LinkedList)
사용처	백트래킹, 순열, 미로 등	최단 거리, 레벨 순회 등
방문 체크	visited[v] = true 위치 중요	동일

3. 부분합 & 누적합

📌 개념 요약

• 인덱스 0부터 i까지의 합을 미리 계산해 두는 방식
• 구간 합 sum(i..j)를 O(1)에 계산 가능

fun computePrefixSum(arr: IntArray): IntArray {
    val prefixSum = IntArray(arr.size + 1) // 0번 인덱스는 0으로 비움
    for (i in arr.indices) {
        prefixSum[i + 1] = prefixSum[i] + arr[i]
    }
    return prefixSum
}

fun main() {
    val arr = intArrayOf(3, 2, 4, 5, 1)
    val prefixSum = computePrefixSum(arr)

    // 예: 1번~3번 인덱스 합 (2 + 4 + 5 = 11)
    val sum = prefixSum[4] - prefixSum[1]
    println("부분합: $sum")  // 11
}

4. 백트래킹

🔷 개념

• 모든 경우를 시도하는 완전탐색 중에, 조건을 만족하지 않는 경우는 중간에 탐색을 멈추는 가지치기(Pruning) 기법.
• DFS 기반으로 재귀를 돌리되,
• 이미 사용한 값은 다시 사용하지 않도록 used 배열 활용.
• 목적 달성하면 return으로 종료.

🔷 예제: 리스트 [1,2,3]에서 2개 숫자를 뽑는 모든 순서 출력

fun backtrack(arr: List<Int>, used: BooleanArray, path: List<Int>, m: Int) {
    if (path.size == m) {
        println(path)
        return
    }

    for (i in arr.indices) {
        if (!used[i]) {
            used[i] = true
            backtrack(arr, used, path + arr[i], m)
            used[i] = false  // 선택 취소 (되돌리기)
        }
    }
}

fun main() {
    val arr = listOf(1, 2, 3)
    val used = BooleanArray(arr.size)
    backtrack(arr, used, emptyList(), 2)
}

출력

[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

5. 다이나믹 프로그래밍(DP)

🔷 개념

• 큰 문제를 작은 문제로 나눠서 푸는 방식이고, 같은 계산을 여러 번 하지 않도록 이전 결과를 저장해서 재활용하는 전략.
• 중복 계산을 방지하기 위해 memo 배열을 사용.
• 재귀 호출에서 이미 계산된 값은 다시 호출하지 않음.

🔷 예제: 피보나치 수열 (F(n) = F(n-1) + F(n-2))

val memo = IntArray(100) { -1 }

fun fib(n: Int): Int {
    if (n <= 1) return n
    if (memo[n] != -1) return memo[n]

    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]
}

fun main() {
    println(fib(10)) // 55
}

6. 그리디(Greedy)

🔷 개념

• 매 순간 가장 최선처럼 보이는 선택을 하면 전체에서도 최적일 거라고 믿고 푸는 방식.
• 선택의 순간마다 "지금 제일 좋은 것"을 고르고,
• 그 결과가 전역적으로도 최적이 되는 문제에만 적용 가능.

🔷 예제: 1260원을 500/100/50/10원 동전으로 최소 개수로 바꾸기

fun main() {
    var money = 1260
    val coins = listOf(500, 100, 50, 10)
    var count = 0

    for (coin in coins) {
        val use = money / coin
        count += use
        money %= coin
    }

    println("필요한 동전 개수: $count") // 6
}

✅ 3가지 비교 요약

알고리즘	개념 요약	코드 특징	언제 사용
백트래킹	조건을 만족하는 모든 경우를 찾되, 불필요한 탐색은 미리 중단	DFS + used[] + 재귀	모든 조합/순열/조건 탐색
DP	중복되는 계산을 기억해서 빠르게 처리	memo[] + 재귀 or 반복문	피보나치, 경로, 최솟값, 최대값
Greedy	지금 당장 가장 좋은 선택만 함	정렬 + 반복문	동전 문제, 회의실 배정 등

7. 이분탐색

✅ 이분 탐색 개념 요약

• 전제: 배열이 오름차순(또는 내림차순)으로 정렬되어 있어야 함
• 중간값과 찾는 값을 비교해서 탐색 범위를 반으로 줄임

fun binarySearch(arr: IntArray, target: Int): Int {
    var left = 0
    var right = arr.lastIndex

    while (left <= right) {
        val mid = (left + right) / 2

        when {
            arr[mid] == target -> return mid // 찾았다!
            arr[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }

    return -1 // 못 찾음
}

fun main() {
    val arr = intArrayOf(1, 3, 5, 7, 9, 11, 13)
    val target = 7
    val index = binarySearch(arr, target)

    if (index != -1) {
        println("값 $target 은 ${index}번 인덱스에 있습니다.")
    } else {
        println("값을 찾을 수 없습니다.")
    }
}