πŸ™ˆ 동적 κ³„νšλ²•

may_soouuΒ·2020λ…„ 12μ›” 31일
0
post-thumbnail

2020λ…„ μ˜¬ν•΄μ˜ λ§ˆμ§€λ§‰ λΈ”λ‘œκ·Έλ₯Ό μž‘μ„±ν•˜κ² μŠ΅λ‹ˆλ‹€.

동적 κ³„νšλ²•μ΄λž€?

λ³΅μž‘ν•œ 문제λ₯Ό μž¬κ·€λ₯Ό 톡해 κ°„λ‹¨ν•œ ν•˜μœ„ 문제둜 λΆ„λ₯˜ 및 λ‹¨μˆœν™”ν•˜μ—¬ ν•΄κ²°ν•˜λŠ” 방법
졜적 λΆ€λΆ„ ꡬ쑰 / μ€‘λ³΅λ˜λŠ” λΆ€λΆ„ λ¬Έμ œκ°€ μžˆλ‹€λ©΄ 동적 κ³„νšλ²•μ„ μ‚¬μš©ν•˜λ©΄ μ’‹μŠ΅λ‹ˆλ‹€.
μ΅œμ λΆ€λΆ„κ΅¬μ‘° : 닡을 κ΅¬ν•˜κΈ° μœ„ν•΄ ν–ˆλ˜ 계산을 λ°˜λ³΅ν•΄μ•Όν•˜λŠ” ꡬ쑰

졜μž₯ 증가 λΆ€λΆ„μ—΄ μ°ΎκΈ°

1. λ™μ κ³„νšλ²•

from bisect import bisect
from itertools import combinations
from functools import wraps

def solution(seq):
    L = [1] * len(seq)
    res = []
    for cur, val in enumerate(seq):
        for i in range(cur):
            if seq[i] <= val:
                L[cur] = max(L[cur], 1 + L[pre])
    return max(L)
profile
back-end 개발자

0개의 λŒ“κΈ€