๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
CS/์•Œ๊ณ ๋ฆฌ์ฆ˜

๋ฐฑ์ค€ 11053 ํŒŒ์ด์ฌ - ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด - ๋™์  ๊ณ„ํš๋ฒ•, LIS

by ๐ŸŒปโ™š 2021. 10. 13.

๋ฐฑ์ค€ 11053 ํŒŒ์ด์ฌ

https://www.acmicpc.net/problem/11053

 

11053๋ฒˆ: ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด

์ˆ˜์—ด A๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ˆ˜์—ด A = {10, 20, 10, 30, 20, 50} ์ธ ๊ฒฝ์šฐ์— ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์€ A = {10, 20, 10, 30, 20, 50} ์ด

www.acmicpc.net

์ด๋ฒˆ ๋ฌธ์ œ๋Š” ์ˆ˜์—ด์˜ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. LIS(Longest Increasing Subsequence)๋ผ๊ณ  ํ•œ๋‹ค.

A๋ผ๋Š” ์ˆ˜์—ด {10, 20, 10, 30, 20, 50}์ด ์žˆ๋‹ค๋ฉด {10, 20, 10, 30, 20, 50}์ด ๊ฐ€์žฅ ๊ธด ๋ถ€๋ถ„ ์ˆ˜์—ด์ด๋‹ค.

 

์ด๋ฒˆ ๋ฌธ์ œ๋Š” ์ง‘ํ•ฉ์—์„œ ํ˜„์žฌ ์œ„์น˜๊นŒ์ง€ ๊ฐ€์žฅ ๊ธด ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ๊ธธ์ด๋ฅผ ๊ธฐ์–ตํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์–ด๋–ป๊ฒŒ ์ €์žฅํ• ์ง€๊ฐ€ ๊ด€๊ฑด์ด๋‹ค. ์ง‘ํ•ฉ์ „์ฒด ์ค‘ ๊ฐ€์žฅ ๊ธด ์ˆ˜์—ด์ด๊ธฐ ๋•Œ๋ฌธ์—... ์ง‘ํ•ฉ์˜ ์œ„์น˜์ค‘ ๊ฐ€์žฅ ๊ธด ๊ฐ’์„ ์ถœ๋ ฅํ•˜๊ฑฐ๋‚˜... ๊ฐ€์žฅ ๊ธด ๊ฐ’์„ ์œ ์ง€ํ•˜๋ฉด์„œ ์ตœ์ข…์ ์œผ๋กœ ๊ฐ’์„ ์ถœ๋ ฅํ•˜๋Š” ๋ฐฉ๋ฒ• ๋‘๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค.

 

 

Python ํ’€์ด 1

ํ•ด๋‹น ํ’€์ด๋Š” ์ง‘ํ•ฉ์˜ ์œ„์น˜๋ณ„๋กœ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ์ €์žฅํ•˜๊ณ  ์ตœ์ข…์ ์œผ๋กœ ์ตœ๋Œ€๊ฐ’์„ ์ถœ๋ ฅํ•˜๋Š” ๋ฐฉ์‹์ด๋‹ค.

import sys
read = sys.stdin.readline

N = int(read())
A = [0] + list(map(int, read().split()))
cache = [0] * (N+1)
cache[1] = 1

for i in range(2, N+1):
    temp = []
    for j in range(1, i):
        if A[j] < A[i]:
            temp.append(cache[j])
    cache[i] = max(temp) + 1 if temp else 1
print(max(cache))
  • ์บ์‹œ์˜ ๊ฐ€์žฅ ์ตœ์ดˆ๊ฐ’์€ ๊ธธ์ด๊ฐ€ 1์ด๊ธฐ ๋•Œ๋ฌธ์— 1๋กœ ์ €์žฅํ•œ๋‹ค.
  • 2๋ถ€ํ„ฐ ์ง‘ํ•ฉ์˜ ๋งˆ์ง€๋ง‰๊นŒ์ง€... ํ˜„์žฌ ๋ณด๋‹ค ์ด์ „ ์œ„์น˜์˜ ์ˆซ์ž๊ฐ€ ์ ์€ ๊ฒฝ์šฐ... ํ•ด๋‹น ์œ„์น˜์—์„œ์˜ ๊ฐ€์žฅ ๊ธด ์ˆ˜์—ด์˜ ๊ธธ์ด ๊ฐ’์„ ๋ฆฌ์ŠคํŠธ์— ์ž„์‹œ๋กœ ์ถ”๊ฐ€ํ•œ๋‹ค.
    • ๋ฉ”๋ชจ์ด์ œ์ด์…˜ ์บ์‹œ๊ฐ’์€ ํ˜„์žฌ ์œ„์น˜๋ณด๋‹ค ์ ์€ ์ˆซ์ž๋ฅผ ๊ฐ–๊ณ  ์žˆ๋Š” ์ „ ์œ„์น˜์˜ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ๊ธธ์ด์— +1ํ•œ ๊ฐ’์ด๋‹ค.

 

 

Python ํ’€์ด 2

