Jin의 일상

문제 풀이

최대 무게가 주어진 뒤, 개별 무게들을 통해 최대 가치를 구하는 문제이므로, DP로 풀 수 있다.

(DP 설명 : gaza-anywhere-coding.tistory.com/117)

코드 작성시 특징

뒤에서부터 반복문이 진행되도록 알고리즘을 작성하면, 훨씬 효율적으로 코드를 작성할 수 있다.

뒤에서 반복문 수행한 코드 (Better)

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

# input data
n, max_weight = map(int, input().split())
data = [tuple(map(int, input().split())) for _ in range(n)]  # weight, value

# dynamic programming
answer = -1
dp = [0] * (max_weight + 1)
for i in range(n):
    unit_weight = data[i][0]
    unit_value = data[i][1]
    for weight in range(max_weight, unit_weight-1, -1):
        dp[weight] = max(dp[weight], dp[weight - unit_weight] + unit_value)
print(dp[max_weight])

앞에서 반복문 수행한 코드 (Worse)

import sys
#sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

# input data
n, m = map(int, input().split())
data = [(0, 0)] + [tuple(map(int, input().split())) for _ in range(n)]  # weight, value

# dynamic programming
answer = -1
dp = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for weight in range(1, m + 1):
        unit_weight = data[i][0]
        unit_value = data[i][1]

        if unit_weight > weight:
            dp[i][weight] = dp[i - 1][weight]
        else:  # unit_weight <= weight
            dp[i][weight] = max(dp[i - 1][weight], dp[i - 1][weight - unit_weight] + unit_value)
print(dp[n][m])

다양한 화폐 단위가 주어졌을 때 n원을 만들 수 있는 경우의 수를 구하는 문제다.

n원을 만들기 위한 경우의 수를 구해야 하므로, "큰 문제를 작은 문제로 나눈다"는 컨셉으로 접근할 수 있다.

따라서 DP 문제다.  (DP 정리 : gaza-anywhere-coding.tistory.com/117)

화폐의 작은 단위부터 만들 수 있는 금액의 경우의 수를 구해나간다.

밑에 적은 표를 보면, 1원과 2원으로 4원을 만들 수 있는 경우의 수는 3이다.

1원을 이용해서 4원을 만들 수 있는 방법 : 1가지  (1원+1원+1원+1원)

+

2원을 이용해서 4원을 만들 수 있는 방법: 2가지 (1원+1원+2원), (2원+2원)

 >>> 4(price) - 2(unit) = 2이므로, 2원을 만들기 위한 경우의 수를 리스트에서 찾고, 기존에 4원을 만들 수 있는 경우의 수를 적었던 리스트의 원소 값에 더해준다.

코드 참고

문제풀이

5 3 5로 테스트 케이스가 주어졌다고 가정하자.

라운드가 끝날 때 마다 승자는 아래 그림과 같이 표시된다.

Kim과 Lim의 랭킹 변화가 나타내는 규칙을 따라가면,

