๐ฑ ๋ฐ๋์ฒด ์ค๊ณ
๋ฐฑ์ค 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๋ฅผ ์ป๊ณ ์ ํ ๋] ์ฌ์ฉํ๋ค.
์ด๊ฒ์ ์ ์ฌ์ฉํ๋์ง๋ ์๋ ์งํ๊ณผ์ ์ ์ดํด๋ณด๋ฉด ๋๋ค.
์ด๋ค ์ซ์ 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))