Jin의 일상

www.acmicpc.net/problem/14938

문제 설명

첫째 줄에는 지역의 개수(n), 수색 범위(m), 길의 개수(r)이 주어집니다.

둘째 줄에는 n개의 숫자가 차례대로 각 구역에 있는 아이템의 수를 나타냅니다.

세 번째 줄부터 r+2번째 줄 까지 지역의 번호 a, b와 길의 길이 i가 주어집니다.

이 때, 각 지역에서 수색 범위(m) 내에서 다른 지역으로 이동했을 때 얻을 수 있는 최대 아이템 개수를 구해야 합니다.

m이 5로 주어졌을 때 2번 지역에서는 "1번, 3번, 5번"으로 이동할 수 있습니다.

2번->1번->4번은 8(0+3+5)의 수색 범위를 가지므로 이동할 수 없습니다.

문제 특성

각 노드에서 다른 노드로 이동했을 때 최소 경로를 구해야 합니다.

따라서 다익스트라 알고리즘을 적용합니다.

알고리즘

1. 1 ~ n번 지역에서 다익스트라 알고리즘 수행  : 각 지역에서 다른 지역으로 이동했을 때 최소 경로를 구합니다.

3. 각 지역에서의 최소 경로 중 m 이하인 수색 범위의 구역에 있는 아이템 개수를 구합니다.

4. 이전 지역과 비교하여 더 많은 아이템 개수로 갱신합니다.

다익스트라 알고리즘

다익스트라 알고리즘의 전체 과정은 다음과 같습니다. 1번~4번 수행과정을 따라 알고리즘을 파악하시면 됩니다!

참고로 0번 인덱스의 [3, 5]에 대해 과정이 모두 수행된 다음에 [1, 3]에서 0(heap[1])과 더하고 dy와 비교하는 과정이 수행됩니다. 

이어서 각 리스트 변수에 대한 세부 사항을 설명하겠습니다.

1. graph는 각 노드 간의 정보를 담고 있습니다.

graph는 총 n 개의 길이를 가지며, 인덱스는 노드 번호를 의미합니다.

 - 문제에서 1번 지역을 graph에서는 0(1-1)번 인덱스로 담았습니다.

또한, graph의 각 인덱스는 복수 개의 [인접한 노드번호, 거리]를 가질 수 있습니다.

2. dy는  한 지역에서 다른 지역으로 이동할 때 최소 거리를 담고 있습니다.

 - dy는 총 n 개의 길이를 가지며, 인덱스는 노드 번호를 의미합니다.

 - dy의 인덱스 초기 값은 int의 최대 값으로 설정합니다. 이 값은 지역 간 이동할 수 있는 최소 거리를 의미합니다.

 - 가령, 2번 지역에서 4번 노드로 이동할 때는 8(3+5)이 최소거리입니다.  따라서 알고리즘이 수행된 후에 dy의 1번 인덱스는 8이 리턴되어야 합니다.

3. heap는  다른 지역으로 이동할 때, 중간 경로의 역할을 수행합니다.

- heap에 들어가는 초기 값은 (출발 지역 번호, 0)입니다. 뒤에 있는 0은 이동해야 하는 거리를 의미합니다.

  - 가령 3번 지역에서 출발한다면  (2, 0) 입니다. (출발 지역 번호-1이므로) 

  - 0번에서 0번을 이동하므로, 초기 거리는 0입니다.

- heap 리스트가 비었을 때 다익스트라 알고리즘은 종료됩니다.

코드

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


def dijstra(x):
    dy = [sys.maxsize] * n
    dy[x] = 0
    heap = [[x, dy[x]]]
    while heap:
        node, dis = heapq.heappop(heap)
        for i in range(len(graph[node])):
            next = graph[node][i]
            if dy[next[0]] > dis + next[1]:
                dy[next[0]] = dis + next[1]
                heapq.heappush(heap, [next[0], dis + next[1]])
    return dy

if __name__ == "__main__":
    n, m, r = map(int, input().split())  # 지역의 개수, 수색범위, 길의 개수
    numItem = list(map(int, input().split()))  # 인덱스는 지역 번호를 의미
    graph = [[] for _ in range(n)]
    for _ in range(r):
        a, b, i = map(int, input().split())  # 연결된 지역의 번호(a, b), 길의 길이(i)
        graph[a - 1].append([b - 1, i])
        graph[b - 1].append([a - 1, i])
    res = 0
    for i in range(n):    # 각 노드에서 최소 경로탐색
        minPath = dijstra(i)
        add = 0
        for j in range(n):    # 최소 경로가 m 이하일 때 획득할 수 있는 아이템 수
            if minPath[j] <= m:
                add += numItem[j]
        res = max(res, add)