Kim - (Kim // 2), Lim - (Lim // 2)임을 알 수 있다.

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

n, kim, lim = map(int, input().split())
ans = 0
while kim != lim:
    kim -= (kim // 2)
    lim -= (lim // 2)
    ans += 1
print(ans)

문제 풀이

1. 이중 반복문을 통해서 최초 land를 찾는다.

 (1) 최초로 발견되는 land의 개수를 카운트 한다.

 (2) 2번 과정을 수행한다.

2. 최초 land의 좌표부터 깊이 우선탐색(DFS)을 수행한다.

 (1) 탐색된 land(1)를 sea(0)으로 바꾼다.

3. 정답을 리턴한다.

코드

import sys

# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def dfs(x, y):
    board[y][x] = 0
    for i in range(8):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if 0 <= next_x < w and 0 <= next_y < h and board[next_y][next_x] == 1:
            dfs(next_x, next_y)


def calc_num_land():
    cnt = 0
    for y in range(h):
        for x in range(w):
            if board[y][x] == 1:
                cnt += 1
                dfs(x, y)
    return cnt

if __name__ == '__main__':
    # 8방향 탐색
    dx = [0, 0, 1, -1, -1, -1, 1, 1]
    dy = [-1, 1, 0, 0, -1, 1, -1, 1]

    while True:
        # 데이터 입력
        w, h = map(int, sys.stdin.readline().split())  # w: 너비(x), h: 높이(y)
        if w == 0 and h == 0:
            break
        board = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]

        # 섬 탐색
        ans = calc_num_land()
        print(ans)

입력예제

반례가 될 수 있는 케이스를 담은 입력 예제입니다.

4 7
3 0 3 4 1 2 1

문제 풀이

문제 풀이는 총 두 단계로 나뉩니다.

1. 물이 고일 수 있는 범위 탐색

 - 0번 인덱스부터 오른쪽으로 이동하며,

(1) 자신보다 크거나 같은 레벨을 갖는 최초 인덱스를 찾습니다. (0번 ~ 2번, 2번~3번)

(2) (1)에 해당하는 것이 없다면, 오른쪽에 있는 인덱스의 레벨 중 가장 큰 값을 가지는 인덱스를 찾습니다(3~5번, 5~6번)

2. 탐색된 범위 내에 고인 물의 양 계산

1번 단계를 통해 찾아진 범위 안에 속하는 물의 양을 계산합니다.

계산 방법은 왼쪽 기둥과 오른쪽 기둥 중, 낮은 기둥을 기준으로 정하고, 물의 양을 계산합니다.

0번~2번 -> 기준: 3 / 답: 3

2번~3번 -> 기준: 3 / 답: 0

3번~5번 -> 기준: 2 / 답: 3

5번~6번 -> 기준: 1 / 답: 0

코드

import sys

# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def find_range(sIdx):
    secIdx = sIdx + 1
    for i in range(sIdx + 1, w):
        if heights[sIdx] <= heights[i]:  # sIdx와 같은 레벨이거나 큰 레벨 탐색
            return i
        if heights[secIdx] < heights[i]:  # sIdx 보다 낮은 레벨 중 가장 큰 레벨 탐색
            secIdx = i
    return secIdx


def calculate_amount_water(sIdx, eIdx):
    horizon = min(heights[sIdx], heights[eIdx])
    cnt = 0
    for i in range(sIdx+1, eIdx):
        cnt += (horizon - heights[i])
    return cnt


if __name__ == "__main__":
    h, w = map(int, input().split())  # h: 세로  w: 가로
    heights = list(map(int, input().split()))
    tot_amount_water = 0
    sIdx = 0
    while sIdx < w - 1:
        eIdx = find_range(sIdx)
        # print(sIdx, eIdx)
        # print(calculate_amount_water(sIdx, eIdx))
        tot_amount_water += calculate_amount_water(sIdx, eIdx)
        sIdx = eIdx
    print(tot_amount_water)

문제풀이

collections 라이브러리를 이용하면 간단히 풀 수 있는 문제다.

입력 받을 때 input()으로 하면 시간 초과가 나온다.

sys.stdin.readline()으로 풀면 된다.

- 데크가 빈 경우를 식별하기 위한 조건문을 사용할 때는 len()를 통해 비교하지 말고, 데크를 가르키고 있는 인스턴트 변수의 존재 유무를 판별하는 것이 합리적이다.

코드

import sys
from collections import deque
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

t = int(sys.stdin.readline())
dq = deque()
for _ in range(t):
    cmd = sys.stdin.readline().strip()
    if cmd == "front":
        if dq:
            print(dq[0])
        else:
            print(-1)
    elif cmd == "back":
        if dq:
            print(dq[-1])
        else:
            print(-1)
    elif cmd == "size":
        print(len(dq))
    elif cmd == "empty":
        if dq:
            print(0)
        else:
            print(1)
    elif cmd == "pop_front":
        if dq:
            print(dq.popleft())
        else:
            print(-1)
    elif cmd == "pop_back":
        if dq:
            print(dq.pop())
        else:
            print(-1)
    else:
        cmd, x = cmd.split(" ")
        if cmd == "push_back":
            dq.append(x)
        else:  # push_front
            dq.appendleft(x)

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

풀이

최단 경로를 찾아야 하므로, BFS를 사용한다.

기본 BFS와 다른 점은, 벽을 부술 한 번의 기회가 있다는 것이다.

코드를 작성하기 전에 아래의 상황을 고려해야 한다.

노란 경로는 시작과 동시에 벽을 부쉈으므로, 파란 경로보다 더 빠르게 출구로 향할 수 있었다.

하지만 출구 바로 직전에 벽이 존재하므로, 더 이상 벽을 부술 수 없다.

따라서 알고리즘 작성 시에 벽을 부술 한 번의 기회를 주어주는 것만으로는 반례가 존재한다.

코드

import sys
from collections import deque
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

n, m = map(int, input().split())  # n(y), m(x)
board = [list(map(int, input())) for _ in range(n)]

check = [[[0, 0] for _ in range(m)] for _ in range(n)]  # x, y, state(0: 벽 안부숨, 1: 벽 부숨)
check[0][0][0] = 1

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
q = deque([[0, 0, 0]])  # 좌표, 벽 부쉈는지: [x, y, state]
while q:
    x, y, state = q.popleft()
    if x == m-1 and y == n-1:
        print(check[y][x][state])
        break

    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0 <= xx < m and 0 <= yy < n:
            if board[yy][xx] == 0 and check[yy][xx][state] == 0:
                check[yy][xx][state] = check[y][x][state] + 1
                q.append([xx, yy, state])
            elif board[yy][xx] == 1 and state == 0:
                check[yy][xx][1] = check[y][x][0] + 1
                q.append([xx, yy, state + 1])
else:
    print(-1)

# for y in range(n):
#     for x in range(m):
#         print(check[y][x], end=' ')
#     print()

가장 많이 팔린 책을 출력하되, 가장 많이 팔린 책이 동일한 개수를 갖는다면 사전 순으로 앞선 것을 출력합니다.

Dictionary를 사용해야 하는데, Python 3.6부터는 입력된 key의 순서에 따라서 정렬이 된다고 합니다.

따라서 Dictionary에 input 값을 넣기 전에, 사전 순으로 정렬을 한 다음 값을 담아 줍니다.

그리고 반복문을 통해 가장 많이 팔린 "책의 개수"와 "책 이름"으로 갱신되게 합니다. 

import sys

# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

n = int(input())
books = [input() for _ in range(n)]
books.sort(reverse=False)  
books_dict = {}
for book in books:
    books_dict[book] = books_dict.get(book, 0) + 1 

mx = -1
mx_k = ''
for k, v in books_dict.items(): 
    if mx < v:
        mx = v
        mx_k = k
print(mx_k)