목록백준/Gold (8)
후라이
https://www.acmicpc.net/problem/1753 해당 백준 문제는 다익스트라 알고리즘을 사용한, 최단 경로를 구하는 문제이다.우선, 다익스트라 알고리즘에 대해 설명해보도록 하겠다. 1. 다익스트라 알고리즘이란?https://www.youtube.com/watch?v=pVfj6mxhdMw 첨부한 유튜브 영상을 통해 쉽게 이해할 수 있지만다익스트라(Dijkstra) 알고리즘은 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 찾는 알고리즘이다.이 알고리즘은 비음수 가중치를 가진 그래프에서만 사용할 수 있다. - 방향 그래프 또는 무방향 그래프- 각 간선에 대한 비음수 가중치- 시작 정점 위 세가지가 주어지면, 시작 정점에서 모든 정점까지의 최단 거리를 구하면 된다.여기서 간선 가중치..
https://www.acmicpc.net/problem/2206 입력첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.출력첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다. 해당 백준 문제는 BFS를 심화한 문제로, NxM의 숫자 맵에 1이 존재할 경우(벽이 존재할 경우), 이 벽을 허물 수 있다는 경우의 수까지 포함하여 최단 거리를 구하는 문제이다. 단, 벽은 한번만 허물 수 있다.만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 우선, 기존의 BFS 최단거리 문제 틀에서 ..
https://www.acmicpc.net/problem/1707 해당 백준 문제는 이분 그래프 판별 문제이다.BFS, DFS 문제를 꾸준히 풀었다면 쉽게 풀이할 수 있을 것이다. 이분 그래프란?: 그래프의 정점들을 두 개의 집합으로 나누었을 때, 각 집합에 속한 정점끼리는 서로 간선으로 연결되지 않으며두 집합에 속한 정점들끼리만 간선으로 연결된다는 것. (1) 정점 집합 분할 : 이분 그래프는 정점들을 두 개의 집합으로 나눌 수 있다.즉, 집합 A와 집합 B가 있고, 각 간선은 집합 A의 정점과 집합 B의 정점 간에만 존재한다. (2) 인접 정점 : 두 집합에 속한 정점들은 서로 인접해야 하며, 같은 집합에 속한 정점들끼리는 인접하지 않다. 이분 그래프인지 아닌지를 탐색하는 데에는 BFS, DF..
https://www.acmicpc.net/problem/17299 해당 백준 문제는 오등큰수를 스택 알고리즘을 사용해 풀이하는 문제이다.예시를 보면 어떤 문제인지 이해할 수 있다. 우선 문제에 맞게1. N개의 수를 저장할 배열2. 배열 내에서 특정 숫자가 몇 번 등장했는지 frequency를 저장할 배열3. NGF를 저장할 배열 을 만들어주면 된다. int N = Integer.parseInt(br.readLine()); int[] A = new int[N]; int[] NGF = new int[N]; // 결과 배열 int[] freq = new int[1000001]; // 등장 횟수 기록 배열 StringTokenizer st =..