Bldev

make X better with code

[자료 구조/알고리즘] 백트래킹 구현 

fun solve(initialState: State): List<Solution> {
    // 탐색을 하며 찾은 정답을 저장할 저장소
    val solutions = mutableListOf<Solution>()
    backtrack(initialState, solutions)
    return solutions
}

fun backtrack(
    // 현재 상태
    currentState: state,
    // 탐색을 하며 찾은 정답을 저장할 저장소
    solutions: MutableList<Solution>
) {
    // 1. 종료 조건 (Base Case)
    // 현재 상태가 문제의 해답이라면
    if (isSolution(currentState)) {
        solutions.add(currentState.toSolution())
        return
    }

    // 2. 재귀 호출 (Recursive Step)
    // 현재 상태에서 다음으로 진행 가능한 모든 상태들을 탐색
    for (state in getNextStates(currentState)) {
        // 상태 확인 (가지치기)
        if (isPromising(state)) {
            // 상태 변환 (전이)
            ...

            // 탐색 진행
            backtrack(state, solutions)
            
            // 백트랙
            // 함수 호출 스택에서 이전 상태로 돌아가는 백트랙은 재귀 호출이 끝난 후 자동으로 이루어진다.

            // 상태 되돌리기
            // 하나의 경로 탐색이 끝난 후에 다른 경로를 탐색할 수 있도록 상태를 이전 상태로 명시적으로 되돌려야 하는 경우 이 곳에서 수행한다.
            ...
        }
    }
}

// 현재 상태가 문제의 해답인지 확인
fun isSolution(state: state): Boolean {
    // 문제의 종료 조건 판별 로직
    ...
}

// 현재 상태에서 다음으로 진행 가능한 모든 상태를 조회
fun getNextStates(state: state): List<state> {
    // 다음으로 진행할 수 있는 모든 경우의 수를 조회
    ...
}

// 상태가 적합한지 확인
fun isPromising(state: state): Boolean {
    // 제약 조건 만족 검사 로직 구현
    ...
}


N-퀸 문제

class Solution {
    fun nQueens(n: Int): Int {
        // 퀸이 위치한 열 번호를 저장할 배열
        val board = IntArray(n) { 0 }
        val count = 0
        backtrack(n, 0, board, count)
        return count
    }

    fun backtrack(
        // 다음 상태 탐색을 위한 변수
        n: Int,
        row: Int,
        // 현재 상태
        board: IntArray
        // 탐색을 하며 찾은 정답을 저장할 저장소
        count: Int
    ) {
        // 1. 종료 조건
        // 모든 퀸을 성공적으로 배치한 경우
        if (row == n) {
            count++
            return
        }

        // 2. 재귀 호출
        // 현재 행(row)에 퀸을 놓을 수 있는 모든 열(col)을 탐색
        for (col in 0 until n) {
            // 상태 확인 (가지치기)
            // 현재 위치(row, col)에 퀸을 놓을 수 있는지 확인
            if (isPromising(row, col, board)) {
                // 상태 변환 (전이)
                // 퀸을 배치
                board[row] = col

                // 탐색 진행
                // 다음 행으로 이동
                backtrack(n, row + 1, board, count)

                // 백트랙

                // 상태를 덮어쓰는 방식이므로, 상태 되돌리기 과정은 별도로 필요하지 않다.
            }
        }
    }

    // 현재 위치(row, col)에 퀸을 놓을 수 있는지 확인
    fun isPromising(
        row: Int,
        col: Int,
        board: IntArray
    ): Boolean {
        // 같은 열에 퀸이 있는지, 대각선에 퀸이 있는지 확인
        for (i in 0 until row) {
            // 같은 열에 퀸이 있는지 (board[i] == col)
            // 또는 대각선에 퀸이 있는지 (abs(row - i) == abs(col - board[i]))
            if (board[i] == col || (row - i) == Math.abs(col - board[i])) {
                return false
            }
        }
        return true
    }
}

