알고리즘 영상 강의 일목요연 정리하기

New-1 알고리즘 영상강의를 정리한 내용입니다. 많은 도움 되길 바랍니다.

[강좌0]

1. 시간복잡도

2. O 분석 (N은 입력값)

 logN이 제일 좋음, N, NlogN이 다음으로 좋음 

 N 3승이 제일 안좋음

[강좌1. 알고리즘과 기초자료 구조]

1. 알고리즘이란

 * 요건 : 입력, 출력, 명확성, 유한성, 유효성

 * 분석기준 : 정확성, 작업량, 사용공간, 단순성, 최적성

  => 가장 효율적인 알고리즘을 개발, 구현 하여야 한다.

2. 자료구조란

 * 정의 : 데이터와 그들의 관계를 조직화, 구조화 하는 것 (입력, 출력값을 조직화 구조화)

 * 형태 

  1) 선형 : 리스트, 스택, 큐

  2) 비선형 : 트리, 그래프

3. 배열

 * 특성

  1) 같은 종류의 자료의 집합을 담는 가장 일반적인 자료구조

  2) 연속된 메모리 공간 활용

  3) 인덱스로 배열안의 순서와 위치를 나타냄

  4) 인덱스로 자료에 직접 접근 가능

 * 주소계산

 1. 일차원 배열 :   A[0]의 주소가 p 이고 data의 크기가 k byte 일 때 A[i] 의 메모리 주소는 p + k * i

 2. 이차원 배열 : 실제로 메모리에는 일차원 배열로 A[0][0] A[0][1] ~ 이렇게 들어간다. 

     따라서 A[0][0] 의 메모리 주소가 p 이고, 각 data의 크기가 k byte이고,

     A의 열의 수가 m 일 때, A[i][j]의 메모리 주소는 p + k * (i * m + j)

4. (선형)리스트

 * 정의 : 자료들 사이에 순서가 주어진 자료구조

 * 가능한 연산 

   - 특정키 값을 갖는 원소의 탐색

   - 왼쪽부터 순서대로 모든 자료 읽기

   - i 번째 원소 삭제

   - i 번째 위치에 새로운 원소의 삽입

 * 배열을 이용한 리스트 구현

 - 장점 : index를 알 때 직접 자료 접근이 가능

 - 단점 : 중간 삽입, 삭제 시 연속성을 유지하기 위하여 다른 자료들의 위치를 바꿔줘야 한다. 

 * 링크를 이용한 리스트의 구현

 - 배열과 달리 실제 메모리 상에서 자료의 순서가 유지되지 않아도 된다.

 - 기본 단위는 노드로 data와 다음 data를 가리키는 pointer로 이루어짐

 - 탐색 : 탐색 시 인덱스를 이용하여 직접 접근할 수 없다. (처음 자료부터 순차 접근해야함)

 - 삽입 : 신규 노드를 만들고 포인터에 다음 노드를 가리키도록 한다. 그리고 이전 노드의 포인터가 이 신규노드를 가리키게 한다. 

 - 삭제 : 삭제할 앞의 노드를 다음 노드를 가리키도록 포인터 수정하면 됨

 - 장점 : 자료의 삽입, 삭제 시 데이터의 이동이 없음

 - 단점 : 인덱스를 이용하여 자료에 직접 접근할 수 없음, 포인터 만큼의 메모리를 더 사용한다.

[강좌2. 스택1]

1. 스택

 * 정의 : 한쪽 끝에서만 삽입과 삭제가 일어나는 자료구조

             가장 위쪽을 가리키는 포인터를 top 이라함

 * 특징 : LIFO 

 

 * 스택에서의 작업 (operation)

   1) stack* Create() : 동적으로 메모리를 할당하여 빈 스택을 만든다. 

   2) bool Empty(stack *s)

    - 스택 s가 비어 있으면 true, 아니면 false

   3) void Push(stack *s, int item) : item 삽입

   4) int Pop (stack *s) : 맨 위의 값 삭제

 * 스택 오버플로우 : 오류

 * 언더플로우(top = -1) : 오류는 아님, 값이 0개 일때를 말함, 더이상 pop할 수 없음

 * 응용 

  - 배열을 모두 스택에 집어넣고 다시 꺼내면  LIFO이기 때문에 배열의 순서가 반대가 된다.

  - 기차 교차로 : 스택을 통해 내가 원하는 대로 배열의 순서를 만들 수 있는지 

[강좌3. 퀵정렬과 합병정렬]

0. 분할 정복 방식

 1) 분할 스탭

 2) 정복 스탭 (보통 = 를 통해 수행) 

 3) 병합 스탭

