알고리즘/문제풀이 - 백준

백준 11053 가장 긴 증가하는 부분 수열

문제 : https://www.acmicpc.net/problem/11053 혼자 풀어내지 못한 문제. 이중 for문을 쓰는것 외에는 푸는 방법이 떠오르지 않았는데, 시간복잡도에 중점을 두는 DP문제라서 이중 for문이 쓰이진 않을것 같았고, LIS문제라고 하니 처음 들어보지만 정형화된 알고리즘이 있을것 같아서 오래 고민 안하고 다른 풀이를 봤다. 풀이 LIS문제. 현재수가 이전의 수보다 크면 이전의 수의 길이값을 +1 해준다. 현재수보다 작은 이전의 수가 여러개라면 이전의 수의 길이값들 중 가장 큰것을 선택하고 +1해준다. seq[0] = 0, seq는 입력받은 수, dp는 현재까지 수열의 최대 길이 1 2 3 4 5 6 seq 10 20 10 30 20 50 dp 1 0 0 0 0 0 seq[1] 1..

2019. 7. 8. 17:44