공부하는 블로그

1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 우선순위가 정해진 문제를 푸는 순서를 찾아내는 문제이다. 문제를 푸는 순서에 대한 조건은 두 가지가 있다. 1. 순서가 정해진 문제는 순서에 맞춰 풀어야 한다. ---- 위상정렬 2. 가능한 쉬운 문제(문제 번호가 낮은 문제) 먼저 풀어야 한다. ---- 우선순위 큐 import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public ..

11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net 최대 힙을 구현하는 문제이다. 직접 최대 힙을 구현해서 풀어보는 방법과 우선순위 큐도 힙의 자료구조를 가지고 있으므로 자바에 이미 구현되어있는 PriorityQueue를 이용하여 푸는 방법이 있다. 공부를 위해 직접 구현해보는 방향으로 문제를 풀어보았다. import java.util.ArrayList; import java.util.Scanner; public class Main { public static class MyMaxHeap { p..

Heap ? 힙(Heap)은 부모 노드와 자식 노드 간에는 키 값의 대소관계가 존재하는 완전 이진트리이다. 대소관계는 오로지 부모 노드와 자식 노드 간에만 성립하며 형제 사이에는 대소관계가 정해지지 않는다. 부모 노드의 값이 자식 노드의 값보다 크거나 같으면 최대 힙(Max Heap), 그 반대면 최소 힙(Min Heap)이다. * 이진트리(Binary Tree) : 한 노드가 최대 두 개의 자식노드를 가지는 트리 * 완전 이진트리(Complete Binary Tree) : 노드를 삽일할 때 왼쪽부터 차례대로 삽입하는 이진 트리이다. 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었으며 우선순위 큐를 구현할 때 주로 사용된다. * 우선순위 큐(Priority Queue) : 우선순위가 ..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 익은 토마토와 인접한 토마토는 하루의 시간이 지나면 익게 된다. 박스에 토마토가 전부 익는데 걸리는 시간을 구하는 문제이다. import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; class Main { static int N; static int M; static int[][] tomatos; static int[] dx = {-1, 0, 1, 0}; sta..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net N x M 행렬로 주어진 미로를 탐색하는 문제이다. (1, 1)에서 출발하여 (N, M)까지 도달하는데 필요한 최소 칸 수를 찾아내야 한다. import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; class Main { static int[][] maze; // 미로 static boolean visit[][]; // 방문 여부 체크 static int[] dx = {-1, 0, 1, 0}; // 시계방향으로..

1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS를 이용하여 그래프를 탐색하는 과정을 출력하는 문제이다. import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; class Main { static int n, m, v; static boolean[][] linked; static boolean[] visit; static StringBuilder sb = new String..

DFS와 BFS는 그래프를 탐색하는 방법이다. 둘의 차이를 간단히 말하자면 깊이(자식)를 우선으로 탐색하냐, 너비(형제)를 우선으로 탐색하냐 이다. DFS (Depth First Search) 깊이 우선 탐색(DFS)은 루트(root) 노드 또는 임의의 노드를 기준으로 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 즉, 한 곳을 선택하여 우선적으로 끝까지 탐색한 후에야 다른 인접한 노드를 방문할 수 있다. 이 방법은 그래프의 모든 노드를 방문하고자 할 경우 유용하다. 코드로 구현할 때에는 스택(stack)과 재귀함수를 사용한다. 재귀함수를 이용하여 DFS를 구현하는 과정은 다음과 같다. * 재귀함수 : 자기 자신을 호출하는 함수 0. 시작 노드가 없을 경우에는..

Graph ? 그래프(Graph)는 노드(N, Node)와 그 노드를 연결하는 간선(E, Edge)을 통해 정점간의 관계를 표현하는 자료구조이다. 일상 생활 속 지도나 지하철 노선도를 그래프라고 할 수 있다. 지도 어플에서 지점 간 최단 거리를 찾는 과정은 그래프를 탐색하는 과정이라 볼 수 있다. Graph 종류 그래프에서 간선은 방향성이 존재하며 화살표를 이용하여 표현한다. 간선은 순환이 가능하며 자체 간선(Self-loop)도 가능하다. 이러한 간선의 방향성과 순환성으로 그래프의 종류를 나눌 수 있다. 방향성의 유무에 따라 방향 그래프(Directed)와 무방향 그래프(Undirected)로, 순환성의 유무에 따라 순환 그래프(Cyclic)와 비순환 그래프(Acyclic)로 나뉜다. 간선에 가중치가 ..