Julie의 개발 기록

문제 링크 : https://www.acmicpc.net/problem/12015 LIS는 최장 증가 부분 수열을 의미한다. 주어진 수열에서 숫자를 몇개 빼서 가장 긴 증가 수열을 만드는 것이 규칙이다. [0, 1, 2, 0, 5, 4]에 대해서 LIS를 찾는다고 하면, [0, 1, 2, 5] 또는 [0, 1, 2, 4]가 답이다. 부분 수열이 인덱스 i에서 끝날 때의 LIS 수열의 길이를 lis[i]라고 할 때, lis[i]에 대한 점화식을 적용하면 O(N^2) 해법을 쉽게 떠올릴 수 있다.def dp(arr): N = len(arr) lis = [1] * N for i in range(N): # 0부터 i까지 구간에서 부분수열의 최대 길이를 구한다. for k in ran..

문은영 교수님의 데이터구조 수업 자료입니다. 문제시 삭제하겠습니다. 방식 i가 0 ~ n-1 일 때, 왼쪽 카드가 지금 카드보다 크다면 교환한다. 그렇지 않다면 다음 iteration으로 넘어간다. 이 작업을 index i부터 1까지 매 iteration에서 반복한다. 일부 항목만 정렬이 흐트러졌을 때 사용하면 유리한데, 1. 배열이 이미 정렬되었을 경우 linear time으로 동작하고 2. 구현이 쉽기 때문이다. 시간복잡도 Avg - O(n^2) iteration i에서 벌어지는 swap과 비교 횟수의 평균은 각각 i/2회이다. 시간복잡도를 big-O natation으로 표현하면 O(T(n)) = O(n(n-1)/4) = O(n^2) 이다. Best - O(n) 배열이 이미 정렬되었을 때 각 iter..

문은영 교수님의 데이터구조 수업 자료입니다. 문제시 삭제하겠습니다. 방식 i번째(0부터 시작) iteration에서 0 ~ i-1 까지는 정렬되어있음이 보장된다. 이때 i ~ n 까지의 entry 중에 가장 작은 값을 a[i]와 교환한다. 구현할 때 entry 범위가 헷갈릴 수 있다. arr[0]에 가장 작은 값이 들어가는 것이 보장되어야함을 기억하면 덜 헷갈린다. 시간 복잡도 Avg - O(n^2) ith iteration에서 n-i 개의 entry 중 가장 작은 값을 찾는데에는 평균 (n-i)/2 의 비용이 든다. i가 1부터 n까지 이므로 평균 시간복잡도는 T(n) = (탐색) + (교환) = ( 0+…+n-1 ) / 2 + ( 1 * n )이고 O(T(n)) = O(n^2) 이다. Best - O..