📚 문제 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 🔍 아이디어 공통 조상을 찾는 문제입니다. 각 노드의 깊이를 먼저 BFS, DFS를 이용하여 계산합니다. (이때 부모 노드도 함께 지정해줍니다, parents 배열) 이후에 a,b 노드의 공통 조상을 찾는 경우 a의 깊이, b의 깊이를 비교하여 두 노드의 깊이가 동일할 때까지 부모로 이동하며 올라옵니다 두 노드의 깊이가 같아졌으면 두 노드를 함께 부모로 노드로 올리는것을 반복합니다...
📚 문제 https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 🔍 아이디어 mst를 활용하여 풀이하였습니다. *(다른 분들과 풀이가 달라 맞는 풀이인지 확신이 들지 않습니다. 참고 부탁드립니다) 가장 힘이 드는경우는 가장 많은 경사로(같은 길이 나오지 않기때문)를 이용하는 경우라고 생각하였습니다 따라서 먼저 경사로를 이용하는 경우의 모든 경로를 연결합니다. 이때 연결된 경사로의 개수의 제곱이 점수가 됩니다. 가장 ..
📚 문제 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 🔍 아이디어 bfs로 해결하였습니다. 한 타임에는 불이 퍼지는 경우와 내가 이동하는 경우를 모두 생각해야했습니다. 또한 이번 타임에 불이 옮겨지는곳에는 자신이 이동하면 안된다는 조건이있습니다. 저의 경우 불이 옮겨 붙어지는 경우를 모두 계산한 후에 이동하지 않고 이동할 수 있는 모든 경우를 이동한 후에, 불이 이동하도록 하였습니다. 이렇게 한 후 다음턴에 자신의 위치가 불로 변한 경우 해당 칸은 이전에 갈 수 없던 칸이었는데 이동한것으로 하여 무시하는 방식으로 진행..
📚 문제 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 🔍 아이디어 완탐으로 i번째 에서 연속해서 먹을 수 있는 만큼 (i+k)만큼을 모두 확인하는 방식으로 풀어도 통과합니다. 저는 슬라이딩 윈도우 방법을 이용해서 풀었습니다 시작 시에 해시에 초기에 k만큼의 접시와, 쿠폰을 이용해 먹은 초밥을 미리 넣어둡니다. 저의 경우 이때 hashmap을 사용하여 먹은 스시를 셌는데 bucket을 이용한 풀이도 가능..
📚 문제 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 🔍 아이디어 투 포인터를 활용하여 해결하였습니다. 정렬 이후에 만약 최단 값 범위 보다 작다면 right를 오른쪽으로 옮겨서 두 수의 차이를 벌리고 만약 최단 값 범위보다 크다면 기존의 diffMin값과 비교하여 더 작은값을 가지도록 생긴하고 두 수의 차이를 줄이기 위해 left를 한칸 오른쪽으로 옮겼습니다. 해당 방법 풀이를 시간을 비교해보니 속도가 다른 분들보다 조..
📚 문제 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 🔍 아이디어 플로이드 알고리즘과, 플로이드 알고리즘의 최단 경로 시에 방문했던 도시들을 찾으면 되는 문제였습니다. p ➡️ q로 가는경우 i를 거쳐서 ( p ➡️ i , i ➡️ q) 가는 경우로 최단 경로를 계산 합니다. 이때 만약 최단 경우로 갱신되는 경우 방문했던 도시의 리스트를 갱신하는 방식으로 풀어 해결하였습니다. 99%에서 틀렸습니다가 나왔었는데, 이 문제는 만약 dMap[..
📚 문제 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 🔍 아이디어 처음에 보고는 우선수위 큐를 이용해서 푸는 문제풀이가 생각났다. 근데 어차피 먼저 들어가는 게 먼저 나오니까 그냥 큐로 풀이했다 트럭이 다리에 입장한다면 해당 트럭의 무게와 다음 차례 트럭 무게의 합에 따라 다음 트럭이 입장할 수 있는지가 정해진다. 그리고 한 타임에는 하나의 트럭만 다리에 입장할 수 있다. 트럭은 큐에서 빼는 ..
📚 문제 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 🔍 아이디어 처음에는 그냥 기본적인 bruteforce풀이를 진행하였다. 골드 문제에 어울리지 않는다고 생각했는데 바로 시간초과가 났다. 이 풀이를 그대로 멀티버스 1번에 넣으니 통과되었다(브론즈 5) 못풀겠다 하고 침대에 누워있었는데 각 행성에 등수를 매기고 그 등수가 동일한 우주가 있다면 동일하게 균등하다고 할 수 있을 것 같다는 생각이 들었다. 그래서 싹 정렬을 하고 등수를 매겼다. 등수를 매길때 동일한 숫자는 동일한 등수를 주어야 하기 때문..
📚 문제 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 🔍 아이디어 최대한 적은 강의실을 사용하여 모든 수업을 할 수 있도록 하는 문제입니다. 처음 문제를 읽었을때는 그리디 문제로 생각하고 끝시간을 기준으로 정렬하고 모든 경우를 확인하였으나 그렇게 하면 시간 초과가 발생합니다. 다른 문제 풀이방법은 강의를 입력받는 경우 시작시간, 끝 시간을 구분하여 입력받고 시작시간인 경우에는 필요한 강의실이 하나 증가, 끝 시간인 경우는 필요한 강의실이 하나 감소하도록 하여 한 시점에 최대 몇개의 강의실이 ..
📚 문제 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 🔍 아이디어 원웅이가 놓을 수 있는 파이프라인의 최대 개수를 출력하는 문제입니다. 해당 문제를 읽으면서 가장 많은 파이프라인을 연결하기 위해서는 가장 위쪽에 있는것이 최댓값을 구하는경우라 생각했습니다. 갈수 있는길은 대각선위, 옆,대각선 아래이고 각 길에 대한 탐색을 진행합니다. 각 길을 가는경우 경로가 가능한지 확인하고 만약 노선하나가 연결되어 true를 리턴한다면 나머지 경로에 대해서는 탐색하지 않고 리턴합니다. 해당 문제의 포인트는 한번 방문했던 곳은 다시 방문하..
