알고리즘(Algorithms)

시간 복잡도(time complexity)

실행 시간은 실행환경에 따라 달라진다.(하드웨어, 운영체제, 언어, 컴파일러 등)

따라서 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트

연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현

데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐

최악의 경우의 시간 복잡도 (worse-case analysis)

평균 시간 복잡도 (average-case analysis)

점근적 분석(Asymptotic analysis)

데이터의 개수 n->inf일 때 수행시간이 증가하는 growth rate로 시간 복잡도를 표현하는 기법

유일한 분석법도 아니고 가장 좋은 분석법도 아니지만, 상대적으로 간단하고 알고리즘의 실행환경에 비의존적이어서 많이 사용됨

가장 자주 실행되는 연산 혹은 문장의 실행횟수를 고려하는 것으로 충분하다.

Ο 표기법은 upper bound를 표현

Ω 표기법은 lower bound를 표현

Θ 표기법은 upper and lower bound를 표현

이진 검색(Binary Search)와 정렬(Sort)

이진 검색

오름차순으로 미리 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 

중앙값을 선택하여 target과 맞는지 비교후

맞으면 끝

중앙값>target이면 중앙값을 새로운 최댓값으로 택한다.

중앙값<target이면 중앙값을 새로운 최솟값으로 택한다.

정렬된 리스트에만 사용할 수 있다는 단점이 있지만 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다 Ο(log_2 (n))

순차 검색과 비교하면 순차 검색은 Ο(n)으로 이진 검색이 훨씬 빠르다.

정렬

버블 정렬 혹은 거품 정렬(bubble sort)

가장 왼쪽(l)과 인접한 오른쪽(r)과 비교후 l>r이면 l<->r

이후 2번째 원소와 3번째 원소를 비교후 같은 방법

한차례 지나고나서 다시 또 한다. (다만 첫포문을 마치고나면 가장 오른쪽엔 가장 큰것이 이미 와있으므로 두번째 포문부터는 n-1까지만 하면된다.)

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

시간 복잡도가 최선/평균/최악=Ο(n)/Ο(n^2)/Ο(n^2)

삽입 정렬(Insertion sort)

index 1의 데이터를 0과 비교해 제자리에 둔다

index 2의 데이터를 0과 1과 비교해 제자리에 둔다.

...

index k의 데이터를 0~k-1까지의 데이터와 비교해 제자리(맞는 자리에) 둔다.

시간 복잡도가 최선/평균/최악=Ο(n)/Ο(n^2)/Ο(n^2)이다.

기타 정렬

퀵소트(quicksort)

합병(merger sort)

힙(heap sort)

등이 있다.

*code review부터 다시보고 정리

순환(Recursion)

순환(재귀함수)이란, 자기 자신을 호출하는 함수(메소드)를 가리킨다.

순환이 무한루프에 빠지지 않기 위한 조건이 있다.

적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. 이것을 base case라 한다. 

recursion을 반복하다보면 결국 base case로 수렴하게 recursive case를 둬야 한다.

가능하면 암시적(implict) 매개변수를 명시적(explicit)매개변수로 표현하라.

예제)(Hello를 n번 출력하는 형태)

public class Code02 { 

public static void main(String [] args) {

int n = 4;

func(n);

}

public static void func(int k) {

if (k<=0)  // base case

return;

else {

System.out.println("Hello");

func(k-1);  //recursive case

}

}

}

예제)(n까지의 합을 출력하는 형태)

public class Code03 {

public static void main(String [] args) {

int result = func(4);

}

public static int func(int n) {

if (n==0)

return 0;

else

return n + func(n-1);

}

}

예제)(실수 x의 n승 구하기)

public static double power(double x, int n) {

if (n==0)

return 1;

else

return x*power(x, n-1);

}

예제(피보나치 수열 구하기)

public int fibonacci(int) {

if (n<2)

return n; // f_0 =0, f_1 =1인 피보나치의 경우

else 

return fibonacci(n-1) + fibonacci(n-2);

}

예제(Euclid algorithm을 이용한 최대공약수 구하는 예제)

public static double gcd(int m, int n) {

if (m<n) {

int tmp = m;

m = n;

n = tmp; // swap m and n(즉 항상 first argument가 더 크거나 같게)

}

if (m%n == 0)

return n;

else 

return gcd(n, m%n);

}

예제(Euclid algorithm을 이용한 최대공약수 구하는 더 간단한 예제)

