[SW정글] Week 04 개발일지

 

Week 04 개발일지

동적 프로그래밍

• 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법
• 비트 연산
  • 1 << k
    • k번째 비트를 켠다
      • 0번째부터 시작
      • 1 << 5 = 0b 100000
    • n & (1 << k)
      • n의 k번째 비트가 켜져있는지 확인
      • 12 & (1 << 3) = True : 0b 1100의 3번째 비트는 1임
    • n | (1 << k)
      • n의 k번째 비트를 켠다
      • 12 | (1 << 2) = 14 : 12의 2번째 비트를 켜서 0b 1110이 됨
  • (1 << k) - 1
    • k개의 비트를 모두 켠다
      • (1 << 5) - 1 = 0b 11111
    • n & ((1 << k) - 1)
      • n의 마지막 k자리 추출
      • 0b 1001 1101 & ((1 << 4) - 1) = 0b 1101

현실에서 유용한 Bitwise 연산 및 활용 모음

 

그리디 알고리즘

부분의 최적의 해를 구해서 전체의 최적의 해를 구하는 알고리즘

 

Test

1890번: 점프

import sys
from functools import cache

input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for x in range(n)]


@cache
def dfs(x, y):
    if x == n - 1 and y == n - 1:
        return 1

    elif arr[x][y] == 0:
        return 0

    result = 0

    dx = [arr[x][y], 0]
    dy = [0, arr[x][y]]

    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < n and ny < n:
            result += dfs(nx, ny)

    return result


print(dfs(0, 0))

1937번: 욕심쟁이 판다

import sys
from functools import cache

input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n = int(input())
arr = [list(map(int, input().split())) for x in range(n)]


@cache
def panda(x, y):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    max_move = 0

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] > arr[x][y]:
            max_move = max(max_move, panda(nx, ny))

    return max_move + 1


result = 0
for i in range(n):
    for j in range(n):
        result = max(result, panda(i, j))

print(result)

1202번: 보석 도둑

import sys
from heapq import *


input = sys.stdin.readline

n, k = map(int, input().split())
j_arr = [tuple(map(int, input().split())) for x in range(n)]
b_arr = [int(input()) for x in range(k)]


def jewel_thief(j_arr, b_arr):
    heapify(j_arr)
    b_arr.sort()

    result = 0
    temp_arr = []
    for bag_w in b_arr:
        while j_arr and j_arr[0][0] <= bag_w:
            weight, value = heappop(j_arr)
            heappush(temp_arr, -value)

        if temp_arr:
            result -= heappop(temp_arr)

    return result


print(jewel_thief(j_arr, b_arr))