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

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

 

2월 12일 오늘의 강의

 

Prem's Algorithm 구현

오늘은 대표적인 최소 신장 트리 알고리즘으로 Prem's Algorithm을 구현했다. 프림 알고리즘은 시작 정점을 선택하고, 정점에 인접한 간선들 중 최소 간선으로 연결된 정점을 선택, 해당 정점에서 다시 최소 간선과 정점을 선택해나가며 트리를 확장해나가는 방식이다.

 

Kruskal's Algoritm과 차이점

둘 모두 탐욕 알고리즘을 기초로 하여 구현되었지만, 크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택하면서 연결해나가지만, 프림 알고리즘은 특정한 정점을 선택한 뒤에 이에 맞춰 연결해나가는 방식이다.

 

알고리즘 구현

 

라이브러리 불러오기

 

알고리즘을 구현하기에 앞서 collections와 heapq 라이브러리를 불러온다. 라이브러리의 기능을 이용하여 자료구조 및 함수 기능을 활용할 예정이다.

 

 

dafaultdict 함수 사용 예시

 

defaultdict 함수는 위와 같이 빈 딕셔너리에서 키 값을 불러올 때 기본 값으로 리스트를 반환해줄 수 있게 해준다. 이를 통해 딕셔너리에 키 값이 없더라도 append 메소드를 통해 값을 입력시킬 수 있게된다.

 

 

heapq 라이브러리 사용 예시

 

heapq 라이브러리에서 heapify 메소드를 통해 리스트 데이터를 heap 자료구조로 변환시켜주고 이를 통해 최솟값(또는 최댓값)을 반환시킬 수 있게된다.

 

 

edge 생성

 

본격적으로 Prem's Algorithm 구현을 위해 그래프를 만든다. 그래프는 리스트 안에 튜플 형태이며, 튜플에서는 가중치, 연결된 정점을 넣어준다. 이때 정점과 간선이 중복되지 않게 작성해준다.

 

 

Prem's Algorithm 구현

 

Prem's Algorithm을 구현한 함수이다. 상세 기능은 다음 편에서  계속 진행해보겠다!

 

 

https://bit.ly/37BpXiC

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

 

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