Jin의 일상

풀이

import sys
INPUT = sys.stdin.readline


def remove_node(tree, parents, n):
    """ 요청받은 노드를 제거 합니다.

    1. tree 내에 자신(n)을 자식으로 나타내는 부모 노드에서 n을 지웁니다.
      -> parents[n] == -1은 루트 노드이므로 부모 노드가 없습니다.
    2. 재귀적으로 자식 노드를 지웁니다. 지워진 자식 노드의 tree 내에 값을 [-1]로 표기합니다.
    """
    if parents[n] != -1:
        tree[parents[n]].remove(n)

    def remove_child(x):
        for i in tree[x]:
            remove_child(i)
        tree[x] = [-1]
    remove_child(n)


def solution():
    """ 자식이 없는 노드의 개수를 출력합니다.

    1. 이중 리스트(tree)를 생성하고 자신의 자식 노드 인덱스를 넣습니다.
      -> 문제에서 주어진 값 중 -1은 부모 노드가 없음을 의미합니다.
    2. 문제에서 주어진 노드를 제거합니다.
    3. tree에서 자식이 없는 노드([], 빈 노드)의 개수를 출력합니다.
    """
    node_num = int(INPUT())
    parents = list(map(int, INPUT().split()))
    tree = [[] for _ in range(node_num)]

    for i in range(node_num):
        if parents[i] == -1:
            continue
        tree[parents[i]].append(i)

    remove_node(tree, parents, node_to_remove := int(INPUT()))
    return tree.count([])

if __name__ == '__main__':
    print(solution())

반례: ValueError 발생 원인

풀이 과정에서 ValueError가 발생했습니다. 0번 인덱스는 루트 노드(-1)라는 가정했기 때문입니다.

이에 대해 아래와 같은 반례를 고려해볼 수 있습니다.

5

1 2 3 4 -1

4

런타임 발생 당시 코드 일부입니다. n != 0을 확인해주시기 바랍니다. 이를 parents[n] != -1으로 수정했습니다.

import sys
INPUT = sys.stdin.readline


def remove_node(tree, parents, n):
    """ 요청받은 노드를 제거 합니다.

    1. tree 내에 자신(n)을 자식으로 나타내는 부모 노드에서 n을 지웁니다.
      -> n == 0은 루트 노드이므로 부모 노드가 없습니다.
    2. 재귀적으로 자식 노드를 지웁니다. 지워진 자식 노드의 tree 내에 값을 [-1]로 표기합니다.
    """
    if n != 0:
        tree[parents[n]].remove(n)

    def remove_child(x):
        for i in tree[x]:
            remove_child(i)
        tree[x] = [-1]
    remove_child(n)

문제 설명

- 첫 번째 줄에서는 주어질 데이터의 개수(N)가 주어진다.

- 다음 줄에는 N개의 데이터가 주어진다. (1 <= N <= 500,000)

- 시간 제한  1초

출력 : 숫자 간 교환이 일어난 횟수를 구해야 한다.

버블 정렬 예시

(1) 321 : 3 2 1 => 2 3 1  => 2 1 3 => 1 2 3

(2) 4253 : 4 2 5 3 => 2 4 5 3=> 2 4 3 5 => 2 3 4 5

문제 풀이

(1) 어떤 정렬 알고리즘을 사용할지?

버블 소트는 N 제곱의 시간 복잡도를 가진다.

문제 조건에 따르면 최대 25 * (10^10)의 시간 복잡도를 가진다.

파이썬의 1초당 계산 가능 횟수는 2 * (10^7)이므로, 버블 소팅으로는 문제를 풀 수 없다.

따라서 다른 방식의 정렬을 이용해야 한다.

병합정렬을 이용하면 N * log(N)의 시간복잡도가 소요된다. 

5*(10^5) * log(5*(10^5))이므로, 시간 복잡도는 해결이 된다.

(2) 숫자 간 교환 횟수를 어떻게 구할지?

버블 정렬에서는, 

1. 두 요소 간 순서가 맞으면 가만히 두고

2. 순서가 틀렸다면 숫자를 교환한다.

2번에 착안해서 버블 정렬에서 정렬하는 과정을 살펴보자.

1. 위 그림의 맨 밑에 줄부터 A와 B를 비교해서 B가 작으면 교환이 일어난다.

이 때, 교환될 숫자의 개수는 CNT에 더해주자. (남은 A의 개수만큼 더해주면 된다.)

