전체 글
[Baekjoon] 7662: 이중 우선순위 큐
[Baekjoon] 7662: 이중 우선순위 큐
2023.03.08문제 삽입 연산과 삽입된 값들 중에 최대값과 최소값 삭제 연산을 통해 최종적으로 남아있는 최대값과 최소값을 출력하는 문제이다. 문제 제목 자체가 이중 우선순위 큐로 힌트를 주기 때문에, 좀 더 풀이가 쉽지 않았나 생각한다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q7662 { private static BufferedReader br; private static StringBuilder sb; public static void main(String[] args) throws IOException { br =..
[Algorithm] 위상 정렬(Topological Sort)
[Algorithm] 위상 정렬(Topological Sort)
2023.03.07위상 정렬(Topological Sort)? 위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘으로, 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것이다. 실생활을 예로 들면, 인터넷 검색을 하기 위해선 다음과 같은 순서로 행동해야한다. 컴퓨터 전원 키기 -> 브라우저 키기 -> 검색 엔진 포털 진입 -> 검색 위 순서가 바뀐다면 검색을 할 수 없을 것이다. 위상 정렬은 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 된다. 그래프가 DAG가 아닌 경우 그래프에 대한 위상 정렬은 불가능하다. 여기서 주의할 점은 E가 수행되기 위해선 B와 D가 모두 수행되어야 한다는 점이다. 비순환 방향 그래프 (DAG: Di..
[Baekjoon] 2533: 사회망 서비스(SNS)
[Baekjoon] 2533: 사회망 서비스(SNS)
2023.03.02문제 문제가 조금 복잡하다. 간단히 설명하자면, 주변의 모든 친구가 얼리어답터이면 자신은 얼리어답터가 될 필요가 없는데, 이때 최소 얼리어답터의 수를 구하는 것이다. 풀이 대표 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class Q2533 { private static List graph; private static int[][] dp; private static boolean[] visited; public static void main(String[] args) thro..
[Baekjoon] 1655: 가운데를 말해요
[Baekjoon] 1655: 가운데를 말해요
2023.03.02문제 수가 순차적으로 주어지면 입력된 수 들 중에서 중간값을 계속 출력해나가는 문제이다 -> 짝수개 일 시 더 작은 값 출력 풀이 내 풀이 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q1655 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuild..
[Baekjoon] 2170: 선 긋기
[Baekjoon] 2170: 선 긋기
2023.03.02문제 선을 정해진 횟수만큼 긋고 최종 길이를 구하는 단순 스위핑 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; public class Q2170 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer..
[Baekjoon] 9935: 문자열 폭발
[Baekjoon] 9935: 문자열 폭발
2023.03.02문제 대상 문자열과 삭제할 문자열이 주어지면, 대상 문자열에서 삭제할 문자열이 더 이상 없을 때까지 계속 삭제해나가는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main9935 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.readLine(); // 대상 문자열 String deleteStr = br.readLin..
[Baekjoon] 16934: 게임 닉네임
[Baekjoon] 16934: 게임 닉네임
2023.03.02문제 닉네임의 접두사를 계속 체크하여 중복없이 별칭을 만들도록 하는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class Main16934 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.i..
[Algorithm] 프림 알고리즘(Prim's algorithm)
[Algorithm] 프림 알고리즘(Prim's algorithm)
2023.02.28프림 알고리즘(Prim's algorithm)? 프림 알고리즘은 임의의 정점부터 시작하여 해당 정점에 연결된 가장 작은 가중치의 간선을 선택하며 확장해나가서 최소 신장 트리를 만드는 알고리즘이다. 구현 탐색을 시작할 임의의 정점을 하나 선택한다. 선택한 정점과 인접하는 정점 중 최소 비용의 간선을 갖는 정점을 선택한다. 모든 정점이 선택될 때 까지(n-1 개의 간선을 가질 때 까지) 반복한다. 동작 과정 코드 다음 코드는 baekjoon: 1197 - 최소 스패닝 트리를 기준으로 작성하였다. 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B..
[Algorithm] 다익스트라(Dijkstra)
[Algorithm] 다익스트라(Dijkstra)
2023.02.26다익스트라(Dijkstra)? 다익스트라(Dijkstra) 알고리즘은 에츠허르 다익스트라가 고안한 알고리즘으로, 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 대표적인 최단 경로 알고리즘이다. 특징 그래프 방향의 유무는 상관 없으나, 간선들 중 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없다. 음의 가중치를 가지는 간선이 있으며, 가중치 합이 음인 사이클이 존재하지 않는 경우 벨만-포드 알고리즘을 사용할 수 있다. 또한 그래프 내에 가중치 합이 음인 사이클이 존재한다면 무한히 음의 사이클을 도는 경우 경로 합이 음수 무한대로 발산하기 때문에 그래프 내의 최단 경로는 구성할 수 없다. 구현 P[A][B]는 A와 B사이의 거리라고 가정한다. 출발점으로부터 최단거리를..
[Baekjoon] 1138: 한 줄로 서기
[Baekjoon] 1138: 한 줄로 서기
2023.02.26문제 각 index 번째에 있는 사람들의 왼쪽에 자기보다 큰 사람이 몇 명 있는지 주어지면, 각 사람들의 번호를 위치 순서로 출력하는 문제이다. 풀이 내 풀이 public class Q1138 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); List numbers = new ArrayList(); int n = Integer.parseInt(br.readLine()); String[] leftCounts = br.readLine().split(" "); for (int i = n - 1; i >= 0; i--) ..
[Algorithm] 크루스칼 알고리즘 (Kruskal Algorithm)
[Algorithm] 크루스칼 알고리즘 (Kruskal Algorithm)
2023.02.19크루스칼 알고리즘 (Kruskal Algorithm)? 크루스칼 알고리즘은 그래프 내의 모든 간선의 가중치를 확인하고 가장 작은 가중치부터 확인해서 최소 신장 트리를 만드는 알고리즘으로, 탐욕적인(greedy) 방법을 통해 구현할 수 있다. greedy? 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 한다. 크루스칼 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다. 구현 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. 가장 낮은 가중치를 먼저 선택한다. 사이클을 형성하는 간선을 제외한다. 해당 간선을 현재의..
[Algorithm] 유니온-파인드(Union-Find)
[Algorithm] 유니온-파인드(Union-Find)
2023.02.19유니온-파인드(Union-Find)? Union-Find는 여러 개의 노드가 존재할 때, 어떤 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 방법 같은 그래프에 속하는지 어떻게 판별할까? 다음 그림을 보고 쉽게 이해하자 먼저 8개의 노드가 위와 같이 있다고 가정한다. 각 노드는 자기 자신을 가리키며 이는 자기 자신이 곧 루트 노드임을 의미한다. 여기서 5와 2가 연결되었다고 해보자. 그럼 다음과 같이 표현할 수 있다. 5번 노드에 2번 노드를 가리키는 값 2가 들어간다. 일반적으로 합칠 때는 더 작은쪽으로 합치며 이를 Union이라 한다. 그 다음 2와 1이 연결되었다고 해보자. 2번 노드는 1번 노드를 가리키며 이를 의미하는 값 1이 들어간다. 그럼 여기서 5번과 1번이 같은 그래프에 속하는..