fun main() {
    val solution = Solution()
    val n = 4
    val result = solution.nQueens(n)
    println(result)
}
  • 노드: 퀸들의 현재 배치 상태
  • 간선: 한 행에서 다음 행으로 퀸을 놓는 것
  • 가지치기: 퀸을 놓으려는 위치가 이미 다른 퀸의 공격 범위에 있는 경우 퀸을 배치하지 않는 것
  • 루트 노드: 퀸이 놓이지 않은 초기 상태
  • 리프 노드: 더 이상 퀸을 놓을 수 없는 최종 상태
    • 정답인 경우: 모든 퀸이 놓인 상태
    • 정답이 아닌 경우: 더 이상 퀸을 놓을 수 없는 상태
  • 경로 탐색: 루트 노드에서 리프 노드까지 이어지는 일련의 퀸 배치 과정
  • 백트랙: 퀸을 놓을 수 없는 경우 이전 행으로 되돌아가서 다른 경로를 탐색하는 것


순열 문제

class Solution {
    fun permutations(n: Int, m: Int): List<List<Int>> {
        val results = mutableListOf<List<Int>>()
        val currentPermutation = mutableListOf<Int>()
        // 1부터 n까지의 숫자 사용 여부를 저장할 배열
        val used = BooleanArray(n + 1) { false }
        
        backtrack(n, m, currentPermutation, used, results)
        
        return results
    }

    fun backtrack(
        // 다음 상태 탐색을 위한 변수
        n: Int,
        m: Int,
        // 현재 상태
        currentPermutation: MutableList<Int>,
        used: BooleanArray,
        // 탐색을 하며 찾은 정답을 저장할 저장소
        results: MutableList<List<Int>>
    ) {
        // 1. 종료 조건
        // 현재 순열의 길이가 m과 같을 경우
        if (currentPermutation.size == m) {
            results.add(ArrayList(currentPermutation))
            return
        }
        
        // 2. 재귀 호출
        // 1부터 n까지의 모든 숫자를 탐색
        for (i in 1..n) {
            // 상태 확인 (가지치기)
            // 현재 숫자를 사용할 수 있는지 확인
            if (isPromising(i, used)) {
                // 상태 변환 (전이)
                currentPermutation.add(i)
                used[i] = true
                
                // 탐색 진행
                backtrack(n, m, currentPermutation, used, results)

                // 백트랙
                
                // 상태 되돌리기
                currentPermutation.removeAt(currentPermutation.size - 1)
                used[i] = false
            }
        }
    }

    // 현재 숫자를 사용할 수 있는지 확인
    fun isPromising(
        i: Int,
        used: BooleanArray
    ): Boolean {
        // 이미 사용한 숫자인지 확인
        if (used[i]) {
            return false
        }
        return true
    }
}

fun main() {
    val n = 3 // 1부터 3까지의 자연수
    val m = 2 // 2개를 선택
    val solution = Solution()
    val result = solution.permutations(n, m)
    result.forEach {
        // 각 순열 출력
        println(it.joinToString(" "))
    }
}
  • 노드: 현재까지 선택된 숫자의 부분 순열
  • 간선: 다음 숫자를 선택하는 것
  • 가지치기: 이미 선택한 숫자를 다시 선택하지 않는 것
  • 루트 노드: 아무 숫자도 선택되지 않은 초기 상태
  • 리프 노드: 더 이상 숫자를 선택할 수 없는 최종 상태
    • 모든 리프 노드가 정답
  • 경로 탐색: 루트 노드에서 리프 노드까지 이어지는 일련의 숫자 선택 과정
  • 백트랙: 선택했던 숫자를 선택하지 않은 상태로 변경하고 다른 숫자를 선택하여 경로를 탐색하는 것


조합 문제

class Solution {
    fun combinations(n: Int, m: Int): List<List<Int>> {
        val results = mutableListOf<List<Int>>()
        val currentCombination = mutableListOf<Int>()
        
        backtrack(n, m, 1, currentCombination, results)
        
        return results
    }

