컴공0개언어

문제링크 : www.acmicpc.net/problem/1932

9461번(파도반 수열)문제처럼 규칙을 구하는 dp문제는 접해본 적이 있지만 이렇게 최대/최소를 구하는 유형의 dp문제는 처음 풀어보았다.

주어진 예제를 통해 풀이 방법을 설명해보도록 하겠다.

맨 밑에 있는 값들을 (1) 맨 왼쪽에 있는 수 (2) 맨 오른쪽에 있는 수 (3) (1)와 (2)사이에 있는 수로 나눌 수 있다. 먼저 (1)의 경우는

으로 오른쪽 상단 한 곳을 통해서만 올 수 있기 때문에 처음 입력한 정수 삼각형 값을 저장하는 리스트를 triangle, 최댓값을 저장하는 리스트를 d라고 하면, d[i][j] = d[i-1][j] + triangle[i][j]이다. 

(2)의 경우는

으로 왼쪽 상단 한 곳을 통해서만 올 수 있기 때문에 d[i][j] = d[i-1][j-1] + triangle[i][j]이다.

(3)의 경우에 해당하는 5, 2, 6중 5에 대해서만 살펴보면

으로, 왼쪽 상단과 오른쪽 상단 두 곳을 통해서 올 수 있기 때문에 두 곳 중 최댓값을 가지는 곳에서 현재값을 더해야 최댓값을 갖게 된다. 따라서 d[i][j] = max(d[i-1][j-1], d[i-1][j]) + triangle[i][j]이다.

따라서 소스코드는 다음과 같다(별로 추천하지 않음. 맨 밑에 있는 소스코드가 좋음) .

import sys

n = int(sys.stdin.readline())
triangle = []
d = []
for _ in range(n):
    nums = list(map(int, sys.stdin.readline().rstrip().split()))
    d.append([0 for _ in range(len(nums))])
    triangle.append(nums)

d[0][0] = triangle[0][0]

for i in range(1, n):
    for j in range(0, i+1):
        if j == 0:
            d[i][j] = d[i-1][j] + triangle[i][j]
        elif j == i:
            d[i][j] = d[i-1][j-1] + triangle[i][j]
        else:
            d[i][j] = max(d[i-1][j-1], d[i-1][j]) + triangle[i][j]

print(max(d[n-1]))

채점 후, 다른 분들의 소스코드를 살펴보니 내가 한 것처럼 입력한 정수 삼각형 값을 저장하는 triangle과 값에 해당하는 최댓값 d리스트를 각각 만들지 않고, 하나의 리스트를 통해서 계산을 하였다. d[i][j]가 계산될 때 재사용하는 값들은 이전 줄들의 값이기 때문에 하나의 리스트를 갱신하며 계산해는 것이 공간적으로도 더욱 효율적이고 소스코드도 더욱 간결하였다.

import sys

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

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

    triangle.append(nums)

for i in range(1, n):
    for j in range(0, i+1):
        if j == 0:
            triangle[i][j] = triangle[i-1][j] + triangle[i][j]
        elif j == i:
            triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]
        else:
            triangle[i][j] = max(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j]

print(max(triangle[n-1]))

문제를 해결하고보니 재귀문제를 푸는 것 같다는 느낌이 들기도 했다.

문제링크 : www.acmicpc.net/problem/9461

dp문제인데, dp문제를 거의 풀어본 적이 없어서 쉽지 않았다. 파도반 수열의 값 P(1) ~ P(11)의 값이 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12인데, 규칙을 찾으려 노력했지만 처음에는 잘 보이지 않았다. 여러가지 관찰을 하던 중 홀수 번째와 짝수 번째 파도반 수열로 나누어서 살펴보았다.

 짝수 번째 값들을 살펴보면 P(4) = P(1) + P(2), P(6) = P(3) + P(4), ..., P(n) = p(n-3) + p(n-2)이고, 홀수 번째 값들을 살펴보면 P(5) = P(2) + P(3), P(7) = P(4) + P(5), ..., P(n) = p(n-3) + p(n-2)이다. 따라서 n의 값이 홀수 짝수와 관계없이 P(n) = P(n-3) + P(n-2)이다. 

사실 이러한 규칙은 홀수 짝수 나누지 않고도 발견할 수 있지만 나누지 않았을 때는 찾지 못하였다.

이에 맞춰서 작성한 소스코드는 다음과 같다.

