1030-TIL 문제풀이

플로이드워셜

모든 정점에서부터의 최단 경로를 찾는 알고리즘인데 간선이 끊어져 있는지 확인하기 위해서도 쓰임

인접행렬

G
for _via range(len(G)):
    for _from range(len(G)):
        for _to range(len(G)):
            dist = G[_from][_via] + G[_via][_to]
                if dist < G[_from][_to]:
                    G[_from][_to] = dist #G 업뎃

LCS 알고리즘

Top-down(recursion) before applying DP

def lcs(i, j):
    # 기본 경우 (Base Case): 두 문자열 중 하나라도 길이가 0이면 최장 공통 부분 수열의 길이는 0입니다.
    if i == 0 or j == 0:
        return 0
    
    # 현재 문자를 최장 공통 부분 수열에 추가하고, 이전 문자열의 최장 공통 부분 수열 길이에 1을 더합니다.
    if str[i] == str[j]:
        return lcs(i-1 ,j-1) + 1
     
    # 현재 문자가 다르다면
    # 한 문자열의 끝에서 한 문자열의 문자를 제외한 경우와 다른 문자열의 문자를 제외한 경우 중 더 긴 최장 공통 부분 수열을 선택합니다.
    return max(lcs(i, j-1), lcs(i-1, j))

Top-down(recursion) after applying DP

import sys

str1 = sys.stdin.readline()
str2 = sys.stdin.readline()
m,n = len(str1), len(str2)
dp = [[-1] * (n + 1) for _ in range(m + 1)] # 여기틀림

# Top-down(recursion) after applying DP
def td_lcs_dp(i, j):
    if i == 0 or j == 0:
        return 0

    # 이미 계산한 결과가 메모에 저장되어 있다면 그 값을 반환
    if dp[i][j] != -1:
        return dp[i][j]
    
    # 현재 문자가 같다면
    if str1[i] == str2[j]:
        # 현재 문자를 최장 공통 부분 수열에 추가하고, 이전 문자열의 최장 공통 부분 수열 길이에 1을 더합니다.
        dp[i][j] = td_lcs_dp(i-1, j-1) + 1
        return dp[i][j]
    
    # 현재 문자가 다르다면
    # 한 문자열의 끝에서 한 문자열의 문자를 제외한 경우와 다른 문자열의 문자를 제외한 경우 중 더 긴 최장 공통 부분 수열을 선택합니다.
    dp[i][j] = max(td_lcs_dp(i, j-1), td_lcs_dp(i-1, j))

    return dp[i][j]

print(td_lcs_dp(m -1, n -1)) # 여기틀림

bottom-up psuedo

# base
dp[0][0]=0
for (int i=1; i<str.length; i+1){
    for(int j=1;j<str.length; j+1){
        if(str1[i]==str2[j]){
            dp[i][j] = dp[i-1][j-1]+1;
            continue
        }
        dp[i][j]=max(dp[i][j-1],[i-1][j]);
    }
}

bottom-up

import sys

string_a = ' ' + sys.stdin.readline().rstrip()
string_b = ' ' + sys.stdin.readline().rstrip()
dp = [[0] * len(string_b) for _ in range(len(string_a))]

for i in range(1, len(string_a)):
    for j in range(1, len(string_b)):
        if string_a[i] == string_b[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            
print(dp[-1][-1])

bottom-up two point (심화)

def btu_lcs_dp(str1, str2):
    m,n = len(str1), len(str2)
    
    # DP 테이블 초기화
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # DP 테이블 채우는 부분
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]: # 현재 문자가 같다면
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # 현재 문자가 다르다면
                # 한 문자열의 끝에서 한 문자열의 문자를 제외한 경우와 다른 문자열의 문자를 제외한 경우 중 더 긴 최장 공통 부분 수열을 선택합니다.
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    # DP 테이블을 이용하여 최장 공통 부분 수열 길이 찾기

    lcs_length = dp[m][n]           # lcs_length는 최장수열의길이
    lcs = [''] * lcs_length         # LCS (최장 공통 부분 수열) 길이에 맞게 빈 문자열 리스트를 생성

    i, j = m, n                     # i와 j를 각각 문자열 str1과 str2의 길이로 초기화.
    index = lcs_length - 1

    while i > 0 and j > 0:
        if str1[i - 1] == str2[j - 1]: # 현재 위치의 문자가 동일한 경우
            # 현재 LCS의 끝에 해당 문자를 추가하고, i와 j를 하나씩 감소.
            lcs[index] = str1[i - 1]
            i -= 1
            j -= 1
            index -= 1 # 아래 a 주석 참조
        elif dp[i - 1][j] > dp[i][j - 1]:# 현재 위치의 문자가 다른 경우
            i -= 1                      # dp 테이블의 위쪽 값이 더 크다면 i를 하나 감소시켜서 위로 이동
        else:
            j -= 1                      # dp 테이블의 왼쪽 값이 더 크다면 j를 하나 감소시켜서 왼쪽으로 이동
    
    # LCS 문자열을 문자열로 변환합니다.
    return "".join(lcs)

