<div id="readability-page-1" class="page"><div>            
<h2>문제로 이동하기</h2>
<p><a href="https://www.acmicpc.net/problem/11053">https://www.acmicpc.net/problem/11053</a></p>
<h2>접근 방식</h2>
<p>가장 긴 증가하는 부분 수열은 <strong>Longest Increasing Subsequence</strong> 라고도 합니다. 줄여서 LIS라고 하는데요. 대표적인 다이나믹 문제입니다. 이 문제는 1차원 배열로도 풀 수 있습니다. 계단수 문제나 123 더하기 5번 문제처럼 2차원 배열을 사용하지 않아도 되는 이유는 이미 있는 수를 사용하기 때문입니다. 즉, 계단수 문제나 123 더하기 5 문제처럼 마지막에 누가 와야할지 알 수 없는 경우에는 마지막에 올 수를 기록하기 위해 이차원 배열을 사용했지만, LIS의 경우, 어떤 수가 오더라도 해당 수는 수열의 일부이므로 숫자를 알 수 있기 때문입니다. </p>
<h2>점화식</h2>
<p>점화식은 매우 단순합니다.</p>
<pre><code>if i &gt; j &amp;&amp; A[i] &gt; A[j] {
    D[i] = max(D[i], D[j]+1)
} </code></pre>
<p>증가하는 부분 수열이 되기 위해선 먼저 나온 수, 즉 A[j]가 뒤에 나온 수 A[i] 보다 작아야 합니다. 이 조건을 만족할 때 <strong>D[i]는 수열의 i번째 숫자를 마지막으로 하는 LIS의 길이</strong>를 의미합니다.</p>
<h2>코드(Go)</h2>
<pre><code>package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var (
    w  = bufio.NewWriter(os.Stdout)
    sc = bufio.NewScanner(os.Stdin)
)

func init() {
    sc.Split(bufio.ScanWords)
}

func main() {
    defer w.Flush()
    N := scanInt()
    A := make([]int, N+1)
    D := make([]int, N+1)
    for i := range A {
        if i != 0 {
            A[i] = scanInt()
            D[i] = 1
        }
    }
    for i := 1; i &lt;= N; i++ {
        for j := 1; j &lt; i; j++ {
            if A[i] &gt; A[j] {
                D[i] = max(D[i], D[j]+1)
            }
        }
    }
    res := D[0]
    for i := 1; i &lt;= N; i++ {
        if res &lt; D[i] {
            res = D[i]
        }
    }
    fmt.Fprintln(w, res)
}

func max(a, b int) int {
    if a &gt; b {
        return a
    }
    return b
}

func scanInt() int {
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    return n
}</code></pre>
<h2>코드(Python)</h2>
<pre><code>import sys; input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
D = [1 for _ in range(N)]
for i in range(N):
    for j in range(i):
        if A[i] &gt; A[j]:
            D[i] = max(D[i], D[j] + 1)
print(max(D))</code></pre>
<h2>여담</h2>
<p>여담이지만, 다시봐도 Golang의 코드 길이는 정말 레전드네요 ㅋㅋㅋ</p>
<h2>마무리</h2>
<p>여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.</p>
<p>혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊</p>
                        
</div></div>

욱이의 IT 생존일지

Jaewook Oh

[BOJ/11053/Golang&Python] 백준 11053 - 가장 긴 증가하는 부분 수열
문제로 이동하기
https://www.acmicpc.net/problem/11053
접근 방식
가장 긴 증가하는 부분 수열은 Longest Increasing Subsequence 라고도 합니다. 줄여서 LIS라고 하는데요. 대표적인 다이나믹 문제입니다. 이 문제는 1차원 배열로도 풀 수 있습니다. 계단수 문제나 123 더하기 5번 문제처럼 2차원 배열을 사용하지 않아도 되는 이유는 이미 있는 수를 사용하기 때문입니다. 즉, 계단수 문제나 123 더하기 5 문제처럼 마지막에 누가 와야할지 알 수 없는 경우에는 마지막에 올 수를 기록하기 위해 이차원 배열을 사용했지만, LIS의 경우, 어떤 수가 오더라도 해당 수는 수열의 일부이므로 숫자를 알 수 있기 때문입니다. 
점화식
점화식은 매우 단순합니다.
if i > j && A[i] > A[j] {
    D[i] = max(D[i], D[j]+1)
} 
증가하는 부분 수열이 되기 위해선 먼저 나온 수, 즉 A[j]가 뒤에 나온 수 A[i] 보다 작아야 합니다. 이 조건을 만족할 때 D[i]는 수열의 i번째 숫자를 마지막으로 하는 LIS의 길이를 의미합니다.
코드(Go)
package main
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)
var (
    w  = bufio.NewWriter(os.Stdout)
    sc = bufio.NewScanner(os.Stdin)
)
func init() {
    sc.Split(bufio.ScanWords)
}
func main() {
    defer w.Flush()
    N := scanInt()
    A := make([]int, N+1)
    D := make([]int, N+1)
    for i := range A {
        if i != 0 {
            A[i] = scanInt()
            D[i] = 1
        }
    }
    for i := 1; i <= N; i++ {
        for j := 1; j < i; j++ {
            if A[i] > A[j] {
                D[i] = max(D[i], D[j]+1)
            }
        }
    }
    res := D[0]
    for i := 1; i <= N; i++ {
        if res < D[i] {
            res = D[i]
        }
    }
    fmt.Fprintln(w, res)
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func scanInt() int {
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    return n
}
코드(Python)
import sys; input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
D = [1 for _ in range(N)]
for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            D[i] = max(D[i], D[j] + 1)
print(max(D))
여담
여담이지만, 다시봐도 Golang의 코드 길이는 정말 레전드네요 ㅋㅋㅋ
마무리
여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.
혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글 을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다