어흥

문제 링크: https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 1. 주의할 점 - 매 쿼리마다 통행을 바꿔야하는 횟수를 구하지 않는다 2. 구현 - Arr[][] 배열을 통해 간선에 대한 정보를 받으며, Arr[a][b]는 a->b로 가기 위해 바꿔야 하는 도로의 수를 저장한다 - Arr[][] 배열을 초기화하고, 입력받을 때 단방향인 경우에는 0,1을 저장하고 양방향인 경우에는 0,0을 저장한다 - 플로이드 와샬 알고리즘을 통해 Arr[][]..

문제 링크: https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 1. 주의할 점 - 최단경로에 사용되는 간선인지 아닌지 구분이 필요하다 - 최단경로 알고리즘에 대해 알고 있어야 한다 2. 구현 - 모든 그래프의 경로를 알기 위해 Arr[][] 배열을 생성과 초기화한다 - 최단경로가 저장된 값을 Result[][] 배열에 저장한다 - Result[][] 배열에 입력된 간선들에 대한 정보를(중복 제외) 우선순위큐에 저장한다(가중치의 오름차순으로 정..

문제 링크: https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 1. 주의할 점 - 출력값은 오름차순으로 출력되어야 한다 - 총 의사전달시간의 최소가 아닌 의사전달시간의 최대값의 최소(전체가 아닌 각각) 2. 구현 - Arr[][] 배열과 Check[] 배열을 초기화한 이후, 값을 입력 받는다 - 플로이드와샬 알고리즘을 통해 Arr[][] 배열을 갱신한다 - 1~Node번까지의 참석자들을 모두 탐색하며 Check[] 값이 False라면 DFS(i..

문제 링크: https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 1. 주의할 점 - 초기화 작업을 거친다 - 다익스트라나 플로이드와샬 알고리즘에 대해 알고 있으면 해결할 수 있다(Tree라서 DFS도 간단히 가능) import java.util.*; import java.lang.*; import java.io.*; class Main { static final int MAX = 987654321; static int node,query; public static void main (Strin..

문제 링크: programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 더보기 0. 유사 문제 www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 1. 주의할 점 - 순위가 정해져 있는 조건은? 2. 구현 - 순위가 정해져 있는 경우: 전체 N명에서 현재 위치에서 자기 앞에 A명, 자기 뒤에 B명이 있다면 A+B = N-1인 경우다(자기자신 제외) - 위의 경우를 어떻게 찾을 것인가? → 플로이드 와샬(다익스트라를..

문제 링크: www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 1. 주의할 점 - 한 학생이 자신의 순서를 정확히 아는 경우: 앞에서 몇번째인지 + 뒤에서 몇번째인지 2. 구현 - 모든 순서에 대한 정보를 V[] 벡터에 담는다. 이때, 앞에 나온 수 V[A]에 뒤에 나온 수 B를 추가한다 - 모든 학생들에 대해서 단방향 BFS를 수행하며 해당 학생이 몇명의 다른 학생에게 도달이 가능한지(자기보다 큰 사람)를 canReach[]++를 통해 저장하며, 도달당한 학생..

문제 링크: www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 1. 주의할 점 - 다익스트라나 플로이드 와샬 알고리즘에 대해 알고 있어야 한다 2. 구현 - 플로이드 와샬 알고리즘(시간복잡도: O(N^3)로 50^3 < 10^9)을 사용하여 구한다 - 간선들의 정보를 입력 받기 전, Dist[][] 배열을 1000으로 초기화한다 - 간선들의 정보를 입력받은 후, 플로이드 와샬을 통해 IJ 까지의 최소 간선 수를 구한다 - 1~N번까지의 사람들 중에서 가장 먼 ..

문제 링크: www.hackerrank.com/challenges/find-the-nearest-clone/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=graphs Find the nearest clone | HackerRank Find the shortest path length between any two nodes with the given condition. www.hackerrank.com 1. 주의할 점 - BFS를 통해 해결하여 TLE가 나지 않도록 한다 - 방문여부를 기록해둔다 2. 구현 - 모든 간선에 대한 정보를 V[] 벡터에 담는다 - Idx: 현재 Node번호, Val..