public static int gcd(int p, int q) {

if ( q==0 )

return p;

else

return gcd(q, p%q);

}

수학함수뿐 아니라 다른 많은 문제들을 순환을 이용하여 해결할 수 있다. 특히 for문, while문을 대신할 수 있다.

순환<->반복문(즉 모든 반복문도 순환으로 만들 수 있다.)

순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.

하지만 함수 호출에 따른 오버해드가 있다.(매개변수 전달, 액티베이션 프레임 생성 등), 즉 순환은 프로그래밍 실행 속도에 단점이 있긴 있다.

예제(문자열의 길이 계산)

public static int length(String str) {

if (str.equals(""))

return 0;

else

return 1 + length(str.substring(1));  // str.substring(1)이란 str의 첫번째 문자를 제거한 substring을 가리킨다.

}

예제(문자열의 출력)

public static void printChars(String str) {

if (str.length() == 0)

return;

else {

System.out.print(str.charAt(0)); // str.charAt(0)란, str의 첫 문자를 리턴하는 메소드이다.

printChars(str.substring(1));

}

}

예제(문자열을 순서를 뒤집어 프린트)

public static void printCharsReverse(String str) {

if (str.length() == 0)

return;

else {

printCharsReverse(str.substring(1));

System.out.print(str.charAt(0));

}

}

(문자열의 출력 예제와 달라진 것은 else내에 출력과 호출의 순서만 바꼈을 뿐이다.)

예제(자연수를 2진수로 변환하여 출력)

public void printInBinary(int n) {

if (n<2)

System.out.print(n);

else {

printInBinary(n/2);

System.out.print(n%2);

}

}

예제(정수 배열(Array)의 합 구하기, data[0]에서 data[n-1]까지의 합)

public static int sum(int n, int [] data) {

if (n<=0)

return 0;

else

return sum(n-1, data) + data[n-1];

}

}

암시적(implicit)매개변수를 명시적(explicit)매개변수로 바꾸어라.

예제(순차 탐색, sequential search)

int search(int [] data, int n, int target) {

for (int i=0; i<n ; i++)

if (data[i]==target)

return i;

return -1;

}

(여기서 n은 명시적인데, search의 시작 인덱스인 0은 암시적 매개변수이다. 하지만 순환을 사용시 시작인덱스도 명시적으로 하자.)

예제(순차 탐색, 매개변수의 명시화)

int search(int [] data, int begin, int end, int target) {

if (begin > end)

return -1;

else if (target==data[begin])

return begin;

else

return search(data, begin+1, end, target);

}

(이렇게 시작 index를 begin으로 명시화하자. search(data, begin, end, target)으로하면 begin index부터 end index까지 target이 있는지 확인)

예제(최대값 찾기)

int findMax(int [] data, int begin, int end) {

if (begin==end)

return data[begin];

else

return Math.max(data[begin], findMaxt(data, begin+1, end));

}

예제(이진 검색, binary search)

public static int binarySearch(String[] items, String target, int begin, int end) {

if (begin>end)

return -1;

else {

int middle = (begin+end)/2;

int compResult = target.compareTo(items[middle]); // string 비교시 자바에서는 compareTo를 사용한다. target이 items[middle]보다 크면 양수, 작으면 음수, 같으면 0을 return한다. //

if (compResult == 0)

return middle;

else if (compResult < 0)

return binarySearch(items, target, begin, middle-1);

else

return binarySearch(items, target, middle+1, end);

}

}

예제(미로찾기)

Recursive한 생각

현재 위치에서 출구까지 가는 경로가 있으려면

1) 현재 위치가 출구이거나 혹은

2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나

예제(미로찾기의 슈도코드1)

boolean findpath(x,y)

if (x,y) is the exit

return true;

else

mark (x,y) as a visited cell; //visited cell개념을 넣지 않으면 무한 루프에 빠질 수 있다.

for each neighbouring cell (x',y') of (x,y) do

if (x',y') is on the pathway and not visited

if findpath(x',y')

return true;

return false;

예제(미로찾기의 슈도코드2)

boolean findpath(x,y)

if (x,y) is either on the wall or a visited cell

return false;

else if (x,y) is the exit

return true;

else

mark (x,y) as a visited cell;

for each neighbouring cell (x',y') of (x,y) do

if findpath(x',y')

return true;

return false;

예제(미로찾기의 실제 자바 코드)