1. 퀵정렬 (quick sort)

  * partition 알고리즘 

   - 첫번째 값을 pivot 으로 설정, 두번 째 부터 pivot보다 큰 값을 찾는다. 맨 끝부터 pivot보다 작은 값을 찾는다.

     두 값을 바꿔준다. 교차되면 앞의 값을 pivot 과 바꾼다. 

   - 최종적으로 위치한 pivot 값은 그 위치가 향 후 변하지 않는다. 

     그 왼쪽은 무조건 pivot보다 작은 값이고, 오른쪽은 pivot값보다 큰 값이다. (두개의 파티션으로 나눔)

 * quick sort 알고리즘 (partion 알고리즘을 이용, 재귀적으로 이루어짐)

   1) 분할 스탭 : 배열(1~n)에 partition 알고리즘을 적용

   2) 정복 스탭 :  pivot의 위치가 j일 때 pivot보다 작거나 같은 왼쪽 부분 (1 ~ j-1) 을 quicksort로 정렬

                          pivot 보다 큰 (j + 1 ~n) 를 quicksort로 정렬

 * 분석

  1) 시간 복잡도 

    - 일반적인 경우 : NlogN

    - 최악의 경우 (데이터가 정렬되어 들어오는 경우) : N2 

      => 해결 방법 : pivot 값을 중간값으로 선택, 또는 무작위로 선택 

2. 합병정렬 (merge sort)

 * merging 알고리즘

 1) 배열 p(1~M) q(1~N)이 오름차순으로 정렬되어 있을 때 이 둘을 합쳐 오름차순으로 정렬된 배열 r 생성

 2) p, q 맨 끝에 어마마 큰 값 설정

 3) p의 가장 첫번째 데이터 주소를 i, q의 가장 첫번째 데이터 주소를 j 라고 할 때

    p[i] 와 q[j] 를 비교하여 작은 값을 r에 추가하고 작은 값인 i 또는 j를 증가 시킴

  1) 분할 스탭 : 그냥 둘로 나눔

  2) 정복 스탭 : 각각에 merging 알고리즘 적용

  3) 병합 스탭 : 정렬된 두개를 그냥 합침

 * 분석

  1) 시간복잡도 : NlogN

  2) 공간복잡도 : 2xN

[강좌3. 큐]

1. 큐 

 - 한쪽 끝에서 삽입, 다른 쪽 끝에서 삭제가 일어나는 자료구조 (맨 앞 front, 맨 뒤 reer)

 - FIFO

 * 큐에서의 작업 (operation)

  1) Create() : 빈 큐를 만든다.

   2) bool Empty (queue *q) : 큐 q가 비어있으면 true, 아니면 false

   3) void insert(queue *q, int item) : rear 가 뒤로 이동

   4) int Remove(queue *q)  : front 가 뒤로 이동

 * 큐 오버플로우 : 큐가 꽉 차있을 때, rear = -1

 * 큐 언더플로우 : front > rear

 [강좌4. 힙과 힙정렬]

 * full 바이너리 트리 : 모든 노드에 대해 child 가 2개, 제일 위의 노드를 root 노드 (level0, 개수 : 2의 0승)

  - level k 에는 2 (k+1)승 -1

  - N개의 노드는 log2N 레벨에 있음

 * complete 바이너리 트리 : 노드의 오른쪽 일부분이 없음

 * 힙

 - 완전 이진 트리 (complete 바이너리 트리) 

 - Max heap : 부모 노드의 값이 자식 노드의 값보다 크거나 같다. (따라서 이 경우 root 값이 가장 크다)

 - Min heap : 위와 반대

 - 실질적으로는 root부터 차례대로 배열에 넣을 수 있다. 

 - i번 노드의 왼쪽 자식 노드는 i * 2 이고 오른쪽 자식 노드는 i * 2 + 1 

 - i 번 노드의 부모노드는 [ i / 2 ]

 * 힙에서의 연산 (삽입, 삭제만 가능)

 1) 삽입

   - Max 힙에 A 삽입하는 연산

    (1) 힙의 마지막 다음 자리에 A 추가

    (2) A를 부모 노드와 비교하여 A가 더 크면 둘의 자리를 바꿈

    (3) 2의 작업을 A가 부모 노드보다 작거나 루트가 될 때까지 반복

     => Max heap은 삽입 후에도 Max heap임

 2) 삭제

  - Max 힙에서 루트를 삭제하는 연산 (루트만 가능)

   (1) 루트를 삭제하고 힙의 마지막 자리에 있는 B를 루트에 넣는다.

   (2) B의 왼쪽 자식 노드와 오른쪽 자식 도드의 값 중 더 큰 값을  B 와 비교하여 B가 작다면 자리를 바꾼다.

   (3) 2를 반복하여 B가 더 크거나 B의 자식노드가 없을 때까지 반복

     => Max heap은 삽입 후에도 Max heap임 

 * 알고리즘

  1) 배열 데이터를 모두 heap에 삽입

  2) 힙에서 데이터를 하나씩 삭제 후 꺼내면서 새로운 배열의 마지막 자리부터 차례로 넣는다.

       Max heap은 오름차순 정렬이 된다.

  * 프로그램

    Heapsort()

   {

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

            insertHeap(a[i]);

        for (i=N; i>=1; i--)

           a[i] = removeHeap();

   }

 * 힙정렬 분석

   1) 시간복잡도 

     - 삽입 시 :  logN => height 가 logN 이므로 (루트까지 가도 logN번 수행)

     - 삭제 시 : logN

     - 삽입 삭제로 힙정렬 시  : 삽입, 삭제가 N번씩 이뤄짐. 힙을 구성하는데 NlogN, 정렬하는데 NlogN이 걸린다.

