그래프

오늘은 무엇을 배우게 될까요? 지난 58일차에서는 유니온 파인드 알고리즘을 배워그래프 내 사이클 여부를 빠르게 탐지하는 방법을 익혔습니다. 이번엔 그 응용 사례 중 하나인 최소 신장 트리(Minimum Spanning Tree) 문제를크루스칼 알고리즘을 통해 해결해볼 거예요. 모든 정점을 연결해야 하고사이클 없이총 연결 비용이 최소가 되도록 하려면?→ 크루스칼 알고리즘이 등장합니다. 최소 신장 트리(MST)란? 신장 트리(Spanning Tree)는그래프에서 모든 정점을 포함하면서 사이클이 없는 트리입니다. 그중에서도 간선들의 가중치(비용) 총합이 가장 작은 것이최소 신장 트리(MST)입니다. 크루스칼 알고리즘이란? 크루스칼 알고리즘은모든 간선을 가중치 오름차순으로 정렬한 뒤,하나씩 사이클이 생기지..

오늘은 무엇을 배우게 될까요? 그래프 알고리즘에서 때때로 중요한 질문이 있습니다. 이 연결 구조 안에 순환(Cycle)이 있을까? 이 질문에 답할 수 있어야위상 정렬을 적용할 수 있는지 판단하고 그래프가 트리 구조인지 검증하고 네트워크 상 충돌 여부나 의존 관계의 모순을 확인할 수 있습니다. 오늘은 사이클이 있는지 효율적으로 판별하는 알고리즘인유니온 파인드 (Union-Find, 서로소 집합)을 배워봅니다. 유니온 파인드란? 서로소 집합(Disjoint Set)은여러 개의 원소를 그룹으로 묶되, 서로 겹치지 않게 관리할 수 있도록 하는 자료구조입니다. 두 노드를 연결할 때 사이클이 생기는지 확인하는 데에 특히 유용합니다. 기본 원리연산설명Find(x)x가 속한 집합(부모 노드)을 찾는다Union(x, ..

오늘은 무엇을 배우게 될까요? 지금까지 그래프에서 최단 경로를 찾는 알고리즘들을 배웠습니다.하지만 그래프는 단순히 거리나 연결만을 표현할 수 있는 것이 아니라,작업의 순서 같은 의존 관계도 표현할 수 있습니다. 예를 들어 “A 작업이 끝나야 B 작업을 할 수 있다”“C 과목을 들어야 D 과목 수강이 가능하다” 이런 순서를 처리하기 위한 정렬 방법이 바로 위상 정렬(Topological Sort)입니다. 위상 정렬이란? 방향 그래프(DAG: Directed Acyclic Graph)에서 정점들을 순서대로 나열하는 방법입니다.→ 단, 어떤 정점으로 들어가는 간선(=선행 조건)은 반드시 그보다 앞에 와야 합니다. 즉, “선수 과목 → 후수 과목” 순으로 정렬된 결과를 찾는 것이 위상 정렬입니다. 전제 조건조..

오늘은 무엇을 배우게 될까요? 지난 시간에 배운 다익스트라 알고리즘은 빠르고 효율적이지만음수 가중치가 있는 경우에는 사용할 수 없었습니다. 오늘은 그런 경우를 해결할 수 있는 벨만-포드 알고리즘을 배워볼 거예요.간선 수만큼 반복하면서 거리 정보를 갱신하는 방식으로,시간은 더 오래 걸리지만 음수 가중치도 처리할 수 있는 강력한 알고리즘입니다. 벨만-포드 알고리즘이란? 음수 가중치가 있는 그래프에서시작 노드에서 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. → 다익스트라는 빠르지만, 벨만-포드는 더 유연합니다.→ 또한 음수 사이클(계속 줄어드는 무한 루프)도 탐지할 수 있습니다! 알고리즘 원리 시작 노드의 거리를 0으로, 나머지는 무한대로 초기화전체 간선 E에 대해 (V-1)번 반복하면서 거리 갱신..

오늘은 무엇을 배우게 될까요? 그래프는 정점(노드)과 간선(연결선)으로 구성된 구조였고,우리는 이 구조 안에서 BFS나 DFS를 통해 탐색하는 방법을 배웠습니다. 그런데 만약 “가장 빠른 길”이나 “가장 비용이 적은 경로”를 찾고 싶다면 어떨까요?이때 사용하는 알고리즘이 바로 다익스트라 알고리즘(Dijkstra’s Algorithm)입니다. 오늘은 이 알고리즘이 어떤 원리로 최단 경로를 구하는지,직접 구현하는 방법과 함께 배워봅니다. 다익스트라 알고리즘이란? 다익스트라 알고리즘은가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘입니다.시작 노드에서 다른 모든 노드까지의 최소 비용 경로를 계산합니다. → 실생활에선 네비게이션, 통신망 최적화, 게임 AI 등에서 사용됩니다. 전제 조건 모든 간선의 가중..

오늘은 무엇을 배우게 될까요? DFS, BFS는 그래프(Graph)를 탐색하기 위한 알고리즘이었죠.하지만 정작 그래프가 뭔지, 어떻게 생겼는지는 제대로 이야기하지 않았습니다. 그래프는 실생활에서 수없이 많이 등장하는 구조입니다.오늘은 그래프의 개념, 구성 요소, 종류, 표현 방식, 그리고 활용 예시까지 살펴보겠습니다. 그래프란? 그래프(Graph)는정점(Vertex, 노드)과 간선(Edge)으로 이루어진 자료구조입니다.→ 정점끼리의 관계를 표현하는 구조입니다. 예를 들어, 사람 간의 친구 관계, 도시 간의 연결, 컴퓨터 네트워크, 소셜미디어 팔로우 등“관계”가 있는 거의 모든 것을 그래프로 나타낼 수 있습니다. 그래프의 구성 요소구성 요소설명정점(Vertex)정보를 담는 기본 단위 (ex: 사람, 도..

안녕하세요!IT 초보 탈출 20일차를 맞이한 블로그입니다! 🌱지난 시간에는 알고리즘의 효율성을 측정하는 방법에 대해 알아봤는데요.오늘은 데이터를 효율적으로 저장하고 관리하는 '자료구조'에 대해 알아볼게요! 😊💡 자료구조란 무엇인가요?자료구조는 데이터를 효율적으로 저장하고, 조직하고, 관리하는 방법이에요.마치 주방에서 식재료를 보관하는 다양한 용기들과 같죠.음식의 종류와 목적에 따라 냉장고, 서랍, 항아리 등 다른 용기를 사용하듯이,데이터도 그 특성과 목적에 맞는 자료구조에 담아야 효율적으로 활용할 수 있어요.자료구조가 중요한 이유효율성: 적절한 자료구조를 선택하면 데이터 처리 속도가 빨라져요메모리 관리: 데이터 특성에 맞는 자료구조를 사용하면 메모리를 절약할 수 있어요코드 가독성: 상황에 맞는 자료..