public class Maze {

private static int N=8;

private static int [][] maze = {

{0, 0, 0, 0, 0, 0, 0, 1},

{0, 1, 1, 0, 1, 1, 0, 1},

{0, 0, 0, 1, 0, 0, 0, 1},

{0, 1, 0, 0, 1, 1, 0, 0},

{0, 1, 1, 1, 0, 0, 1, 1},

{0, 1, 0, 0, 0, 1, 0, 1},

{0, 0, 0, 1, 0, 0, 0, 1},

{0, 1, 1, 1, 0, 1, 0, 0},

};

private static final int PATHWAY_COLOUR = 0; // white

private static final int WALL_COLOUR = 1; // blue

private static final int BLOCKED_COLOUR = 2; // red

private static final int PATH_COLOUR = 3; // green

public static boolean findMazePath(int x, int y) {

if (x<0 || y<0 || x>=N || y>=N)

return false;

else if (maze[x][y] != PATHWAY_COLOUR)

return false;

else if (x==N-1 && y==N-1) {

maze[x][y] = PATH_COLOUR;

return true;

}

else {

maze[x][y] = PATH_COLOUR ;

if (findMazePath(x-1,y) || findMazePath(x,y+1) || findMazePath(x+1,y) || findMazePath(x,y-1)) {

return true;

}

maze[x][y] = BLOCKED_COLOUR; // dead end

return false;

}

}

public static void main(String [] args) {

printMaze();

findMazePath(0,0);

printMaze();

}

}

예제(Counting cells in a Blob)

상황:

입력으로 binary image를 받는다. 그리고 하나의 좌표(x,y)도 받는다.

각 픽셀은 background pixel이거나 혹은 image pixel

서로 연결된 image pixel들의 집합을 blob이라고 부름

상하좌우 및 대각방향으로도 연결된 것으로 간주

(x,y)가 image pixel로서 택해졌다면, 그 pixel이 속한 blob의 총 image pixel의 개수를 return하는 문제이다.

(x,y)가 background pixel이면 0을 return

슈도코드:

if (x,y)가 이미지 밖이면 

결과는 0

else if (x,y)가 image pixel이 아니거나 already counted면

결과는 0

else

(x,y)를 다른 색(예를 들면 빨강)으로 색칠하라; // 이미 카운트 됐음을 표시

1+(인접한 영역의 count값);

실제 코드

private static int BACKGROUND_COLOR = 0;

private static int IMAGE_COLOR = 1;

private static int ALREADY_COUNTED = 2;

public int countCells(int x, int y) {

if (x<0 || x>=N || y<0 || y>=N)

return 0;

else if (grid[x][y] != IMAGE_COLOR)

return 0;

else {

grid[x][y] = ALREADY_COUNTED;

return 1 + countCells(x-1, y+1) + countCells(x, y+1)

+ countCells(x+1, y+1) + countCells(x-1, y) 

+ countCells(x+1, y) + countCells(x-1, y-1)

+ countCells(x, y-1) + countCells(x+1, y-1)

}

}

예제(N-queens problems)

상황:

NxN 체스판에 N개의 말을 놓는다. 

이때 각 말은 같은 행, 같은 열, 같은 대각선 상에 놓이지 않게 N개의 말을 놓을 수 있는지?에 대한 대답

Backtracking이용

일련의 선택을 하다가 조건에 부합하지 않게 되면, 그 이전의 선택으로 거슬러 올라가 번복하는 방법

각 행에는 1개의 말만 올 수 있음을 인지하고

0행에서 (0,0)에 말을 놓은 뒤

1행에서 (1,2)에 말을 놓은 뒤..... 쭉 하다가 안된다는 것을 깨달으면 그 이전의 행에서 놓은 말을 이동시킨다.(열을 증가하는 방향으로)

상태공간트리(State Space Tree)이용

뿌리에 Start를 두고

뿌리와 거리가 1인 노드들에는 0행에 놓일 0번 말의 가능한 좌표를 vertex에 표시하여 둔다

뿌리와 거리가 2인 노드들에는 이전 vertex(좌표)에서 1행에 놓일 1번 말의 가능한 좌표를 vertex에 표시하여 둔다.

.... 반복

해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드sequence에 해당한다. 따라서 이 트리를 체계적으로 탐색하면 해를 구할 수 있음

트리를 탐색하는 기법들

