[이것이 코딩테스트다] 12일차 - 백준 연산자 끼워넣기, 인구이동

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 5 DFS/BFS

오늘 풀이한 문제

1. [백준 14888] 연산자 끼워넣기

14888번: 연산자 끼워넣기

 

문제 설명

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×3-4+5+6 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다. 1+2+3-4×5÷6 = 1 1÷2+3+4-5×6 = 12 1+2÷3×4-5+6 = 5 1÷2×3-4+5+6 = 7 N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오

 

 

접근 방법 (permutations 라이브러리 사용)

1. 각 연산자 개수만큼 연산자가 모두 담긴 리스트를 만들고 itertools의 permutations를 이용하여 가능한 모든 연산자 조합을 만든다 

oper_list = []
for p in range (plus): oper_list.append('+')
for m in range (minus): oper_list.append('-')
for mu in range (mul): oper_list.append('*')
for d in range (div): oper_list.append('//')

oper_list ## 2 1 1 1 -> ['+', '+', '-', '*', '//']

2. 연산자 리스트를 돌며 숫자를 순서대로 불러와 연산 후 결과 저장 

3. min, max출력

n= 6

## 연산자 조합 만들기 
plus, minus, mul, div  = map(int, input().split())
nums = 1,2,3,4,5,6
oper_list = []
for p in range (plus): oper_list.append('+')
for m in range (minus): oper_list.append('-')
for mu in range (mul): oper_list.append('*')
for d in range (div): oper_list.append('//')
    
from itertools import permutations 
per_oper = list(permutations(oper_list, len(oper_list)))

result = []
for oper in per_oper:
    num = nums[0]
    for idx,o in enumerate (oper):
        if o == '+':
            num += nums[idx+1]
        elif o =='-':
            num -= nums[idx+1]
        elif o =='*':
            num *= nums[idx+1]
        else:
            if num < 0:
                num = ((num*(-1)) // nums[idx+1])*(-1)
            else:
                num = num // nums[idx+1]
    result.append(num)
    
print (max(result), min(result))

접근 방법 (DFS)

## dfs 
n= 6
plus, minus, mul, div  = map(int, input().split())
nums = 1,2,3,4,5,6

max_ans, min_ans = -1e9, 1e9

def solution(num, idx, add, sub, mul, div):
    global max_ans, min_ans
    if idx == n:
        max_ans = max(max_ans, num)
        min_ans = min(min_ans, num)
        return 
        
    ## 각 연산을 할때 마다 숫자를 차감하는 방식
    if add > 0:
        solution(num + nums[idx], idx + 1, add - 1, sub, mul, div)
    if sub > 0:
        solution(num - nums[idx], idx + 1, add, sub - 1, mul, div)
    if mul > 0:
        solution(num * nums[idx], idx + 1, add, sub , mul -1, div)
    if div > 0:
        solution(int(num / nums[idx]), idx + 1, add, sub, mul, div -1)


solution(nums[0], 1, plus, minus, mul, div)
print(max_ans)
print(min_ans)

 

엄청 어려운 문제는 아니었지만 dfs로 풀 경우 속도가 훨씬 빠르다고 하니 재귀로 푸는 경우도 많이 연습해야겠다! 

 

 

2. [백준 16234] 인구 이동

문제 설명

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다. 연합을 해체하고, 모든 국경선을 닫는다. 각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

 

접근 방법 (BFS)

0. 방문을 확인 할  country과 동일한 크기의 check 리스트, 유닛별 평균 인구수를 구하고 기존 country에 업데이트 하기 위한 pin 변수 준비

1. dx, dy 를 사용하여 이동할 좌표를 구하고 다음 좌표가 한번도 방문하지 않고, 인구 차이가 l~r 사이라면 이동

     방문한 좌표의 check = 1,  pin에 좌표 저장

2. 이동할 수 있는 위치가 없으면 평균 인구를 구해 country 업데이트

 

from collections import deque

def bfs(x,y):
    q = deque()
    q.append((x,y))
    check[x][y] = 1  ## 방문확인 
    pin = [(x,y)]    ## 좌표저장
    people = country[x][y]  ## 시작하는 곳의 인구수 
    while q:
        x,y = q.popleft()
        for f in range (4):
            nx = x + dx[f]
            ny = y + dy[f]
            if nx < 0 or nx>= n or ny < 0 or ny >= n:
                continue
            if check [nx][ny] == 1: ## 방문한 곳 패스
                continue 
            p = abs(country[x][y] - country[nx][ny])
            if l <= p <= r:  ## 방문한적 없고, 인구 차이가 조건 이내일 때 
                people += country[nx][ny]
                check[nx][ny] = 1 
                q.append((nx,ny))
                pin.append((nx,ny))
    p_new = people // len(pin)
    for p_x, p_y in pin: ## 새로운 인구수 업데이트
        country[p_x][p_y] = p_new

    return len(pin)
    
    
country =[[10,15,20], [20,30,25], [40,22,10]]
n = 3
l, r = 5, 10
cnt= 0 

dx = [0,0,1,-1]
dy = [1,-1,0,0]

while True :    
    stop = True
    check = [[0]*n for _ in range(n)]
    for i in range (n):
        for j in range(n):
            if check[i][j] == 0 :
                if bfs (i,j) > 1:
                    stop  = False
    if stop :
        break
    else:
        cnt += 1
print (cnt)

bfs를 여러번 수행하는 곳에서 살짝 어려움이 있었다 그래도 많이 수월해졌다 아자자~

 

 

연습문제 풀이는 깃허브에도 업로드 되어있습니다 

GitHub - gymin97/algorithm_study: Solve the algorithm problems (python3)