데이터 구조 15 ( graph AOE , Sorting )

AOE Network

 

Active On Edge

• Edge가 Ativity를 의미
• Weighted(=cost) edge
• Vertex = 작업이 완료된 상황

 

분석 )

 

 Critical Path

 = The Longest Path - cost가 가장 큰 path

여기에서 crtical path를 보면

a3 -> a6 -> a8 -> a10 

6 + 7 + 7 + 4 = 21 이다.

 

전체 성능에 영향을 준다는 이유는, 군대 밥먹는 거라고 생각하면 됨. 

마지막 사람이 올 때까지는 출발 못 하듯

8상태가 되기 위해서는 a10와 a11을 지나야 함.

 

 

---

 

 Earliest start time

 = 해당 Activity 가 시작되려면 필요한 시간

=  마지막 주자까지 와야 그게 기록 종료임. 빨리 오는 애들은 영향없음. 

or a8 도로를 거치기 전에 애들 다 픽업해서 출발하는데, 출발하려면 얼마 걸리는지 생각.

• a7을 보자.
  a7 을 시작하기 위해서는 a1과 a4만 지나면 되고, 그에 대한 cost는 5+3 = 8이다.

 

• a8을 생각해보면 vertex 5 의 상태로 되기 위해선
  a2 a5를 거쳐서 다 했다해도 a3 a6이 안 되어있으니 vertex 5 earliest임.
  
  
  
• a11을 생각해보자
  a11을 거치는 방법은 vertex 7을 거쳐서 오는 것 밖에 없다.
  vertex 7 을 거치는 법은 a9밖에 없고. 그러려면 vertex 5를 지나야하는데
  a8=a9 이므로 13+4(a9) 이므로 17

 

 

일 처리한다고 생각하면

[ 빠르면 2와 3한테서 자료를 받았을 때 시작가능! ] 

 + ( 둘 중에 하나라도 못 받으면 늦게 준 애가 줬을 때 시작 가능 )   

" 빠르면 (   ) 뒤에 시작 가능 "

 

---

 

 

Latest start time

= 해당 activity가 시작되어야 하는 가장 늦은 시간

= 해당 edge를 거쳐서 만나는 곳에 오는 애 중에 가장 늦게 오는 애랑 맞춰서 도착한다고 생각

 

a7을 거쳐서 만나는 곳에 가장 늦게 오는 애랑 동시에 만날 계획이라고 생각하면 됨

 

a11만 생각해보자.

a11을 거쳐서 8에 도달하는데, 거기에서 만나러 오는 애 중에 가장 늦게 오는 애는 24 가 걸린다.

그럼 24 뒤에 도착하니까 난 5시간 걸리는 거 감안하면 19에 출발하면 됨

 

weight 가 지하철타고 걸리는 시간이라고 생각하면 편함

" 늦어도 (    ) 뒤에는 시작해야함. " 

 

 

---

 

Sorting (오름차순만)

 

목적 :

1) Search

2) list끼리 비교 검증하기 위해

 

 

 

1. Search 알고리즘

 

int search(element a[] , int k , int n){

int j = 0 

while( ( j < n ) && (a[j].key != k ){

j++;

}

if(j<= n ) {

return -1;

}

return j;  

 

분석 : J<n 이 조건이 false로 반복문을 나오게 되면 if 문으로 들어가서 -1리턴

key값이 일치해서 나오면 그 인덱스 리턴

 

 

2. Binary Search 알고리즘

 

int binary_search(element a[ ], int k, int left, int right){

int middle ; 

while( left <= right ) {

middle = (left+right)/2 ;

if(a[middle].key ==k){

return middle;

}

if (a[middle].key > k)

right = middle -1;

if (a[middle].key < k)

left = middle +1;

}

return -1;

}

 

원리 : 책 100페이지가 있다. << 검색 범위를 반씩 줄일거임

내가 찾아야 하는 게 21 페이지임

첫 기준 : 왼1  중50  오100  ==> key값(21)이 middle 값보다 작음

다음 기준 : 왼1 중25  오49   ==> key값(21)이 middle 값보다 작음

다음 기준 : 왼1 중12  오 24   == > key값 (21)이 middle 값보다 큼

다음 기준 : 왼13 중18 오 24  ==> key값 (21) 이 ""

다음 기준 : 왼19 중21 오 24  ==> key값 (21) 이랑 일치 --> 바로 리턴

 

O(log n)

 

 

 

---

 

 

List Validation

 

위 리스트( sorting x) 
a에 있는 15 에 대해 b리스트에서 전체 한 번을 돌아야함

=  a에 있는 하나의 원소에 대해 b리스트 전체 원소를 돌아봐야한다.

아래는  작은 쪽부터 검색

a 1번째 -> b 1번째 비교

그렇게 하다가 한 쪽의 값이 더 작다?
걔가 새로 들어온 애일 수도 있으니   
작은 애가 있는 리스트에서만 인덱스를 한 칸 뒤로 가서 다시 비교 .

 

 

---

Insertion Sort

 

아래를 반복

1) 현위치보다 앞쪽에 있는 원소들 중 자신보다 큰 값을 자신의 뒤로 보냄

2) 더 이상 앞에 큰 값이 없거나 맨 앞 위치에 도달하면 그 곳에 원소를 넣는다.

 

숫자 = 인덱스 / 노란색에 있는 원소는 정렬했다는 의미임

 

이런 식으로 조금씩 정렬해나간다.

비교대상은 노란색 안에 있는 애들 :  노란색 바로 옆에 있는 애

 

---

앞 뒤 애를 큰 놈 작은 놈을 바꿈

--> 각 사이클마다 제일 큰 값이 제일 뒤로 감