코딩테스트나 알고리즘 문제는 다양한 유형과 난이도로 등장합니다. 이번 강좌에서는 괄호의 배치를 통해 수식을 어떻게 최솟값으로 만들 수 있는지를 다루어 보겠습니다. 이 문제는 괄호 배치를 통해 수식을 얼마나 효율적으로 계산하는지를 묻는 문제입니다.
문제 설명
주어진 숫자와 연산자로 이루어진 수식을 최솟값으로 만드는 괄호 배치를 찾는 문제입니다.
예를 들어, 수식 “2 – 3 + 5″가 주어졌을 때, 괄호를 적절히 배치하여 최솟값을 계산해야 합니다.
괄호는 각 연산자의 앞뒤에 자유롭게 넣을 수 있으며, 그 결과로 도출되는 값을 최소화해야 합니다.
입력
수식은 문자열로 입력되며, 연산자는 +, – 두 가지 뿐입니다. 수식에는 공백이 포함되지 않습니다.
수식의 길이는 1 이상 50 이하입니다.
출력
괄호를 적절히 배치하여 계산한 최솟값을 출력합니다.
문제 해결 과정
문제를 해결하기 위해서는 동적 프로그래밍(Dynamic Programming) 또는 분할 정복(Divide and Conquer) 기법을 사용할 수 있습니다.
여기서는 분할 정복 방식을 사용하여 문제를 해결해보겠습니다.
1단계: 입력을 파싱하기
문제를 해결하기 위해서는 먼저 입력된 수식을 숫자와 연산자로 분리해야 합니다.
수식에서 숫자는 정수일 것이고, 연산자는 ‘+’ 또는 ‘-‘입니다.
따라서 문자열을 순회하면서 숫자가 나오면 숫자 배열에 추가하고, 연산자가 나오면 연산자 배열에 추가합니다.
2단계: 모든 경우의 수를 고려하기
이후에는 모든 가능한 괄호의 배치를 고려하여 수식의 최솟값을 계산해야 합니다.
이를 위해서, 모든 연산자에 대해 왼쪽 부분과 오른쪽 부분을 나누어 각각의 최솟값을 구합니다.
나누어진 양쪽의 최솟값에 연산자를 적용하여 새로운 값을 만들고, 이 중 최솟값을 찾으면 됩니다.
3단계: 재귀적 접근
위 과정을 재귀적으로 구현함으로써 각 부분 문제로 나누고 이를 해결해 나갈 수 있습니다.
각 단계에서 최솟값을 찾기 위해 연산자를 기준으로 수식을 자르고, 왼쪽 부분과 오른쪽 부분에서 최솟값을 계산하는 방식으로 진행합니다.
예제 코드
fun findMinimumValue(expression: String): Int {
val numbers = mutableListOf()
val operators = mutableListOf()
var num = StringBuilder()
// 수식 파싱
for (char in expression) {
when {
char.isDigit() -> num.append(char)
char == '+' || char == '-' -> {
numbers.add(num.toString().toInt())
operators.add(char)
num = StringBuilder()
}
}
}
// 마지막 숫자 추가
if (num.isNotEmpty()) {
numbers.add(num.toString().toInt())
}
return calculateMinimum(numbers, operators, 0, numbers.size - 1)
}
fun calculateMinimum(numbers: List, operators: List, start: Int, end: Int): Int {
if (start == end) return numbers[start]
var minValue = Int.MAX_VALUE
for (i in start until end) {
val leftMin = calculateMinimum(numbers, operators, start, i)
val rightMin = calculateMinimum(numbers, operators, i + 1, end)
val result = when (operators[i]) {
'+' -> leftMin + rightMin
'-' -> leftMin - rightMin
else -> throw IllegalArgumentException("Unsupported operator: ${operators[i]}")
}
minValue = minOf(minValue, result)
}
return minValue
}
fun main() {
val expression = "2-3+5"
val result = findMinimumValue(expression)
println("최솟값: $result")
}
결론
이번 강좌에서는 괄호의 배치를 통해 수식을 최솟값으로 만드는 문제를 다뤘습니다.
다양한 접근 방법을 통해 문제를 해결할 수 있지만, 여기서는 재귀적 접근과 분할 정복 방식을 사용했습니다.
실제 코딩 테스트에서 이러한 문제를 만난다면 철저히 문제를 분석하고,
효율적이고 명확한 알고리즘을 통해 접근하는 것이 중요합니다.
앞으로도 다양한 문제에 대한 해결책을 찾아보시길 바랍니다.