ํ’€์ด1์˜ ๊ฒฝ์šฐ ๋งค๋ฒˆ for๋ฌธ์„ 2๊ฐœ ์‚ฌ์šฉํ•˜๋Š”๋ฐ.... ํ•ด๋‹น ์œ„์น˜๊นŒ์ง€ ํ™•์ธํ•ด์ค˜์•ผํ•œ๋‹ค. ๊ทธ๋ž˜์„œ ์ง‘ํ•ฉ์˜ ํฌ๊ธฐ๊ฐ€ ์ปค์งˆ์ˆ˜๋ก ์‹œ๊ฐ„๋„ ์˜ค๋ž˜ ๊ฑธ๋ฆฐ๋‹ค. ์ด๋ฒˆ ํ’€์ด์—์„œ๋„ for๋ฌธ์„ 2๊ฐœ ์‚ฌ์šฉํ•˜์ง€๋งŒ... ์ด์ „ ์œ„์น˜๊ฐ€ ์•„๋‹Œ... ๊ฐ€์žฅ ๊ธด ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ํฌ๊ธฐ๋ฅผ ๊ธฐ์ค€์œผ๋กœํ•˜๋Š” ๋ฆฌ์ŠคํŠธ๋ฅผ ์ƒ์„ฑํ•ด์„œ ์‚ฌ์šฉํ•œ๋‹ค.

import sys
read = sys.stdin.readline

N = int(read())
seq = list(map(int, read().split()))

counts = [seq[0]]
for i in range(1, N):
    if counts[-1] < seq[i]:
        counts.append(seq[i])
    else:
        idx = 0
        for j in range(len(counts)):
            if counts[j] < seq[i]:
                idx += 1
            else:
                counts[idx] = seq[i]
                break
print(len(counts))
  • ์ดˆ๊ธฐ ๊ฐ’์œผ๋กœ ์ฒซ๋ฒˆ ์งธ ์ˆ˜๋ฅผ counts ๋ฆฌ์ŠคํŠธ์— ๋„ฃ์–ด์ค€๋‹ค.
  • ์ฃผ์–ด์ง„ ์ˆ˜์—ด์˜ ์ˆซ์ž๋ฅผ ํ™•์ธํ•˜๋Š”๋ฐ ๋‘๊ฐ€์ง€ ์กฐ๊ฑด์œผ๋กœ ๋ถ„๊ธฐํ•œ๋‹ค.
    • counts ์ˆ˜์—ด์˜ ๋งˆ์ง€๋ง‰ ์ˆซ์ž๋ณด๋‹ค ํฌ๋ฉด ๋ฆฌ์ŠคํŠธ์— ์ถ”๊ฐ€ํ•œ๋‹ค.
    • ๋งˆ์ง€๋ง‰ ์ˆ˜์—ด๋ณด๋‹ค ์ž‘์œผ๋ฉด counts๋ฅผ ์ˆœํšŒํ•˜๋ฉด์„œ ๊ต์ฒดํ•  ์ˆซ์ž๋ฅผ ์ฐพ๋Š”๋‹ค.
      • ์˜ค๋ฆ„์ฐจ์ˆœ์„ ์œ ์ง€ํ•˜๊ณ  ์œ„์น˜๋ฅผ ์ฐพ์œผ๋ฉด ๋” ํฐ ์ˆซ์ž์™€ ์ž๋ฆฌ๋ฅผ ๊ต์ฒดํ•œ๋‹ค.
        • ๋” ๊ธด ์ˆ˜์—ด์„ ์ˆ˜์—ด์ด ๋งŒ๋“ค์–ด ์งˆ ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ํฐ ์ˆซ์ž์™€ ๊ต์ฒดํ•œ๋‹ค.
  • ์ตœ์ข…์ ์œผ๋กœ ๋ฆฌ์ŠคํŠธ์˜ ๊ธธ์ด๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

 

๋ฆฌ์ŠคํŠธ์˜ ์ˆซ์ž๋“ค์„ ๊ณ„์† ๊ต์ฒดํ•ด์ฃผ๋Š” ์ด์œ ๋Š” ๋” ๊ธด ๊ธธ์ด์˜ ์ˆ˜์—ด์ด ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•จ์ด๋‹ค.

A = {7, 8, 9, 1, 2, 3, 4} ๋‹ต์€ 1,2,3,4 ๊ธธ์ด 4 ์ด๋‹ค.

๊ฐ€์žฅ ํฌ๊ณ  ์ž‘์€ ์ˆซ์ž๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋ฌด์–ธ๊ฐ€ ๊ตฌ๋ถ„ํ–ˆ๋‹ค๋ฉด... ์•ž์— 7, 8, 9 ๊นŒ์ง€ ์ถ”๊ฐ€ํ•˜๋‹ค๊ฐ€ ๋’ค์— ์ถ”๊ฐ€ํ•˜์ง€ ๋ชปํ•˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ๋‹ค. ์ด๋ ‡๊ฒŒ ์ˆซ์ž๋ฅผ ์œ„์น˜์— ๋งž๊ฒŒ ๊ต์ฒดํ•ด๊ฐ„๋‹ค๋ฉด ์ค‘๊ฐ„ ์ดํ›„์— ์žˆ๋Š” ๋” ๊ธด ๊ธธ์ด์˜ ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ์žก์•„๋‚ผ ์ˆ˜ ์žˆ๋‹ค.

๋Œ“๊ธ€