Algorithm/BOJ
-
[BOJ] - 11437번Algorithm/BOJ 2022. 9. 15. 00:46
문제 [BOJ] - 11437번 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 이해 더보기 문제 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트..
-
[BOJ] 1753번 - 최단경로Algorithm/BOJ 2022. 8. 31. 00:51
문제 BOJ 1753번 최단 경로 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 문제 이해 더보기 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까..
-
[BOJ] 2283번 - 구간 자르기Algorithm/BOJ 2022. 7. 6. 15:13
[BOJ] 2283번 - 구간 자르기 문제 푼 방식과 어떻게 풀었는지에 대해 설명하여 보겠습니다. 문제 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2283 2283번: 구간 자르기 1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다. www.acmicpc.net 문제 이해 처음 문제를 이해한 바로는 N 은 1000까지 K는 10억까지로써, K로 나누어질 수 있는 좌우 부분을 구하라는 문제로 이해하였습니다. 이에 따라 10억까지의 숫자 범위에서 메모리적으로 투포인터로 범위를 구하..
-
[BOJ] 2461번 - 대표 선수Algorithm/BOJ 2022. 7. 5. 23:43
[BOJ] 2461번 - 대표 선수 https://www.acmicpc.net/problem/2461 2461번: 대표 선수 입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 www.acmicpc.net 문제 이해 문제는 N개의 반에 M명씩 있을 때 각각의 학생들을 선택하여 최대 최소 구간이 적게 만드는 문제 알고리즘 문제는 N개의 반에 M명씩 있을 때 각각의 학생들을 선택하여 최대 최소 구간이 적게 만드는 문제이다. 1. 접근 시에는 각 N개의 List를 Heapq로 구현 -> 맨 앞에 있는 값들을 매번 갱신하며 찾아보았지만, 시간 초과가 발생..
-
[BOJ] 20922번 - 겹치는 건 싫어Algorithm/BOJ 2022. 6. 29. 12:16
오늘 풀어본 문제는 [BOJ] 20922번 - 겹치는 건 싫어 입니다. https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 알고리즘 위 문제는 연속되는 부분 수열 중에서 특정 숫자가 K개 아래인 경우 중 제일 긴 길이를 선택하면 됩니다. N의 범위는 10만 a의 범위는 10만으로써, 메모리가 1024MB임으로 여유가 있으니 해당 범위만큼 길이를 선언하고 시작해도 무방할 것으로 보입니다. 한번만 순회하면서 가장 긴 경우의 수를 찾기 위해 투포인..
-
[BOJ] 13144번 - List of Unique NumbersAlgorithm/BOJ 2022. 6. 22. 15:41
[BOJ] 13144번 - List of Unique Numbers https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 문제 이해 수열에서 연속되게 1개 이상 뽑는 경우에서 같은 수가 등장하는 경우는 제외하고 갯수를 세라. 여기서 중요한 점이 "연속"과 "같은 수"이다. 알고리즘 처음 문제를 보자마자 투포인터로 풀어야겠다는 생각을 하였다. 각 시작점에서 같은 수가 없이 등장하는 뒷단계를 알면 한번에 계산이 되기 때문이다. 처음에는 Left , Right를..
-
[BOJ] 2110번 - 공유기 설치Algorithm/BOJ 2022. 6. 20. 23:14
[BOJ] 2110번 - 공유기 설치 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 접근 방식(틀린 풀이) 해당 문제는 풀어본적 있는지 여부에 따라 풀 수 있는지 여부가 달라질 것으로 보인다. 처음에는 공유기를 맨 앞과 맨뒤로 부터 놓은 다음에 하나씩 증가 시키며 Devide 시켜 그 중에 max된 값을 추출하여 값을 구하는 방식으로 구현하였다. 하지만 위와 같은 방식은 O(N^2)이 소요되..
-
[BOJ] 8980번 - 택배Algorithm/BOJ 2022. 6. 20. 17:36
[BOJ] 8980번 - 택배 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 알고리즘 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다. 최대한 많은 박스들을 가져가야 함으로 그리디 알고리즘으로 생각하여 구현하였습니다. 처음에는 Truck을 Time에 따라 구현하였으나, 시간 복잡도가 부족하여 75점이 나왔기 때문에 후에 정렬된 박스들의 표를 보고 얼마나 보낼 수 있는지로 구현하여 O..