[TIL] 2024년 7월 24일 오늘의 TIL

08:00 ~ 12:00	알고리즘 풀이
13:00 ~ 18:00	키워드 정리
19:00  ~ 24:00	알고리즘 정리

 

 

 

1. LCS.py

A = input()
B = input()

def get_LCS(sequence_A, sequence_B):
    len_a = len(sequence_A)
    len_b = len(sequence_B)

    # LCS 빈 배열 만들기
    LCS = [[0] * (len_b + 1) for _ in range(len_a + 1)]

    for i in range(1, len_a + 1):
        for j in range(1, len_b + 1):
            if sequence_A[i - 1] == sequence_B[j - 1]: ## sequence Index와 LCS index가 다름 주의
                LCS[i][j] = LCS[i - 1][j - 1] + 1
            else:
                LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

    return LCS[len_a][len_b]

print(get_LCS(A, B))

 

 

2. 01타일.py

# 01타일
# https://www.acmicpc.net/problem/1904

# num = int(input())
# mod = 15746
# def cal_tile(n):
#     cache = [0] * (n+1)
#     cache[1] = 1
#     cache[2] = 2
#
#     if n <= 2:
#         return n
#
#     for i in range(3, n+1):
#         cache[i] = (cache[i-1] + cache[i-2]) % mod
#     return cache[n]
#
# print(cal_tile(num))


### bottom - up 방식 ###
num = int(input())
mod = 15746

def cal_tile(n):
    if n == 1:
        return 1
    if n == 2:
        return 2

    cache = [0] * (n + 1)
    cache[1] = 1
    cache[2] = 2

    for i in range(3, n + 1):
        cache[i] = (cache[i - 1] + cache[i - 2]) % mod

    return cache[n]

print(cal_tile(num))

 

 

 

3. 가장 긴 증가하는 부분 수열.py

import sys
input = sys.stdin.readline

# 수열의 크기
n = int(input())
# 수열을 이루고 있는 원소들
li = list(map(int, input().split()))


# 수열 A의 가장 긴 증가하는 부분 수열의 길이 출력
def find_longest(a):
    if not a:
        return 0

    # 테이블 초기화
    dp = [1] * len(a)

    # Bottom-Up 방식으로 dp 테이블 채우기
    for i in range(1, len(a)):
        for j in range(i):
            if a[i] > a[j]:
                dp[i] = max(dp[i], dp[j] + 1)
                
    # 가장 긴 증가하는 부분 수열의 길이 반환
    return max(dp)


print(find_longest(li))

1. 함수의 정의
2. 점화식 

 

 

 

오늘 코어타임 때 교수님한테 사고하는 방식?을 제대로 배운 것 같다. 그동안 알고리즘 잘 푸는 사람들은 어떻게 생각할까 되게 궁금했었는데 오늘 드디어 알게된 듯하다. 예를 들어 마지막 가장 긴 증가하는 부분수열 문제를 풀 때 함수를 구현한다면 어떤 식으로 구현하는게 맞는지 어떤 값을 받아서 어떻게 돌아갈 것인지. 그리고 왜 그렇게 생각했는지. 만약 반례가 있다면 어떻게 처리할 것인지. 하나하나 뜯어보고 차곡차곡 쌓아서 완성하는 것이다. 그리고 어렴풋이 테이블을 1로 초기화 할거야 ! 했으면 왜 그렇게 했는지. 남에게 설명할 수 있는 근거가 꼮 있어야 한다는 것. (그냥 되니까 이렇게 했는데요.. / 다른 사람 코드 봤떠니 이렇게 하던데요  와 같은 말은 집어치워야한다는 것)  . 암튼 . 

공부는 이렇게 하는 거구나 ~ 많은 것을 깨닫는다. 글로는 설명 못하겠으니 여기서 각설하고 , 하루가 24시간이여서 너무 모자른데 나만 2배 이벤트로 48시간 줬으면 좋겠다. 끝.

오늘 제대로 혼난 사람의 한탄.