[3] [1] => [1, 3]           [2] [4] => [2, 4]

CNT += len(A)

2. [1, 3] [2, 4]를 비교한다. 

A의 맨 앞과 B의 맨 앞을 비교했을 때, A가 작으므로, A의 1이 빠진다.

[1,3] [2, 4] => [3] [2, 4],  [1]

3. A의 맨 앞과 B의 맨 앞을 비교했을 때, B가 작으므로, B의 2가 빠진다.

B가 작으면, 스와핑이 일어나야 하므로 남은 A의 총 길이를 CNT에 더해준다. 

[3] [2, 4] => [3] [4],  [1, 2]

CNT += len(A)

4. A의 맨 앞과 B의 맨 앞을 비교했을 때, A가 작으므로, A의 3이 빠진다.

[3] [4], => [] [4], [1, 2, 3]

5. A에 들어있던 모든 원소가 빠졌으므로, B에 남은 원소를 추가한다

[] [4] => [] [], [1, 2, 3, 4]

6. 스와핑이 일어난 횟수(CNT):  2

반례

문제에는 동일한 원소가 나오지 않는다는 조건이 없다.

즉, 3 2 5 3 4와 같은 경우가 있을 수 있다.

이를 고려하여 코드를 작성해야 한다.

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def mergeSort(start, end):
    global cnt
    if start < end:
        mid = (start + end) // 2
        mergeSort(start, mid)
        mergeSort(mid + 1, end)

        a = start
        b = mid + 1
        tmp = []
        while a <= mid and b <= end:
            if arr[a] <= arr[b]:
                tmp.append(arr[a])
                a += 1

            else:
                tmp.append(arr[b])
                b += 1
                cnt += (mid - a + 1)  # 스와핑 했을 때 개수추가
        if a <= mid:
            tmp = tmp + arr[a:mid+1]
        if b <= end:
            tmp = tmp + arr[b:end+1]

        for i in range(len(tmp)):
            arr[start + i] = tmp[i]

if __name__ == '__main__':
    cnt = 0
    n = int(input())
    arr = list(map(int, input().split()))
    mergeSort(0, n-1)
    print(cnt)

www.acmicpc.net/problem/13458

문제

세 줄로 데이터가 주어진다.

각 줄은 시험장의 개수 (n), 각 시험장의 응시자 수 (a), 총 감독관 역량(b), 부 감독관 역량(c)를 의미한다.

 - b와 c는 감독 가능한 응시자 수를 의미한다.

총감독관은 각 시험장에 최소 한 명 들어가야 하며, 부 감독관은 여러 명이 들어가도 된다.

이 때, 모든 응시자를 감독하기 위한 감독관의 수를 구해야 한다.

알고리즘

1. 시험장에는 최소 한 명의 총 감독관이 들어가야 한다.  따라서 각 시험장의 응시자 수에서 b를 뺀다.

 (1) n - b <= 0인 경우에는 정답으로 제출할 총 감독관 수에 1을 더한다.

   한 명의 총 감독관이 모든 응시자를 감독할 수 있으므로, 부 감독관이 필요없기 때문이다.

 (2) n - b > 0인 경우에는 2번으로 넘어간다.

2. n - b를 한 값에 부 감독관의 역량인 c를 나누어 준다.

 (1) 나머지가 있는 경우에는 정답으로 제출할 총 감독관 수에 3을 더해준다.

   - 총 감독관 1명 + 부 감독관 2명

 (2) 나머지가 없는 경우에는 정답으로 제출할 총 감독관 수에 2를 더해준다.

  - 총 감독관 1명 + 부 감독관 1명

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

n = int(input())
a_list = list(map(int, input().split()))
b, c = map(int, input().split())

cnt = 0
for i in range(n):
    tmp = a_list[i] - b
    if tmp <= 0:
        cnt += 1
    else:
        q, r = divmod(tmp, c)
        if r == 0:
            cnt += (q + 1)
        else:
            cnt += (q + 2)
print(cnt)

문제 설명

N*N개의 방이 있습니다.

각 방은 (1, 1)부터 (N, N)까지 번호가 매겨져 있습니다.(2≤N≤100).

베시는 최대한 많은 방에 불을 밝히고 싶어 합니다.

- 베시는 유일하게 불이 켜져 있는 방인 (1,1) 방에서 출발합니다.

