CS/Algorithm

패스트캠퍼스 챌린지 19일차

신웅철 2022. 2. 11. 16:36

[강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다.

 

2월 11일 오늘의 강의

 

자료형 생성

 

kruskal 알고리즘의 첫 번째 단계에서 필요한 자료형으로 딕셔너리를 생성해준다. parent는 독립적인 원소들의 집합으로, 초기화를 해줄 때 그래프의 각 정점들이 입력되고, rank에서는 이 정점들의 높이 값을 0으로 초기화하여 입력시켜준다.

 

 

make_set 함수 생성

 

kruskal에서 그래프의 모든 정점들을 독립적인 원소에 대한 집합과 나눠진 원소들에 대한 rank 값을 초기화한다.

 

 

find 함수 생성

 

find 함수는 path compression 기법을 사용한다. 노드 자신과 부모 노드의 값을 확인한다. 같다면 그대로 노드 자신이자 부모 노드의 값을 반환한다. 다르다면 조건문을 통해 값을 입력한다(하지만 똑같은 값을 입력하는데 왜 입력하는 지는 의문이다.) 해당 값을 통해 반환되어 kruskal 함수에서 for 문 내 조건문을 통해 부모 노드가 다를 경우에 한해서 union 함수를 통해 각 부분 집합을 연결시켜준다.

 

 

uinion 함수 생성

 

 

find 함수를 통해 부모 노드를 확인해서 루트 노드에 값을 할당하고 각 부모 노드의 rank 값을 비교하여 값이 다를 경우 rank가 큰 노드에 작은 노드를 연결하고, 같을 경우에는 하나의 노드에 연결해준 뒤 해당 노드의 rank 값을 증가시켜준다.

 

 

kruskal 함수 생성

 

함수가 실행되면 mst라는 리스트를 생성해준다. 이후 첫 번째 단계에서 초기화를 해주는데 초기화는 그래프에 있는 노드를 빼서 parent와 rank 딕셔너리에 해당 값을 입력해준다.

 

해당 값들을 입력해서 초기화시킨 후, 두 번째 단계에서 탐욕 알고리즘을 기반으로 간선의 가중치 값을 정렬시킨다. 정렬시킨 값들은 리스트 내 튜플 형태로 존재하게 된다.

 

이를 세 번째 단계에서 for문을 통해 간선별로 weight, node_v, node_u에 언패킹해준다. 이의 변수들을 find 함수를 통해 path compression 기법을 적용하여 값을 node_v, node_u와 비교하고 값이 다를 경우에 한해서 union 함수를 통해 root1, root2에 값을 할당하여 union-by-rank 기법을 적용해서 rank 값을 비교한다. 만약 rank 값이 높은 노드가 있을 경우, 낮은 노드의 부모 노드를 rank가 높은 노드로 설정한다. 만약 rank가 같을 경우에는 parent node를 하나의 노드의 높이를 1 증가시키고 증가되지 않은 트리의 부모 노드로 설정한다. 그리고 mst 리스트에 edge 값을 넣어준다.

 

https://bit.ly/37BpXiC

 

패스트캠퍼스 [직장인 실무교육]

fastcampus.co.kr

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.