while의 if문 마지막에 index -= 1 하는 이유 :
현재 LCS의 문자를 찾았을 때 이 문자를 'lcs' 리스트의 마지막 위치에 추가한 후 그 다음 위치로 이동하기 위함
chatgpt says
이 코드에서 lcs_length는 초기에 lcs 리스트의 마지막 인덱스를 나타내며,
매번 LCS 문자를 찾을 때마다 해당 위치에 문자를 추가한 후,
다음 문자를 저장할 위치로 이동하기 위해 lcs_length를 1 감소시킵니다.
이렇게 하면 lcs 리스트에 LCS 문자열이 역순으로 저장되는데,
이후에 "".join(lcs)를 사용하여 역순으로 저장된 LCS 문자열을 올바른 순서로 결합합니다.

점프

knapsack

그리디/회의실

그리디/신입사원

import sys

# 테스트 케이스의 개수를 읽어옵니다
T = int(sys.stdin.readline())

# 각 테스트 케이스를 처리하는 반복문을 시작합니다
for _ in range(T):
    # 이번 테스트 케이스에서의 참가자 수를 읽어옵니다
    n = int(sys.stdin.readline())
    
    # 참가자들의 순위 정보를 리스트로 읽어옵니다
    rank = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    # 참가자들을 점수(첫 번째 요소)를 기준으로 정렬합니다
    rank.sort(key=lambda x: x[0])

    # 더 나은 순위를 가진 참가자들의 수를 세는 변수를 초기화합니다
    cnt = 1

    # 이전 최고 순위자의 순위를 첫 번째 참가자의 순위로 초기화합니다
    maxRank = rank[0][1]

    # 정렬된 참가자 목록을 반복하면서 처리합니다
    for i in range(n):
        # 현재 참가자의 순위가 이전 최고 순위보다 낮은지 확인합니다
        if rank[i][1] < maxRank:
            # 그렇다면, 더 나은 순위를 가진 참가자 수를 증가시키고 최고 순위를 업데이트합니다
            cnt += 1
            maxRank = rank[i][1]

    # 더 나은 순위를 가진 참가자들의 수를 출력합니다
    print(cnt)

2/1904/하/동적프로그래밍/01타일

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

for k in range(3,n+1):
    dp[k] = (dp[k-1]+ dp[k-2])%15746
print(dp[n])

N이 주어졌을 때 가능한 조합 개수 구하기.

N = 1, 1
N = 2, 00, 11
N = 3, 100, 001

n=1일때 조합 1개,
n=2일때 조합 2개,
n=3일때 조합 3개,
n=4일때 조합 5개,,, -> 피보나치임을 알 수 있지만 본 문제에서로부터 규칙을 찾아보자.

n이3일떄 보면 100과 001 이렇게 두가지 조합이 나오는데 이는
(n-2) + 00 , (n-1) + 1
즉, n이 1일때에서 00을 붙인 것과, n이 2일때에서 1을 붙인 형태이다.

따라서, 아래의 식을 만들 수 있다.
dp[i] = dp[i-1] + dp[i-2]

[주의점]
처음에 %15746 연산을 출력할 때 돌려주었는데 이렇게 하니 메모리 초과가 났다. 그래서 dp 테이블에 넣을 때 연산을 해서 넣으니 문제가 해결되었다.

3/11047/하/그리디/동전0

'''
n = 동전 갯수
k = 총 금액
'''

n, k = map(int, input().split())

coins=list()

for i in range(n):
    coins.append(int(input()))

coins.sort(reverse=True)

result = 0
for i in coins:
    if k == 0:
        break
    result += k // i
    k %= i

print(result)

'''
count = 0
for i in reversed(range(N)):
    count += K//coin_lst[i] #카운트 값에 K를 동전으로 나눈 몫을 더해줌
    K = K%coin_lst[i] # K는 동전으로 나눈 나머지로 계속 반복

'''

그리디로 큰 동전 먼저 넣는 방식으로 접근

구현 하다가 시간 지나서 다른 분 코드보니 나와 달랐던 점

• 리스트로 간단하게 입력 받으심
• 나는 거스르고 남은 돈 K를 어떻게 처리해야할 지 몰랐는데 간단하게 K %= i로 하심

11/1541/하/그리디/잃어버린괄호

코드를 입력하세요