print(res)

www.acmicpc.net/problem/10775

문제 설명

1. G개의 게이트 수가 주어진다.

2. P개의 비행기는 순차대로 날아오며, 비행기마다 i값을 갖는다.

3. 비행기는 1~G(i) 게이트 중 하나에 주차된다.

 - 주차될 수 없다면, 더 이상 비행기가 공항으로 날아오지 않는다.

4. 가장 많은 비행기가 주차됐을 때 수는?

조건 범위

G (1 ≤ G ≤ 10^5)

P (1 ≤ P ≤ 10^5)

gi (1 ≤ gi ≤ G)

특이사항

반복문으로 이 문제를 풀 경우, 최대 10^5 * O(10^5)가 걸립니다. (10,000,000,000)

파이썬이 1초에 50,000,000 정도 계산한다고 가정했을 때, 반복문으로 풀면 안됩니다.

따라서 이 문제는 "유니온-파인드"를 이용해서 해결해야 합니다.

알고리즘

총 6대의 비행기가 각 [4, 3, 2, 1, 4]의 값을 가지고 게이트에 날아온다고 가정하겠습니다.

1. 리스트를 만듭니다. 리스트 명은 gates로 정의하겠습니다. 또한, 각 인덱스의 값은 parent를 의미합니다.

 - 인덱스와 parent가 같다면, 주차장이 빈 상태임을 의미합니다.

 - 인덱스와 parent가 다르다면, 이미 비행기가 주차된 상태를 의미합니다.

2. i가 4인 비행기가 날아옵니다.

(2-1) gates의 4번 인덱스의 부모 노드를 확인합니다.

 - 부모노드는 4이므로, 해당 게이트에 주차되지 않은 상태입니다. 비행기를 4번 게이트에 주차시킵니다. (cnt 1 증가)

(2-2) 4번 게이트가 주차됐으므로, 한 칸 앞에 위치한 게이트의 부모노드를 값으로 수정합니다.

3. i가 3인 비행기가 날아옵니다.

 - 알고리즘 2번과 동일한 상황이므로, 3번 게이터에 주차(cnt 1 증가)시키고 앞에 위치한 부모노드 값으로 수정합니다.

4. i가 2인 비행기가 날아옵니다.

 - 알고리즘 2번과 동일한 상황이므로, 2번 게이터에 주차(cnt 1 증가)시키고 앞에 위치한 부모노드 값으로 수정합니다.

5. i가 1인 비행기가 날아옵니다.

 - 알고리즘 2번과 동일한 상황이므로, 1번 게이터에 주차(cnt 1 증가)시키고 앞에 위치한 부모노드 값으로 수정합니다.

6. i가 4인 비행기가 날아옵니다.

- gates의 4번 인덱스의 부모 노드를 확인합니다.

4번 인덱스의 부모노드는 자신의 값과 다릅니다. 즉, 4번 인덱스에는 비행기가 주차되어 있습니다.

따라서 4번 인덱스의 부모 노드로 이동합니다. 조금 전과 같은 상황이 연쇄적으로 반복됩니다.

재귀적으로 호출한 결과는 역순으로 리턴됩니다.

따라서 지나온 경로의 gates 인덱스는 부모 노드로 수정됩니다. 

참고로 지나온 경로를 이렇게 수정하는 테크닉을 "경로 단축"이라고 합니다.

경로 단축 테크닉을 사용하면 다음 번에 다시 i가 4인 비행기가 날아왔을 때

이번과 같이 O(N)경로를 지나지 않고 O(1)로 리턴할 수 있습니다.

방금 과정에서 4번 비행기가 날아왔을 때 0을 리턴했습니다.

이는 모든 게이트가 꽉 찼음을 의미합니다. 따라서 알고리즘을 종료합니다.

코드

import sys

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


def find(n):
    if gates[n] == n:
        return n
    else:
        gates[n] = find(gates[n])
        return gates[n]


def union(a, b):
    x = find(a)
    y = find(b)
    gates[x] = y
    return

if __name__ == "__main__":
    numGate = int(input())
    numPlane = int(input())
    gates = list(range(numGate + 1))

    cnt = 0
    for _ in range(numPlane):
        gate = int(input())
        parent = find(gate)
        if parent == 0:
            break
        union(parent, parent-1)
        cnt += 1
    print(cnt)

문제 설명

1. 1부터 1,000,000,000 까지의 범위를 갖는 n이 주어집니다.

2. 피보나치 수열을 최소의 개수로 더해서 n을 만들었을 때 결과를 리턴해야 합니다.

