[백준] 11053번: 가장 긴 증가하는 부분 수열

링크:www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

문제접근

이번 문제는 조금 어려웠다... 이 문제는 동적 프로그래밍(Dynamic programming)을 통해서 문제를 풀어야 한다. 간단히 말하면 이전에 구해놓았던 값을 사용해서 그 다음 값을 알아내는 것인데...

예를들어 피보나치 수열의 경우, f(n) = f(n-1) + f(n-1)의 형태를 띈다. 여기서 대부분 재귀를 통해 피보나치를 표현하지만, 피보나치의 f(5)를 구하기 위해서 f(5) = f(4) + f(3) = f(3) + f(2) + f(2) + f(1) = f(2) + f(1) + f(2) + f(1).... 다음 처럼 f(2)같은 수가 계속해서 호출되면서 계산된다. f(5)면 다행인데, f(100)이면 어떨까... 재귀모델은 값의 규모가 커지면 효율적이지 못하다. 따라서 생겨난 것이 동적 계획법, 다이나믹 프로그래밍인데, 이전에 구해놓은 값을 이용해서 다음 값을 구하도록 설계하는 것이다.

동적 프로그래밍에 대한 내용은 나중에 포스팅해야겠다...

 

암튼 문제의 접근은 동적 계획법을 이용해서 푸는건데, 2차원 반복문을 만들어서 풀도록 했다.

---

코드

"""
백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053

증가하는 부분 수열: 동적프로그래밍(Dynamic programming)으로 풀 수 있는 기초적인 문제

참고
https://post.naver.com/viewer/postView.nhn?volumeNo=27105374&memberNo=33264526
https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4
"""
import sys

def calc(n, data):
    # 해당 변수는 data 배열에서 해당 각각의 인덱스까지 중 가장 긴 증가수열의 길이를 담는다.
    # 답을 구해 놓은걸 또 사용하기 위한 변수임
    lenArr = [1 for i in range(n)]
    for i in range(1,n):
        for k in range(i):
            if data[i] > data[k]: #현재 인덱스(i)의 값이 그 이전의 인덱스(k) 값보다 크면
                lenArr[i] = max(lenArr[i],lenArr[k]+1)
                # 인덱스 i까지의 data 배열의 증가하는 수열의 길이는 lenArr[i]와 이전 인덱스(k)에서
                # 가장 긴 증가수열의
                # 길이에서 +1(자기 자신을 추가하면 길이가 +1 되는 것)한 값을 비교하여
                # lenArr[i]에 저장함, 즉 lenArr는 이전까지의 길이를 담고 있는 것
                # 탐색 중에 증가하는 수를 찾았을 때(18 line), 해당 인덱스(k)에서 가장 긴 증가수열을 비교함
    return max(lenArr)



def main():
    n = int(sys.stdin.readline())
    data = sys.stdin.readline().split()
    data = [int(i) for i in data]
    print(calc(n, data))

if __name__ == "__main__":
    main()

주석에 설명한대로 풀었다. calc()함수에 파라미터 data와 같은 길이의 lenArr를 만들어서 모든 요소가 1을 가지게 한다.(초기 설정: 증가하는 수열에서 자기 자신만 포함해 길이가 1이라고 가정한 것) 그리고 0번 인덱스부터 현재 탐색하고자 하는 요소의 인덱스(변수: i)까지 크기를 비교한다. 크기를 비교해서 더 크다면 lenArr에 추가하여 이전까지의 길이를 담아 놓는다. 이를 반복하면서 증가하는 수열의 길이를 갱신하여 마지막 가장 긴 수열의 길이를 리턴하도록 설계하였다.