컴공0개언어

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

deque를 사용하면 문제가 아주 간단해진다.

문제 설명에 나와있는대로 위에 있는 카드를 뺄 때는 deque.popleft()를 하면 되고, 위에 있는 카드를 아래로 옮길 때는 deque.popleft()값을 append해주면 된다.

import sys
from collections import deque

N = int(sys.stdin.readline())
deque = deque([i+1 for i in range(N)])

while len(deque) > 1:
    deque.popleft()
    deque.append(deque.popleft())

print(deque[0])

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

지도와 동일한 크기를 가지는 visited리스트를 만든다. visited는 방문했으면 True, 방문하지 않았으면 False값을 가진다. 따라서 map이 '1'값을 가지고, visited가 False값을 가질 때 탐색을 시작하도록 한다. 탐색한 부분의 visited는 True로 변경하고, 상하좌우 중 map이 '1'값을 가지고 visited가 False인 지점이 있으면 재귀를 이용하여 탐색을 진행한다.

import sys
sys.setrecursionlimit(10**9)

house_num = 0
house_nums = []
def dfs(house_map, visited, start_row, start_col):
    if visited[start_row][start_col]:
        return

    global house_num

    dx = [0, 0, -1, 1] # 상 하 좌 우
    dy = [-1, 1, 0, 0]

    house_num += 1
    visited[start_row][start_col] = True

    for i in range(len(dx)):
        if 0 <= start_row + dy[i] < len(house_map) and 0 <= start_col + dx[i] < len(house_map[start_row+dy[i]]):
            if house_map[start_row+dy[i]][start_col+dx[i]] == '1' and not visited[start_row+dy[i]][start_col+dx[i]]:
                dfs(house_map, visited, start_row+dy[i], start_col+dx[i])


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

house_map = [sys.stdin.readline().rstrip() for _ in range(N)]
visited = [[False] * N for _ in range(N)]

group_count = 0
for i in range(len(house_map)):
    for j in range(len(house_map[i])):
        if house_map[i][j] == '1' and not visited[i][j]:
            dfs(house_map, visited, i, j)
            group_count += 1

            if house_num != 0:
                house_nums.append(house_num)
                house_num = 0

print(group_count)

house_nums.sort()
for house_num in house_nums:
    print(house_num)

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