pjaehyun의 개발일지

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제

은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다.  서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다.

은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대해서 다음과 같은 과정을 거친다.

1. 서랍 Ai가 비어있다면, i번 술을 그 서랍에 보관한다.
2. 서랍 Bi가 비어있다면, i번 술을 그 서랍에 보관한다.
3. Ai에 들어있는 술을 다른 서랍으로 이동시킨다.(다른 서랍은 Ai에 들어있는 술이 들어갈 수 있는 서랍 중 하나이다) 만약, 그 서랍에도 이미 술이 들어있다면, 그 술을 다른 서랍으로 이동시킨다. 이런 과정을 거쳐서 빈 서랍을 하나 찾아 술을 모두 이동할 수 있는 경우에는, 술을 이동시키고 i번 술을 Ai에 보관한다. 불가능한 경우에는 다음 규칙으로 넘어간다.
4. Bi에 들어있는 술을 다른 서랍으로 이동시킨다. 만약, 그 서랍에도 이미 술이 들어있다면, 그 술을 다른 서랍으로 이동시킨다. 이런 과정을 거쳐서 빈 서랍을 하나 찾아 술을 모두 이동할 수 있는 경우에는, 술을 이동시키고 i번 술을 Bi에 보관한다. 불가능한 경우에는 다음 규칙으로 넘어간다.
5. 위의 과정이 모두 불가능한 경우에는 i번 술을 그 자리에서 마셔버린다. (은기는 전혀 취하지 않는다)

각각의 술에 대해서, 서랍에 보관할 수 있는지, 그 자리에서 마셔버리는지를 구하는 프로그램을 작성하시오.

첫째 줄에 N과 L이 주어진다. (1 ≤ N, L ≤ 300,000)

다음 N개 줄에는 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ L, Ai ≠ Bi)

출력

1번 술부터 N번 술까지 순서대로 보관할 수 있는지, 그 자리에서 먹어야 하는지를 출력한다.

보관할 수 있는 경우에는 "LADICA"를, 먹어버려야 하는 경우에는 "SMECE"를 출력한다.

예제

어떤 도시의 지하철 노선에 대한 정보가 주어졌을 때, 출발지에서 목적지까지의 최소 환승 경로를 구하는 프로그램을 작성하시오. 실제 경로를 구할 필요는 없고, 환승 회수만을 구하면 된다.

입력

첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발지 역의 번호와 목적지 역의 번호가 주어진다. 역 번호는 1부터 N까지의 정수로 표현된다. 각 노선의 길이의 합은 1,000,000을 넘지 않는다.

출력

첫째 줄에 최소 환승 회수를 출력한다. 불가능한 경우에는 -1을 출력한다.

예제

문제풀이 코드

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

def bfs(start, end, subways):
    if start == end:
        return 0
    visited_subway = [False for _ in range(len(subways))]
    visited_station = [False for _ in range(N + 1)]

    dq = deque()
    for subway in graph[start]:
        dq.append((subway, 0))
        visited_subway[subway] = True
    visited_station[start] = True
    
    while dq:
        subway, count = dq.popleft()
        # 현재 지하철이 갈 수 있는 지하철역을 탐색
        for station in subways[subway]:
            # 방문했던 지하철역이면 패스
            if visited_station[station]:
                continue
            # 현재 역이 도착역과 같으면 return
            if station == end:
                return count       
            visited_station[station] = True
            for trans in graph[station]:
                # 한번도 타지않은 지하철일 때 dq에 삽입
                if not visited_subway[trans]:
                    dq.append((trans, count+1))
                    visited_subway[trans] = True
    return -1
            
N, L = map(int, input().split())

# 지하철역에서 탈수있는 호선
graph = defaultdict(list)

# 호선이 지나는 지하철역
subways = []
for i in range(L):
    lst = list(map(int, input().split()))
    subways.append(lst[:-1])
    for l in lst:
        if l == -1:
            continue
        graph[l].append(i)

start, end = map(int, input().split())
result = bfs(start, end, subways)
print(result)

다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다.

조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다.

2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CONVEX HULL) 이라 한다. 아래 그림은 N=10인 경우의 한 예이다.

