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))

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

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 만큼의 시간이 걸린다! 따라서 이 문제를 해결 가능.

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

길이가 같은 두 배열 A, B에 대해

S = A의 같은 인덱스항들의 곱들의 합

으로 정의할 때, B를 건드리지 않고 A의 순서만 건드려서 S의 최솟값을 찾는 문제.

무식하게 풀려면 A를 나열하는 모든 경우의 수 = N!개에 대해 따져야 하니 타임아웃.

단순히 A만을 오름차순 / 내림차순 하면 어떨까라고 생각해봤으나 B가 어떤 순서로 주어지는지 알 길이 없기 때문에 이것 역시 적절한 방법이 아니었다.

이에 대한 해결은 A는 오름차순, B는 내림차순으로 정렬해 각 항의 곱들의 합을 구하는 것.

곱해서 나오는 값들의 수를 최대한 작게 나오게 하는 게 관건이므로 A의 가장 작은 값을 B의 가장 큰 값과 짝지어주고, 또다시 남은 A의 가장 작은 값을 남은 B의 가장 큰 값과 짝짓는 과정을 반복해야 하므로 B도 내림차순으로 정렬할 필요가 있다.

뭐 정말 나는 B를 건드리기 싫다! 하면 A만 정렬하고 매번 B의 max값을 찾아 매치해줄 수 있지만 굳이 그럴 필요 없이 B도 정렬해주면 될 것 같다는 생각에서 했다.

정당성 증명 - 왜 가장 작은 값과 큰 값을 매칭해야 하는가

B를 내림차순으로 일단 한 상황에서, A를 왜 가장 작은 값부터 매칭시켜줘야 하는가. 

a1과 a2, b1과 b2라는 수가 있고 a1 >= a2, b1 > b2라고 하자. 이 때 주어진 논제를 귀류법으로 증명하기 위해

a2b1 + a1b2이 a1b1 + a2b2보다 작다고 해보자. 우리가 원하는 건 a1b1 + a2b2 >= a2b1 + a1b2임을 보이는 것이다.

뭐 복잡하게 생각할 것 없이, 그냥 이항해서 정리하면 (a1 - a2)b1 >= (a1 - a2)b2임을 보여야 하는 상황이 되는데, 양변을 (a1 - a2)로 나누면 b1 >= b2가 되는데 문제의 조건상 b1 > b2이므로 참이다. 이로써 증명 끝.

곱의 합을 구할 땐 가장 큰 값끼리 곱해준 게 제일 큰 답이 나온다.