코테준비

문제 Gold5 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 풀이 시작점에서 모든 정점까지의 최단경로를 구하는 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘 구현 - 시작점에서부터 방문여부와 시작점부터의 최소 경로 정점을 탐색 - 최소 경로 정점 탐색 후, 해당 정점에 대한 distance배열(해당 정점을 경유해서 갈 수 있는 최단 거리)을 재설정 그래프 정보를 처음 인접행렬로 풀었으나 테케의 크기가 매..

문제 Silver1 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 사방탐색 중 깊이우선탐색(DFS)를 사용하여 해결 기본 DFS코드에 단지 내 집의 수를 저장 할 cnt배열을 추가하였다. 따로 배열을 만들어 준 이유는 마지막에 sort를 해야하기 때문. 코드 더보기 import java.io.*; import java.util.*; public class Main{ static int N, idx; static int[][] arr; st..

문제 Gold5 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 같은 색이 상하좌우 한곳이라도 인접해있으면 같은 area로 되므로, 깊이우선탐색을 통해 같은 구역을 확인한다. 문제에서 '같은 색상이 상하좌우로 인접해 있는 경우'라고 되어 있어서 상하좌우에 모두 인접해있어야 한다고 생각했었다...┗|｀O′|┛ 일반인이 보는 구역을 확인하기 위해 입력받은 배열 그대로 DFS를 돌린다. DFS를 돌리면서, 'G'색을 만나면 해당 인덱스에..

문제 Gold5 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 우선순위 큐(PriorityQueue) 활용 우선순위 큐란? 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조 문제에서는 강의가 가장 일찍 끝나는 강의실이 우선순위로 배정되어야 함(PriorityQueue Default) 강의의 start와 end를 int[]로 입력받아 저장.끝나는 시간을 기준으로 오름차 순 정렬.첫 번째 원소의 endTime을 큐에 먼..