- 각 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있습니다.

  예를 들어, (1, 1)방에 있는 스위치로 (1, 2) 방의 불을 끄고 켤 수 있습니다.

- 베시는 불이 켜져 있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있습니다. 

입력

첫 번째 줄에는 N(2≤N≤100)과, M(1≤M≤20,000)이 정수로 주어집니다.

다음 M 줄에는 네 개의 정수 x, y, a, b가 주어집니다. (x, y) 방에서 (a, b) 방의 불을 켜고 끌 수 있다는 의미입니다.

한 방에 여러 개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있습니다. 

아래 링크에서 15개의 샘플 케이스를 다운로드 받을 수 있습니다.

www.usaco.org/current/data/lightson_silver_dec15.zip

알고리즘

1. 각 방에는 여러 개의 스위치가 있습니다. 따라서 매트릭스를 만들어서 다른 방의 스위치 좌표들을 저장합니다

위 입력을 토대로 한 예시 매트릭스입니다. 이 매트릭스는 switchs라고 부르겠습니다.

2. 스위치의 상태(on/off)와 베스가 이동 가능한 방인지를 표현할 매트릭스를 만듭니다.

이 매트릭스는 board라고 부르겠습니다.

불이 꺼진 상태 : 0

불이 켜진 상태 : 1

베스가 이동 가능한 방 : 2

베스는 항상 (1, 1)에서 출발한다고 했으므로, (1, 1)의 초기값은 2입니다.

3. 베스의 출발 지점인 (1, 1)을 queue 리스트에 담습니다.

  - queue 리스트에 들어 있는 좌표는 다른 방의 스위치를 탐색하기 위해 사용됩니다.

  - queue에 리스트에 값이 없어질 때 까지 4 ~ 4-2-1 과정에 대한 반복문이 수행됩니다.

4. queue에 있는 좌표 (1, 1)을 빼내고, 해당 좌표의 switchs 매트릭스에 있는 모든 다른 방의 스위치를 누릅니다.

  - 스위치를 켠 방의 상하좌우를 탐색하여 주변에 2가 있는지 확인합니다.

4-1. 주변에 2가 없다면 board 매트릭스의 해당 좌표에 1을 입력합니다.

  (불만 켭니다 : 해당 방에는 베스가 들어갈 수 없습니다.)

4-2. 주변에 2가 있다면 board 매트릭스의 해당 좌표에 2를 입력합니다.

 (불이 켜져 있는 인접한 방이므로, 베스가 들어갈 수 있습니다.)

  - 주변에 1이 남아 있는 경우를 고려하여, 다시 한 번 상하좌우를 탐색해야 합니다

4-2-1. 상하좌우로 인접한 방에 1이 있는지 확인한 후, 존재한다면 2로 수정합니다. 

 -  4-2-1번 작업은 BFS 알고리즘이 재귀적으로 수행되어야 합니다.

 -  2로 수정된 방의 좌표에서는 switchs에 기록된 정보들의 탐색이 이뤄지지 않았으므로, queue에 담습니다.

* 4-2-1 작업이 재귀적으로 수행되어야 하는 이유

첫 번째 그림은, 기존에 불 켜져있는 방들이 밀집됐지만, 베스가 들어갈 수 없는 방을 표현했습니다.

두 번째 그림에서 (1, 2)에 불이 켜짐으로써 나머지 (2, 2), (3, 2), (3, 3)도 들어갈 수 있는 방으로 변해야 하는 상황이 되었습니다. 따라서 4-2-1 작업은 재귀적으로 수행되어야 합니다. 그 결과는 세 번째 그림과 같습니다.

코드

import sys
from collections import deque
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

n, m = map(int, input().split())  # n : n x n의 방을 만듦, m : m개의 데이터를 받음
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