알고리즘

1. 주어진 범위 내에서 가능한 피보나치 수열을 리스트에 담습니다. (1 ≤ n ≤ 1,000,000,000)

2. 이분 탐색 알고리즘을 통해 n보다 작거나 같은 수를 찾습니다. 

3. n에서 찾은 수를 빼줍니다. 

4. n이 0이 될 때 까지 2~3번 과정을 반복합니다.

코드

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

fibo = [0, 1]
idx = 0
while fibo[idx + 1] < 1000000000:
    fibo.append(fibo[idx] + fibo[idx + 1])
    idx += 1

t = int(input())
for _ in range(t):
    n = int(input())
    stack = []
    lt = 0
    rt = len(fibo) - 2
    while n != 0:
        while lt <= rt:
            mid = (lt + rt) // 2
            if fibo[mid] > n:
                rt = mid - 1
            else:
                lt = mid + 1
        n -= fibo[rt]
        stack.append(fibo[rt])
        lt = 0
    stack.reverse()
    print(*stack)

문제 설명

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)

programmers.co.kr/learn/courses/30/lessons/43165

문제 설명

1. 배열 변수인 numbers가 주어진다. ex) [1, 3, 4, 5, 2]

2. int형 변수인 target이 주어진다.

3. 각 numbers를 무작위로 더하거나 빼서 target 값과 같은 개수는?

문제 풀이

1. 모든 경우의 수를 찾아야 하므로 완전 탐색 문제 입니다.

2. 더하거나 뺐을 때 나오는 값을 재귀적으로 실행시킵니다.

3. 경우의 수가 만들어질 때 마다 target 값과 sum 값이 같은지 비교후 리턴 합니다.

  - 같다면, cnt를 1씩 올려줍니다.

4. cnt를 정답으로 제출합니다.

코드

def solution(numbers, target):
    def DFS(L, sum):
        nonlocal cnt
        if L == len(numbers):
            if sum == target:
                cnt += 1
            return
        else:
            plus = sum + numbers[L]
            DFS(L + 1, plus)
            minus = sum - numbers[L]
            DFS(L + 1, minus)
            
    cnt = 0
    DFS(0, 0) 
    return 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/1946

문제 설명

1. 지원자 n명에 대한 [면접랭킹, 인터뷰랭킹]이 주어집니다.

2. 선별 기준은 다른 모든 지원자와 비교했을 때 적어도 하나의 랭킹은 남들보다 부족하지 않아야 합니다.

3. 최대한 많은 사람을 뽑았을 때 몇 명인지 제출해야 합니다.

알고리즘

1. "면접 랭킹" 또는 "인터뷰 랭킹" 중 하나를 오름차순으로 정렬한다.

  - 이 글에서는 면접 랭킹을 정렬한다. 

2. 면접 랭킹을 기준으로 정렬 후, 가장 앞에 있는 지원자는 선별이 확정된다. 

3. "선별이 확정된 지원자의 인터뷰 랭킹"과 "다음 지원자의 인터뷰 랭킹"과 비교합니다.

  - 다음 지원자의 랭킹이 높다면, 선별을 확정합니다

  - 그렇지 않다면, *선별하지 않습니다.

* 선별하지 않는 이유

선별된 지원자인 A[1, 4]와 선별되지 않은 지원자 B[2, 5]를 비교해보겠습니다.

- [2, 5] 중에 2는 면접랭킹을 가르키고, 5는 인터뷰랭킹을 가르킵니다.

B가 선별되기 위해서는 A와 비교하여 적어도 하나의 우수한 성적이 있어야 합니다.

 - B의 면접랭킹(2)은 A(1)보다 더 낮습니다.

 - B의 인터뷰랭킹(5)은 A(4)보다 더 낮습니다.

따라서 B는 선별되지 못합니다.

문제 특징

1. O(N)으로 해결해야 한다.

 - list.sort(), sorted()이 포함되면 시간초과가 나거나, 시간 효율성이 매우 떨어진다.

 따라서 리스트를 만들어서 인덱스를 면접 랭킹으로 사용하고, 인덱스 값을 인터뷰 랭킹으로 사용한다.

코드

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

numCase = int(input())
for _ in range(numCase):
    numApplicants = int(input())
    ranks = [0] * (numApplicants + 1)
    for _ in range(numApplicants):
        doc, intvw = map(int, input().split())
        ranks[doc] = intvw

    cnt = 0
    last_intvw = numApplicants + 1
    for i in range(1, numApplicants+1):
        if ranks[i] < last_intvw:
            last_intvw = ranks[i]
            cnt += 1
    print(cnt)