알고리즘 스터디 - 정렬 3문제 풀이 (feat. 통나무 건너뛰기, 색종이 올려 놓기, 장난감 조립)

정렬 문제도 풀이를 하게 되었는데 정렬에 위상정렬도 들어가 있고 퀵 정렬, 힙 정렬 등 다양한 것들이 존재를 하여 일부로 조금 섞게 되었다.

백준 11497번 : 통나무 건너뛰기 - 실버 1

여러 개의 통나무 길이가 주어지는데 통나무 길이 간의 간격을 줄여 원형으로 배치하는 문제이다. 여기서 난이도란 옆칸의 통나무 길이 차이가 최소가 되도록 하고 그 중 가장 큰 길이 차이를 말한다. 이번에 힙 정렬 중 최대 힙을 사용하여 가장 큰 통나무를 가운데에 놓고 왼쪽은 작은 것, 오른쪽은 큰 것을 놓아 구성을 하고 갱신할 때마다 난이도를 새로 생성하게 되었다.

알고리즘 코드

import sys, heapq

t = int(sys.stdin.readline())

result = []

for _ in range(t):
    n = int(sys.stdin.readline())
    tree = list(map(int, sys.stdin.readline().split()))

    h = []
    for i in tree:
        heapq.heappush(h, (-i, i))

    if n >= 3:
        difference = 0
        center = heapq.heappop(h)[1]
        right = heapq.heappop(h)[1]
        left = heapq.heappop(h)[1]
        
        difference = max(difference, center-left)
        difference = max(difference, center-right)
        while h:
            if len(h) == 0:
                break

            if len(h) == 1:
                final = heapq.heappop(h)[1]
                difference = max(difference, right-final)
                break
            
            first = heapq.heappop(h)[1]
            second = heapq.heappop(h)[1]

            difference = max(difference, left-second)
            difference = max(difference, right-first)

            right, left = first, second

        result.append(difference)
    elif n == 2:
        result.append(abs(tree[0]-tree[1]))

    else:
        result.append(tree[0])

for i in result:
    print(i)

백준 2643번 : 색종이 올려 놓기 - 골드 4

이번 문제 같은 경우에는 정렬 + 가장 긴 증가하는 부분 수열(LIS) 결합 문제로 색종이의 최대 개수도 100장으로 작았기에 맘 편히 Python 내장 함수를 마구 썼다. 먼저, 입력을 받을 때 가장 작은 부분이 오도록 먼저 정렬을 하고 paper 배열에 집어 넣었다. 그 다음, x를 기준으로 sort를 하게 되면 우리가 이 종이가 fit한지 살펴보려면 y값만 기준으로 판단하면 된다. 여기서 y 값들만 비교하여 DP의 가장 긴 증가하는 부분 수열로 최장 길이를 찾으면 된다. 최종 코드는 아래와 같다. (근데 DP도 선택 정렬과 유사하게 O(N^2)로 판단을 하는 구만 나중에 다른 방식도 공부해봐야겠다.)

알고리즘 코드

import sys

n = int(sys.stdin.readline())
paper = []

for _ in range(n):
    width = list(map(int, sys.stdin.readline().split()))
    paper.append(sorted(width))

paper.sort()

dp = [1 for _ in range(n)]

for i in range(n):
    for j in range(i):
        if paper[i][1] >= paper[j][1]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

백준 2637번 : 장난감 조립 - 골드 2

이 문제 같은 경우 최종 장난감을 만들기 위한 중간 부품 및 기본 부품들이 존재하고 중간 부품은 기본 부품 및 다른 중간 부품을 통하여 만들 수 있다. 서로 어떤 것을 하나 만들기 위하여 선행되어 필요한 부품들이 존재하는 것을 알 수 있다. 여기서 위상정렬을 사용하는 것을 알 수 있었지만 중요한 것은 최종적으로 필요한 기본 부품들의 수를 구하는 것이다. 아래의 코드만 위상 정렬 아래의 넣으면 최종 개수를 알 수 있다.

if now == n:
    part[next] += number
else:
    if now in middle:
        part[next] += (part[now] * number)

알고리즘 코드

from collections import deque
import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

degree = [0] * (n+1)
graph = [[] for _ in range(n+1)]
part = [0] * n
middle = set()

for _ in range(m):
    x, y, k = map(int, sys.stdin.readline().split())
    graph[x].append([y, k])
    middle.add(x)
    degree[y] += 1

def topology_sort():
    result = []
    q = deque()

    for i in range(1, n+1):
        if degree[i] == 0:
            q.append(i)
    
    while q:
        now = q.popleft()
        result.append(now)

        for next, number in graph[now]:
            degree[next] -= 1

            if degree[next] == 0:
                q.append(next)
            
            if now == n:
                part[next] += number
            else:
                if now in middle:
                    part[next] += (part[now] * number)

topology_sort()

for i in range(1, n):
    if i not in middle:
        print(i, part[i])