[JAVA] 프림 알고리즘 (+ 크루스칼과는 어떻게 다를까?)
CS/알고리즘2025. 6. 21. 20:44[JAVA] 프림 알고리즘 (+ 크루스칼과는 어떻게 다를까?)

이전 포스팅에 이어 이번에는 MST 알고리즘을 구현하는 방식 중 하나인 프림 알고리즘에 대해 알아보려 합니다.우선 MST에 대해 다시 한번 짚고 넘어가겠습니다. 📑 MSTMST를 다시한번 간단하게 설명하면 "최소 비용으로 모든 정점을 연결한 트리 구조"입니다.트리 구조 특성 상 사이클이 발생하면 안되는데요.이유는 트리는 정점 간 유일한 경로, 최소 연결성이라는 특성이 있기 때문입니다. 이러한 MST를 구하는 방식 중 하나인 크루스칼 알고리즘에 대해서는 아래 포스팅을 참고해주세요.[JAVA] 크루스칼 알고리즘 (Kruskal Algorythm) [JAVA] 크루스칼 알고리즘 (Kruskal Algorythm)최근 알고리즘 문제 풀이를 다시 시작하며 기억에서 희미해져버린 MST 알고리즘에 대해서 정리해볼까..

[JAVA] 크루스칼 알고리즘 (Kruskal Algorythm)
CS/알고리즘2025. 6. 14. 19:17[JAVA] 크루스칼 알고리즘 (Kruskal Algorythm)

최근 알고리즘 문제 풀이를 다시 시작하며 기억에서 희미해져버린 MST 알고리즘에 대해서 정리해볼까 합니다.정리하려는 주된 내용은 아래와 같습니다.❓ MST가 무엇인지, 크루스칼 알고리즘의 구현 및 동작 방식 📑 MST란?MST는 Minimum Spanning Tree의 약자로 최소 신장 트리를 찾기 위한 알고리즘입니다.또한 Spanning Tree(신장 트리)는 간단하게 설명하면 모든 정점을 포함하면서 사이클이 없는 연결 그래프를 의미합니다.더보기왜 사이클이 없어야할까❓ (25.06.21 추가)처음에는 모든 정점이 연결만 되면 된다고 생각했습니다. (이 과정에서 사이클이 생기든 말든지요.)그러나 MST 또한 트리이며, 트리 특성을 생각해보면 사이클이 없어야 합니다.트리에서 한 정점에서 다른 정점으로 가..

"같은 네트워크"가 무엇을 의미하는지
CS/네트워크2025. 3. 8. 18:43"같은 네트워크"가 무엇을 의미하는지

네트워크 스터디 준비를 하면서 문득 "같은 네트워크"라는 말이 이해가 안되서 한번 찾아봤습니다.오늘은 같은 네트워크가 무엇인지에 대해 정리 해보려합니다.  한줄로 요약해본다면 아래와 같습니다.서로 다른 장치가 직접적으로 통신이 가능하면 같은 네트워크. 그러나 직접적으로 통신이 가능한게 어떤것이며, 간접적으로 통신하는건 어떤건지에 대해 다시금 의문이 생겼습니다. 네트워크 영역은 아래와 같은 요소들로 논리적으로 구성되어 있습니다.VPC(Virtual Private Cloud)서브넷(Subnet)VLAN(Virtual LAN)네트워크 영역의 범위는 아래로 내려갈수록 작아집니다. 👀 "같다"라는 기준같은 네트워크가 되는 기준은 크게 IP 주소 체계, 서브넷, 라우팅 규칙, 네트워크 장비(스위치/라우터) 연결 ..

CS/알고리즘2025. 2. 7. 18:46[알고리즘] 특정 수열에서 양 옆 최대값을 O(1)로 구해보자!

✏️ 알고리즘 개요알고리즘 문제를 풀다보면 특정 수열에서 i번째 원소를 기준으로 왼쪽 혹은 오른쪽 원소들에 대해 최대값을 구해야하는 경우가 종종 있다. 아래와 같이 단순하게 왼쪽, 오른쪽 원소들에 대해 반복문을 통해 최대값을 구하는 것을 생각해볼 수 있다.int[] arr = new int[]{5,9,6,2,1,4,5,6,8,10,4};for(int i=0; i=0; j--) { leftMaxValue = Math.max(leftMaxValue, arr[j]); } //오른쪽 최대값 int rightMaxValue = 0; for(int j=i+1; j 그러나 수열의 길이가 매우 길어지고, 찾아야하는 원소의 개수가 많아질수록 위와 같은 반복문은 매우 긴 시간복잡도를 가지..

image