Algorithm6 [Algorithm] 최소 신장 트리(MST) (1) - 크루스칼 알고리즘 MST(Minimum Spanning Tree)란? 신장 트리(Spanning Tree) : 연결 그래프의 부분 그래프로서, 모든 정점과 간선의 부분 집합으로 구성 되는 트리이다. 모든 노드는 적어도 하나의 간선에 연결되어 있어야 한다. 최소 신장 트리(Minimum Spanning Tree) : 트리를 구성하는 간선들의 가중치를 합한 것이 최소가 되는 신장 트리이다. 트리의 정의에 알맞게 사이클(Cycle)이 존재하면 안된다. 크루스칼 알고리즘 (Kruskal's Algorithm) 방향성이 없는 가중치 그래프에서 최소 신장 트리를 찾는 대표적인 그리디 알고리즘이다. 동작 방식 첫번째로, 모든 간선을 가중치를 기준으로 오름차순 정렬한다. 가장 낮은 가중치의 간선을 선택하고, 신장 트리에 추가한다.. 2023. 7. 7. [Algorithm] 위상 정렬 위상 정렬 (Topological Sorting) 위상 정렬이란? 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 쉽게 말하자면, 순서가 정해져 있는 작업을 정렬 할 때 사용할 수 있는 알고리즘이다. 정의만으로는 무슨 의미인지 파악하기 힘들다. 예시 사진을 보자. 사진과 같이 1부터 6까지의 노드가 있고, 방향성이 있는 간선이 각각 존재한다. 위상 정렬 알고리즘을 구현하기 위해 다음과 같은 과정만 지키면 된다. 1. 진입차수가 0인 노드를 큐에 모두 넣는다. 2. 큐에서 노드(V1)를 하나 꺼낸다. 3. V1에 연결 된 모든 노드를 순회한다. 4. 노드(V2) 발견 시, 간선을 제거 한다. 5. V2의 진입차수.. 2023. 4. 16. [Algorithm] 최단 거리 알고리즘 총 정리 최단 경로 알고리즘을 만날 때 마다 어떤 알고리즘을 사용할지, 어떻게 사용하는지 헷갈려서 한번에 총 정리 해보았다. 참고 포스팅 최단 경로 알고리즘 종류 가중치가 없거나 동일한 그래프 BFS (완전탐색 알고리즘) 가중치가 없거나 동일한 그래프에서 BFS로 완전탐색하는 것이 최단경로 구하기에 가장 빠르다. 가중치가 각각 다른 그래프 음수가 아닌 가중 그래프 다익스트라(Dijkstra) 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제 음수가 존재하는 가중 그래프 벨만-포드 알고리즘(Bellman-Ford Algorithm) 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 전체 쌍, 다수 출발, 단일 도착 최단 경로 문제 A* 알고리즘(.. 2023. 2. 4. [Java] 프로그래머스 86971 - 전력망을 둘로 나누기 1. 문제 소개 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전.. 2023. 1. 4. [Java] 프로그래머스 17683 - 방금그곡 1. 문제 소개 https://school.programmers.co.kr/learn/courses/30/lessons/17683 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, 라디오 등에서 나온 음악에 관해 제목 등의 정보를 제공하는 서비스이다. 네오는 자신이 기억한 멜로디를 가지고 방금그곡을 이용해 음악을 찾는다. 그런데 라디오 방송에서는 한 음악을 반복해서 재생.. 2022. 12. 24. [Java] 프로그래머스 131130 - 혼자 놀기의 달인 1. 문제 소개 https://school.programmers.co.kr/learn/courses/30/lessons/131130 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다. 숫자 카드 더미에는 카드가 총 100장 있으며, 각 카드에는 1부터 100까지 숫자가 하나씩 적혀있습니다. 2 이상 100 이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비하고, 준비한 카드의 수만큼 작은 상자를 준비하면 게임을.. 2022. 12. 14. 이전 1 다음 728x90 반응형