깊이 우선 탐색, (이후에 정확한 정의를 파악), 일단 위의 예제에서 backtracking을 상태공간트리에 적용하면 그게 깊이 우선 탐색

실제코드(recursion과 stack을 사용할 수도 있다. 아래는 recursion을 이용한 코드이다.)

int [] cols = new int [N+1]; // 매개변수 level은 현재 노드의 level(트리의 root에서 떨어진 길이)을 표현, cols[i]=j 는 i번째 말이 (i행,j열)에 놓였음을 의미

boolean queens(int level) { // 매개변수는 내가 현재 트리의 어떤 노드에 있는지를 지정, level을 넣음으로써 정확한 위치는 아니지만 몇행인지는 앎

if (!promising(level))

return false;

else if (level==N) { // level이 N인데 promising(level)이 true가 나왔으니까 끝난것

for (int i=1 ; i<=N ; i++)

System.out.println("(" + i + ", " + cols[i] + ")");

return true;

}

for (int i=1 ; i<=N ; i++) {

cols[level+1] = i;

if (queens(level+1))

return true;

}

return false;

}

boolean promising(int level) {

for (int i=1 ; i<level ; i++) {

if (cols[i]==cols[level]) // level번째 말이 이전의 말들과 같은 열에 있는 경우를 검사

return false;

else if (level - i==Math.abs(cols[level] - cols[i]) // level번째 말이 이전의 말들의 영향받는 대각선에 있는 경우를 검사

return false;

}

return true;

}

(실제 사용시 queens(0)으로 호출하면 된다.)

(이해를 하기위해 queens(0)을 생각해보기)

예제(powerset 출력하기)

상황:

주어진 집합의 모든 부분집합을 출력하는 문제

전략:

만약 {a,b,c,d,e,f}라면 

a를 포함하지 않는 부분집합을 나열한 후,

각각의 부분집합마다 a를 포함시켜 나열하면 된다.

(b를 포함하지 않는){c,d,e,f}의 모든 부분집합들에 a를 추가한 집합들을 나열하고

(b를 포함하는){c,d,e,f}의 모든 부분집합에 {a,b}를 추가한 집합들을 나열

....

즉 recursion을 해나간다.

powerSet이란 함수를 설정하는데에 있어서 argument를 집합1개만 받게 설정하면 recursion과정에서 각각의 부분집합마다 포함시켜 나열하는 경우가 해결이 안된다. 

실제 코드:

private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};

private static int n=data.length;

private static boolean [] include = new boolean [n];

public static void powerSet(int k) { // k와 include를 통해 상태공간트리에서 현재 위치를 알려주는 것이다.

if (k==n) { // 상태공간 트리에서 현재위치가 가장 밑인 경우

for (int i=0 ; i<n ; i++)

if (include[i]) System.out.print(data[i] + " "); // P를 출력

System.out.println();

return;

}

include[k]=false; // data[k]를 포함하지 않는 경우

powerSet(k+1);

include[k]=true; // data[k]를 포함하는 경우

powerSet(k+1);

}

(data[k], ..., data[n-1]의 멱집합을 구한 후 각각에 include[i]=true, i=0,...,k-1인 원소를 추가하여 출력하라는 mission)

(처음 이 함수를 호출할 때는 powerSet(0)로 호출한다.)

상태공간트리 활용

해를 찾기 위해 탐색할 필요가 있는 모든 후보들을 포함하는 트리

트리의 모든 노드들을 방문하면 해를 찾을 수 있다.

루트에서 출발하여 체계적으로 모든 노드를 방문하는 절차를 기술한다.

k=0일땐 공집합

k=1일땐 공집합이거나 a만 있거나(k=0일때의 집합에 a를 안넣거나 넣거나)

k=2일땐 k=1에서의 각각의 집합에서 b를 넣거나 안 넣거나를 만듦

k=3일땐 k=2에서의 각각의 집합에서 c를 넣거나 안 넣거나를 만듦

정렬

종류:

Simple하고 slow:Bubble sort, Insertion sort, Selection sort, 

조금 복잡하지만 fast한:Quick sort, Merge sort, Heap sort, 

그 외:Radix sort

기본적인 정렬 algorithm

Selection Sort:

1. 가장 큰 값(M)을 찾는다.

2. 가장 오른쪽 값(R)과 exchange(정렬한다.)

3. 가장 오른쪽 값을 제외하고 1,2를 다시 한다.

