컴공0개언어

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42885

기본적인 그리디 문제와 유사해 보인다. 따라서 people을 오름차순으로 정렬한 후, limit에 넘지 않도록 최대한 많은 사람을 태우면 될 것 같다. 하지만 최대 2명 탑승가능 조건이 있기 때문에 앞에서부터 차례로 태우는 것이 아니라 보트에 탄 사람들의 무게가 limit에 최대한 가깝도록 사람들을 태워야 한다. 

예시로 people이 [40, 50, 60, 70, 80, 90]로 정렬되어 있는 상태이고 limit은 120이라고 하자.

그러면 앞에서부터 차례로 사람들을 태우는 경우 다음과 같이 5개의 구명보트가 필요하다.

따라서 보트에 탄 사람들의 무게가 limit에 최대한 가깝도록 하기 위해 다음과 같이 low와 high를 설정할 수 있다. 

여기서 people[low]+people[high]가 130이므로 limit 120보다 크다. 따라서 high에 있는 사람은 구명보트를 혼자서밖에 탈 수 없으므로 구명보트 개수를 1 증가시키고 high를 1 감소시켜서 high에 있는 사람을 구명보트에 태워 보낸다. 

갱신된 low와 high상태는 다음과 같다.

여기서는 people[low]+people[high]가 120이므로 limit와 같다. 따라서 low와 high에 있는 사람을 모두 구명보트에 태울 수 있으므로 구명보트 개수를 1 증가시키고 low는 1 증가, high는 1 감소시킨다.

이러한 작업을 low <= high일 동안 반복한다.

def solution(people, limit):
    answer = 0
    
    people.sort()
    
    low = 0
    high = len(people) - 1
    
    while low <= high:
        if (people[low] + people[high]) > limit:
            answer += 1
            high -= 1
        elif (people[low] + people[high]) <= limit:
            answer += 1
            low += 1
            high -= 1
    
    return answer

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

key로 숫자, value로 (0이 출력되는 횟수, 1이 출력되는 횟수)를 저장하는 counts 딕셔너리를 이용하였다.

fibonacci(0)이 호출되었을 때는 0이 출력되는 횟수가 1, 1이 출력되는 횟수가 0이므로 counts[0]은 (1, 0)으로 초기화하고, 같은 방법으로 counts[1]은 (0, 1)로 초기화 하였다.

따라서 counts[i]는 (counts[i-1][0] + counts[i-2][0], counts[i-1][1] + counts[i-2][1])가 된다.

import sys

counts = {0: (1, 0), 1: (0, 1)} # key: num, value: (0이 출력되는 횟수, 1이 출력되는 횟수)

def fibonacci(n):
    if n == 0: return 0
    if n == 1: return 1

    for i in range(2, n+1):
        counts[i] = (counts[i-1][0] + counts[i-2][0], counts[i-1][1] + counts[i-2][1])


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

for _ in range(N):
    n = int(sys.stdin.readline())

    if n in counts:
        print(counts[n][0], end=' ')
        print(counts[n][1])
    else:
        fibonacci(n)

        print(counts[n][0], end=' ')
        print(counts[n][1])

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

입력받은 연산자들에 대해서 itertools에 있는 permutation에 대해서 가능한 모든 경우에 대해서 계산을 진행하여 최대/최소값을 구하였다.

import sys
from itertools import permutations

