문제 https://programmers.co.kr/learn/courses/30/lessons/43238 풀이 처음에 문제풀이 방법을 떠올리기 쉽지 않은 문제다. 풀이 시 다음 사람을 어떤 심사관에 배정할까 ? 라는 의문으로 시작하면 가능한 방법이 떠오르지 않는다. 이 문제는 파라메트릭 서치 개념을 사용해서 풀이할 수 있다. 파라메트릭 서치란 최적화 문제를 결정 문제로 바꾸어서 풀이하는 개념이다. 이 문제의 경우 "심사시간이 주어졌을 때, N명의 사람을 모두 심사할 수 있는가?" 라는 내용으로 주어진 시간 범위 내에서 이분탐색을 진행하며, N명의 사람을 심사할 수 있는가? 를 확인 후 N명의 사람을 모두 심사할 수 있는 시간들 중 최소값을 정답으로 결정하면 된다. 소스 코드 #include #inclu..
문제 https://programmers.co.kr/learn/courses/30/lessons/49189 N개의 노드 중 1번 노드와 가장 먼 거리의 노드수를 구하는 문제 문제 풀이 시작점이 정해져있고 최단거리로 이동할 경우 가장 먼 거리를 파악해야 한다. 1번 노드로부터 다익스트라 수행 후 가장 먼 거리를 가진 노드들의 수를 카운트하여 return 한다. 소스 코드 #include #include #include const int MAX_N = 20001; const int MAX_M = 50000; using namespace std; int solution(int n, vector edge) { vector adj[MAX_N]; int d[MAX_N]; int answer = 0; int maxD..
문제 https://www.acmicpc.net/problem/2170 풀이 시작하는 점을 1, 끝나는 점을 -1로 저장하고 스택을 이용해 겹치는 선분이 끝날 경우 길이를 구해줬습니다. 선분 A(1,3), 선분 B(4, 6) 을 예로 들면, 정점 1 스택에 push 정점 3 은 끝 점이므로 pop 하고 길이(3-1) 저장 정점 4 은 시작점이므로 push 정점 6 은 끝 점이므로 pop 하고 길이 (6,4) 저장 겹치는 경우도 손으로 해보면 올바르게 계산된다는 점을 알 수 있습니다. 소스코드 #include #include #include #include using namespace std; int n; vector points; int main(){ ios::sync_with_stdio(false..