🤔 Floyd-Warshall 플로이드-와샬 알고리즘? 그래프에 있는 모든 정점에 대해 각 정점들이 다른 정점들까지 도달하기 위해 필요한 모든 최단 거리를 구할때 사용합니다. 플로이드-와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행하는 특징이 있습니다. 즉, 정점 A, 정점B 까지의 최단 거리를 구하기 위해 중간에서 거쳐갈 수 있는 모든 정점들을 확인해보고 그 중 최단 거리의 경로를 찾습니다. (플로이드 와샬은 다이나믹 프로그래밍 기법을 사용한 알고리즘이고, 인접 행렬로 표현하여 최단 거리를 계산합니다.) ✔ 시간복잡도 3중 for문을 통해 거쳐가는 정점을 이용하여 그래프를 탐색하기 때문에 O(n^3)의 시간복잡도를 갖습니다. ✔ 탐색 방법 문제와 함께 플로이드-와샬 알고리즘의 탐색방법을 살펴보..
✔ 문제 난이도 : 실버 🥈 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net ✔ 문제 풀이 임의의 두 사람이 최소 몇 단계만에 이어질 수 있는지 계산하는 문제입니다. 즉, 정점에서 다른 정점까지의 최단거리들을 계산하여 최단거리들의 합이 가장 낮은 사람을 출력 해야합니다. BFS와 DFS 모두 이용 가능하지만 DFS로 풀 경우 시간 초과가 났습니다.😭 하지만 풀이는 가능함으로 BFS와 DFS모두 풀어보겠습니다. 📌 설명은 코드 주석에 있습니다! 🔎 BFS 풀이 i..
🤔 BFS ( Breadth First Search ) 너비 우선 탐색? 그래프 탐색 알고리즘의 하나로, 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법입니다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다. 즉, 깊게 탐색하기 전에 넓게 탐색하는 것입니다. 두 노드 사이의 최단 경로 또는 임의의 경로를 찾고 싶을 때 쓰입니다. 장점 출발노드에서 목표노드까지의 최단 경로를 보장한다. 단점 노드의 수가 많을수록 탐색 가지가 급격하게 증가하여 보다 많은 기억 공간이 필요하다. 해가 존재하지 않는다면 유한 그래프의 경우 모든 그래프를 탐색한 후에 실패한다. ✔ 문제유형 최단 경로 찾기 ✔ 시간복잡도 노드가 N이고, 간선의 수가 E인 그래프의 경..
🤔 DFS ( Depth First Search ) 깊이 우선 탐색? 그래프 탐색 알고리즘으로 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 알고리즘 입니다. 즉 그래프 형태의 자료구조에서 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 그림처럼 한 방향으로 인접한 노드가 없을 때까지 탐색한 후 이전 노드로 돌아가서 다음 인접한 노드를 탐색하며 이 과정을 반복합니다. 장점 현재 경로상의 노드를 기억하기 때문에 적은 메모리를 사용합니다. 찾으려는 노드가 깊은 단계에 있는 경우 BFS보다 빠르게 찾을 수 있습니다. 단점 DFS를 통해 얻어진 해가 최단 경로라는 보장이 없습니다. DFS는 찾으려는 해에 도착하면 탐색을 종료하기 때문입니다. 최..
🤔 Deque? Deque는 'Double Ended Queue'의 약자로 큐의 기능을 확장한 자료구조로 볼 수 있습니다. 큐는 뒤쪽(rear)에서 삽입 앞쪽(front)에서 삭제 연산이 가능했다면 기능을 확장하여 큐의 양쪽에서 모두 삽입과, 삭제가 가능합니다. 즉, stack의 LIFO과 queue의 FIFO 특징을 모두 사용할 수 있습니다. ✔ Deque 구현하기 큐를 확장한 자료구조임으로 이전에 만든 큐 인터페이스를 implements하여 기능을 추가하여 구현 하겠습니다. 실제 자바의 덱 자료구조에는 여러가지 기능을 하는 메서드들이 더 있지만, 덱의 가장 큰 특징인 양쪽에서의 삽입,삭제에 관한 기능을 구현하도록 하겠습니다. 메소드명 리턴 타입 설명 offerFirst(E e) E 큐의 첫 번째(Fr..
🤔 Queue? '대기열'이라고 생각하면 이해가 쉬울 것 입니다. 흔히 게임에서 '큐 돌린다', '큐 잡혔다' 같은 말을 들은적이 있을 것 입니다 이때 큐는 Queue를 의미합니다. 큐는 FIFO(First In First Out)선입선출 즉, 먼저 들어간것이 먼저 빠진다 라는 특징이 있습니다. 즉 대기열처럼 데이터를 시간 순서에 따라 순차적으로 처리할때 쓰일 수 있습니다. 한쪽 끝에서는 삽입, 반대쪽 끝에서는 삭제 작업이 이루어지는 자료구조 입니다. ✔ Queue 인터페이스 만들기 실제 자바의 큐 인터페이스 에는 더 많은 메소드들이 있지만 큐의 특징적인 메소드만 우선 만들어보고 추후에 큐의 기능을 확장한 덱(Deque) 자료구조도 만들어보기 위해 최소한의 메소드만 만들어 보겠습니다. 메소드 메소드명 리..
