어흥

문제 링크: https://www.acmicpc.net/problem/14588 14588번: Line Friends (Small) Q개의 줄에 걸쳐 두 선분이 가까운 정도를 출력한다. 만약, 두 선분 사이의 친구 관계가 단절되었다면 -1을 출력한다. www.acmicpc.net 1. 주의할 점 - 2개의 선분이 겹치는 조건을 잘 생각한다 - 플로이드 와샬 알고리즘에 대하여 알고 있어야한다 - 양방향 그래프이므로 플로이드 와샬을 사용할 경우, 배열의 원소를 잘 초기화 해야한다(내 코드의 경우 한번에 2개의 원소를 초기화 해야 한다) 2. 구현 - Arr[][]배열을 전부 987654321로 초기화하며, i==j인 경우에만 0으로 초기화한다 - 각 선분에 대한 정보를 입력받은 후, 2개의 선분(I,J)을 ..

문제 링크: https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으�� www.acmicpc.net 1. 주의할 점 - N^2으로 풀지 않도록 한다 -> TLE 발생 - Stack을 사용하여 풀도록 한다 2. 구현 - 모든 수들을 배열 Arr[]에 입력받으며, 가장 높은 빌딩의 높이+1을 Maxi 변수에 넣는다(가장 오른쪽에 위치한 건물의 오른쪽에 가상의 Maxi 높이만큼의 건물이 있다고 가정하고 풀기 위해 사용한다) - 건물 배열은 1~N에 담았기 때문에 N+1번째 빌딩..

문제 링크: https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n(1≤n≤100)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 www.acmicpc.net 1. 주의할 점 - 플로이드 와샬 알고리즘을 진행하면서 경로를 저장해야 빠르게 문제를 풀 수 있다 - 플로이드 와샬 알고리즘을 진행하면서 새로운 최단 경로가 생성되는 경우, I~K까지의 경로 + K~J까지의 경로를 I~J까지의 경로에 갱신해서 저장한다. 단, K가 2번 입력되지 않도록 설정한다 - 간선의 정보를 입력받을 때, I~J까지의 경로가 1가지가 아닐 수..

문제 링크: https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 1. 주의할 점 - 다익스트라 알고리즘에 대해 알고 있어야 한다 - 다익스트라 알고리즘을 수행할때, 초기화를 잘해줘야 한다 2. 구현 - 민준이가 건우를 도와서 마산에 도착하는 경우, 민준-> 건우 + 건우->마산까지의 거리가 민준->마산까지의 거리와 같을 때다(각 간선의 가중치는 1보다 큰 정수이기 때문이다) - 모든 간선에 대한 ..

문제 링크: https://www.acmicpc.net/problem/10836 10836번: 여왕벌 입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 �� www.acmicpc.net 1. 주의할 점 - 매일마다 애벌레의 크기를 바꾸면 시간초과가 발생한다 - 0,1,2의 순서로 증가하는 크기를 나타내므로, 좌, 좌상, 상과 비교할때 제일 많이 자란 애벌레는 무조건 상이다 2. 구현 - 매일 자라는 애벌레의 크기를 Order[] 배열에 담는다. 단, 1씩 자라기 시작하는 곳, 2씩 자라기 시작하는 포인트에서만 ++한다 - 왼쪽과 상단의 ..

문제 링크: https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위�� www.acmicpc.net 1. 주의할 점 - 플로이드와샬 알고리즘을 통해 미리 각 Node간 최단거리를 구해놓는다 2. 구현 - 각 Node간의 거리를 입력 받은 후, 플로이드 와샬 알고리즘을 사용하여 각 Node간 최단거리를 구한다 - 시작하는 행성의 Visit[]값을 True로 바꾼후, DFS()를 수행한다 - DFS(int idx, int dist, int planet) 함수는 각각 현재 행성,..

문제 링크: https://www.acmicpc.net/problem/10021 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 1. 주의할 점 - MST문제로, MST 생성할 수 없다면 -1을 출력한다 2. 구현 - 크루..

문제 링크: https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 문제 농부 존은 남는 시간에 MooTube라 불리는 동영상 공유 서비스를 만들었다. MooTube에서 농부 존의 소들은 재밌는 동영상들을 서로 공유할 수 있다. 소들은 MooTube에 1부터 N까지 번호가 붙여진 N ( www.acmicpc.net 1. 주의할 점 - 시작하는 정점은 세지 않는다 2. 구현 - 그래프에 대한 정보를 V[] 벡터에 입력한다 - Query문 마다 Result, Visit[] 배열을 초기화하고 시작한다 - While문을 통해 방문하지 않은 Node중에서 간선의 값이 입력 받은 유사도의 값이상이면 큐에 추가하며 Result++한다 #include #incl..