크래프톤 정글 TIL : 0722

lazyArtisan·2024년 7월 22일

TIL

정글 TIL

목록 보기

22/147

🎯 To-do List

☑️ CSAPP 저자 직강 유튜브 보기
☑️ 운영체제 영상 보기
☑️ 운영체제 블로그 보기

📝 배운 것들

🏷️ 3.7 레지스터

🏷️ LCS (Longest Common Sequence) 알고리즘

이미지 출처

i랑 j for문 2개 돌리면서 순회하는데,

첫번째 문자열의 i번째 글자랑
두번째 문자열의 j번째 글자를 비교한다.

다르면 왼쪽 칸, 위쪽 칸 중 최댓값을 가져오고
같으면 왼쪽 위 대각선 칸 값에서 1 더한 값을 넣는다.

그림과 이야기로 설명을 해보자.

첫번째 문자열의 2번째 글자 (AB에서 B)
두번째 문자열의 3번째 글자 (GBC에서 C)가
다른 걸 발견함
→ "B랑 C 비교했더니 다르네. 부분 순열에 같이 포함 못 시키겠다."
→ 1. B만 넣은 AB하고, C를 안 넣은 GB의 공통 순열 길이는 B 1개
→ 2. B를 안 넣은 A하고, C를 넣은 GBC를 공통 순열 길이는 0개
→ "1.의 결과를 골라서 순열의 다음 글자로 B를 추가하면 되겠다."

아니 뭐하러 결과를 두개나 비교함? 그냥 B 넣은 AB하고 C 넣은 GBC를 비교하면 되는거 아님?
→ 이전 결과 두 개 중의 최댓값이 이번 결과값인데 뭐하러 또 비교를 해서 연산 늘림? 이렇게 연산 줄이는게 dp잖음.

첫번째 문자열의 3번째 글자 (ABC에서 C)
두번째 문자열의 3번째 글자 (GBC에서 C)가
같은 걸 발견함
→ "C랑 C 비교했더니 같네. C를 부분 순열에 포함시켜야겠다."
→ "C랑 C 비교하기 전에 AB랑 GB 비교했을 때 부분순열 길이 몇이었음? 거기에 1개 더 추가하면 됨."

🏷️ 배낭 문제

이미지 출처

각 물건마다 배낭 용량을 늘려가며

'이거 넣어질까?' (= 물건을 넣을만큼 배낭 용량이 충분한가?)
'넣었을 때, 안 넣은 경우보다 가치가 높은가?'

이 2가지를 물어보면 끝이다.

물건 1의 무게는 5이므로 배낭 용량 5 이상부터 1개 넣을 수 있다. 당장은 비교할 최댓값 없으니 다 넣는다.

물건 2의 무게는 4이므로 배낭 용량 4 이상부터 1개를 넣을까 말까 고민해야 한다.
배낭 용량 4일 때는 비교할 최댓값이 없었으니 그냥 넣는다.
배낭 용량 5일 때 물건 2를 1개 넣어봤더니 가치가 40이다. 이전의 최대 가치보다 크므로 채택한다.
... 같은 방식으로 진행한다.

물건 3의 무게는 6이므로 배낭 용량 6 이상부터 1개 넣을까 말까 고민해야 한다.
배낭 용량 6일 때 물건 3을 1개 넣어봤더니 가치가 30이다. 이전의 최대 가치가 더 크므로 채택하지 않는다.
...
배낭 용량 10일 때 물건 3을 1개 넣어봤더니 남은 배낭 용량이 4이다.
배낭 용량 4에 대한 최댓값(3은 넣으면 안됨)은 40이다. 이것과 물건 3의 가치를 더하면 70이다.
이전의 최대 가치인 50과 비교하면 더 크므로 채택한다.

이거 반복하면 맨 마지막 칸에 최대 가치 구할 수 있음.
모든 배낭 용량에 대해 모든 물건의 최적의 경우의 수를 구할 수 있기 때문이다.

⚔️ 백준

📌 9084 동전

T = int(input())
for i in range(T):
    N = int(input())
    coins = list(map(int, input().split()))
    M = int(input())
    case_list = [0]*(M+1)
    case_list[0] = 1
    for coin in coins:
        for money in range(coin, M+1):
            case_list[money] += case_list[money-coin]
    print(case_list[M])

풀긴 풀었는데 답지 보고 기억 더듬어서 푼 거에 더 가까웠다.
이해는 살짝 한듯.

동전 1원, 5원, 10원이 있을 때 1000원을 만들려면
999원 경우의 수 + 995원 경우의 수 + 990원 경우의 수를 합쳐야 한다.

10원을 만들려면
9원 경우의 수 + 5원 경우의 수 + 0원 경우의 수를 합쳐야 한다.

즉, 동전마다 경우의 수를 한 번씩 끌어올려주는 것이다.

📌 9251 LCS

F = input()
S = input()
L = [[0]*(len(S)+1) for i in range(len(F)+1)]

for i in range(1,len(F)+1):
    for j in range(1,len(S)+1):
        if F[i-1] == S[j-1]:
            L[i][j] = L[i-1][j-1] + 1
        else:
            L[i][j] += max(L[i-1][j],L[i][j-1])

print(L[i][j])

LCS 개념 정리만 확실하게 했더니 (구현 코드도 보긴 했었음) 코드가 술술 쓰였다.
[[0]*(len(S)+1) for i in range(len(F)+1)] 여기서 S랑 F 위치가 바뀌어서
한창 인덱스 오류로 헤매고 있었는데 동기인 배지훈 교수님이 틀린 부분을 짚어주셨다.

📌 12865 아주 평범한 배낭

import sys
input = sys.stdin.readline
# N = 물품의 수, K = 배낭 용량
N, K = map(int,input().split())
objs = [tuple(map(int,input().split())) for _ in range(N)]
objs.sort()
dp = [[0]*(K+1) for _ in range(N+1)]

# 물건을 하나씩 순회한다
for i in range(1,N+1):
    # 배낭 용량을 하나씩 늘린다
    obj = objs[i-1]
    # print('obj',obj)
    for j in range(obj[0],K+1):
        # 넣으면 최댓값인가? ('현재 물건 가치 + 남은 용량 최대 가치'와
        # '지금까지 계산한 현재 용량에서의 최대 가치' 비교)
        now = obj[1] + dp[i-1][j-obj[0]]
        until = dp[i-1][j]
        # print('now until',now,until)
        if now > until:
            dp[i][j] = now
        else:
            dp[i][j] = until

print(dp[-1][-1])
    
for d in dp:
    print(d)

이렇게 풀었는데 반례가 있었다.

정답 17 나와야 되는데 16이 나온다.

gpt한테 고쳐달라고 했더니

import sys
input = sys.stdin.readline

# N = 물품의 수, K = 배낭 용량
N, K = map(int,input().split())
objs = [tuple(map(int, input().split())) for _ in range(N)]

dp = [0] * (K + 1)

# 물건을 하나씩 순회한다
for weight, value in objs:
    # 배낭 용량을 하나씩 줄인다 (역순으로 순회)
    for j in range(K, weight - 1, -1):
        dp[j] = max(dp[j], dp[j - weight] + value)

print(dp[K])