시간복잡도 : O(n^2) = 1부터 n-1까지의 합, 최선/평균/최악 모두 정확히 n(n-1)/2이다.

for 루프가 n-1번 반복, 가장 큰 수를 찾기 위한 비교 횟수:n-1, n-2, ..., 2, 1, 그리고 교환은 상수시간

Bubble Sort

1. 첫번째 값과 두번재값과 비교

2. 정렬(교환or유지)한다.

3. 두번째값과 세번째값과 비교

4. 정렬한다.

...반복

결과적으로 가장 큰 값이 가장 오른쪽에 오게 된다.

5. 이후 가장 오른쪽 값을 제외하고 다시 1~4를 한다.

시간복잡도 : O(n^2) = 1부터 n-1까지의 합, 최선/평균/최악 모두 정확히 n(n-1)/2이다.

for 루프가 n-1번 반복, 안쪽 for문이 n-1,n-2,...,1번 반복, 교환은 상수시간 작업

Insertion Sort

1. 첫번째 값에 두번째 값을 끼워 넣는다.

2. 세번째 값을 이전 결과에 끼워 넣는다.

3. 네번째 값을 이전 결과에 끼워 넣는다.

...반복

즉 k-1개가 이미 정렬되어 있고 k번째 item을 끼워넣는 것을 반복하는 것

구체적으로

copy the k번째 item to tmp

k번째 item이랑 k-1번쨰 item이랑 비교, k번째가 k-1번째보다 크면 끝, 작으면 k-1번째 아이템을 오른쪽으로 덮어쓰기(shift), 

그리고 k번째 item이랑 k-2번째 item비교,... 이것을 반복

(만약 k번째 item을 k-1, k-2, k-3,...순으로비교할게 아니라, 1,2,3,...으로 비교한다면 대칭이므로 차이가 없어보이지만, 주어진게 배열이라면, 오른쪽에서부터 비교하는, 즉 k-1,k-2,k-3,...순으로 비교하는게 효율적이다. 왜냐하면 대상이 배열이기때문에 결국 k번째 item을 k-1개의 item들 사이에 끼워넣기 위해선, k번째 item보다 큰 녀석들을 결국 오른쪽으로 옮겨야하고, k번째 item보다 큰 값을 가진애들을 한번씩은 접근을 해야하기 때문이다. 즉 1,2,3,...순은 총 k-1개의 데이터를 결국 다 접근해야하는 것이고, k-1,k-2,k-3,... 순은 접근해야할 개수가 k-1개 전체가 되진 않을 수도 있다. 그래서 k-1,k-2,...순으로 비교하는 것이다.)

시간복잡도 : 최악이 O(n^2) = n(n-1)/2, 최선이 O(n) = n-1, 평균도 O(n^2)

for 루프는 n-1번 반복, i번째 item을삽입(Insertion)하는 최악의 경우 i-1번 비교

Merge Sort

Divide and conquer(본질적으론 recursion과 유사)

분할정복법):예전에 로마 제국이 주변 나라를 정복할 때, 전체를 통채로 정복하기 보다는 작은 것으로 분할하여 정복한 것과 유사함

분할:해결하고자 하는 문제를 작은 크기의 "동일한" 문제들로 분할(recursion할 때와 비슷)

정복:각각의 작은 문제를 순환적으로 해결

합병:작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

     Merge sort    

데이터가 저장된 배열을 절반으로 나눔

각각을 순환적으로 정렬

정렬된 두 개의 배열을 합쳐 전체를 정렬<<<이게 가장 중요, 관건

9개 데이터있는 1개의 배열이 있다면, 절반으로 나누는 과정을 몇번하면 정렬된 9개의 배열을 갖게 된다.

그리고 다시 2개씩 합쳐주며 merge하는 것이다.

Merge를 하는 방법(a1<a2<a3, b1<b2<b3인 경우)

추가 배열을 만든다.

a1과 b1 중 작은 것을 추가배열의 왼쪽에 둔다.(a1<b1이라하자)

a2과 b1 중 작은 것을 추가배열의 왼쪽에 둔다(a2<b1이라하자)

a3와 b1 중 작은 것을 추가배열의 왼쪽에 둔다(b1<a3이라하자)

...이하 반복

(a배열의 index i, b배열의 index j, 추가배열의 index k중 k는 항상 +1, i는 a가 작을때 +1, j는 b가 작을 때 +1)

