기본 콘텐츠로 건너뛰기

개발 공부 - [그래프 알고리즘] 순회 - DAG와 위상순서

 DAG (Directed Acyclic Graph)


유향 비순환 그래프(directed acyclic graph, DAG, 유향 비사이클 그래프), 방향 비순환 그래프(방향 비사이클 그래프, 방향성 비사이클 그래프)는 수학, 컴퓨터 과학 분야의 용어의 하나로서 방향 순환이 없는 무한 유향 그래프이다. 즉, 무한히 수많은 꼭짓점과 간선으로 구성되며 각 간선은 하나의 꼭짓점에서 다른 꼭짓점으로 방향을 잇는데 이처럼 어떠한 꼭짓점 v에서 시작하여 끝내 다시 v로 돌아가 순환 반복되는 일정한 방향의 일련 한 간선을 따라가는 방법이 없다. 다시 말해 DAG는 위상정렬이 있는 유향 그래프이다.

출처: https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%96%A5_%EB%B9%84%EC%88%9C%ED%99%98_%EA%B7%B8%EB%9E%98%ED%94%84


DAG는 방향 사이클(directed cycle)이 없는 방향 그래프

사이클 : 다시 자기 자신으로 돌아오는 경로

예시 : 작업들의 우선순위

예를 들면, 집을 지을 때 기초공사나 기둥세우기, 인테리어 등을 해야한다.

이 때, 기둥을 세우기 전에 인테리어를 할 수 없듯이

다른 것 보다 선행 되어야 하는 것들 표현 하기 위해 DAG가 유용하게 사용된다.

출처: https://new93helloworld.tistory.com/182


위상정렬 (topoligical ordering)

DAG에서 노드들의 순서화 v1, v2, ... vn,

단, 모든 (vi, vj)에 대해서 i<j가 되도록


DAG에서는 우선순위를 표현하기 위해 위상 정렬을 사용한다.

위상 정렬이란, 작업을 실제로 한번에 하나씩 순서대로 처리한다면 

어떤 순서로 작업해야 하느냐를 표현한 것이다.

즉, 작업의 순서대로 노드를 일렬로 정렬하는 것이다.

출처: https://new93helloworld.tistory.com/182


위상정렬 알고리즘 1

topoligicalSort1(G){

    for <- 1 to n{

        진입간선이 없는 임의의 정점 u를 선택한다;

        A[i] <- u;

        정점 u와 u의 진출간선을 모두 제거한다;

    }

    > 배열 A[1...n]에는 정점들이 위상정렬 되어있다

}


수행시간 : O(n+m)


위의 코드는 첫번째 위상 정렬 알고리즘이다.

알고리즘을 보기에 앞서 그래프에 대한 용어를 정리하자.

방향 그래프에서 들어오는 엣지를 Incomming 나가는 엣지를 Outgoing이라고 한다.

또한, 들어오는 엣지의 개수를 Indegree 나가는 엣지의 개수를 Outdegree라고 한다.


첫번째 위상 알고리즘은 간단하고 직관적이다.

첫째로, 모든 노드들에 대해서 indegree가 0인 노드를 찾는다.

indegree가 0라는 것은 해당 작업에 선행해야 할 작업이 없다는 것을 뜻한다.

2개 이상 존재하면 그중 하나를 선택한다.

그 후, 노드 A와 A에서 나가는 엣지를 그래프에서 제거한다.

그리고 다시, 남은 그래프에서 indegree가 0인 노드를 찾는다.

작업이 끝났으면 해당 노드와 해당 노드에서 나가는 엣지를 그래프에서 제거한다.


이와같은 작업을 반복하면 결론적으로 마지막 노드까지 도달할수 있으며

모든 노드가 위상 정렬된다.



= 들어오는 엣지의 개수가 0인 것을 찾아서 (indegree가 0인 것을 찾아서)

걔를 처리하고, (제거하고) 남은 그래프에서 또 indegree가 0인 것을 찾아서 제거하는 구조



