컴공0개언어

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

처음에 나타난 최대 중량을 구하는 방법을 찾는데 시간이 조금 걸렸다. 로프가 버틸 수 있는 최대 중량은 (선택한 로프들의 버틸 수 있는 중량 중 최솟값) x (선택한 로프의 개수)이다. 따라서 예제를 살펴보면 로프가 2개가 있고, 버틸 수 있는 중량이 10, 15이다. 여기서 로프를 모두 사용할 필요는 없으므로 가능한 경우의 수는 2가지이다.

① 버틸 수 있는 중량이 15인 로프만 사용 ==>  버틸 수 있는 중량 = 15 x 1 = 15

② 버틸 수 있는 중량이 10인 로프만 사용 ==> 버틸 수 있는 중량 = 10 x 1 = 10

③ 두 개의 로프를 모두 사용 ==> 버틸 수 있는 중량 = 10 x 2 = 20

따라서 버틸 수 있는 최대 중량은 20이다.

이를 통해 생각한 문제풀이 방법은 다음과 같다.

① 중량들을 내림차순으로 정렬하고, 최대 중량을 첫 번째 원소의 값으로 초기화

② 다음 로프가 추가되었을 때의 중량이 최대 중량보다 크면 최대 중량을 갱신

import sys

N = int(sys.stdin.readline())
ropes = []
for _ in range(N):
    rope = int(sys.stdin.readline())
    ropes.append(rope)

ropes.sort(reverse=True)

weight = 0
max_weight = ropes[0]
for i, rope in enumerate(ropes):
    weight = rope * (i+1)

    if weight > max_weight:
        max_weight = weight

print(max_weight)

제출 후 다른 분들의 코드를 살펴보았는데 리스트 표현식, max()함수 등을 이용하여 소스코드를 간결하게 작성이 가능했다. 따라서 간결한 버전의 소스코드는 다음과 같다.

import sys

N = int(sys.stdin.readline())
ropes = [int(sys.stdin.readline()) for _ in range(N)]

ropes.sort(reverse=True)

weight = 0
max_weight = ropes[0]
for i, rope in enumerate(ropes):
    max_weight = max(max_weight, rope*(i+1))
    
print(max_weight)

문제링크 : 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)

백준 1931번 문제를 해결하면서 리스트를 다중 정렬이 필요했다.

그러면 다중 정렬이란 무엇일까?? 다음과 같은 리스트가 있다고 하자.

list1 = [(5, 4), (4, 4), (4, 3), (5, 2), (3, 1), (3, 2), (2, 5), (2, 1)]

원소가 투플인 해당 리스트를 다음과 같은 조건으로 정렬하고자 한다.

① 투플의 첫 번째 원소에 대해서 오름차순

② 첫 번째 원소의 값이 같으면 두 번째 원소에 대해서 오름차순

먼저 sort()의 key에서 투플의 첫 번째 원소만을 조건으로 주면 결과는 다음과 같다.

list1.sort(key=lambda x: x[0])
# [(2, 5), (2, 1), (3, 1), (3, 2), (4, 4), (4, 3), (5, 4), (5, 2)]

첫 번째 원소에 대해서 정렬은 되지만, 두 번째 원소에 대해서는 정렬이 되지 않고 입력한 순서대로 출력이 된다.

따라서 조건에 맞게 정렬하기 위해서는 다음과 같이 작성하면 된다.

list1.sort(key=lambda x: (x[0], x[1]))
# [(2, 1), (2, 5), (3, 1), (3, 2), (4, 3), (4, 4), (5, 2), (5, 4)]

lambda함수에서 정렬 조건에 맞에 투플 형식으로 주면 된다. 우선순위가 높은 조건을 먼저 인자로 준다.

추가적인 정렬예제들

① 투플의 첫 번째 원소에 대해서 오름차순

② 첫 번째 원소의 값이 같으면 두 번째 원소에 대해서 내림차순

list1.sort(key=lambda x: (x[0], -x[1]))
# [(2, 5), (2, 1), (3, 2), (3, 1), (4, 4), (4, 3), (5, 4), (5, 2)]

① 투플의 두 번째 원소에 대해서 오름차순

② 두 번째 원소의 값이 같으면 첫 번째 원소에 대해서 오름차순

list1.sort(key=lambda x: (x[1], x[0]))
# [(2, 1), (3, 1), (3, 2), (5, 2), (4, 3), (4, 4), (5, 4), (2, 5)]

문제 링크 : 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())