Ray`s Tech Lab

https://www.acmicpc.net/problem/2504

구현방법에서 낑낑댔다. 괄호는 스택을 사용해서 매칭시킬 수 있다는 것은 스택을 공부해봤다면 알고 가게 되는 기본 지식이지만, 중간값들을 어떻게 처리할 것인지에 대해서 계속 고민이 됐다.

어떻게 처리할지 고민하다 분할정복 기법으로 풀어봤다. 다 풀고 다른 사람들 풀이를 봤는데, 음.. 내가 좀 어렵게 푼 편이구나 싶기도 하고. 그래도 문제 푸는 방법이 1가지만 있는 게 아니니까 뭐.

def solution(parenthesis, s, e):
	# base case : 바로 답을 구할 수 있는 경우
    if e == s + 1:
        if parenthesis[s] == "(":
            return 2
        else:
            return 3
	
    # recursive case : 문제가 너무 커서 바로 답 못 구하는 경우 -> 그룹별로 쪼갠다
    group, stack = [], []
    little_s, little_e = 0, 0

    for i in range(s + 1, e):
        if parenthesis[i] in ("(", "["):
            if not stack:
                little_s = i
            stack.append(parenthesis[i])
            continue
        if len(stack) == 1:
            little_e = i
            group.append([little_s, little_e])
        stack.pop()
        continue

    result = 0
    for ns, ne in group:
        result += solution(parenthesis, ns, ne)
    return 2 * result if parenthesis[s] == "(" else 3 * result


parenthesis = "(" + input().strip() + ")"
stack = []
for i in range(len(parenthesis)):
    if parenthesis[i] in ("(", "["):
        stack.append(parenthesis[i])
        continue
    if not stack:
        print(0)
        exit()
    if (parenthesis[i] == ")" and stack[-1] == "[") or (parenthesis[i] == "]" and stack[-1] == "("):
        print(0)
        exit()
    stack.pop()

print(solution(parenthesis, 0, len(parenthesis) - 1) // 2)

기본적인 컨셉은 괄호 문자열을 그룹별로 나눌 수 있다는 점을 이용한 거다. ([])[[]]라는 문자열은 ([])과 [[]]라는 두 개의 그룹으로 구성되는 것을 이용하는 것. 그룹별로 계속 쪼개주다가 ()나 []이라는 base case를 만나게 되는데, 그 때는 2나 3을 리턴하도록 만들었다. 각 그룹에 대해 solution메서드가 동작하며, 이 놈이 파라미터로 받은 그룹을 쪼개서 쪼개진 그룹의 결과들을 더해가도록 만들면 됐다.

분할정복은 다음 영상을 참고하면 된다(본인 유튜브 홍보..ㅋㅋㅋㅋ)

https://www.youtube.com/watch?v=qDEKiNzAH1U&t=144s 

https://www.acmicpc.net/problem/17142

조합과 BFS가 짬뽕된 문제. 바이러스를 놓을 수 있는 위치들에 대한 m개의 조합들을 하나하나 살펴보며 BFS를 돌려 판별하면 된다. 

이 문제에선 고려해야 할 사항이 좀 더 있다. 바로 BFS의 종료조건.

https://www.acmicpc.net/problem/7576

위 문제 "토마토"는 본 문제인 "연구소 3"과 꽤나 유사하다. 익은 토마토가 매 페이즈마다 주변 토마토를 익게 하듯이, 본 문제에서의 바이러스도 매 페이즈마다 주변 칸들에 퍼져 나간다. 또한 모든 토마토가 익을 때까지 최소 며칠이 걸리는지 계산하는 것과 빈 칸이 모두 바이러스가 퍼질 때까지 최소 얼마나 걸리는지를 요구하는 것도 비슷하다.

그러나 디테일에 차이가 있다. 토마토 문제는 모든 토마토가 익을 때까지 BFS를 돌려야 한다면, 본 문제는 빈 칸에 바이러스가 채워질 때까지만 BFS를 돌려야 한다. 즉 벽을 제외한 모든 칸이 활성 바이러스로 채워질 때까지 돌리는 게 아니다. 비활성된 바이러스가 있어도 다른 빈 칸들이 남아있지 않다면 더 이상 BFS를 돌릴 필요가 없다.

따라서 안 익는 토마토가 있든 없든 일단 Queue가 빌 때까지 BFS를 돌려 가능한 모든 구역의 토마토가 익게 한 다음, Queue가 비고 나면 그제서야 모든 토마토가 익어도 되는지 판단해도 되는 토마토 문제와는 달리, 본 문제는 BFS를 돌릴 때마다 연구소 상황을 체크해야 한다. (무작정 큐가 빌 때까지 돌리면 빈 칸들이 다 찰 때까지가 아니라 벽을 제외한 모든 칸에 활성 바이러스가 퍼질 때까지를 보게 되는 문제로 바뀌니까)

즉 빈칸들을 채울 때마다 카운트해주고, 매 BFS마다 현재까지 채운 빈칸의 수와 처음에 셌던 빈칸의 수가 일치하는지를 판단해야 한다. 즉 큐에서 꺼낸 노드마다 상하좌우 네 방향에 대해 방문여부를 확인하고 방문여부를 안 했고 그 칸이 빈칸이면 채운 빈칸의 수를 하나 늘리면 된다.

내가 실수한 부분은, 빈칸을 채운 뒤 채운 빈칸의 수를 늘리는 작업과 빈 칸을 다 채웠는지 판단하는 작업을 동시에 안 했다는 거다. 나는 BFS를 할 때 보통 종료조건을 판단하는 작업을 큐에서 노드를 꺼내고 난 바로 다음에 한다. 얘를 들어 지금 꺼낸 노드가 도착지점이라면 지금까지 카운트한 수가 정답이다! 처럼 판단하는 것. 즉 이 문제는 이런 습관에 따라 처음에 다음과 같이 BFS코드를 짰다.

while q:
    1. 만약 지금까지 채운 빈칸의 수가 처음에 센 빈칸의 수와 같다면 종료하는 코드
    2. 인접한 칸들이 빈 칸이고 방문하지 않았다면 그 칸을 방문처리하고 큐에 추가한 다음
    지금까지 채운 빈칸 수를 += 1

빈칸을 채우고 채운 빈칸 수를 늘리는 작업(2)과 빈칸을 다 채웠는지 판단하는 작업(1)을 동시에 하고 있지 않는 모습이다. 이 때문에 오답이 날 수 있다. 큐에서 노드를 하나 꺼냈는데 x초에 방문한 노드였고, 이 노드의 인접한 빈칸을 채우고 채운 빈칸 수를 늘렸다. 큐에서 다음 노드를 빼냈고 똑같이 x초에 방문한 노드인데, (1)에 의해 지금껏 채운 빈칸 수가 처음에 센 빈칸의 수와 같아 x초에 모든 빈칸을 채웠다고 오답을 뱉게 된다. 사실 x + 1초에 모든 빈 칸이 채워지는 건데 말이다. 만약 임의의 시간 x초에 방문하는 모든 노드들이 방문하지 않은 인접한 빈 칸을 하나 이상씩 가지고 있는게 보장된다면 이런 일은 안 생기겠지만, x초에 방문하는 모든 노드가 방문하지 않은 인접한 빈칸을 가지고 있다는 보장이 없으니 이런 상황이 생긴다.

난 그래서 처음에 틀렸다..ㅋㅋㅋㅋㅋ

암튼..! 빈칸을 채우고 채운 빈칸 수를 늘리는 작업과 빈칸을 다 채웠는지 판단하는 작업을 동시에 해야 한다. 다음과 같이 바꿀 수 있을 것이다.

while q:
    1. 지금 꺼낸 노드가 빈 칸이면 지금껏 채운 빈 칸의 수 += 1
    2. 만약 지금까지 채운 빈칸의 수가 처음에 센 빈칸의 수와 같다면 종료
    3. 인접한 칸들이 빈 칸이고 방문하지 않았다면 그 칸을 방문처리하고 큐에 추가

또는 다음과 같이도 가능하다. 중요한 건 동시에 두 작업을 순서대로 해야 한다는 거.

while q:
    1. 꺼낸 노드에 인접한 칸들이 빈 칸이고 방문하지 않았다면 그 칸을 방문처리하고 큐에 추가한 다음
    지금까지 채운 빈칸 수를 += 1
    2. 지금까지 채운 빈칸 수가 처음에 센 빈칸 수와 같다면 종료. 단 이 작업은 1이 이루어지고 난 이후에만 진행

전체 코드는 다음과 같다.

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


def solution(n, m, board):
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    empty_count = 0
    virus = []
    for r in range(n):
        for c in range(n):
            if board[r][c] == 2:
                virus.append((r, c))
            elif board[r][c] == 0:
                empty_count += 1

    answers = []

    for activate_viruses in combinations(virus, m):
        q = deque([])
        visited = set()
        for r, c in activate_viruses:
            q.append((r, c, 0))
            visited.add((r, c))

        empty_to_virus_count = 0

        while q:
            r, c, h = q.popleft()
            if board[r][c] == 0:
                empty_to_virus_count += 1
            if empty_to_virus_count == empty_count:
                answers.append(h)
                break
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if nr < 0 or nc < 0 or nr >= n or nc >= n:
                    continue
                if board[nr][nc] != 1 and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    q.append((nr, nc, h + 1))

    if answers:
        return min(answers)
    return -1


N, M = map(int, input().split())
_board = [list(map(int, input().split())) for _ in range(N)]

print(solution(N, M, _board))

이 문제를 통해 얻은 것.

"다음 노드들에 대한 작업과 종료여부를 판단하는 작업은 동시에 할 것"

https://www.acmicpc.net/problem/14890

행 하나하나, 열 하나하나에 대해 지나갈 수 있는지 판단해주면 되는 문제. 단순히 구현만 해주면 된다.

내가 처음에 작성한 코드는 다음과 같다.

import sys
input = sys.stdin.readline


def is_all_same_height(heights):
    for i in range(len(heights) - 1):
        if heights[i] != heights[i + 1]:
            return False
    return True


def is_all_same_column(board, c):
    for r in range(len(board) - 1):
        if board[r][c] != board[r + 1][c]:
            return False
    return True


def solution(n, k, board):
    answer = 0

    for row in board:
        checked = [False for _ in range(n)]
        if is_all_same_height(row):
            answer += 1
        else:
            for c in range(n - 1):
                if row[c] == row[c + 1]:
                    continue
                if row[c] + 1 == row[c + 1]:
                    for nc in range(c, c - k, -1):
                        if nc < 0 or checked[nc] or row[nc] != row[c]:
                            break
                    else:
                        nc = c - k + 1
                        for i in range(nc, c + 1):
                            checked[i] = True
                        continue
                    break
                elif row[c] == row[c + 1] + 1:
                    for nc in range(c + 1, c + 1 + k):
                        if nc >= n or checked[nc] or row[nc] != row[c + 1]:
                            break
                    else:
                        nc = c + 1 + k
                        for i in range(c + 1, nc):
                            checked[i] = True
                        continue
                    break
                else:
                    break
            else:
                answer += 1

    for c in range(n):
        checked = [False for _ in range(n)]
        if is_all_same_column(board, c):
            answer += 1
        else:
            for r in range(n - 1):
                if board[r][c] == board[r + 1][c]:
                    continue
                if board[r][c] + 1 == board[r + 1][c]:
                    for nr in range(r, r - k, -1):
                        if nr < 0 or checked[nr] or board[nr][c] != board[r][c]:
                            break
                    else:
                        nr = r - k + 1
                        for i in range(nr, r + 1):
                            checked[i] = True
                        continue
                    break
                elif board[r][c] == board[r + 1][c] + 1:
                    for nr in range(r + 1, r + 1 + k):
                        if nr >= n or checked[nr] or board[nr][c] != board[r + 1][c]:
                            break
                    else:
                        nr = r + 1 + k
                        for i in range(r + 1, nr):
                            checked[i] = True
                        continue
                    break
                else:
                    break
            else:
                answer += 1
    return answer


N, L = map(int, input().split())
_board = []
for _ in range(N):
    _board.append(list(map(int, input().split())))

print(solution(N, L, _board))

사실 나조차도 돌이켜보면 어떤 일을 하는지 참 알기 어려운 코드..우테코 프리코스 이후로 이런 더러운 코드 작성을 내면에서 혐오하곤 있긴 한데, 코테의 특성상 일단 구현하는게 먼저라고 생각해 더러운 걸 알면서 일단 저렇게 풀어봤다.

대충 저 코드의 핵심은 행과 열에 대해 지나갈 수 있는지를 판단하는 코드가 다르다는 것이다. 행에 접근할 때와 열에 접근할 때는 인덱싱 방법이 달라지기 때문에 구분해서 만들었다.

그러나 다른 사람들의 풀이를 보니, 좀 더 간단한 방법이 있었다. 바로 행과 열을 인덱싱 방법 이런 거 상관없이 똑같은 하나의 1차원 배열로 보는 것이다. 즉 열도 행처럼 보는 것! 파이썬의 for문을 이용하면

board = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
]

column = [board[i][0] for i in range(4)]

이런 식으로 하나의 열을 1차원 리스트, 즉 하나의 행처럼 가져올 수 있다. 이렇게 하면 행과 열에 대한 판단을 할 때 각기 다른 코드를 만들 필요 없이 하나의 코드로 행과 열에 대한 판단을 내릴 수 있다.

import sys
input = sys.stdin.readline


def check_path(path, k):
    length = len(path)
    check = [0 for _ in range(length)]

    for i in range(length - 1):
        if abs(path[i] - path[i + 1]) > 1:
            return False
        if path[i] + 1 == path[i + 1]:
            for j in range(i, i - k, -1):
                if j < 0 or check[j] or path[j] != path[i]:
                    return False
                check[j] = 1
            continue
        if path[i] == path[i + 1] + 1:
            for j in range(i + 1, i + 1 + k):
                if j >= length or check[j] or path[j] != path[i + 1]:
                    return False
                check[j] = 1
    return True


def solution(n, k, board):
    answer = 0
	# 행에 대한 판단
    for row in board:
        if check_path(row, k):
            answer += 1
	# 열에 대한 판단
    for c in range(n):
        if check_path([board[i][c] for i in range(n)], k):
            answer += 1

    return answer


N, L = map(int, input().split())
_board = []
for _ in range(N):
    _board.append(list(map(int, input().split())))

print(solution(N, L, _board))

구현..이라는 종목을 풀 때는, 이런 식으로 단순화해서 생각하는게 중요한 것 같다. 안 그러면 시간이 너무 오래 걸리는 듯..

신장 트리 (Spanning Tree) ? 

하나의 그래프가 있을 때 그 그래프의 모든 노드를 가지고 있으면서 사이클(Cycle)이 없는 부분 그래프(Sub graph)!

원래 그래프가 N개의 노드를 가진다면, 그 놈의 신장트리는 N개의 노드와 N-1개의 간선(edge)를 갖는다. (간선이 N - 1개보다 적으면 모든 노드가 연결돼있지 않고 N - 1개보다 많으면 사이클이 있는 그래프다).

최소 신장 트리?

신장 트리는 원본 그래프의 부분 그래프이므로 당연히 여러 개 존재할 수 있는데, 그 중 간선들의 가중치 합이 가장 적은 신장 트리를 최소 신장 트리(MST, Minimun Spanning Tree)라고 부른다.

크루스칼 알고리즘?

주어진 그래프에서 최소 신장 트리를 찾는 알고리즘이다. 그리디 알고리즘의 일종으로, 이해하기 매우 쉬운 알고리즘이다. 

1. 가장 작은 가중치를 갖는 간선을 선택한다. 
2. 선택되지 않은 간선 중 가장 가중치를 갖는 간선을 선택한다
3. 그 간선이 기존에 선택했던 간선들과 사이클을 이루지 않는지 체크. 만약 사이클을 이룬다면 그 간선은 버린다.
4. 모든 노드들이 골라질 때까지 2 ~ 3을 반복

모든 노드들이 골라지는지의 여부는 노드들을 세도 되고, 선택된 간선의 개수가 N - 1개인지로 해도 되고, 아니면 그냥 모든 간선들에 대한 조회가 끝날 때까지 해도 된다. 매 페이즈마다 사이클을 이루지 않게끔 골라왔으니 이렇게 만들어진 서브트리는 신장 트리임이 보장되며, 또한 매 페이즈마다 항상 작은 가중치를 갖는 간선들을 골라왔으니 이렇게 만들어진 신장트리는 당연히 최소 신장 트리임이 보장된다.

가장 까다로운 작업은 사이클을 이루는지 판단하는 작업인데, 이는 유니온 파인드를 통해서 간단히 판별할 수 있다.

※ 유니온 파인드에 대해 정리했던 글

https://jofestudio.tistory.com/11

유니온 파인드로 사이클을 판별가능한 이유

유니온 파인드를 이용하면 무방향 그래프에서의 사이클 판별이 가능하다. 방향 그래프에서는 DFS를 통해 가능함. 근데 어떻게 가능한 걸까?

우선 다음 작업으로 사이클을 판단가능하다.

1. 간선을 고른다.
2. 그 간선들에 딸린(?) 노드 두 개가 있을 것이다. 그 두 놈이 같은 집합에 있는지, 즉 같은 그래프에 있는지 확인한다.
3. 두 놈이 다른 그래프에 있다면 두 노드에 대해 Union연산을 한다. 두 놈이 같은 그래프에 있다면 사이클이 있는 거다.

왜 이 작업으로 사이클 판단이 된다는걸까?

유니온 파인드는 집합에 대한 연산들로 생각할 수 있다. 유니온은 두 집합을 합치는거고, 파인드(흔히들 getParant라는 이름으로 메서드를 짓기도 함)는 특정 원소가 속한 집합을 알려주는 연산인 거다. 여기서, 그래프를 일종의 집합으로 볼 수 있다!

이 그래프에서 가장 작은 노드를 리더로 생각한다면 어떨까. 그럼 위 그래프에서의 리더는 0이다. 

1이 속한 그래프의 리더 = 0 이다.

5가 속한 그래프의 리더 = 0 이다.

이런 식으로, 그래프를 하나의 집합으로 표현가능한 것이다. 

이 그래프에서, 우선 처음에 다음과 같이 리더 테이블을 만들어줬다고 하자. 육안으로 세 놈이 같은 그래프에 있는 걸 당연히 확인가능하지만 일단 각자가 서로 다른 그래프에 있다고 생각하고 테이블을 초기화한다.

간선 (1, 2)를 골랐다. 두 노드가 같은 집합에 속하는지(즉 두 놈이 속한 집합의 리더가 같은지)를 보니까, 다르다. 그럼 두 놈을 Union해준다.

즉 이제 노드 1과 노드 2는 같은 집합, 즉 같은 그래프에 있다고 생각할 수 있다.

이번엔 간선 (1, 3)을 골랐다. 두 노드가 같은 집합에 속하는지를 보니까, 다르다. 그럼 두 놈을 Union해준다.

즉 이제 노드 1과 노드 3은 같은 집합 즉 같은 그래프에 있다고 생각할 수 있는 거다.

이제 간선 (2, 3)을 골랐다. 두 노드가 같은 집합에 속하는지를 보니까 같은 집합에 있다! 노드 2가 속한 집합의 리더와 노드 3이 속한 집합의 리더가 같기 때문이다. 따라서 처음에 그림으로 주어진 그래프가 사이클이 있다고 판별가능하다. 왜냐하면 간선 (2, 3)을 골랐다는 것 자체가 노드 2와 3은 서로 이어져있음을 의미하는 것이기 때문이다.

• 즉 노드 2와 노드 3이 서로 다른 집합이었다면, 이 둘을 이어도(둘 사이의 간선을 그린다고 생각) 사이클은 생기지 않음. 원래 둘이 속한 집합 즉 그래프가 겹치지 않는 것이었으니까!
• 그러나 노드 2와 노드 3이 서로 같은 집합이었다면..즉 둘 사이를 잇기도 전에 애시당초 같은 그래프 안에 있던 거라면 그 둘을 잇는다는 것은 사이클을 만드는 것이 되는 것임. 

따라서 유니온 파인드로 그래프의 사이클 판단을 내릴 수 있는 것이다.

그래서 크루스칼은 결국 다음과 같은 순서로 진행한다고 볼 수 있다

1. 가장 작은 가중치를 갖는 간선을 선택한다. 
2. 그 간선에 딸린 두 노드가 같은 집합인지 판단(즉 두 노드의 리더를 비교)
3. 같은 집합이면(두 노드의 리더가 같다면) 그 간선을 선택하지 않음. 5로 건너뜀
4. 다른 집합이면(두 노드의 리더가 다르면) 그 간선을 선택. 두 노드는 union연산해줌
5. 그 다음으로 작은 가중치를 갖는 간선을 골라 2부터 반복. 모든 노드들이 골라질 때까지!

https://www.acmicpc.net/problem/2075

계속 고민한 문제다. 그러다 떠오른 방법이 있는데 괜찮은 방법같았다. 우선 각 열들(column)들의 스택으로 갖게 한다. 그럼 스택의 top은 그 열에서 가장 큰 값들을 갖고 있게 된다. 그리고 각 스택의 top들을 비교해 가장 큰 값을 가진 스택에서 pop을 한다. 이 과정을 N번 반복한다. 그러면 N번째에 pop된게 답이다! 

시간복잡도는 O(N^2)으로 끊어진다. 우선 입력된 값들로부터 스택들을 세팅하는데 O(N^2)이다. 그리고 N번에 걸쳐 pop을 하는데, N개의 스택들에 대해 매번 top들의 값을 비교하니까 이것도 O(N^2)이다. 따라서 전체 시간복잡도는 O(N^2).

이 논리로 문제를 풀었는데, 틀려버렸다. 메모리제한이 있었다.

N x N 보드의 전체 값들을 저장하면 안된다. 아니 그럼 어케 하징?

이건 내가 지금 떠올릴 수 없는 쌈박한 접근방법이 필요하다고 느꼈다. 뭐 그 전에도 잘한 건 아니었지만 알고리즘 문제들에서 눈을 돌린지 너무 시간이 많이 지나서..이건 내가 지금 머리끄댕이 잡고 낑낑대는건 시간낭비라고 생각했다. 마에스트로.. 준비해야 되니까!

일단 코드는 다음과 같다.

우선 이 문제는 다음 논리로 해결가능하다.

• N개의 값을 보관가능한 박스를 만든다.
• 모든 숫자들을 박스에 넣어볼 것이다.
• 박스에 들어있는 숫자가 N개가 아니면 일단 집어넣는다.
• 박스에 들어있는 숫자가 N개면 박스에 들어있는 숫자 중 제일 작은 값과 지금 넣으려는 숫자를 비교한다
• 지금 넣으려는 숫자가 더 크면 박스에 그 숫자를 넣고, 박스에서 젤 작은 숫자를 뺀다.
• 즉 항상 박스안의 숫자는 N개로 유지되며, 모든 숫자에 대한 작업을 끝내면 가장 큰 N개의 숫자가 들어있다.

다만 박스를 그냥 리스트로 만들면 시간복잡도가 너무 커진다. 리스트에서 최솟값 찾는 시간복잡도 = O(N)이고 N^2개들의 숫자에 대해서 작업하니까 전체시간복잡도가 O(N^3)이 됨!

이 떄 우선순위 큐를 쓰면 쉽게 해결가능해진다.우선순위 큐! 어떤 목록으로부터 항상 작은 값들을 가져오고 싶거나 항상 큰 값을 가져오고 싶거나..뭐 그럴 때 쓰던 놈이다. push, pop모두 log n 만큼의 시간이 걸린다! 따라서 이 문제를 해결 가능.

고정된 사이즈의 자료구조를 만들고 활용하는 테크닉.. 꼭 기억하자.