* downheap 작업(operation)

  - 흐트러진 complete 바이너리 트리를 heap 으로 만드는 방법

  - 부모노드와 자식노드 중 큰 값과 비교하여 자식노드가 크면 그 자식노드와 부모노드의 자리를 바꾸는 것

* downheap 작업을 통한 heap 구성

 - 자식노드가 있는 마지막 노드 부터 시작하여 거꾸로 루트에 이르기 까지 downHeap 작업을 한다.

   (데이터의 수가 N개라면 [N/2]번째 노드부터 자식노드가 있다.)

  - O(N) 의 시간복잡도 임

  - 이를 통한 heap 정렬은 총 NlogN이 걸린다.

[강좌4, 8. 그래프 알고리즘]

* 용어 : 정점(vertext), 간선(edge) 

  자가루프

  완전그래프

  부 그래프

  인접하다. (방향 그래프에서는 v 는 w와 인접한다 w는 v로 부터 인접한다.)

  차수 : 정점과 인접한 정점의 수

 방향그래프의 경우 : 내향 차수, 외향 차수

정점 수 : n, 간선 수 : m 일 때

 인접행렬 (o(n2)) => 정점이 많고 간선이 적으면 불리

 인접리스트 (o(n+m)) => 간선 수가 적을 때 유리, 완전그래프와 같이 정점 수에 비해 간선 수가 많으면 불리

 깊이우선탐색 (스택사용), 너비우선탐색(큐사용)

* 스패닝 트리 : 연결된 비방향성, 그래프 G에서 순환경로를 제거하면서 연결된 부분 그래프가 되도록 이음선을 제거하면 스패닝 트리가 됨

                       따라서 스패닝 트리는 G안의 모든 정점을 모두 포함하면서 트리가 되는 연결된 부분 그래프 이다.

* 최소 스패닝 트리 : 가중치의 합을 최소로 한 스패닝 트리

* 응용 : 통신 네트웍의 최소 비용 설계

* prim 알고리즘 ( O(N2) )

 1. 그래프 G에서 한 정점 선택

 2. 각 반복과정마다 구성된 최소 스패닝 트리에 새로운 정점, 에지 첨가

 3. 알고리즘 진행동안 G의 각 정점들은 다음 범주로 나눔

  1) 트리 정점 : 현재까지 구성된 트리 내의 정점

  2) 인접 정점 : 트리 내의 정점과 인접한 트리 밖의 정점

  3) 그 외 정점 : 나머지 정점

4. 인접 정점으로부터 정점을 선택하여 트리에 포함시키는 것이 핵심 (최소 가중치를 갖는 에지)

 => greedy 방법의 한 예시임

* 크루 스카너 알고리즘 (NlogN) => 정점 수에 비해 간선이 많은 경우

 - 사이클이 생성되지 않도록 최소 에지들을 추가 (사이클 생성 여부는 유니언 파인드로 파악)

* 최단 경로와 도달 가능 행렬

 => 단순하게 최소 스패닝 트리로는 해결이 안됨

 => dijkstra 최단 경로 알고리즘 (O(N2))

 최소 가중치의 에지를 선택하지 않고, (트리 내 정점 까지의 거리 + 인접 에지의 가중치) 가 최소인 에지 선택

[강좌4. 스텍2]

* 후위 표기법 

 - 중위 표기식은 컴퓨터가 이해하기 어려움

 - 후위 표기식은 괄호가 필요 없음

* 스택을 이용한 후위 표기식 계산 알고리즘

 - 피연산자가 나오면 스택에 넣는다.

 - 연산자가 나오면 스택에서 두개의 피연산자를 꺼내 계산한 뒤 그 결과값을 다시 스택에 넣는다.

* 후위표기식으로 변환하는 방법 (스택을 이용하여 중위 표기식을 후위표기식으로 변환하는 알고리즘)

 - 결과배열, 연산자 우선순위

[강좌5. 기본정렬]

 1. 선택정렬 (selection sort) : 전체 수중 가장 작은 수를 파악하여 차례대로 배열에 삽입

 - 시간복잡도 : 원소가 n개 일 때 안쪽 for 루프의 반복횟수는 (n-1) + (n-2) ~ 1 = n(n-1) / 2

                       교환횟수는 n-1

 2. 버블정렬 (bubble sort) :  양 옆 원소를 비교하여 자리를 바꿈. 더 이상 바꿀게 없으면 소트 작업을 끝낸다.

 - 시간복잡도 : 최악의 경우(역순으로 소팅되어 있을 때) : for 루프 수행횟수가 n2 / 2

3. 삽입 정렬 (insert sort) : n2

더 효율적인 정렬 방식은? n2 이 아닌 nlogn 의 정렬

어떻게 효율적인 정렬이 존재하는가? => 2>5>7 인 경우 2, 7은 비교할 필요가 없다.

=> 퀵소트, 합병소트

o(n) 도 가능하다. => 제약이 있다. 1. 공간복잡도 커짐, 2. 미리 자료의 크기와 값을 알 수 있어야 한다.