메타 스터디 그룹

[자료구조 목차]

1. 우선순위 큐를 위한 Heap

1) 정의 

- 여러 개의 노드들 가운데서 최대값이나 최소값을 빠른 시간내에 찾아내도록 만들어진 완전 이진 트리 자료 구조

** 이진트리,  우선순위 큐

2) 특징

- 힙 순서 속성 만족, 대부분 이진 힙, O(log n)

2. Heap 의 종류 및 연산

1) Max Heap과 Min Heap

구분	Max Heap	Min Heap
개념도
개념	부모노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전 이진 트리	부모노드의 키 값이 자식노드의 키 값보다 작거나 같은 완전 이진 트리
힙 순서 속성	key(부모노드) ≥ key(자식노드)	key(부모노드) ≤ key(자식노드)

2) Heap의 연산

구분	설명
삽입 연산	1. 최고 깊이, 최우측에 새 노드 추가 2. 삽입 노드와 부모노드 비교 3. 삽입노드보다 부모노드가 작으면 연산 종료, 크면 위치 교환 4. 2번 단계 다시 진행
삭제 연산	1. 최고 깊이, 최우측에 있던 노드를 루트노드로 이동(힙속성 파괴) 2. 옮겨온 노드와 양쪽 자식 비교, 작은쪽 자식과 위치 교환 3. 옮겨온 노드가 더 이상 자식이 없거나 양쪽 자식보다 작은 값인 경우 연산 종료, 아닌 경우 2번 진행

[자료구조 목차]

I.  재귀알고리즘의 개요

가.  재귀알고리즘의 정의

-   수학적 귀납법을 역순으로 이용하여 자신의 함수를 반복적으로 호출하는 알고리즘

수행 과정 중 스스로 호출하는 함수

재귀의 설명 그대로 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식이다.

그렇기에 특정 분기까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용한다.

우리가 흔히 알고 있는 반복문은 for, while 등이 있는데, 이러한 반복문으로 구현가능한 로직은 모두 재귀함수로도 가능하고 그 반대 역시 가능하다.

II. 종료조건

가 종료조건 필요성

종료조건이 없으면 무한 루프 및 Stack Overflow 발생

나. 종료조건

호출이 일어날때마다 재귀 케이스에서 인자 값이 감소

최종적으로 if 문의 조건을 만족시켜 기본 케이스 실행 후 종료

if(함수 호출 멈출 조건) : #기본 케이스

    마지막으로 실행할 명령

else: #재귀 케이스

    재귀함수 호출

III.  재귀알고리즘의 작성절차 및 효율성

가. 재귀알고리즘의 작성절차

나. 재귀 알고리즘의 효율성

-   공간적 비효율(저장공간)

-   시간적 비효율(저장, 복원에 걸리는 시간)

-   가능하다면 반복문으로 대치하는 것이 유리

[자료구조 목차]

개념

• 선택 시 마다 그 순간 최적의 해를 선택하여 최종적인 해를 도출하는 알고리즘
• 최적해를 구하는 목적으로 사용하는 근시안적인 알고리즘 기법

도출 해의 최적에 대한 보장은 불가

그리디 알고리즘의 특징

그리디 알고리즘 수행절차

그리디 알고리즘 적용조건

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않음.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적해로 구성.
• 이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못함 
  -> 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능, 계산 속도 빨라 실용적 사용 가능.
• Matroid 구조에서는 탐욕 알고리즘은 언제나 최적해 구할 수 있음
  * Matroid : 일차독립의 성질을 공리화하여 얻은 조합론적 구조
   매트로이드 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

[자료구조 목차]

1. 다익스트라 알고리즘 개요

1) 다익스트라 알고리즘 정의

• 너비우선탐색(BFS) 기반으로 하나의 시작 정점에서 부터 다른 모든 정점들까지 증가하는 거리의 순으로 최단 경로를 찾는 탐색 알고리즘
• 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘

2) 다익스트라 알고리즘의 특징

• 방향/무방향그래프 관계없이 사용가능
• 가중치가 음수인 edge 가 존재할 경우 사용이 불가함

3) 다익스트라 알고리즘 활용

• 네비게이션의 도시간 최단 거리 탐색
• 미로탐색 알고리즘
• 리우팅(OSPF) 프로토콜
• 공업입지론에서 최소 운송비 지점 구하기
• 루빅스 규브 해법
• A* 알고리즘 : 다이스트라 알고리즘 확장

2. 다익스트라 알고리즘 절차

1) 그래프 탐색과정 

2) 그래프 수행 절차

