[WEEK05] DAY32 & TMI

DAY32

2021.12.02 THU

알고리즘 한 달 과정의 마지막 날 !
어제 새벽까지 지난 4주 과정을 복습하다 귀가해서 2주차까지는 복습을 끝냈다.
이번 주차에는 C언어를 공부하면서 틈틈히 쉬고싶을 때 3~4주차 알고리즘 개념을 다시 복습해내야겠다.

2579 계단 오르기 (DP)

코드

import sys

n = int(sys.stdin.readline())
stairs = [int(sys.stdin.readline()) for _ in range(n)]
dp = [[0 for _ in range(2)] for _ in range(n)]
# dp[n] = n번째 계단까지 밟았을 때 최대 점수

if n == 1:
    print(stairs[0])
else:
    dp[0][0] = stairs[0]
    dp[1][0], dp[1][1] = stairs[1], stairs[1] + stairs[0]

    for i in range(2, n): # n번째 = i
        dp[i][0] = max(dp[i - 2][0], dp[i - 2][1]) + stairs[i] # 규칙2
        dp[i][1] = dp[i - 1][0] + stairs[i] # 규칙1

    print(max(dp[n - 1][0], dp[n - 1][1])) 

.
.

1202 보석 도둑 (그리디, DFS)

코드

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
n, k = map(int, input().split())
jewerly = tmp = []
for i in range(n):
    m , v = map(int, input().split())
    jewerly.append([m, v])
bag = [int(input()) for _ in range(k)]
jewerly.sort()
bag.sort()
result = i = 0
for b in bag:
    ## 현재 가방의 무게보다 무게가 작은 보석들을 찾음
    while i < n and jewerly[i][0] <= b:
        heappush(tmp, -jewerly[i][1])
        i += 1
    ## 가치가 제일 큰 보석을 tmp에서 빼고 result에 넣는다
    if tmp:
        result -= heappop(tmp)
print(result)

힙을 잘 사용하자.

.
.

1520 내리막길 (DP)

코드

import sys
input = sys.stdin.readline

# 상하좌우 방향
# 다음값이 현재 값보다 < 작을 때만 이동
# DP[N] = (n-1, n-1)까지 항상 내리막길로만 이동하는 경로의 개수

def dfs(x, y):
    if [x, y] == [N-1, M-1]:
        return dp[x][y]
    if dp[x][y] != -1: # 탐색한 길일 때
        return dp[x][y]
    dp[x][y] = 0 # 탐색한 길은 0(초깃값) 경로값은 가산할 예정
    for i in range(4):
        nx = x + dx[i] # 행
        ny = y + dy[i] # 열
        if 0<=nx<N and 0<=ny<M and arr[x][y] > arr[nx][ny]: # 범위 안에 있고, 이동할 좌표의 값이 현재위치 값보다 작으면
            dp[x][y] += dfs(nx, ny) # 경로 가산
    return dp[x][y]

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
dp = [[-1] * M for _ in range(N)] # -1 아니어도 됨
dp[-1][-1] = 1 # 최종 도착지
dx = [1, -1, 0, 0] # 하 상
dy = [0, 0, 1, -1] # 우 좌
print(dfs(0,0))

피곤피곤.
알고리즘 주차는 끝났지만 앞으로도 1~2일에 하나씩 알고리즘을 꼭 계속해서 풀어볼 예정이라 알고리즘/파이썬 스터디를 하기로 했다.

새로운 C언어 공부도 파이팅 아자아자