    private fun backtrack(
        // 다음 상태 탐색을 위한 변수
        n: Int,
        m: Int,
        start: Int,
        // 현재 상태
        currentCombination: MutableList<Int>,
        // 탐색을 하며 찾은 정답을 저장할 저장소
        results: MutableList<List<Int>>
    ) {
        // 1. 종료 조건 (Base Case)
        // 현재 조합의 길이가 m과 같을 경우
        if (currentCombination.size == m) {
            results.add(ArrayList(currentCombination))
            return
        }
        
        // 2. 재귀 호출 (Recursive Step)
        // start부터 n까지의 숫자를 탐색
        for (i in start..n) {
            // 상태 변환 (전이)
            currentCombination.add(i)
            
            // 탐색 진행
            // 현재 숫자 다음부터 탐색
            backtrack(n, m, i + 1, currentCombination, results)
            
            // 백트랙

            // 상태 되돌리기
            currentCombination.removeAt(currentCombination.size - 1)
        }
    }
}

fun main() {
    val n = 3 // 1부터 3까지의 자연수
    val m = 2 // 2개를 선택
    val solution = Solution()
    val result = solution.combinations(n, m)
    result.forEach {
        // 각 조합 출력
        println(it.joinToString(" "))
    }
}


문자열 조합 문제

class Solution {
    fun letterCombinations(digits: String): List<String> {
        val lettersArray = arrayListOf("", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")
        val result = mutableListOf<String>()
        val initialState = StringBuilder()

        if (digits.isEmpty()) {
            return emptyList()
        }

        fun backtrack(
            // 다음 상태 탐색을 위한 변수
            digits: String,
            index: Int,
            // 현재 상태
            currentState: StringBuilder,
            // 탐색을 하며 찾은 정답을 저장할 저장소
            result: MutableList<String>
        ) {
            // 1. 종료 조건
            // 모든 자릿수에 대해 처리한 경우
            if (index == digits.length) {
                val terminalState = currentState.toString()
                result.add(terminalState)
                return
            }

            val digit = Character.getNumericValue(digits[index])
            val letters = lettersArray[digit]

            // 2. 재귀 호출
            // 해당 자릿수의 모든 문자를 탐색
            for (i in letters.indices) {
                // 상태 확인 (가지치기)
                val letter = letters[i]
                currentState.append(letter)
                
                // 탐색 진행
                backtrack(digits, index + 1, currentState, result)

                // 백트랙

                // 상태 되돌리기
                currentState.deleteCharAt(currentState.length - 1)
            }
        }

        backtrack(digits, 0, initialState, result)

        return result
    }
}

fun main() {
    val solution = Solution()
    val result = solution.letterCombinations("23")
    println(result)
}


부분 집합

  • 노드: 현재까지 선택된 부분집합
  • 간선: 다음 원소를 포함하거나 포함하지 않는 것
  • 가지치기: 없음
  • 루트 노드: 아무 원소도 선택되지 않은 초기 상태
  • 리프 노드: 더 이상 숫자를 선택할 수 없는 최종 상태
    • 모든 리프 노드가 정답
  • 경로 탐색: 루트 노드에서 리프 노드까지 이어지는 일련의 원소 선택 과정
  • 백트랙: 포함한 원소를 제외하고 다른 경로를 탐색하는 것

Comments

You May Also Enjoy

[아키텍처/소프트웨어] 캐싱

캐싱(caching)이란 데이터 원본을 별도의 저장소에 복제하여 빠르게 제공하는 것이다. 캐싱은 데이터의 응답 지연 시간을 단축시키고 데이터를 제공하는 서버와 데이터를 제공받는 클라이언트 모두의 성능을 향상시킬 수 있는 중요한 방법이다.

[자료 구조/알고리즘] 문자열

문자열은 연속된 문자들이 그룹화되어 구성된 자료 구조이다. 따라서 데이터를 그룹화한 추상 자료형인 컬렉션(collection)의 다양한 자료 구조로 문자열을 구조화할 수 있으며 다양한 자료 구조 탐색 알고리즘을 사용하여 부분 문자열들을 탐색 및 비교하는 등의 문제를 해결할 수 있다.

[자료 구조/알고리즘] 백트래킹

백트래킹(backtracking)(또는 역추적) 알고리즘이란 최적의 해결책을 찾기 위해 모든 가능한 방법을 후보(candidate)로 구성한 후, 점진적으로 후보들을 시도하면서 유효한 후보가 아닐 경우(문제의 정답 조건을 만족하지 않을 경우) 문제 해결 과정에서 제외하고 되돌아가 ...