점의 집합이 주어졌을 때, 볼록 껍질을 이루는 점의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범위는 절댓값 40,000을 넘지 않는다. 입력으로 주어지는 다각형의 모든 점이 일직선을 이루는 경우는 없다.

출력

첫째 줄에 볼록 껍질을 이루는 점의 개수를 출력한다.

볼록 껍질의 변에 점이 여러 개 있는 경우에는 가장 양 끝 점만 개수에 포함한다.

예제

문제풀이 코드

import sys
input = sys.stdin.readline

def ccw(A, B, C):
    return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])
n = int(input())
points = []

for _ in range(n):
    x, y = map(int, input().split())
    points.append([x, y])

# 시계 반대방향으로 정렬 시작
points.sort()
start = points[0]
points.remove(start)

inf = []
for i in range (n-1):
    if start[0] == points[i][0]:
        # 시작점와 같은 y축에 있는 좌표는 따로 빼준다
        inf.append(points[i])
    else:
        # 두 점사이에 기울기를 추가
        points[i].append((start[1]-points[i][1])/(start[0]-points[i][0]))

for i in inf:
    points.remove(i)
# 기울기를 기준으로 정렬
points.sort(key=lambda x : x[2])

for i in inf:
    points.append(i)
# 정렬 종료

stack = []

stack.append(start)
stack.append(points[0])

# Convex Hull(Graham's Scan)
for i in range(1, len(points)):
    # 평행을 이루고 있거나, 시계방향으로 갈 때는 스택에서 제거한다.
    while len(stack) >= 2 and ccw(stack[-2], stack[-1], points[i]) <= 0:
        stack.pop()
    stack.append(points[i])

print(len(stack))

이전엔 Monotone Chain 알고리즘을 사용하여 Convex Hull 문제를 해결했고, 이번 문제는 Graham's Scan 알고리즘을 사용하여 문제를 해결했다. ccw를 이용한 스캔과정을 이전과 유사하나, 위 아래로 탐색하는것이 아니기 때문에 중복되는 좌표를 제거하지 않아도 된다.

1. 그레이엄 스캔을 시작하기 이전에 모든 점은 시계 반대방향으로 정렬되어 있어야 한다.

2. 시작지점을 가져오기 위해서 x축을 기준으로 점들을 정렬한다.

3. 첫번째에 있는 점을 시작포인트로 가져오고, 배열에서 제거한다.

4. 시계 반대방향으로 정렬하기 위해서, 시작점과 points[i]의 기울기를 구하여 추가해준다.(시작점과 y좌표가 같은 점들은 따로 빼둠)

5. 추가된 기울기를 기준으로 배열을 정렬하면 시계 반대방향으로 정렬하게 되고, 이전에 제거했던 시작점과 y좌표가 같은 점을 추가

6. 해당 문제는 한 직선에 점은 두개만 있으면 되기 때문에 ccw에서 받은 값이 0보다 작거나 같을 때 스택에서 pop해준다.

7. 반복문이 종료되면 스택에는 볼록껍질에 해당하는 점만 들어가있기 때문에 스택의 길이를 반환한다.

문제

때때로 주어진 점들 사이에서 볼록 껍질(Convex Hull)을 찾아내는 기술은 요긴하게 쓰인다. ACM 월드파이널에서 볼록 껍질을 응용해야 하는 문제가 출제되다 보니, 이걸 할 줄 아는 것은 참가자의 소양이 되었다.

이 작업은 크게 두 단계의 과정으로 이루어진다. 첫 번째 단계는 볼록 껍질을 이루는 점들을 찾아내는 것이고, 두 번째 단계는 이 점들을 반시계 방향으로 순서를 매기는 것이다. 첫 번째 단계는 이미 완료되었다고 할 때, 두 번째 단계를 수행하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 점의 개수 n이 주어진다. (3 <= n <= 100,000)

두 번째 줄부터 n개의 줄에 걸쳐 각 점에 대한 정보 x, y, c가 주어진다. x, y는 정수이며 절댓값이 1,000,000,000을 넘지 않고, c는 Y 또는 N인 문자이다. Y는 이 점이 볼록 껍질에 속해있음을, N이면 아님을 의미한다.

중복되는 점은 없으며, 모든 점이 한 직선 위에 있는 경우도 없다.

출력