(sub배열중 1개가 완료되면 나머지 sub배열을 그대로 가져오면된다.)

알고리즘:

mergeSort(A[], p, r) { // 배열 A[]을 index p에서 index r까지 배열

if (p<r) then {

q = (p+q)/2 ; // p, q의 중간 선택

mergeSort(A, p, q); // 전반부 정렬

mergeSort(A, q+1, r); // 후반부 정렬

merge(A, p, q, r); // 합병

}

}

merge(A[], p, q, r) {

정렬되어 있는 두 배열 A[p,...q]와 A[q+1,...,r]을 합하여 정렬된 하나의 배열 A[p,...,r]을 만든다.

}

(merge부분을 실제 자바 코드로 써보면)

void merge(int data[], int p, int q, int r) {

int i = p; // 앞 배열 index

int j = q+1; // 뒤 배열 index

int k =p; // 도움배열의 index

int tmp[data.length()]; // 도움을 줄 추가배열을 만듦

while(i<=q && j<=r) {

if (data[i] <= data[j]) {

tmp[k++] = data[i++];

}

else {

tmp[k++]=data[j++]; // k는 항상 증가, i,j는 비교해서 작을때만 증가

}

}

while ( i <= q)

tmp[k++]=data[i++]; // 남은 것들 추가로 가져오는 과정

while (j <= r)

tmp[k++]=data[j++]; // 이 2개의 while문 중 1개만 사실 실행됨

for (int i = p ; i<=r ; i++)

data[i] =tmp[i] // 원래 데이터에 도움배열 정보를 넣는 과정

}

Merge Sort의 유일한 단점:추가배열을 잡아둬야한다는 것

시간복잡도:

T(n)

=0 (n=1일때)

=T(ceil(n/2)) + T(floor(n/2)) + n (n>=2) // n은 merge하는데 비교연산의 최대횟수가 n, 사실 ceil, floor는 필요없음, n->inf일때 고려하므로

=O(n*logn))

Quick Sort

마찬가지로 Divide and Conquer

다만, divide가 다름

pivot 선택하기

어떤 값을 pivot을 선택할 지는 나중에 배우기

현재 강의 내용에선 배열의 가장 오른쪽 값을 pivot으로 선택

알고리즘 개요

1. "pivot보다 작은 것, pivot, pivot보다 큰 것"으로 분할(분할하면서 좌, 우가 정렬하지는 않음)

2. pivot 기준으로 나뉘어진 좌, 우의 부분들에 다시 recursion으로 분할

3. "합병"단계가 필요가 없다.

알고리즘

quicksort(A[], p, r) { // A[p,...,r]을 정렬한다.

if (p<r) then {

q=partition(A, p, r);

quicksort(A, p, q-1);

quicksort(A, q+1, r);

}

}