위상정렬 알고리즘 2

topoligicalSort1(G){

    for each v∈V

        visited[v] <- NO;

    make an empty linked list R;

    for each v∈V  : 정점의 순서는 상관없음

        if(visited[v] = NO) then

            DFS-TS(v, R)

}


DFS-TS(v, R){

    visited[v] <- YES;

    for each x adjacent to v do

        if(visited[x] == NO) then

            DFS-TS(x,R);

    add v at the front of the linked list R;                                                             

}


DFS-TS(v, R){

    visited[v] <- YES;

    for each x adjacent to v do

        if(visited[x] == NO) then

            DFS-TS(x,R);

    add v at the front of the linked list R;                                                             

}


두번째 위상 정렬 알고리즘이다.

일단, 모든 노드들에 대해서 visited를 NO로 설정해준다.

아직 아무 노드도 출력 되지 않았다는 뜻이다.

그 후에, 하나의 빈 링크드 리스트 R을 만드는데,

노드를 위상 정렬해서 정렬된 순서대로, 연결 리스트로 노드들을 정렬할 것이기 때문이다.

그리고 아직 방문하지 않은 아무 노드 하나를 잡아서 그 노드에서 출발하는 DFS를 실행한다.

DFS는 방문한 노드를 체크하고 그 노드와 인접한 노드 x에 대해 

해당 노드가 방문되지 않았다면 다시 DFS를 실행한다.


그러나 일반적인 DFS와 다른점은 마지막 줄이다.

for 반복문을 빠져 나왔다는 것은 모든 노드를 방문해보고 갈곳이 없을 때 이다.

일반적인 DFS는 뒤로 되돌아 갔으나, 여기서는 링크드 리스트 R에 해당 노드를 추가해준다.


= 알고리즘이 끝나면 연결 리스트 R에는 정점들이 위상정렬된 순서대로 매달려 있다.


댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ * https://joker1209.tistory.co

개발 공부 - json JSONObject 사용 시 백슬래시(\), 원화 표시(\) 제거 및 치환

import org.json.simple.JSONObject; String dataString = new String(authData.toJSONString()); dataString = dataString.replaceAll("\\\\", ""); String 으로 안 바뀌는 가 싶어서 String 으로 변환 해 주고 작업 하였다. 사실 toJSONString 해도 정상 동작 해야 하는데 이유를 잘 모르겠음. 그리고 나서 다시 이클립스 구동 하니 toString 도 먹은 걸로 봐서 이상하다고 생각! String dataString = authData.toString(); dataString = dataString.replaceAll("\\\\", ""); 어쨌든 백 슬래시 제거를 해줘야 하는데 \\ 도 아니고 \\\\를 해야 변환이 가능했다는 결말이었습니다. 참고 : https://stackoverflow.com/questions/15450519/why-does-string-replace-not-work/15450539 test =test.replace("KP", "");  replace 후에 담아 주지 않으면 적용이 안 됩니다!

개발 공부 - OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다.

여러 가지 요인이 있지만 PC 이름 변경시 OracleXETNSListener 서비스 시작이 불가능합니다. 고치는 법은 C:\oraclexe\app\oracle\product\11.2.0\server\network\ADMIN 와 같은 설치 경로에서 listener.ora와 tnsnames.ora 의 pc명을 바꾼 PC명으로 바꿔주면 됩니다. 그래도 안 된다면 cmd 창에서 services.msc 를 입력 후 OracleXETNSListener 서비스를 시작 시키면 됩니다. 오류명: OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다. 일부 서비스는 다른 서비스 또는 프로그램에서 사용되지 않으면 자동으로 중지됩니다. 참고한 사이트들 1. http://blog.naver.com/visioner7/120165951652 2. http://database.sarang.net/?inc=read&aid=6819&criteria=oracle&subcrit=&id=&limit=20&keyword=ora-12560&page=5 이런 걸 보면 오라클은 앙칼진 시골 아가씨야