Algorithm/알고리즘
시간제한과 시간복잡도
대략 1억 번의 연산이 1초가 걸린다. O(1억) = 1초 빅오 N O(N) 약 1억 O(NlogN) ≤ 10,000,000 (약 1000만) O(N2) ≤ 10000 O(N3) ≤ 500
전체 글
Algorithm/알고리즘
✨그래프 알고리즘 비교✨
알고리즘 클릭 시, 해당 페이지로 이동 정점 중심 구현 최단 경로: 두 노드 사이의 경로들 중 간선의 가중치 합이 최소인 경로를 찿는 알고리즘 다익스트라 알고리즘 : 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 O(ElogV) 플로이드 워셜 알고리즘 : 모든 노드에서 다른 모든 노드의 최단 경로 O(V3) 최소 신장 트리(MST): 최소한의 비용으로 모든 노드를 포함하면서 사이클이 존재하지 않는 그래프 프림 알고리즘 : 시작 노드에서 가까운 노드를 선택하여 트리 구성 ➜ 사이클 검사X O(V2) 간선 중심 구현 최단 경로 벨만포드 알고리즘 : 음의 가중치를 허용 최소 신장 트리(MST) 크루스칼 알고리즘 : 최소 비용의 간선을 차례대로 대입하여 트리를 구성 ➜ 사이클 검사必 O(ElogE)..
Algorithm/Problem Solving
[BOJ/GoldIV] 17471. 게리맨더링 - JAVA 자바
17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 120ms DFS BFS 부분집합 이 문제는 두 개의 선거구로 나누는데 같은 선거구끼리는 서로 인접해야 한다. n개의 구역들을 2개의 선거구로 나누기 ➜ 부분집합 DFS 각각의 선거구 구역들끼리 서로 인접한지 확인 ➜ BFS 두 개의 선거구로 나누는 작업은 부분집합으로 한 선거구에는 반드시 하나의 구역이 포함되어야 한다. private static void divide(int idx) { if (idx == N) { a.clear(); b.clear(); for (int i = 0; ..
Algorithm/알고리즘
프림 알고리즘 : 최소 신장 트리(MST)를 찾는 알고리즘
프림 알고리즘 최소 신장 트리(MST)를 찾기 위한 알고리즘이다. 프림 알고리즘은 주어진 그래프에서 시작 정점을 선택하고 해당 정점을 기준으로 MST를 구축해나가는 방식으로 동작한다. 1. 시작 정점을 우선순위 큐에 넣는다. (우선순위 큐는 가중치에 따라 오름차순 정렬되어야 함) 2. 우선순위 큐에서 노드 하나를 꺼내 MST에 포함되어 있는지 확인 2-1. 포함되어 있다면 무시. 다시 1번으로 2-2. 포함되어 있지 않다면 방문처리 후 해당 노드와 연결된 노드를 우선순위 큐에 추가 3. 2번 과정 반복 최소 신장 트리에 대해서는 크루스칼 알고리즘 참고! static class Edge implements Comparable { int v; int cost; public Edge(int v, int cos..
Algorithm/알고리즘
크루스칼 알고리즘 : 최소 신장 트리(MST)를 찾는 알고리즘
신장 트리란 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다. 최소 신장 트리(MST) 최소한의 비용으로 구성되는 신장 트리를 찾아야 하는 경우 → 예를 들어 N개의 도시가 있을 때, 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결되도록 최소한의 비용으로 도로를 설치하는 경우 크루스칼 알고리즘 크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘으로 간선을 중심으로 해결한다. 그리디 알고리즘으로 분류된다. 동작과정 1. 간선 데이터를 비용에 따라 오름차순 정렬 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인 2-1. 사이클이 발생하지 않는 경우 최소 신..
Algorithm/알고리즘
유니온 파인드(Union-Find) : 서로소 집합을 판단하기 위한 자료구조
서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조 서로 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 합집합 Union : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기 Find : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조는 Union-Find 자료구조라고 한다. 동작과정 0. 노드 개수 크기의 부모 테이블을 자신의 값을 갖도록 초기화 1. 합집합 Union 연산을 확인하여 서로 연결된 두 노드 A, B를 확인 A와 B의 루트 노드 A’, B’를 각각 찾는다 A’를 B’의 부모 노드로 설정한다 2. 모든 합집합 Union 연산을 처리할 때까지 1번 과정 반복 #예시 Union(1, 4) Union(2,..
Algorithm/Problem Solving
[BOJ\GoldIV] 1753. 최단 경로 - JAVA 자바
1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 728ms 다익스트라 방향 그래프가 주어지고 출발 노드에서 모든 노드로의 최단 경로를 구하는 문제로 최소힙을 이용한 다익스트라 알고리즘을 구현하면 된다. # 소스코드 import java.io.*; import java.util.*; public class Main { static class Node implements Comparable { int index; int distance; public Node(int index..
Algorithm/Problem Solving
[BOJ/GoldIV] 11404. 플로이드 - JAVA 자바
11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 368ms 플로이드 워셜 인접행렬 모든 노드에서 다른 모든 노드까지의 최단 비용을 찾는 문제로 노드의 범위(N≤100)가 작아 플로이드 워셜 알고리즘을 이용한다. 이 문제에서 주의해야 할 점은 입력값으로 중복된 출발도시와 도착도시가 들어올 수 있다는 점 갈 수 없는 곳은 0으로 출력해야 한다는 점 따라서 처음 입력을 받을 때, 출발노드에서 도착노드로 가는 비용이 더 작은 것을 이차원 테이블에 넣어줘야한다. 또한 모든 노드를 INF 로 초기화 후 구현하기 때문에 마..
Algorithm/알고리즘
플로이드 워셜 알고리즘 : 모든 출발지에서 다른 모든 출발지까지 최단 경로 계산
플로이드 워셜 플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 다만 매 단계에서 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다. 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장하며 동적계획법(DP) 유형에 포함된다. 각 단계마다 특정한 노드 k를 거쳐가는 경우를 확인한다. a에서 b로 가는 최단거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 체크한다. 따라서 점화식은 다음과 같다. 동작과정 인접한 노드만 확인하여 최단 거리 테이블을 초기화한다. 1번 노드(k)를 거쳐가는 경우를 고려하여 테이블을 갱신한다. 이후 반복하여 n번 노드를 거..
Algorithm/알고리즘
다익스트라 알고리즘 : 하나의 출발점에서 다른 모든 출발지까지 최단 경로 계산
최단 경로 알고리즘은 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로를 찿는 알고리즘을 의미한다. 다익스트라 알고리즘 다익스트라 알고리즘은 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 그리디 알고리즘으로 분류되며 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. 동작과정 1. 출발노드 설정 2. 최단 거리 테이블 초기화 ➜ 기본적으로 모든 노드까지 가는 비용을 무한으로 3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 5. 위 과정에서 3번, 4번 반복 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 ..
Algorithm/Problem Solving
[SWEA/D4] 3234. 준환이의 양팔저울 - JAVA 자바
1066ms 순열 부분집합 DFS 양팔저울에 왼쪽 또는 오른쪽에 무게 추를 하나씩 올리는데 추를 올리는 과정에서 오른쪽이 왼쪽보다 무거워지면 절대 안된다는 것이 조건이다. 즉 추를 올리는 순서와 어느 쪽 저울에 추를 올릴지 고려해야한다. 추를 올리는 순서를 정하는 것은 순열, 올리는 순서가 정해진 추들을 어느쪽에 올릴 것인지 정하는 것은 부분집합을 이용하여 구현하였다. 추의 순서를 정한 후 부분집합을 통해 추들을 올렸을 때, 오른쪽무게가 왼쪽무게보다 커지지 않고 모든 추를 다 올렸으면 결과값++ 문제가 헷갈릴 수 있어 꼼꼼하게 읽어봐야 이해하는 문제였다. 순열과 부분집합을 함께 이용하는 문제로 되게 괜찮은 문제라고 생각이 든다 # 소스코드 import java.io.BufferedReader; impor..
Algorithm/Problem Solving
[SWEA/D5] 7258. 혁진이의 프로그램 검증 - JAVA 자바
149ms 빡구현 BFS 문자에 따라 명령어를 실행시켰을 때, 프로그램 종료 문자인 @ 까지 도달할 수 있는가 없는가에 대해 확인하는 문제이다. 이 문제에서 중요하게 고려해야 할 점은 ? 문자는 4방향 중 어느 방향으로 갈 것인가 프로그램이 종료하지 않는 케이스면 어떻게 종료하지 않은 것을 판단할 것인가 두 가지만 신경쓴다면 복잡하지만 빡구현으로 해결할 수 있다. ? 문자를 만났을 때, 각각의 방향에 따라 경우의 수를 따져야하므로 BFS로 구현하였다. 또한 프로그램이 종료되지 않는 케이스를 판단하기 위해 (행, 열, 방향, 메모리)의 방문체크를 해주는 4차원 배열이 필요하다. (x,y)좌표와 방향, 메모리에 방문체크가 되어있다면 계속 루프를 돌고 있는 것으로 프로그램이 종료할 수 없는 경우이다. 그래서 ..