partition(A[], p. r) {

x = A[r]; // pivot넣기

i = p-1 // 작은 애들 index

j = p // 큰 애들 index

for j to r-1 {

if A[j]<=x {

i++;

exchange A[i] and A[j];

}

}

exchange A[i+1] and A[r]

return i+1;

(배열 A[p,...,r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고 A[r]이 자리한 위치를 return한다.)

(작/큰/x로 만든 다음, 큰애들 중 가장 왼쪽인 애를 x와 exchange할 것이다.)

(작은 애들 중 마지막 값 index i, 검사하려는 값 index j, A[j]와 pivot과 비교하여 A[j]가 x보다 같거나 크면 그냥 j++(다음꺼 검사), A[j]가 x보다 작으면 A[j]와 A[i+1]과 exchange하고 i++ 그리고 j++(다음꺼 검사))

(제일 마지막에 i+1과 pivot의 exchange, 그리고 i+1을 return)

}

복잡도

partition 한번 하는데 걸리는 시간은 O(n) // 정확히는 n-1번의 비교연산

T(n)

최악의 경우는 아이러니하게, pivot이 가장 큰 값일 때, 즉 이미 정렬된 배열인 경우이다. (pivot을 항상 가장 오른쪽 값을 갖는 상황이라 한다면)

T(n) 

= T(0) + T(n-1) + Θ(n-1) = T(n-1) + Θ(n-1)

= T(n-2) + Θ(n-1) + Θ(n-2)

...

=Θ(1) + Θ(2) + ... + Θ(n-1) 

= Θ(n^2)

항상 절반으로 분할되는 경우(최선의 경우)

T(n)

=2*T(n/2) + Θ(n-1)

...

=Θ(n*logn)

항상 한쪽이 적어도 1/9이상이 되도록 분할된다면(편의상 항상 1:9일때를 고려)

T(n)

= T(n/10) + T(9n/10) + Θ(n-1) 

...

= k * Θ(n) = Θ(n*logn)

(이때 (9/10)^k * n = 1, k=log_(10/9) n )

(따라서 분할이 아주 극단적으로 일어나지 않는다면, Quick Sort는 빠르다.)

평균 시간 복잡도

A(n) = sum over all input I of size n P(I)*T(I), where P(I):I가 일어날 확률, T(I):I의 시간복잡도

P(I)를 구하기가 힘드므로 가정을 한다. P(I)=1/n!이라 가정(즉, 서로 다른 값을 갖는 배열만 고려)

A(n) 

= 2/n * sum from i=0 to i=n-1 {A(i) + Θ(n)} // pivot의 rank가 1,2,.i..,n 일 확률이 각각이 모두 1/n, 그때마다 A(i-1) + A(n-i) + Θ(n)

= Θ(n*logn)

pivot 선택하는 기준

첫번째 값이나 마지막 값을 pivot으로 선택

이미 정렬된 데이터 혹은 거꾸로 정렬된 데이터가 최악의 경우

현실의 데이터는 랜덤하지 않으므로 정렬/거꾸로 정렬 된 데이터가 입력으로 들어올 가능성은 매우 높음

따라서 좋은 방법이라고 할 수 없음

"Median of Three"

첫번째 값과 마지막 값, 그리고 가운데 값 중에서 중간값(median)을 pivot으로 선택

최악의 경우 시간 복잡도가 달라지지는 않음, but 현실적인 방법이긴 함

Randomized Quick Sort

pivot을 랜덤하게 선택

no worst case instance(즉 최악의 입력은 없음), but worst case execution(즉 최악의 실행은 가능함)

(다른 방법들은 최악의 입력이 존재하지만, 이 경우는 최악의 입력이 아니라 최악의 주사위(랜덤)에 의해 최악의 실행이 가능)

평균 시간복잡도 Θ(n*logn)

그래프

개체(object)들 간의 이진관계(binary relation)를 표현하는데 사용한다.

vertex의 개수를 n, edge의 개수를 m

undirected graph, directed graph, weighted graph 등이 있다.

별말없으면 simple undirected graph를 다룬다,

그래프의 표현

undirected simple의 경우

인접행렬(Adjacency Matrix)

저장 공간:Ο(n^2)

어떤 v에 인접한 모든 노드 찾기:Ο(n)

어떤 에지 (u,v)가 존재하는지 검사:Ο(1)

Symmetric Matrix가 된다.

인접리스트(Adjacency List)

V집합을 표현하는 하나의 배열과 각 v마다 인접한 정점들의 연결 리스트

노드개수:2m(edge 하나당 2번세니까)

저장 공간:Ο(n+m)

어떤 노트 v에 인접한 모든 노드 찾기:O(d(v)) // d(v)란 degree of v 라 하자

어떤 에지 (u,v)가 존재하는 지 검사:Ο(d(u)) // u에 해당하는 배열에 있는 리스트를 다 읽어봐야 하므로

directed의 경우

인접행렬

비대칭행렬

인접리스트

m개의 노드를 가짐

weighted의 경우

인접행렬

에지의 존재를 나타내는 값으로 1대신 에지의 가중치를 저장

에지가 없을 때 혹은 대각선

특별히 정해진 규칙은 없으며, 그래프와 가중치가 의미하는 바에 따라서

예:가중치가 거리 혹은 비용을 의미하는 경우라면 에지가 없으면 inf, 대각선은 0

예:가중치가 용량을 의미한다면 에지가 없을 때 0, 대각선은 inf

그래프의 순회(traversal)

모든 v를 방문하는 작업

대표적인 방법

BFS(Breadth-First search, 너비우선순회)

L_0 = {v_0} //출발노드 선택

L_1 = L_0의 모든 이웃 노드들

L_2 = L_1의 이웃들 중에서 L_0에 속하지 않는 노드들

...

L_i = L_(i-1)의 이웃들 중에서 L_(i-2)에 속하지 않는 노드들

(순회 그래프에서의 BFS, 6분40초부터 다시보기)

DFS(Depth-First search, 깊이우선순회)