패스트캠퍼스 챌린지 20일차 - 보충 학습

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

 

Prem's Algorithm 상세 구현

 

Prem's Algorithm 코드 구현

 

prem 함수에 인수 입력

 

 

Prem's Algorithm을 구현한 함수와 인수이다. 시간 복잡도는 최악의 경우로, while 구문에서 모든 간선에 대해 반복하고, 최소 힙 구조를 사용하기 때문에 O(E logE)의 시간 복잡도를 가진다. 코드별로 자세히 알아보자.

 

 

 

prim 함수의 매개변수는 start_node와 edges다. 인수로 전달받을 땐 start_node는 string 값이며 edges는 list 형태로 전달받게 된다.

 

이때 변수 2개가 선언되어지는데 이 중 첫번째 mst는 Minimum Spanning Tree의 약자로 prim 함수를 통해 출력될 값이다. 먼저 변수 mst를 list로 선언해준다. 그리고 adjacent_edges는 특정 정점과, 이에 연결되어있는 정점 및 간선들을 나타낸 딕셔너리다. 이는 collections 라이브러리의 defaultdict 함수를 통해 인자의 기본값을 딕셔너리의 초깃값으로 지정해준다.

 

 

 

매개변수 edges를 통해 인수를 전달받으면 for 문을 통해 인수의 weight와 n1, n2를 추출하게 된다.

이때 n1과 n2는 adjacent_edges의 키로 사용되고, 각 키에 튜플로 weght와 n1(2), n2(1)을 추가해준다.

 

 

 

그리고 connected_nodes 변수를 선언하고, 이에 start_node를 통해 전달받어 set 자료형을 할당 및 초기화한다. 이러한 connect_nodes는 최소 신장 트리를 확장시켜나갈 때 조건을 비교하는 변수로 사용되어진다.

 

그리고 candidate_edge_list 변수도 선언해준다. 이를 통해 특정 정점을 시작으로 정점을 연결해나가면서 요소를 최신화시키고 가중치가 최솟값인 요소를 추출하며 조건에 따라 최소 신장 트리에 삽입할 수 있다. 여기선 adjacent_edges에서 키(start_node)에 해당하는 밸류를 가져오기 때문에 리스트 자료형이 할당된다. heapify 함수를 통해 candidate_edge_list를 리스트 자료구조에서 힙 자료구조로 변환시킨다.

 

 

 

다음은 while 문이다. while문은 candidate_edge_list의 요소가 존재하는 동안 계속 반복된다. heappop을 통해 candidate_edge_list의 첫 번째 요소가 추출되는데 heap의 특성으로 최솟값이 먼저 추출되어진다. 요소는 튜플로 구성되어 있기 때문에 최솟값은 튜플의 최솟값을 우선으로 추출한다. 여기서 최솟값은 weight가 5인 튜플이 추출된다.

 

추출되어진 값은 weight, n1, n2의 변수에 언패킹되고 이는 if 문에서 사용되어진다. if 문에는 특정 정점과 연결되어있는 정점이 connected_nodes에 없을 경우를 조건으로 실행된다. connected_nodes는 정점 A로 초기화 되어있기 때문에 첫 실행에서는 D가 없으므로 조건을 만족하여 if 문이 실행된다. 실행이 되어지면 connected_nodes에 요소가 추가되고 mst에는 튜플 형태로 요소가 추가된다.

 

 

 

if 문 내에 있는 for 문이다. for 문을 통해 특정 정점에 연결되어 있던 정점을 기준으로, 다음 정점과 간선을 탐색한다. for 문을 통해 n2와 연결되어 있는 정점 및 간선을 추출하고 connected_nodes의 요소와 비교하는데, 없을 경우에는 candidate_edge_list에 해당 edge를 넣어주고 다음 요소를 추출하여 반복한다. 있을 시 다시 for 문으로 돌아간다.

 

 

https://bit.ly/37BpXiC

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

 

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