board = [[0] * (n+1) for _ in range(n+1)]  # 1: 불 켜짐, 2: 이동 가능
board[1][1] = 2
switchs = [[[] for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    x, y, a, b = map(int, input().split())
    switchs[x][y].append([a, b])


def BFS(x, y):
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0 < xx <= n and 0 < yy <= n:
            if board[xx][yy] == 1:
                board[xx][yy] = 2
                queue.append([xx, yy])
                BFS(xx, yy)


cnt = 1
queue = deque([[1, 1]])
while queue:
    x, y = queue.popleft()
    for a, b in switchs[x][y]:
        for i in range(4):
            aa = a + dx[i]
            bb = b + dy[i]
            if 0 < aa <= n and 0 < bb <= n:
                if board[a][b] == 2:
                    break

                if board[aa][bb] == 2:
                    cnt += 1
                    board[a][b] = 2
                    queue.append([a, b])
                    BFS(a, b)
                    break
        if board[a][b] == 0:
            board[a][b] = 1
            cnt += 1
print(cnt)

문제설명

1. N으로 3이 주어졌다면, 수열 1 2 3이 생성됐음을 의미한다. (3 <= N <= 9)

2. 각 숫자 사이에는 '+' 또는 '-', '  '가 들어간다.

(' '는 숫자를 이어 붙이는 것을 의미한다. 예를 들어 2 3이라면, 23이 된 것이다.)

3. n이 주어졌을 때 수열 사이에 '+', '-', ' ' 을 넣은 후 0이 나오는 수식을 ascii 순서에 따라 출력해야 한다.

알고리즘

1. DFS를 통해 수열 사이에 들어간 문자 형태의 경우의 수를 구한다.

  - ASCII 순서에 따라 수식을 출력하라고 했으므로, [' ', '+', '-']가 되어야 합니다. 

  - 답이 틀렸을 시에는 ASCII 순서로 작성되지 않았는지 확인합니다.

2. 경우의 수가 되는 형태 마다 0이 되는지 계산한다.

  - N개의 수열이 모두 들어간 상태에서 0이 되는지 확인해야 하므로, 가지치기(컷팅)가 되지 않습니다

'  ', '+', '-'의 ASCII 순서 비교

# ' '가 '+'보다 작다.
print(ascii(' ') < ascii('+'))  # TRUE

# ' '가 '-'보다 작다
print(ascii(' ') < ascii('-'))  # TRUE

# '+'가 '-'보다 작다
print(ascii('+') < ascii('-'))  # TRUE

# 따라서...  ' ' --> '+'  --> '-'

함수설명

- replace : 블로그 참고 [ gaza-anywhere-coding.tistory.com/21?category=827729 ]

- eval : string으로 주어진 수식에서 숫자와 부호를 구분하여 계산합니다. 결과 값은 int로 리턴됩니다.

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def calculator(form):
    form = form.replace(" ", '')
    return eval(form)


def DFS(L, form):
    if L == n:
        tot = calculator(str(form))
        if tot == 0:
            print(form)
        return

    else:
        for x in [' ', '+', '-']:
            transform = str(form) + x + str(r[L+1])
            DFS(L+1, transform)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        n = int(input())
        r = list(range(n+1))
        DFS(1, 1)
        print()

www.acmicpc.net/problem/9576

문제

1. N권의 책이 있다. 각 책에는 1부터 N까지 순차대로 번호가 매겨져 있다.

2. M명의 학생이 가지고 싶은 책의 번호를 a b 형태로 제출한다.

3. a부터 b까지의 책 중 남는 것이 있다면 한 개씩 받을 수 있다.

 - 남는 책이 없으면 받지 못한다.

4. 책을 받을 수 있는 최대 학생 수는?

알고리즘

1. 학생들이 제출한 목록을 "b를 기준으로 오름차순 --> a를 기준으로 내림차순" 한다.

2. 책의 분배 상태를 의미하는 리스트를 한 개 만든다.

 - 인덱스는 책의 번호를 의미한다.

 - 인덱스 값은 책을 분배했음(1), 분배하지 않음(0)을 의미한다.

3. 학생들이 제출한 범위 내에서 반복문을 진행하고, 책의 분배 상태를 확인한다.

 - 분배되지 않은 책을 발견하면, 리스트의 해당 인덱스를 1로 변경한 후 반복문을 종료한다.

* b를 기준으로 오름차순 한 이유

[1, 2]와 [2, 4]의 예제가 존재한다고 가정하자.앞선 학생이 갖는 선택지는 1과 2가 있다.뒷 학생이 갖는 선택지는 2, 3, 4가 있다.

만약 앞선 학생이 1번 책을 선택한다면, 뒷 학생은 온전히 2, 3, 4의 선택지를 갖게 된다.

하지만 만약 앞선 학생이 2번 책을 선택한다면, 뒷 학생은 3, 4의 선택지를 갖게 된다.

또한, [a, b]에서 b는 언제나 a보다 작거나 같다. (a<=b)

따라서 b가 낮은 학생들이 우선순위를 가져야 한다.

* a를 기준으로 내림차순 한 이유

b를 기준으로 오름차순한 상태에서 a를 기준으로 내림차순 한 이유는 다음과 같다.

예를 들어, [2, 3]과 [1, 3]이 존재한다고 하자.

앞선 학생의 경우의 선택지는 2와 3이 있다.

반면에 뒷 학생의 선택지는 1, 2, 3이 있다.

따라서 선택지가 더 적은 [2, 3]을 제출한 학생이 우선순위를 가져야 한다.

즉, a를 기준으로 내림차순 해야 한다.

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


n = int(input())
for _ in range(n):
    numBooks, numStudents = map(int, input().split())
    queue = [list(map(int, input().split())) for _ in range(numStudents)]
    queue.sort(key=lambda x: x[1])

    status = [0] * (numBooks+1)
    for i in range(numStudents):
        for j in range(queue[i][0], queue[i][1]+1):
            if status[j] == 0:
                status[j] = 1
                break
    print(sum(status))

www.acmicpc.net/problem/1931

문제설명

1. n개의 회의 스케줄이 주어진다.

2. 각 스케줄에는 (시작시간, 종료시간)이 주어진다.

3. 가장 많은 회의를 진행했을 때 개수는?

4. 단, 회의 시간이 종료되자마자 회의가 시작될 수 있으며, 회의시작 시간과 종료시간이 같을 수 있다.

문제 특징

- 회의가 빨리 끝나면 더 많은 회의를 할 수 있다.

하지만 단순히 회의 종료시간을 기준으로 오름차순을 하게 되면 반례에 걸리게 된다.

예를 들어, [5, 5], [5, 5], [4, 5]가 스케줄로 주어진다고 하자.

그렇다면 우리가 예상하는 답은 [4, 5], [5, 5], [5, 5]이다.

하지만 만약 회의 시작시간이 내림차순으로 되어 있다면 [5, 5], [5, 5], [4, 5]가 출력이 된다.

따라서 "종료시간(오름차순) -> 시작시간(오름차순)"으로 정렬이 이뤄져야 한다.

코드

import sys
import heapq
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

n = int(input())
heap = []
for _ in range(n):
    s, e = map(int, input().split())
    heapq.heappush(heap, (e, s))

cnt = 0
before_e = 0
while heap:
    e, s = heapq.heappop(heap)
    if s >= before_e:
        before_e = e
        cnt += 1
print(cnt)

문제설명

1. 설탕을 담을 수 있는 3kg짜리 봉투와  5kg짜리 봉투가 있다.

2. 설탕의 무게인 N이 주어졌을 때 사용할 최소의 봉투를 출력하자.

3. 정답이 없다면, -1을 출력한다.

문제 특이사항

- 반례로 N이 11인 상황을 예로 들 수 있습니다.

일반적인 풀이로는 5kg짜리 봉투가 가장 많을 때 답이 된다고 생각할 수 있습니다.

이런 경우에는 5kg짜리 봉투를 2개를 사용한 뒤에 나머지를 3kg짜리 봉투에 담아야 합니다.

그렇게 되면 3kg짜리 봉투에 들어갈 수 있는 설탕의 양은 2kg 밖에 되지 않습니다. 

즉, 문제에서 요구하는 답을 낼 수 없습니다.

5kg짜리 봉투 1개에만 적당히 소금을 담고,  3kg짜리 봉투를 2개를 사용하여 설탕을 담으면 문제에서 요구하는 정답을 제출할 수 있습니다.

알고리즘

N이 11로 주어진 상황을 가정하고 설명하겠습니다.

1. 5kg짜리 봉투가 허용하는 최대 무게부터 5 단위로 감소시키며, 0까지 반복문을 실행합니다.

2. N에서 5가 허용하는 무게(10, 5, 0)를 뺍니다.

뺀 값은 다시 N에 담습니다.

3. N을 3으로 나눕니다. 이 때 나머지가 0이면, 반복문을 빠져나옵니다.

4. 답으로는 5의 "'배수(2)'가 되는 값 + N/3의 몫"으로 제출합니다. (나머지가 0인 것이 없다면 -1을 답으로 제출합니다)

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

inputData = int(input())
T = inputData//5
answer = -1
for i in range(T, -1, -1):
    n = inputData - (5 * i)
    a, b = divmod(n, 3)
    if b == 0:
        answer = i + a
        break
print(answer)