이코테 유형별 기출문제

DFS/BFS

괄호 변환

풀이특징

• 올바른 괄호 문자열인지 확인하는 함수 필요: isRight(w)
• 균형잡힌 문자열 u와 나머지 v로 분리하는 함수 필요: divide(w)
• 문자열을 뒤집는 함수 필요: flip(u)
• 재귀적으로 호출되는 올바른 문자열로 변환하는 함수 필요: rightString(p)
• 최종적으로 rightString(p)를 호출한 결과를 반환하며, rightString(p)는 재귀적으로 호출된다.
• isRight 함수의 경우 stack 구조를 통해 구현
• divide 함수의 경우 괄호형태에 따라 +1, -1 하여 0이 될 때 u, v를 분리한다.

# 문자열 w가 올바른 괄호 문자열인지 확인하는 함수
def isRight(w):
    stack = []
    for i in w:
        if i == '(':
            stack.append('(')
        elif i == ')':
            if len(stack) == 0:
                return False
            stack.pop()
    return True if len(stack) == 0 else False            

# 균형잡힌 문자열 u 분리하는 함수
def divide(w):
    count = 0
    u = []
    for i in w:
        u.append(i)
        if i == '(':
            count += 1
        else:
            count -= 1
        if count == 0:
            break
    return ("".join(w[:len(u)]), "".join(w[len(u):]))

# 문자열 뒤집기
def flip(u):
    result = ""
    for i in u:
        if i == "(":
            result += ")"
        else:
            result += "("
    return result
    
# 올바른 괄호 문자열로 변환한 결과를 반환
def rightString(p):
    if p == "":
        return ""
    u, v = divide(p)
    if isRight(u):
        v = rightString(v)
        return u + v
    else:
        result = "("
        result += rightString(v)
        result += ")"
        result += flip(u[1:-1])
        return result

# 올바른 괄호 문자열로 변환한 결과를 반환
def solution(p):
    return rightString(p)

연산자 끼워 넣기

풀이특징

• 연산자 개수를 통해 연산자배열 생성
• 순열을 통한 연산자 정렬: from itertools import permutations
• 음수 나눗셈의 경우 int(result / num) 식으로 구현

# 만들 수 있는 식의 결과값의 최댓값, 최솟값을 출력
from itertools import permutations
import math
PLUS, MINUS, MULTI, DIVID = 0, 1, 2, 3

n = int(input())
num = list(map(int, input().split()))
plus, minus, multi, divid = map(int, input().split())

operations = []
operations.extend([PLUS]*plus)
operations.extend([MINUS]*minus)
operations.extend([MULTI]*multi)
operations.extend([DIVID]*divid)

maxValue = -math.inf
minValue = math.inf

for oper in permutations(operations, n-1):
    result = num[0]
    for i in range(1, n):
        if oper[i-1] == PLUS:
            result += num[i]
        elif oper[i-1] == MINUS:
            result -= num[i]
        elif oper[i-1] == MULTI:
            result *= num[i]
        elif oper[i-1] == DIVID:
            result = int(result/num[i])
    
    maxValue = max(maxValue, result)
    minValue = min(minValue, result)

print(maxValue)
print(minValue)