Intro어떤 정점으로부터 모든 정점들로의 최단 경로를 구하는 문제는 최단 경로 알고리즘을 적용해서 정해를 구할 수 있다.이 때 사용되는 최단 경로 알고리즘으로는 아래와 같다.다익스트라(Dijkstra) 알고리즘벨만-포드(Bellman-Ford) 알고리즘플로이드-워셜(Floyd-Warshall) 알고리즘아래 표는 최단 경로 알고리즘 3가지의 각 차이점에 대해 참고할 수 있도록 생성형 AI를 통해 생성한 자료구분다익스트라(Dijkstra)벨만-포드(Bellman-Ford)플로이드-워셜(Floyd-Warshall)목적단일 출발점에서 다른 모든 정점까지의 최단 거리단일 출발점에서 다른 모든 정점까지의 최단 거리모든 정점 쌍 간 최단 거리음수 가중치❌ 불가능 (음수 간선 있으면 오동작)✅ 가능✅ 가능음수 사이클..

문제https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이정석적인 구간합 풀이 (투포인터) 접근법문제를 조금 읽어보면 알 수 있듯, 특정 합(k)을 만족하는 구간을 구하는 문제로 구간합을 구하는 알고리즘을 적용해서 풀 수 있다.처음에 떠올린 방법은 투포인터를 활용해서 구간합 조건을 검색하는 방식이였고, 두번째는 누적합이다.만약 '비내림차순'이 아니라 정렬이 되어 있다는 가정이라면 이분탐색을 활용해도 풀 수 있다. 우선 해당 문제의 조건은 간단하다. 만족하는 구간합이 여러 CASE일 경우 아래 조건에 따..

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

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

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