문제 설명
괄호의 배치에 따라 수식의 계산 결과가 달라질 수 있습니다. 예를 들어,
2 * 3 + 4와 (2 * 3) + 4는 같은 결과를 주지만,
2 * (3 + 4)는 다른 결과를 줍니다.
주어진 수식에서 괄호의 위치에 따라 가능한 최소 값을 찾는 문제를 해결하려고 합니다.
수식은 숫자와 연산자(+, -, *)로 구성되어 있습니다.
문제 정의
정수로 이루어진 배열과 연산자가 주어질 때, 괄호를 적절히 배치하여
가장 작은 결과값을 만들어내는 방법을 찾는 과제를 수행하십시오.
구체적으로 말하자면, 수식이 다음과 같은 형태일 때:
2 * 3 - 5 + 7이 수식을 괄호를 이용해 최솟값으로 만드는 방법을 찾아야 합니다.
문제 접근 방법
이 문제를 해결하기 위한 전략으로는 재귀 탐색을 사용하여 모든 괄호의 배치를 고려해야 합니다.
괄호를 배치할 수 있는 모든 조합을 생성하고, 각 경우에 대한 결과를 계산하여 가장 작은 값을 찾는 방식입니다.
1. 문제를 단순화하기
먼저, 아래와 같은 수식을 배열로 표현해보겠습니다.
예를 들어, 2 * 3 - 5 + 7는
다음과 같은 구조로 변환됩니다:
[2, '*', 3, '-', 5, '+', 7]2. 재귀적 접근
각 가능한 위치에 긴 구문을 제어하는 괄호를 배치하기 위해서,
재귀적인 함수를 사용하여 모든 경우를 탐색할 것입니다.
주요 단계는 다음과 같습니다:
- 수식을 재귀적으로 나누어 괄호를 추가합니다.
- 각 부분 표현의 결과를 계산합니다.
- 계산된 결과 중 최솟값을 갱신합니다.
3. 코드 구현
아래는 C#으로 구현한 예제 코드입니다.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
string expression = "2*3-5+7";
int result = MinValue(expression);
Console.WriteLine("최솟값: " + result);
}
static int MinValue(string expression)
{
var numbers = new List();
var operators = new List();
// 입력 문자열을 숫자와 연산자로 나눈다.
for (int i = 0; i < expression.Length; i++)
{
if (char.IsDigit(expression[i]))
{
int num = 0;
while (i < expression.Length && char.IsDigit(expression[i]))
{
num = num * 10 + (expression[i] - '0');
i++;
}
numbers.Add(num);
i--; // i 값을 조정
}
else
{
operators.Add(expression[i]);
}
}
return CalculateMin(numbers, operators);
}
static int CalculateMin(List numbers, List operators)
{
// 기본 경우: 숫자가 하나만 남아 있을 때
if (numbers.Count == 1)
return numbers[0];
int minValue = int.MaxValue;
for (int i = 0; i < operators.Count; i++)
{
char op = operators[i];
List leftNumbers = numbers.ToList();
List rightNumbers = numbers.ToList();
List leftOperators = operators.GetRange(0, i);
List rightOperators = operators.GetRange(i + 1, operators.Count - i - 1);
// 연산자에 따라 왼쪽과 오른쪽 구문을 나눈다.
int leftValue = CalculateMin(leftNumbers.GetRange(0, i + 1), leftOperators);
int rightValue = CalculateMin(rightNumbers.GetRange(i + 1, rightNumbers.Count - i - 1), rightOperators);
// 연산을 수행한다.
int result = PerformOperation(leftValue, rightValue, op);
// 최솟값 갱신
if (result < minValue)
minValue = result;
}
return minValue;
}
static int PerformOperation(int left, int right, char op)
{
switch (op)
{
case '+':
return left + right;
case '-':
return left - right;
case '*':
return left * right;
default:
throw new InvalidOperationException("지원하지 않는 연산자입니다.");
}
}
}
4. 코드 설명
위 코드에서 사용된 함수들은 다음과 같은 기능을 수행합니다:
MinValue: 주어진 수식 문자열을 숫자와 연산자로 나누고, 최솟값 계산을 위한 초기 데이터를 준비합니다.CalculateMin: 가능한 모든 서브 표현을 재귀적으로 계산하며, 최솟값을 찾습니다.PerformOperation: 두 숫자와 연산자를 이용해 계산을 수행합니다.
이 구조를 통해 모든 괄호 배치 조합을 탐색하고, 계산된 결과 중 최솟값을 도출하게 됩니다.
마무리
본 예제 문제를 통해 괄호 배치와 알고리즘적 접근 방법을 이해하는 데 도움이 되었기를 바랍니다.
이 방식과 코드를 바탕으로 다양한 수식에 대한 최솟값을 찾아내는 문제들을 해결해볼 수 있습니다.
항상 문제를 단순화하고 재귀적 접근 방식을 활용하는 연습을 통해 알고리즘적 사고를 극대화할 수 있습니다.
추가 학습 자료
알고리즘을 깊이 있는 학습을 위해서는 다음의 자료를 참고해보시기 바랍니다: