[Algorithm] 개념 1

 

• 순차검색

 

2. 분할정복

• 이분검색
• 합병정렬 : 다 하나짜리로 쪼개고 하나씩 합치며 정렬
• QuickSort 빠른정렬. 분할 교환 정렬 : 기준값(pivot, 보통 맨 첫번째 값)을 정함. 남은 것들 양쪽ij인덱스로 좁히면서 기준값보다 큰거<->작은거 자리바꾸고 마지막에 j랑 기준값이랑 자리바꿈

 

3. Greedy 알고리즘

• 순서 
  1. 선정 selection
  2. 적정성 점검 feasibility check : 조건에 만족하는가
  3. 해답 점검 solution check : 최적의 해인가 - 증명은 어려워도 반례가 없는지 마지막에 확인해보는 절차 권장
• Fractional Knapsack problem : 단위무게당 profit이 큰 것 부터 넣는 것이 최적
• 0-1 Knapsack problem
• Two-way Optimal Merge Patterns : 다양한 수의 데이터를 담은 파일을 원소로 갖는 두 개의 정렬된 파일 배열을 정렬된 하나의 배열로 합병 시 비교 횟수 최소로 하기 (파일이 갖고 있는 데이터 수에 따라 비교횟수 카운트됨)
  • Greedy방법으로 현재 존재하는 파일들 중 데이터 수가 가장 적은 두 파일을 선택해 하나로 합병하고 다시 정렬한 후 두 파일 선택을 반복.
  • 선택과정을 뒤집어 그리면 트리모양. 
  • 트리모양의 간선개수와 가장 끝에 있는 leaf노드값(파일의 데이터수)들을 이용해 총 비교 횟수 계산 가능.
• Huffman Code : 암호화 방법. prefix code. 집합의 어떤 원소도 다른 원소의 시작부분(prefix)이 아님. 각 원소는 한 글자를 의미하고 그런 원소들을 연속으로 나열하여 암호화 함.
  • 글자에 해당하는 이진수 마지막 부분까지 읽어야 확실히 어떤 글자인지 알 수 있음.
  • 문자 종류가 n개인 문자열을 암호화하려면 2^n개 이상 자리수digit의 이진수까지를 사용해야 함
  • greedy알고리즘으로 암호화 가능 (문자 사용 빈도 고려해여 효율적으로.)
    • 빈도로 two-way optimal merge를 뒤집은 tree를 그린 다음 한쪽방향 엣지는 0, 다른쪽 방향 엣지는 1로 생각해 leaf노드까지 내려가면 그 leaf노드에 해당하는 빈도값의 문자를 의미하는 이진수 코드가 된다.
    • root노드의 빈도수가 100이라면 코드 메세지가 100일 경우 메세지의 평균 길이는 총 비교횟수 계산 결과와 같다. (빈도*코드길이 들의 합이므로)
• Spanning Tree (신장트리) : 방향성과 cycle이 없는 연결그래프 (비방향, 비순환)
• Minimum Spanning Tree (최소비용 신장트리) : 엣지마다 가중치가 있는 순환 연결그래프가 주어졌을 때, 비용이 최소인 Spaning Tree 
  • 주어진 Spanning Tree로부터 Minimum Spanning Tree를 구하는 조건 : 모든 노드 포함. 사이클없음. 모두 연결.
  • 구하는 방법 - Greedy로. Feasibility check 조건은 cycle이 없는가.(두 방법 모두 선택 시 cycle을 생성하는 것은 선택하지 않고 버림)
    • Prim's : 현재 선택되어있는 정점들에 연결된 엣지들 중 가중치가 가장 적은 엣지를 선택. 그 엣지로 이어지는 정점을 선택(이 때 선택 시 cycle이 생기면 선택 안함). 반복
    • Kruskal's : 엣지를 가중치로 정렬함. 정렬된 엣지를 앞에서부터(가중치가 작은 엣지부터) 선택(선택 시 cycle이 생기면 선택 안함).
    • 엣지가 많으면(densd) Prim's가, 적으면(sparse) Kruskal's가 효율적임.
• Single Source Shortest path (단일경로 최단거리) 문제 : 최단 경로 구하기
  • Dijkstra's (다익스트라) 알고리즘 - 시작노드로부터 다른 모든 노드 각각으로 가는 최단경로를 구함. 전체 고려x
    1. 모든 노드v들의 dist(v)를 설정(시작노드와 연결 안되어있으면 무한대로 설정)
    2. 시작노드 방문하고 V_f에 추가
    3. 방문한 노드집합 V_f 이 전체 노드 집합V와 같으면 알고리즘 완료
    4. 방문 전 노드들의 dist최소값 업데이트
    5. dist가 가장 작은 노드를 방문하고 V_f에 추가
    6. V_f=V체크 - dist업데이트 - 노드방문 반복
  • Prim's는 전체 비용 총합을 최소로 하는데에 적합 / Dijkstra's는 시작부터 목표들 각각까지 비용 최소에 적합.