초기화 : 시작노드를 제외한 모든 노드의 거리정보를 무한대로 설정

시작노드를 기준으로 BFS 탐색으로 이웃 노드의 거리정보를 Update하여 최단거리 노드 탐색 및 방문을 반복적으로 수행

3. 계산 복잡성 및 단점

1) 계산 복잡성

• BFS 적용 미방문노트 탐색 O(V), 한노드당 엣지의 기대값 E / V
• 평균 복잡성 O(V2)  [ O(V2+E) ]

2) 단점 및 해결방법

• 가중치가 음수인 경우 탐색 불가
• 해결방법 양수화(모든 거리에 |음수거리|+한후 적용이 끝나면 절대값 - )

참조: 다익스트라 알고리즘 · ratsgo's blog

[자료구조 목차]

1. 버블 정렬

• 왼쪽끝에서부터 시작해서 인접하는 두 항목의 값을 비교하여 원하는 순서(오름차순 또는 내림차순)로 되어있지 않으면 서로 위치를 교환하는 정렬
• Sorted flag를 이용하여 정렬이 완료되었는지를 판단 -> 교환이 한번도 발생하지 않는다면 정렬이 완료된 것임
• 이웃노드간 비교 if A[i] < A[i+1] -> 비교횟수 O(N^2), 이동횟수 O(N^2), 도중 정렬 완성시 멈출 수 있음 - 최선O(N)

2. 선택 정렬

• 주어진 리스트 중에서 최소값(또는 최대값)을 찾고 그 값을 맨 앞에 위치한 값과 교체함으로써 정렬을 완성하는 알고리즘
• 최소값/최대값(Min/Max) 찾아 교체 -> 비교횟수 O(N^2), 이동횟수 O(N^2)

3. 삽입 정렬

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 데이터를 정렬된 데이터에 삽입해 나가는 방법 -> 비교횟수 O(N^2), 이동횟수(최악 O(N^2), 최선 O(1)-발생 않할때) 

4. 쉘 정렬

• 특정 레코드와 거리가 일정한 레코드끼리 부파일로 나누어 각 부파일을 삽입 정렬하는 방식 - O(N^2)

5. 퀵 정렬

• 입력자료를 Pivot(기준데이터)을 중심으로 작은 값을 갖는 자료들과 큰 값을 갖는 자료들로 분할하여 정렬하며, 분할된 각 부분 리스트에 대해 반복적으로 퀵 정렬을 수행하는 정렬 알고리즘
• 최악 -> 정렬된 입력데이터 O(N^2), 평균: O(N log N), 분할,정복 기법

6. 힙(Heap) 정렬

• 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법 - 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하여 정렬
• 완전이진트리, 힙의 삭제 이용(최대힙 - 내림차순) -> 평균,최악 O(N log N)

7. 합병 정렬

• 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
  정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
  결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
• 두 개 파일 합쳐 한개 파일 만듬. 추가적 메모리 필요, 2배 공간 -> N개 레코드 있을때, 2C(N/2) + N - 1, 평균, 최악 O(N log N)

※ 정렬(sort) 정리

버블정렬?  이웃노드간 비교 if A[i] < A[i+1] -> 비교횟수 O(N^2), 이동횟수 O(N^2), 도중 정렬 완성시 멈출 수 있음 - 최선O(N)

선택정렬? 최소값/최대값(Min/Max) 찾아 교체 -> 비교횟수 O(N^2), 이동횟수 O(N^2)

삽입정렬? 데이터를 정렬된 데이터에 삽입해 나가는 방법 -> 비교횟수 O(N^2), 이동횟수(최악 O(N^2), 최선 O(1)-발생 않할때)  

쉘정렬? 데특정 레코드와 거리가 일정한 레코드끼리 부파일로 나누어 각 부파일을 삽입 정렬하는 방식 - O(N^2)

퀵정렬? Pivot(기준데이터)을 중심으로 작은 값을 갖는 자료들과 큰 값을 갖는 자료들로 분할하여 정렬 - 최악 -> 정렬된 입력데이터 O(N^2), 평균: O(N log N), 분할,정복 기법

힙정렬? 완전이진트리, 힙의 삭제 이용(최대힙 - 내림차순) -> 평균,최악 O(N log N)

2-Way merge? 두 개 파일 합쳐 한개 파일 만듬. 추가적 메모리 필요, 2배 공간 -> N개 레코드 있을때, 2C(N/2) + N - 1, 평균, 최악 O(N log N)

기수 정렬? 공간복잡도 큼, 비교없이 분배 -> O(N)