import sys

def padovan(d, n):
    if 1 <= n <= 3:
        return 1

    if d[n] != 0:
        return d[n]

    d[n] = padovan(d, n-3) + padovan(d, n-2)

    return d[n]


T = int(sys.stdin.readline())
d = [0 for _ in range(101)]
d[1], d[2], d[3] = 1, 1, 1

for _ in range(T):
    N = int(sys.stdin.readline())
    print(padovan(d, N))

문제링크 : www.acmicpc.net/problem/1541

연산자로는 -와 +밖에 없기 때문에 덧셈을 먼저 계산한 후 뺄셈을 계산하면 최대한 큰 수를 빼게되어서 최솟값이 나올 것이라 생각하였다.

import sys

ops = sys.stdin.readline().rstrip().split('-')

for i in range(len(ops)):
    if '+' in ops[i]:
        nums = list(map(int, ops[i].split('+')))
        sum = 0
        for num in nums:
            sum += num

        ops[i] = sum
    else:
        ops[i] = int(ops[i])

result = ops[0]
for i in range(1, len(ops)):
    result -= ops[i]

print(result)

문제 링크 : www.acmicpc.net/problem/1931

그리디 문제로 최대 테스트 케이스가 100000개이므로 최대 O(nlogn)알고리즘으로 작성해야 될 것 같았다.

회의가 끝나는 시간에 대해서 오름차순으로, 끝나는 시간이 같은 부분에서는 시작하는 시간에 대해서 오름차순으로 정렬하도록 하였다. 이를위해 sort()를 이용한 다중정렬을 이용하였다.

import sys

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

meetings = []
for _ in range(N):
    tp = tuple(map(int, sys.stdin.readline().rstrip().split())) # (start, end)
    meetings.append(tp)

meetings.sort(key=lambda tp: (tp[1], tp[0]))
result = 0
end_time = 0
for meeting in meetings:
    start_time = meeting[0]

    if start_time >= end_time:
        end_time = meeting[1]
        result += 1

print(result)

문제 링크 : www.acmicpc.net/problem/1920

단순 탐색 문제로, 처음에는 이진탐색을 이용해서 풀었다.

import sys

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (high+low)//2

        if arr[mid] < target:
            low = mid + 1
        elif arr[mid] == target:
            return mid
        elif arr[mid] > target:
            high = mid - 1

    return -1


N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().rstrip().split(' ')))
arr.sort()
M = int(sys.stdin.readline())
targets = list(map(int, sys.stdin.readline().rstrip().split(' ')))

for target in targets:
    if binary_search(arr, target) == -1:
        print('0')
    else:
        print('1')

제출 후에 다른 분들의 코드를 살펴보니 수행시간이 유독 짧은 코드들이 있었는데, 이진 탐색이 아니라 set을 이용한 풀이가 있었다. set을 이용한 코드는 다음과 같다.

import sys

N = int(sys.stdin.readline())
arr = set(sys.stdin.readline().split())
M = int(sys.stdin.readline())
targets = sys.stdin.readline().split()

for target in targets:
    if target in arr:
        print('1')
    else:
        print('0')

두 번째 코드가 첫 번째 코드보다 약 4배정도 빨랐다.

문제 링크 : www.acmicpc.net/problem/10828

스택을 직접 구현하지 않아도 해결 가능하지만 구현해보았음

import sys

class Stack:
    def __init__(self):
        self.stack = []
        self.ptr = 0

    def push(self, data):
        self.stack.append(data)
        self.ptr += 1

    def pop(self):
        if self.ptr > 0:
            ret_value = self.stack[self.ptr - 1]
            del self.stack[self.ptr - 1]
            self.ptr -= 1

            return ret_value
        else:
            return -1

    def top(self):
        if self.ptr > 0:
            return self.stack[self.ptr - 1]
        else:
            return -1

    def size(self):
        return self.ptr

    def empty(self):
        if self.ptr > 0:
            return 0
        else:
            return 1


N = int(sys.stdin.readline())
stack = Stack()
for _ in range(N):
    op = sys.stdin.readline().strip().split()

    if 'push' == op[0]:
        data = int(op[1])
        stack.push(data)
    elif 'pop' == op[0]:
        print(stack.pop())
    elif 'size' == op[0]:
        print(stack.size())
    elif 'empty' == op[0]:
        print(stack.empty())
    elif 'top' == op[0]:
        print(stack.top())