Q&A 11주차 greedy algorithm

• 실제 삶의 선택은 그리디알고리즘과 비슷하다.
  • 최적의 결과를 보장하진 않지만 충분히 괜찮은 선택이다.
• Activity selection
  • by person이든 by lecture hall이나 관점이 똑같다.
  • finish time을 기준으로 정렬 후에 그담거의 start time와 지금 진행되고있는거의 finish time을 비교하여 후자가 더 작거나 같으면 연속되어 실행할 수 있다!
  • efficient greedy algorithm → 시간복잡도의 minimum을 찾아라
• Fractional Knapsack Problem 부분적인 배낭 문제(배낭에 어떤 것을 넣을 건지 선택)
  • 단가 = value / weight 이므로 단가가 높은 순서로 정렬한 후에 수용력(capacity = 가져올 수 있는 weight의 총합)에따라 가져온다. 만일 마지막 weight를 가져와야하는데 수용력을 초과한다면 비율만큼을 나눠서 해당 비율만큼만 가져온다.

Q&A 정답

1. 1), 2)
2. 2activities, finish time으로 sorting 후에 (왜? 1개의 홀에 activities를 넣어야하는데 끝나는 시간 그 다음의 시작 시간을 알아야하니까)
3. 4activities, start time으로 sorting 후에 계산( 왜? 여러개의 홀에 activities를 넣어야하는데 시작시간 순으로 정렬하고 그 순서에 맞게 강의실을 늘려가며 넣으면 되고, 만일 시작시간이 기존의 홀에 있던 activity의 끝나는 시간보다 크거나 같으면 강의실을 늘리지 않고 넣을 수 있다.
   • 실제 코드로 구성할 때, busy hall / free hall 로 나누어 코드 구현
4. 60 (20 + 30 + 10)
5. O(n)이므로 sorting 안된다! → value/weight = 단가의 비율을 계산하는 것 O(n) → 단가들의 median 값을 구하여 median값을 기준으로 더 큰 sub set과 더 작은 sub set을 구하고 더 큰 subset만 생각하고 더 큰 sub set의 weight를 다 더해준다. 더해준값을 M이라했을 때, 수용력(W)과 비교한다.
   • M>W → 더 큰 sub set에 대해서 한 번 더 해줘야함
   • M<W → 큰 sub set에 대해서 다 더해주고, 작은 sub set에서 조금 더 더해줘야한다. (W-M만큼이 수용력이 된다.)
   • M=W → 정답
   • T(n) = T(n/2) + O(n) ⇒ O(n)

• 5번문제 중요하다고 말씀 → 시험가능성!

1. 60 - 44 = 16
2. weight가 증가하는 방향 + value가 감소하는 방향으로 정렬하면 value / weight 인 단가가 감소하는 방향으로 정렬이 될 것이다. → 단가가 높은 순서대로 고르면 되니까 weight가 lightest한 애들(정렬한 것을 생각해보면 무게가 가벼운 것이 가장 가치있는 것이다.)부터 고르면 된다.
   • 이 방법이 최적의 방법인지 알아내는 법 → 다른 최적의 방법이 어떤 가정을 한 것을 반박을 하며 가정에 오류가 있음을 찾아내면 기존의 방법(이 방법)이 최적의 방법이다!
3. 1. → frequency 순서로 정렬해놓고, 가장 작은 2개의 빈도수들끼리 계속 합침 → 합친 것을 새로 정렬하고 기존의 합쳐진 2개의 빈도수들을 지움 → 결과가 트리 모형처럼 나옴 → 왼쪽 노드를 0,. 오른쪽 노드를 1로 생각하여 암호 해독하면 됨
   • 왼쪽 노드 1, 오른쪽 노드 0으로 생각하여 해독하면 불가능하다 따라서 해보고 안되면 비트를 0→1 1→0으로 스왑!
   • 위와 같이 계산하면 문제에서 A : 00 B : 100 C : 01 D : 11 E : 101
     • 이것을 prefix code라고 한다.

21, 22강 Elementary Graph Algorithms

• 그래프 G = (V,E)

  • V : vertices 정점
  • E : edge or link or arc

• 그래프의 종류

  • Undirected 무방향성(방향성이 없는) : edge (u,v) = (v,u)
    • (v,v) = self loop가 허용되지 x
  • directed 단방향성(방향성이 있는) : edge (u,v) = u → v
    • digraph라고도 부름
    • (v,v) = self loop가 허용됨
  • Weighted : edge에 가중치가 있다.
  • Dense 조밀하다 : |E| ~ |V|^2 둘이 비슷하다.
  • Sparse 널널하다 : |E| << |V|^2
    • 따라서 시간 복잡도는 |E| = O(|V|^2)

• 그래프에 대해 자세하게 알아보자

  • (u,v)는 u와 v가 인접(adjacent)하다는 것을 의미한다.

    • directed의 경우 방향에 따라 인접인지 아닌지 결정됌

  • G가 connected(연결됨) → 모든 정점이 연결되어 있다.

    • |E| ≥ |V| - 1 ⇒ 같다면 G는 트리이다.(일직으로 쭉 연결됨)

  • Eulerian and Hamiltonian Graph

    • Eulerian Graph : 오일러 그래프, 모든 간선을 정확히 한 번씩 돌고 초기 정점으로 돌아오는 그래프
    • Hamiltonian Graph : 해밀턴 그래프, 모든 정을 정확히 한 번씩 돌고 초기 정점으로 돌아오는 그래프

  • Tree and Planar Graph

    • Tree 트리 : 모든 정점이 오직 하나의 엣지에 의해서만 연결되있는 상태 1번
    • Connected graph : 모든 정점이 연결되어 있는 그래프 2번
    • planar graph : 모든 정점이 crossing 없이 연결되어 있는 그래프 3번

    

    • Isomorphic 동형사상

      • 두 그래프가 표현은 다르지만, 구조는 완전히 같은 것을 의미한다.
        • G와 G’이 동형사상이다.

      

• Connected and Strongly Connected

  • connected : 모든 정점이 연결되어 있어서 다른 2개의 digraph로 분리할 수 없다.
  • Strongly Connected : 임의의 정점 u,v 에 대해 u→v 도달가능한 경우를 의미함
    • u→v, v→u로 가는 방법(양방향)도 존재해야 함
    • strongly connected → connected (o) / connected → strongly connected (x)
  • 그래프G에 방향을 부여하여 directed graph를 만들었을 때, 그 그래프가 strongly connected라면 G는 **orientable(방향적)**이라고 한다.

• Adjacency 인접성

  • 정점 v, w이 엣지로 연결되어 있으면 둘은 인접하다(adjacent)고 말하며, 그 연결해주는 엣지와 v, w는 연결(incident)되어있다고 한다.
  • 또한, 엣지 2개가 1개의 정점을 공유하고 있는 경우 엣지 2개는 인접하다고 한다.

• 그래프의 표현

  

  • 인접 리스트, 인접 행렬로 표현가능하다.

  • 인접 행렬

    • A는 정점을 기준으로 작성됨
    • M은 엣지가 열, 정점이 행을 기준으로 작성됨

    

  • 인접 리스트

    • 인접 리스트는 한 정점과 연결된 정점에 대한 정보를 저장해놓은 리스트(가중치저장가능)

    

• Degree 차수

  • 정점 v의 차수는 v에 연결되어있는 엣지의 수를 의미한다. deg(v)로 표시
  • deg = 0인 정점은 고립된 정점, 1인 정점은 끝점(리프노드)
  • the handshaking lemma 악수정리
    • 모든 정점의 차수를 더했을 때**, 2|E|가 나온다.**
      • 엣지 1개 정점 2개가 공유하기 때문에 (두사람이 악수하는 것 생각)
      • 모든 그래프에서 홀수 deg를 가지는 정점의 수는 짝수 → 그래야 짝수가 나옴
    • handshaking dilemma

• 인접 리스트 저장공간 조건

• 인접 행렬

• Graph-Searching Algorithms 탐색 알고리즘