๐Ÿ“ฑ ๋ฐ˜๋„์ฒด ์„ค๊ณ„

๋ฐฑ์ค€ Gold2

๋ฐ˜๋„์ฒด ์„ค๊ณ„

๋ฌธ์ œ

๋ฐ˜๋„์ฒด๋ฅผ ์„ค๊ณ„ํ•  ๋•Œ n๊ฐœ์˜ ํฌํŠธ๋ฅผ ๋‹ค๋ฅธ n๊ฐœ์˜ ํฌํŠธ์™€ ์—ฐ๊ฒฐํ•ด์•ผ ํ•  ๋•Œ๊ฐ€ ์žˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด ์™ผ์ชฝ ๊ทธ๋ฆผ์ด n๊ฐœ์˜ ํฌํŠธ์™€ ๋‹ค๋ฅธ n๊ฐœ์˜ ํฌํŠธ๋ฅผ ์–ด๋–ป๊ฒŒ ์—ฐ๊ฒฐํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค. ํ•˜์ง€๋งŒ ์ด์™€ ๊ฐ™์ด ์—ฐ๊ฒฐ์„ ํ•  ๊ฒฝ์šฐ์—๋Š” ์—ฐ๊ฒฐ์„ ์ด ์„œ๋กœ ๊ผฌ์ด๊ธฐ ๋•Œ๋ฌธ์— ์ด์™€ ๊ฐ™์ด ์—ฐ๊ฒฐํ•  ์ˆ˜ ์—†๋‹ค. n๊ฐœ์˜ ํฌํŠธ๊ฐ€ ๋‹ค๋ฅธ n๊ฐœ์˜ ํฌํŠธ์™€ ์–ด๋–ป๊ฒŒ ์—ฐ๊ฒฐ๋˜์–ด์•ผ ํ•˜๋Š”์ง€๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์—ฐ๊ฒฐ์„ ์ด ์„œ๋กœ ๊ผฌ์ด์ง€(๊ฒน์น˜์ง€, ๊ต์ฐจํ•˜์ง€) ์•Š๋„๋ก ํ•˜๋ฉด์„œ ์ตœ๋Œ€ ๋ช‡ ๊ฐœ๊นŒ์ง€ ์—ฐ๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š”์ง€๋ฅผ ์•Œ์•„๋‚ด๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ์ •์ˆ˜ n(1 โ‰ค n โ‰ค 40,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ ์ค„์—๋Š” ์ฐจ๋ก€๋กœ 1๋ฒˆ ํฌํŠธ์™€ ์—ฐ๊ฒฐ๋˜์–ด์•ผ ํ•˜๋Š” ํฌํŠธ ๋ฒˆํ˜ธ, 2๋ฒˆ ํฌํŠธ์™€ ์—ฐ๊ฒฐ๋˜์–ด์•ผ ํ•˜๋Š” ํฌํŠธ ๋ฒˆํ˜ธ, โ€ฆ, n๋ฒˆ ํฌํŠธ์™€ ์—ฐ๊ฒฐ๋˜์–ด์•ผ ํ•˜๋Š” ํฌํŠธ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด ์ˆ˜๋“ค์€ 1 ์ด์ƒ n ์ดํ•˜์ด๋ฉฐ ์„œ๋กœ ๊ฐ™์€ ์ˆ˜๋Š” ์—†๋‹ค๊ณ  ๊ฐ€์ •ํ•˜์ž.

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ์ตœ๋Œ€ ์—ฐ๊ฒฐ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

์˜ˆ์ œ ์ž…๋ ฅ 1

6
4 2 6 3 1 5

์˜ˆ์ œ ์ถœ๋ ฅ 1

3

๐Ÿ“– ์•Œ๊ณ ๋ฆฌ์ฆ˜

LIS ํ’€์ด๋ฒ• 1: DP

์ฒ˜์Œ ์ด ๋ฌธ์ œ๋ฅผ ๋ณด๊ณ  DP๋กœ ๋ฐ”๋กœ ์ ‘๊ทผํ•˜์˜€๋‹ค. ์ „๊นƒ์ค„ ๋ฌธ์ œ, LIS ๋ฌธ์ œ์™€ ๋น„์Šทํ•˜๋‹ค๊ณ  ๋Š๊ผˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

line[i]๋ฅผ i๋ฒˆ์งธ ์›์†Œ๋ฅผ ๋งˆ์ง€๋ง‰์œผ๋กœ ํ•˜๋Š” LIS ๊ธธ์ด๋ผ๊ณ  ์ •์˜ํ•˜์—ฌ ํ’€๋ฉด ๋˜๋Š”๋ฐ ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•˜์˜€๋‹ค.


import sys

input = sys.stdin.readline

n = int(input())
port = list(map(int,input().split()))

# line[i]: i๋ฒˆ ํฌํŠธ์—์„œ ์ตœ๋Œ€๋กœ ์—ฐ๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ์„ ์˜ ๊ฐœ์ˆ˜
line = [1]*(n)

for i in range(n) :
    for j in range(i) :
        if port[i] > port[j] :
            line[i] = max(line[i],line[j]+1)

print(line[n-1])

LIS ํ’€์ด๋ฒ• 2: Lower Bound

๊ฒฐ๊ตญ ์†”๋ฃจ์…˜์„ ์ฐธ์กฐํ–ˆ๊ณ  ๋”์šฑ ์ ์€ ์‹œ๊ฐ„๋ณต์žก๋„๋กœ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์„ ๋ฐฐ์› ๋‹ค.

๐Ÿ‘‰๐Ÿป Lower Bound๋Š” ์ˆซ์ž๋ฅผ [์ •๋ ฌ๋œ ๋ฐฐ์—ด์— ์‚ฝ์ž…์‹œ ์ œ์ผ ์ž‘์€ index๋ฅผ ์–ป๊ณ ์ž ํ•  ๋•Œ] ์‚ฌ์šฉํ•œ๋‹ค.

์ด๊ฒƒ์„ ์™œ ์‚ฌ์šฉํ•˜๋Š”์ง€๋Š” ์•„๋ž˜ ์ง„ํ–‰๊ณผ์ •์„ ์‚ดํŽด๋ณด๋ฉด ๋œ๋‹ค.

แ„‹แ…งแ†ซแ„‰แ…ณแ†ธแ„Œแ…กแ†ผ-3

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2022-07-25 แ„‹แ…ฉแ„Œแ…ฅแ†ซ 4 32 41

์–ด๋–ค ์ˆซ์ž n์„ ๋„ฃ๋Š”๋‹ค๊ณ  ๊ฐ€์ •ํ•ด๋ณด์ž. ๋งŒ์ผ LIS ๋ฐฐ์—ด์ด ๋น„์–ด์žˆ๊ฑฐ๋‚˜ ๋งˆ์ง€๋ง‰ ์›์†Œ๊ฐ€ n๋ณด๋‹ค ์ž‘๋‹ค๋ฉด n์„ LIS ๋ฐฐ์—ด์— ์ถ”๊ฐ€์‹œํ‚จ๋‹ค.

๊ทธ๋Ÿฐ๋ฐ LIS ๋ฐฐ์—ด์˜ ๋งˆ์ง€๋ง‰ ์›์†Œ๊ฐ€ n๊ณผ ๊ฐ™๊ฑฐ๋‚˜ ๋” ํฌ๋‹ค๋ฉด n์„ ์ถ”๊ฐ€ ์‹œ์ผœ์ฃผ๋Š”๋ฐ ์ด ๋•Œ, LIS๋Š” ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ์ด๊ธฐ ๋•Œ๋ฌธ์—

Lower Bound๋ฅผ ์ด์šฉํ•˜์—ฌ ์‚ฝ์ž…ํ•  index๋ฅผ ์ฐพ์•„์ค€๋‹ค.

๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ป CODE

import sys
input = sys.stdin.readline

# ์ดˆ๊ธฐ ์กฐ๊ฑด
n = int(input())
port = list(map(int,input().split()))

# ์ •๋ ฌ๋œ ๋ฐฐ์—ด์—์„œ value๊ฐ€ ์œ„์น˜ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฐ€์žฅ ์ž‘์€ index
def lower_bound(start,end,value,arr):
    while start < end:
        mid = (start+end)//2

        if arr[mid] < value:
            start = mid+1
        else:
            end = mid
    
    return end

lis = []

for i in range(n):
    if i == 0:
        lis.append(port[i])
    else:
        if lis[-1] < port[i]:
            lis.append(port[i])
        else:
            idx = lower_bound(0,len(lis),port[i],lis)
            lis[idx] = port[i]

print(len(lis))

ยฉ 2022. All rights reserved.

Powered by Hydejack v9.1.6