알고리즘4 MST (Minimun Spanning Tree, 최소 신장 트리) 그래프와 트리비선형 자료구조 : 객체간의 관계를 관리하며 하나의 자료 뒤에 여러 개의 자료가 존재그래프 : 노드(정점, 위치), 간선(위치간 관계), 가중치(간선에 할당된 비용)로 이루어진 자료구조유향 그래프, 무향 그래프 : 단방향이면 유향, 양방향이면 무향트리 : 사이클 없이 모든 노드가 하나의 연결 요소인 그래프사이클 - 단순 경로(노드가 중복되지 않은 경로)의 시작점과 종점이 동일한 그래프→ 노드의 개수가 n개일 때, 간선의 개수는 n-1개 이다.기본 트리는 루트를 고려하지 않음, 루트를 고려하면 루티드 트리가 된다.신장 트리(Spanning Tree) : 그래프 내의 모든 정점을 포함하는 트리→ 최소 연결(간선의 수가 가장 적은 부분 그래프)→ n개의 노드에 n-1개의 간선으로 모두 연결된 그래.. 2024. 6. 26. [알고리즘/프로그래머스] 아이템 줍기 (Lv.3) [ 문제이해 ] 이 문제는 좌표평면에 여러개의 사각형이 놓여 하나의 다각형의 형태로 이루어져 있을 때, 다각형의 둘레를 따라 캐릭터가 이동하며 아이템이 놓여있는 곳까지의 최소 거리를 구하는 문제이다. 문제의 경우에서는 2개 이상의 다각형 또는 한 직사각형이 다른 직사각형을 완전히 포함하는 경우를 제외하기 때문에 어렵지 않은 문제였다. [ 문제풀이 ] 이 문제에서의 키 포인트라면 좌표 평면을 기준으로 플레이어가 둘레를 따라 움직여야 한다. 하지만 일반적인 DFS로 해결하려 한다면 위의 빨간줄을 따라 캐릭터가 이동한다면 캐릭터가 (3, 5)에 위치한다면 (4, 6)으로 이동할 뿐 아니라 (3, 6)으로도 이동할 수 있다. 이 방법은 생각보다 매우 쉽게 해결되었다. 그 방법은 바로 모든 좌표를 2배로 늘려주어.. 2023. 10. 4. [알고리즘/프로그래머스] 양과 늑대 (Lv.3) [ 문제이해 ] 문제의 기본 유형은 이진 트리 모양의 초원에 각 노드마다 양 또는 늑대가 한마리씩 놓여있다. 이때, 루트 노드에서 출발하여 각 노드를 돌아다니면서 노드에 있는 동물을 데리고 다니는데 양의 수가 늑대의 수보다 항상 많아야 한다. 만약 늑대의 수가 더 많다면 양은 모두 잡아먹혀 양은 0마리가 된다. 또한, 한번 방문한 노드를 다시 방문할 수 있고, 중간에 양이 잡아 먹히지 않으면서 가장 많은 수의 양을 모으는 경우에서 양의 수를 결과값으로 내면 된다. [ 문제풀이 ] 사실 문제 자체는 어렵지 않아 처음 문제를 접했을 때, 간단한 DFS문제로 해결하면 되는 줄 알았다. 하지만 보통의 DFS의 경우 한번 방문한 노드의 경우 다시 방문하지 않는다. 이 문제에서는 방문한 노드를 다시 방문해도 되지만.. 2023. 10. 4. 플로이드 와샬 개념 + 구현(최단 경로 찾기) 최단 거리를 구하는 다양한 알고리즘이 있지만 오늘은 플로이드 와샬의 개념과 구현에 대해서 한번 포스팅 해보려고 한다. 1. 플로이드 와샬 알고리즘 개념플로이드 와샬 알고리즘과 다른 최단 경로를 찾는 알고리즘의 차이점은 플로이드 와샬의 경우 모든 정점에서 모든 정점으로의 최단 경로를 한번에 구한다. 즉 정점과 정점, 모든 쌍의 최단 경로를 구하는 것이다. 방법은 먼저 가능한 모든 쌍을 표현하는 행렬(이차원 배열)을 선언하고 다이나믹 프로그래밍(dp)의 방식으로 각각의 원소들(각 쌍의 최단거리)을 업데이트 해나간다.업데이트 기준를 행하는 기준은 현재 거쳐가는 정점이다거쳐가는 정점을 기준으로 알고리즘을 수행한다.i 에서 j 로 가는데 해당 정점을 경유해서 가는 것이 더 빠르다면 그 정점을 거쳐서 가는걸로 업데.. 2023. 10. 2. 이전 1 다음
