코딩테스트 문제를 풀다 보면 그래프 문제를 마주하는데, 이렇게 정점과 간선 정보가 주어졌을 때 어떻게 그래프로 표현할 수 있을까?그래프를 표현하는 방법은 크게 2가지가 있다. 바로 인접 행렬과 인접 리스트다. 🟣 인접 행렬인접 행렬은 (정점 * 정점)을 배열로 두고, 두 정점 사이에 간선이 있으면 1로 표시하는 방식이다.배열이다 보니 탐색이 빠르다는 장점이 있다! 그렇지만 아무래도 메모리 공간을 많이 사용한다는 단점이 있다. 정리하면, 인접 행렬을 사용하는 경우는 다음과 같다.상황이유정점의 수가 작을 때$O(V^2)$ 공간이 감당 가능한 경우, 보통 정점이 1000개 이하일 때 사용한다.간선의 수가 많을 때(dense graph)거의 모든 정점이 연결되면 리스트보다 오히려 효율적이다.간선 유무를 자주..

벨만-포드(Bellman-Ford)벨만-포드 알고리즘은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다.다익스트라 알고리즘도 최단 거리를 구하는 알고리즘인데, 벨만-포드는 뭐가 다를까?다익스트라 알고리즘과 비교해 보면 다음과 같다.다익스트라 vs 벨만-포드다익스트라매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나간다.음수 간선이 있을 때에는 적용할 수 없다.시간 복잡도가 벨만-포드에 비해 빠르다 → O(ElogV)벨만-포드매 단계마다 모든 간선을 전부 확인하면서 모든 노드 간의 최단 거리를 구해나간다.간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다.단, 시간 복잡도가 다익스트라 알고리즘에 비해 느리다 → O(VE)즉, 모든 간선의 가..

주어진 숫자 하나가 소수인지 아닌지 판단하는 함수2부터 N까지 전부 순회하면서 isPrime이 true를 반환하면 개수가 증가하는 방식이다. √num까지만 확인해 봐도 충분하다.하지만 N이 100만 정도라면, 이 방식은 O(N√N)이라서 느릴 수 있다.class Solution { static boolean isPrime(int num) { if (num 에라토스테네스의 체성능을 고려하면 에라토스테네스의 체가 더 효율적이다. 이는 boolean 배열 기반의 함수로 구현한다.에라토스테네스의 체가 무엇인지 궁금하다면? https://www.youtube.com/watch?v=oYj_rwUpncM 에라토스테네스의 체는 O(NloglogN)​의 시간복잡도를 가진다. (O(NloglogN) 정도..

다익스트라(Dijkstra)시작점에서 다른 정점으로 가는 최단거리를 각각 구해주는 알고리즘이다.음수 가중치가 있을 때의 최단거리는 다익스트라를 이용해서는 절대 구할 수 없다!그래프 내의 정점의 수를 V, 간선의 수를 E라고 했을 때 이 알고리즘의 시간 복잡도는 O(ElogV)가 된다.순서그래프에 있는 모든 노드들에 대해서 초기값을 전부 아주 큰 값(INF)로 설정한다.시작점에 대해서만 dist 값을 0으로 초기화한다.최소 힙(Java에서는 우선순위 큐(Priority Queue)로 구현)를 둠으로써 누적 최단 거리(dist)가 가장 작은 값을 빠르게 찾아낼 수 있다. 시작점만 먼저 넣는다. 우선순위 큐(pq)가 비어 있지 않을 때까지 반복한다.pq에서 Edge를 꺼낸다. pq의 정렬 기준이 dist 기준..

1. Union-FindUnion-Find란 서로소 집합(Disjoint Set)을 관리하는 자료구조다. 여러 개의 원소, 여러 개의 집합이 있다고 가정했을 때 특정 원소가 어떤 집합에 속해있는지 확인하거나 특정 집합을 합쳐야 할 일이 있다면 Union-Find 자료구조를 사용한다.💡 서로소란?겹치는 원소가 없는 그룹들Union-Find의 원리는 다음의 영상에서 잘 나타나있다. https://www.youtube.com/watch?v=ayW5B2W9hfo 예를 들면, 다음과 같은 경우에 사용한다.사이클 판별: 빠르게 연결 여부를 확인할 수 있다.MST(크루스칼 알고리즘): 안전한 간선만 선택할 수 있다.집합의 수 세기: 루트만 추적하면 바로 카운트할 수 있다.즉, 연결되어 있는지, 같은 그룹인지를 빠르..