이모저모

선택 정렬구간 내에서 최솟값을 들어가야 할 위치와 현재 최솟값의 위치를 바꿔 주면서 차곡 차곡 최솟값을 하나씩 1....n까지 채워가는 형태

버블 정렬오름차순 정렬이라면현재 범위에서 최댓값을 범위의 끝에 위치하도록 하는 방법1번 가장 큰 값이 n번째 위치로 이동2번 두번째로 큰 값이 n-1번째 위치로 이동.....O(N^2)의 시간복잡도를 가진다. 소스코드for(int i=1; i

삽입 정렬현재 조사해야할 위치가 k라면 1~k-1까지 정렬된 상태에서k의 위치를 찾아 1~k를 정렬된 상태로 만들어최종적으로 전체 원소를 정렬하는 방식만약 k의 위치가 들어갈 자리가 x라면1, 2, 3,..... k-1 k 를1, 2, ... x, x+1, .... k 형태로 만들어 줘야 하므로x+1, k-1 까지를 한 칸씩 땡기고 x자리에 k번째 원소를 집어 넣는 구조로 진행된다. 소스코드for(int i=2,j,tmp; i=1; j--){if(data[j] > tmp){data[j+1] = data[j];}}data[j+1] = tmp;}

Knapsack Problem 은 크게 4가지 먼저 입력으로는 i, vi, wi, mi : i번째 물체의 무게는 wi이고, 가치는 vi이고, 갯수는 mi라는 뜻이다.1. Fractional Knapsack Problem물체를 쪼개는 경우해법 : sort 후 greedy하게 풀이시간복잡도 : O(NlogN)공간복잡도 : O(N) 2. 0-1 Knapsack Problem물체가 1개 인 경우loop W->0dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi)시간복잡도 : O(NW)공간복잡도 : O(W) 3. Unbounded Knapsack Problem물체가 무한대의 갯수 만큼 있는 경우loop 0->Wdp[w] = (for all i) max(dp[w-wi]+vi)시간복잡도..

문제)1 3 4 2 8 7 -1 3 5 ....n개의 숫자가 주어지고, 윈도우 크기 l이 주어졌을 때A(i-l+1) ~ A(i) 범위 내의 최소값 혹은 최댓값을 구하여라 다음과 같은 문제가 주어졌을 때 무식하게 풀면 O(NL)의 복잡도를 가진다. 우리가 생각할 알고리즘은 슬라이딩 윈도우 알고리즘이다. 위의 문제에 대해서 optimal 한 알고리즘이며, 복잡도는 O(N)이 된다. 슬라이딩 윈도우 알고리즘기존의 계산했던것을 최대한 활용하여 다음것을 빠르게 구할 수 있도록 하는 방법이다.문제에 따라서 공간적, 시간적 두가지 방법으로 접근하여 사용할 수 있다. 위의 문제를 생각해 보면N을 2L-1크기로 나누어 보자.A(1) A(2) ... A(L-1) A(L) A(L+1) ... A(2L-1)M(1,L) M(2..