첫 번째 줄에 볼록 껍질을 이루는 점의 개수를 출력한다.

이어서 한 줄에 하나씩 그 점들의 좌표를 x y 형태로 출력하는데, 이 점들은 반시계 방향으로 순서를 이루어야 한다. 첫 번째 좌표는 x좌표가 가장 작은 점이어야 하며, 만약 그런 좌표가 여러 개라면 그 중에서 y좌표가 가장 작은 점을 선택한다.

예제

문제풀이 코드

import sys
from itertools import chain
input = sys.stdin.readline

N = int(input())

# 세 점의 방향 관계를 구함(반시계방향)
def ccw(A, B, C):
    return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])

points = []
for _ in range(N):
    x, y, c = map(str, input().split())
    points.append([int(x),int(y)])

points.sort()
stack = []

# Monotone Chain
for i in chain(range(len(points)), reversed(range(len(points) - 1))):
    while len(stack) >= 2 and ccw(stack[-2], stack[-1], points[i]) < 0:
        stack.pop()
    stack.append(points[i])
    
# 중복 껍질 제거
stack.pop()
for i in range(1, (len(stack) + 1) // 2):
    if stack[i] != stack[-1]:
        break
    stack.pop()

print(len(stack))
for s in stack:
    print(s[0], s[1])

해당 문제는 볼록껍질에 속해있는 좌표를 알 수 있지만 모든 좌표가 주어졌기 때문에 전체 좌표에서 볼록껍질에 해당하는 부분을 구하여 반환하는 방법으로 문제를 해결했고, ConvexHull 알고리즘 중에 Monotone Chain을 이용하였다. 이유는 Graham's Scan은 좌표를 반시계방향으로 정렬해야하는 과정을 거쳐야하기 때문에 좀 더 간단한 Monotone Chain을 사용하기로 했다.

1. Monotone Chain은 껍질의 윗방향과 아랫방향을 만들어 합치기 때문에 chain을 이용하여 반복문을 (0 ~ n ~ 0)으로 돌도록 만든다.

2. stack에는 ccw로 체크를 하기위해 최소 2개의 좌표가 들어가있어야 한다.

3. ccw의 결과가 시계방향이면 0보다 작은값, 평행하면 0, 시계 반대방향이면 0보다 큰 값을 반환한다.

4. stack[-2], stack[-1], points[i]를 A, B, C로 두고 해당 좌표들이 시계 반대방향으로 돌고있으면 현재 좌표를 스택에 넣어주고

5. 세 좌표가 조건을 만족하지 못하면 stack에 있는 값을 하나씩 뽑아준다.

6. 좌표를 구하는 과정이 종료되면 Monotone Chain 알고리즘은 위아래를 합치는 것이기 때문에 중복된 껍질을 제거한다.

7. 마지막으로 스택에 들어있는 좌표들의 수와 순서대로 좌표를 출력한다.

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

예제

문제풀이 코드

import heapq
N, M, X = map(int, input().split())

student = [[] for _ in range(N+1)]
shortest_distances = [0 for _ in range(N+1)]
result = 0

for _ in range(M):
    start, end, time = map(int, input().split())
    student[start].append((end, time))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distances = [int(1e9)] * (N + 1)
    distances[start] = 0

    while q:
        distance, now = heapq.heappop(q)
        if distances[now] < distance:
            continue
        for i in student[now]:
            weight = distance + i[1]
            if weight < distances[i[0]]:
                distances[i[0]] = weight
                heapq.heappush(q, (weight, i[0]))
    return distances

for i in range(1, N+1):
    shortest_distances[i] = dijkstra(i)

for i in range(1, N+1):
    if i == X:
        continue
    result = max(result, shortest_distances[i][X] + shortest_distances[X][i])
print(result)

다익스트라 알고리즘을 사용하여 문제 풀이 

1. 모든 노드의 최단거리를 구해서 배열에 담아준다.

2. i == X와 같을 때는 continue -> X까지의 최단거리가 필요하기 때문에 i가 X일때는 필요없음

3. i -> X로 가는 값 + X -> i로 가는 값(왕복)을 계산해서 result중 더 큰 값을 result에 넣어준다.

4. 반복문이 종료되면 result에는 왕복값이 가장 큰 값이 들어가있다.