#  1-2÷3+4+5×6 ==> 54
def get_result(nums, ops):
    N = len(nums)
    result = 0

    if ops[0] == '+':
        result = nums[0] + nums[1]
    elif ops[0] == '-':
        result = nums[0] - nums[1]
    elif ops[0] == 'x':
        result = nums[0] * nums[1]
    elif ops[0] == '/':
        if nums[0] < 0 or nums[1] < 0:
            result = -(abs(nums[0]) // abs(nums[1]))
        else:
            result = nums[0] // nums[1]

    for i in range(1, N-1):
        if ops[i] == '+':
            result = result + nums[i+1]
        elif ops[i] == '-':
            result = result - nums[i+1]
        elif ops[i] == 'x':
            result = result * nums[i+1]
        elif ops[i] == '/':
            if result < 0 or nums[i+1] < 0:
                result = -(abs(result) // abs(nums[i+1]))
            else:
                result = result // nums[i+1]

    return result

N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
op_count = list(map(int, sys.stdin.readline().split())) # + - x %
ops = ['+'] * op_count[0] + ['-'] * op_count[1] + ['x'] * op_count[2] + ['/'] * op_count[3]

min_result = sys.maxsize
max_result = -sys.maxsize
for permutation in permutations(ops, N-1):
    temp_result = get_result(nums, permutation)

    if min_result > temp_result:
        min_result = temp_result

    if max_result < temp_result:
        max_result = temp_result

print(max_result)
print(min_result)

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

조합의 경우들을 출력하는 것으로, itertools에 있는 combinations를 사용하면 간단하게 해결할 수 있다.

import sys
from itertools import combinations

N, M = map(int, sys.stdin.readline().split())
nums = list(range(1, N+1))

for combination in combinations(nums, M):
    print(*combination)

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

순열 경우의 수들을 출력하는 것으로, itertools에 있는 permutations()을 이용하면 간단하게 해결할 수 있다.

import sys
from itertools import permutations

N, M = map(int, sys.stdin.readline().split())
nums = list(range(1, N+1))

for permutation in permutations(nums, M):
    print(*permutation)

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

deque를 이용하여 문제를 해결하였다. 먼저 톱니바퀴 위치에 따른 index는 다음과 같다.

따라서 왼쪽 톱니바퀴의 회전 여부를 판단할 때는 현재 톱니바퀴에서 index가 6인 원소의 값과 왼쪽 톱니바퀴에서 index가 2인 원소의 값을 비교하고, 오른쪽 톱니바퀴의 회전 여부를 판단할 때는 현재 톱니바퀴에서 index가 2인 원소의 값과 오른쪽 톱니바퀴에서 index가 6인 원소의 값을 비교한다.

그리고 N극은 0, S극은 1이므로 위의 톱니바퀴를 deque로 나타내면 "01011111"이고, 시계방향과 반시계 방향으로 회전했을 때의 값은 다음과 같다.

 따라서 시계 방향으로 회전시킬 경우 deque.appendleft(deque.pop()), 반시계 방향으로 회전시킬 경우 deque.append(deque.popleft())를 사용한다.

import sys
from collections import deque

# N극 : 0, S극 : 1
# 초록색 판단 부분 index : 2, 6
wheels = [deque(list(sys.stdin.readline().rstrip())) for _ in range(4)]

def init_rotate(wheel_num, direction):
    if 1 <= wheel_num <= 3:
        # 오른쪽 톱니바퀴 회전 판단
        if wheels[wheel_num-1][2] != wheels[wheel_num][6]:
            rotate(wheel_num+1, -1*direction, True)

    if 2 <= wheel_num <= 4:
        # 왼쪽 톱니바퀴 회전 판단
        if wheels[wheel_num-1][6] != wheels[wheel_num-2][2]:
            rotate(wheel_num-1, -1*direction, False)

    if direction == 1:  # 시계
        wheels[wheel_num - 1].appendleft(wheels[wheel_num - 1].pop())
    elif direction == -1:  # 반시계
        wheels[wheel_num - 1].append(wheels[wheel_num - 1].popleft())


def rotate(wheel_num, direction, next_right=True):
    if next_right and 1 <= wheel_num <= 3:
        # 오른쪽 톱니바퀴 회전 판단
        if wheels[wheel_num-1][2] != wheels[wheel_num][6]:
            rotate(wheel_num+1, -1*direction, True)

    if not next_right and 2 <= wheel_num <= 4:
        # 왼쪽 톱니바퀴 회전 판단
        if wheels[wheel_num-1][6] != wheels[wheel_num-2][2]:
            rotate(wheel_num-1, -1*direction, False)

    if direction == 1:  # 시계
        wheels[wheel_num - 1].appendleft(wheels[wheel_num - 1].pop())
    elif direction == -1:  # 반시계
        wheels[wheel_num - 1].append(wheels[wheel_num - 1].popleft())

def calc_score():
    score = 0

    for i, wheel in enumerate(wheels):
        if wheel[0] == '1':
            score += 2 ** i

    return score


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

for _ in range(K):
    # wheel_num : 회전시키는 톱니바퀴 번호, direction: 1이면 시계방향, -1이면 반시계방향
    wheel_num, direction = map(int, sys.stdin.readline().rstrip().split())

    init_rotate(wheel_num, direction)

print(calc_score())

init_rotate()와 rotate()를 합치고 싶었는데 생각보다 쉽지 않아서 하지 못한 점이 아쉽다.

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

① 처음 테이프 시작 지점(start)을 (처음 물이 새는 위치 - 0.5), 마지막 지점(end)을 (처음 물이 새는 위치 + 0.5)로 설정 

② 물이 새는 위치를 하나씩 가져오면서 마지막 지점을 (현재 물이 새는 위치 + 0.5)로 갱신하고, (end-start)값이 테이프의 길이보다 큰지 확인

③ 크면 이전 물이 새는 위치까지 막을 수 있다는 것이므로, 테이프 개수를 1 증가하고 테이프 시작 지점을 (현재 물이 새는 위치 - 0.5)로 갱신하고 동일한 과정을 반복

④ 마지막 (start-end)값이 테이프 길이와 같거나, 마지막 물이 새는 위치가 하나 남았을 때에도 막아야하므로 (end-start)이 1이상이면 테이프 개수 1 증가

처음 소스코드를 제출했을 때 맞게 작성한 것 같았는데 틀려서 살펴보니 정렬을 하지 않은 상태에서 진행했었다. 예제에서는 물이 새는 위치가 오름차순으로 입력되어 있어서 정렬을 안해도 될 것 같지만 문제를 살펴보면 내림차순 or 오름차순으로 입력한다는 부분이 없으므로 물이 새는 위치를 오름차순으로 정렬한 후 진행해야한다. 

import sys

N, L = map(int, sys.stdin.readline().split())

locations = list(map(int, sys.stdin.readline().split()))
locations.sort() # 위치가 오름차순 or 내림차순으로 입력된다는 조건이 없으므로

tape_count = 0
start = locations[0] - 0.5
end = locations[0] + 0.5
for loc in locations:
    end = loc + 0.5

    if (end - start) > L:
        tape_count += 1
        start = loc - 0.5

if (end - start) >= 1:
    tape_count += 1

print(tape_count)

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

그렇게 어려운 문제는 아니었다. 첫 날부터 캠핑장을 사용한다고 하면 최대 캠핑장 사용 일수를 구할 수 있다.

구체적으로는 V일 중 P일의 사이클이 V//P번 완전하게 반복하므로 L*(V//P)일동안 캠핑장을 사용하고, 마지막 부분은 V%P와 L중 작은 값 만큼 캠핑장을 사용한다. 따라서 캠핑장 최대 사용일은 L*(V//P) + min(V%P, L)이다. 

예제로 주어진 L=5, P=8, V=20일 경우를 살펴보면

V//P = 2이므로 P일의 사이클이 2번 반복되므로 16일까지 10번 캠핑장을 이용하고, V%P = 4, L=5이므로 마지막 4일동안 모두 캠핑장을 사용하므로 총 14일동안 캠핑장을 이용한다. 소스코드는 다음과 같다.

import sys

i = 0
while True:
    L, P, V = map(int, sys.stdin.readline().rstrip().split())

    if L == 0 and P == 0 and V == 0:
        break

    print('Case %d: %d' % (i+1, L*(V//P) + min(V%P, L)))

    i += 1