알고리즘 마라톤 5일차

27번

다리 놓기

알고리즘 마라톤 26번 문제의 응용 버전이라 할 수 있다.

순열과 조합에 대한 개념을 이해해야 한다. 순열은 순서가 상관 있는 나열(Permutation), 조합은 순서 상관 없는 조합(Combination)
따라서 순열은 n!/n-r!, 조합은 n!/r!(n-r)!

이 문제는 조합으로 풀면 간단히 답이 나온다.
좌측의 모든 사이트를 연결하는 것이므로 우측 사이트 m개 중 좌측 사이트 n개를 뽑는 것과 의미가 같다.
예를 들어 우측 사이트가 1번, 2번, 3번, 4번이 있는데 이 중 2개를 뽑는 경우의 수를 찾아야 한다면, 다리는 서로 교차되면 안되기 때문에 순서를 고려하는 순열이 아니라 (1번, 2번), (2번, 1번) 중 하나만 고려하는 조합을 사용하여야 한다.

def factorial(n):
    num = 1
    for i in range(1, n+1):
        num *= i
    return num

T = int(input())

for _ in range(T):
    n, m = map(int, input().split())
    bridge = factorial(m) // (factorial(n) * factorial(m - n))
    print(bridge)

28번

균형잡힌 세상

알고리즘 마라톤 24번 괄호 문제와 비슷하다.

import sys
lines = sys.stdin.readlines()
for line in lines[:-1]:
    stack = []
    for t in line:
        if t in '([':
            stack.append(t)
        elif t == "]":
            if not stack or stack.pop() != '[':
                print('no')
                break
        elif t == ')':
            if not stack or stack.pop() != '(':
                print('no')
                break
        elif t == '.':
            if stack:
                print('no')
            else:
                print("yes")

29번

스택 수열

문제만 잘 이해하면 어렵지 않은 문제

import sys
case_cnt = sys.stdin.readline()
n = int(case_cnt)
stack = []
result = []
pointer = 1
for i in range(n):
    num = int(input())
    while pointer <= num:
        stack.append(pointer)
        result.append('+')
        pointer += 1

    if stack[-1] == num:
        stack.pop()
        result.append('-')
    else:
        print('NO')
        exit(0)

for i in result:
    print(i)

30번

회전하는 큐

deque를 활용하면 성능이 좋아진다.
이 문제의 핵심은 숫자를 앞에서 뒤로 회전 시키는 게 나은지, 뒤에서 앞으로 회전 시키는 게 나은지를 구분하는 것이다.

from collections import deque

n, m = map(int, input().split())
p = list(map(int, input().split()))
queue = deque(range(1, n+1))
count = 0
for i in range(m):
    q_len = len(queue)
    q_idx = queue.index(p[i])
    if q_idx > q_len // 2:
        queue.rotate(q_len - q_idx) # 양수일 경우 맨 뒤의 값을 맨 앞으로 이동
        count += (q_len - q_idx)
    else:
        queue.rotate(-q_idx) # 음수일 경우 맨 앞의 값을 맨 뒤로 이동
        count += q_idx
    queue.popleft()

print(count)

31번

큐 2

성능을 위해 deque와 sys.stdin.readline()를 사용한다.

import sys
from collections import deque
n = int(sys.stdin.readline())
queue = deque([])
for i in range(n):
    s = sys.stdin.readline().split()
    if s[0] == 'push':
        queue.append(s[1])
    elif s[0] == 'pop':
        if not queue:
            print(-1)
        else:
            print(queue.popleft())
    elif s[0] == 'size':
        print(len(queue))
    elif s[0] == 'empty':
        if not queue:
            print(1)
        else:
            print(0)
    elif s[0] == 'front':
        if not queue:
            print(-1)
        else:
            print(queue[0])
    elif s[0] == 'back':
        if not queue:
            print(-1)
        else:
            print(queue[-1])

32번

DFS와 BFS

나름대로 문제를 이해하기 위해 그림을 그려보았다.

DFS(깊이우선탐색)인 경우는 1 → 2 → 4 → 3
BFS(너비우선탐색)인 경우는 1 → 2 → 3 → 4 순일 것이다.

어떤 분은 DFS를 이어달리기, BFS를 와이파이에 비유하셨는데 이해가 쉬웠다.

일반적으로 DFS는 스택, BFS는 큐로 구현한다.
DFS는 재귀를 이용하면 좀 더 간단히 구현할 수 있다.
BFS는 재귀로 동작하지 않는다.

나중에 그래프에 대해서 한 번 이론적인 정리를 해야겠다.

import sys
input = sys.stdin.readline
from collections import deque

def dfs(graph, v):
    visited = {}
    stack = [v]
    while stack:
        n = stack.pop()
        if n not in visited:
            visited.setdefault(n)
            stack += reversed(graph[n])
    return visited

def bfs(graph, v):
    visited = {}
    queue = deque([v])
    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.setdefault(n)
            queue += graph[n]
    return visited

n, m, v = map(int, input().split())
graph = {i: [] for i in range(1, n + 1)}
for i in range(1, m + 1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    for key in graph:
        graph[key].sort()
    # print('graph', graph)

print(' '.join(list(map(str, dfs(graph, v)))))
print(' '.join(list(map(str, bfs(graph, v)))))

graph는 왜 이 모양인지 알겠는데, DFS와 BFS에는 왜 각각 스택과 큐 자료형을 사용하며 왜 저런 식으로 코드를 작성했는지 아직 잘 이해가 가지 않는다. 😭

33번

통계학

시간 초과 때문에 기본으로 제공해주는 Counter 모듈의 most_common 함수를 사용하여 최빈값을 튜플 형태로 받았다. {문자:개수}

import sys
from collections import Counter

n = int(sys.stdin.readline())
nums = []
for i in range(n):
    nums.append(int(sys.stdin.readline()))
nums.sort()

print(round(sum(nums) / n)) # 산술평균

print(nums[n // 2]) # 중앙값

nums_s = Counter(nums).most_common() # 최빈값
if len(nums_s) > 1:
    if nums_s[0][1] == nums_s[1][1]: # 가장 빈도수 높은 상위 2개가 같을 경우
        print(nums_s[1][0]) # 두 번째로 작은 값(오름차순이므로)
    else:
        print(nums_s[0][0])
else:
    print(nums_s[0][0])

print(nums[-1] - nums[0]) # 범위

34번

색종이 만들기

재귀로 범위를 점점 좁혀나간다.

import sys

n = int(sys.stdin.readline())

color_paper = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] # X 곱하기 Y 리스트
white, blue = 0, 0

def cut(x, y, n):
    global blue, white
    check = color_paper[x][y]
    for i in range(x, x + n):
        for j in range(y, y + n):
            if check != color_paper[i][j]:
                cut(x, y, n // 2)
                cut(x, y + n // 2, n // 2)
                cut(x + n // 2, y, n // 2)
                cut(x + n // 2, y + n // 2, n // 2)
                return

    if check == 0:
        white += 1
        return
    else:
        blue += 1
        return

cut(0, 0, n)
print(white)
print(blue)

4등분 하는 방법은 반복 시작점을 잘 정하는 것이다.