🧪Computer Science

[알고리즘] 최소 스패닝 트리 알고리즘 | 크루스칼/프림 알고리즘

~목차~ 스패닝 트리란? 크루스칼 알고리즘 프림 알고리즘 (최소) 스패닝 트리란? 최소 스패닝 트리 알고리즘을 설명하기 이전에 스패닝 트리(Spanning Tree)란 무엇인가 알아보도록 하겠습니다. 스패닝 트리는 어떤 그래프에서 모든 노드를 연결하며 사이클이 없는 부분 그래프를 의미합니다 그림으로 이해해보겠습니다 왼쪽과 같은 초기 그래프가 있을 때 오른쪽 그래프는 스패닝 트리입니다. 그럼 아래 그래프는 스패팅 트리 일까요? 아닙니다. 오른쪽 그래프는 사이클이 발생했고, 오른쪽 그래프는 모든 노드를 연결하지 않고 있습니다. 그렇다면 아래 그래프는 신장(스패닝) 트리일까요? 그렇습니다. 신장 트리 중 최소 신장 트리입니다. 최소 신장(스패닝) 트리는 신장 트리 중 가장 적은 비용을 갖는 그래프입니다. 모든..

[알고리즘] 최단 경로 알고리즘 | 다익스트라 | 플로이드 워셜

~목차~ 최단 경로 문제 다익스트라 알고리즘 플로이드워셜 알고리즘 최단 경로 문제 최단 경로 문제는 그래프 문제로 우테캠 6기 코딩테스트에도 나왔었다 최단 경로 알고리즘은 크게 두 가지로 다익스트라(Dijkstra, 데이크스트라) 알고리즘과 플로이드 워셜 알고리즘이 있다 기본적으로 그래프에 대한 이해를 바탕으로 알고리즘이 진행된다 노드에서 다른 노드로 접근 방법이 없다면 무한수(int(1e9) in Python)로 표시한다. 다익스트라 알고리즘 시작 노드로부터 각 노드까지 최단 경로를 구할 수 있는 알고리즘이다. 문제 해결을 위한 방법은 2가지가 있다. 리스트(배열)을 사용하거나 우선순위 큐 사용하는 것이다. 리스트를 사용하는 것이 우선순위 큐를 사용하는 것보다 쉽지만 시간 복잡도에서 차이가 많이 나므로..

[알고리즘] 시간복잡도 구하기

처음 알고리즘 분류 글을 작성하게 되었습니다(두근) 작년(2022) 이맘때쯤 학교에서 학습했던 알고리즘의 시간복잡도에 관한 내용입니다. 코딩테스트가 익숙해지면서 효율성을 요구하는 문제들과 맞딱뜨리게 되었는데, 이때 알아야 할 기초 개념이 바로 시간복잡도입니다. 내가 짠 코드가 입력 대비 얼마큼의 시간이 필요한가를 계산하여 효율성을 판단하고, 비효율적이라면 어떤 부분을 수정할지 생각해 볼 수 있기 때문입니다. 목차 1. 정의 & 표기법 2. O(1) 2. O(N) 3. O(N²) 4. O(NlogN) 1. 정의 & 표기법 위키 백과에서 인용해 온 컴퓨터과학에서 시간복잡도의 정의 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것 다음은 시간복잡도의 3가지 표현법입니다. 최..