JUNGLE 240408 ~ 240409 (W03)

in Study #Jungle

KRAFTON JUNGLE Week 03

1. Keywords

LCS

  • 최장 공통 부분 수열은 주어진 두 문자열의 부분 수열 중에서 가장 긴 것을 찾는 문제
  • 최장 공통 문자열은 주어진 두 문자열의 (연속된) 부분 문자열 중에서 가장 긴 것을 찾는 문제
  • 즉, 최장 공통 부분 수열은 두 문자열 내에서 문자의 상대적인 순서는 유지되지만, 띄어쓰기 등의 간격은 무시됨
최장 공통 부분 수열 (Longest Common Subsequence)
def LCS(A, B):
    m = len(A)
    n = len(B)
    
    # dp[i][j]는 A[:i]와 B[:j]의 LCS 길이를 저장하는 배열
    dp = [[0] * (n+1) for _ in range(m+1)]
    
    # Bottom-up 방식으로 LCS 길이 계산
    for i in range(1, m+1):
        for j in range(1, n+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]
최장 공통 문자열 (Longest Common Substring)
def longest_common_substring(A, B):
    m = len(A)
    n = len(B)
    
    # dp[i][j]는 A[i-1]과 B[j-1]을 마지막 문자로 하는 공통 부분 문자열의 길이를 저장
    dp = [[0] * (n+1) for _ in range(m+1)]
    
    max_length = 0  # 최장 공통 부분 문자열의 길이
    end_index = 0    # 최장 공통 부분 문자열의 끝 인덱스
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_length:   # 새로운 LCS의 길이가 기존의 최장 길이보다 길다면 최장 길이 업데이트
                    max_length = dp[i][j]
                    end_index = i - 1
            else:
                dp[i][j] = 0
    
    # 최장 공통 부분 문자열 구하기
    longest_substring = A[end_index - max_length + 1: end_index + 1]
    
    return longest_substring

플루이드-와샬 알고리즘

3주차 퀴즈를 위해 복습한 내용,,, but 퀴즈에 나온 알고리즘과는 좀 달랐음..ㅎ

def floyd_warshall(graph):
    n = len(graph)
    dist = [[0 if i == j else graph[i][j] if graph[i][j] != 0 else INF for j in range(n)] for i in range(n)]
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

2. BOJ Issues

1931. 회의실 배정

import sys
input = sys.stdin.readline

N = int(input())
time = [[0] * 2 for _ in range(N)]

for i in range(N):
    a, b = map(int, input().split())
    time[i][0] = a
    time[i][1] = b

# 끝나는 시간을 기준으로 정렬. 끝나는 시간이 같다면 시작 시간이 빠른 순으로 정렬
time.sort(key=lambda x: (x[1], x[0]))

count = 1
end = time[0][1]            # 첫번째 활동의 끝나는 시간 저장
for i in range(1, N):
    if time[i][0] >= end:   # 현재 활동의 시작 시간이 이전 활동의 끝나는 시간보다 크거나 같으면 선택
        count += 1          # 선택된 활동의 개수 증가
        end = time[i][1]    # 선택된 활동의 끝나는 시간 갱신

print(count)
  • 희의실 데이터를 (끝나는 시간, 시작하는 시간) 기준으로 정렬
    • ✔ sorted(e, key = lambda x : (-x[0], x[1])): 튜플로 그 순서를 보내주면 다중 정렬 가능
  • 회의가 빨리 끝날수록 뒤에 희의를 더 많이 진행할 수 있음