1. 문제 n개의 노드가 있는 그래프 => 각 노드는 1부터 n까지 번호가 적혀있다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고한다. 가장 멀리 떨어진 노드란 최단 경로로 이동햇을 때 간선의 개수가 가장 많은 노드를 의미한다. 노드의 개수 n은 2 이상 20,000이하이다. 간선은 양방향이며 총 1개이상 50,000개 이하의 간선이 있다. vertex 배열 각 행 [a, b] 는 a번 노드와 b번 노드 사이에 간선이 있다는 의미이다. 2. 너비우선 탐색 그래프의 최단거리를 구하는 방법은 여러가지가 있다. 그 중 한점을 기준으로 하는 탐색방법은 bfs O(|V| + |E|)를 이용하는것과 bfs에 우선순위큐를 활용한 다익스트라 O(ElgV) , 간선을 기준으로 업데이트하여 구하는 벨만 포드 O..

1. 문제 사용할 수 있는 숫자들과 타겟 넘버가 주어진다. 사용할 수 있는 숫자들 모두 사용하여 타겟넘버를 만들어라 단, 이때 연산은 +, - 만 가능하다. 2. 핵심 이 문제의 핵심은 사용할 수 있는 숫자들 모두를 사용하는 것이다. 처음에는 순서도 포함하여 세는줄 알았지만 순서는 필요없다는 것 그냥 숫자를 사용하기만 하면된다는 것이다. 모든 숫자를 사용해야하므로 재귀를 통해 모든 숫자를 탐색하면서 + 이나 - 를 해주며 마지막 숫자일때 타겟넘버와 동일한지 검사한다. 이는 dfs형태로 이루어지며 혹시모를 겹치는 부분을 대비하여 dp 를 적용시킬 수 있다. (실제로 테스트 1 과 테스트 2의 경우 시간이 빨라진다.) 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..

1. 문제 반 학생들의 체육복이 도난당했다. 도난당한 학생의 번호와 여유분을 가진 학생의 번호가 주어진다. 여유분을 가진 학생이 도난당한 학생에게 체육복을 빌려줄때 체육복을 최대한 나눠주고, 체육수업을 들을 수 있는 최대 학생수를 구하여라 단, 체육복은 자신의 앞뒤 번호한테만 빌려줄 수 있다. 단, 여유분을 가지고 있던 학생이 도난당했을 수 있다. 그러면 빌려주지 않는다. 2. 자원분배 문제: 네트워크 플로 이 문제는 이분 그래프의 최대매칭 문제로 네트워크 플로로 풀 수 있다. 여유분 그룹에서 도난 그룹으로가는 그래프를 그린 후 네트워크 플로우 알고리즘을 사용하면 문제가 해결된다. 단, 여유분을 가지고 있던 학생이 도난당할경우 그래프를 그리지 않는다. 1 2 3 4 5 6 7 8 9 10 11 12 13..

1. 문제 모든 음식의 스코빌 지수를 K 이상으로 만들어야한다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다. 섞으면 새로운 음식이 된다. 가장 작은 섞는 횟수를 구하여라 2. 우선순위 큐- 힙 우선순위 큐로 가장 작은것을 골라낼 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include #include #include using namespace std; int solution(vector scoville, int K) { int answer = 0; priority_queu..

1. 문제 참가자 명단과 완주한 참가자 명단이 주어질때 완주하지 못한 참가자 한명을 찾아라 단, 동명이인이 존재할 수 있다. 2. map map 의 valu값을 동명이인을 가진 사람의 수로 두었다. 초기값을 1로 설정해두고 참가자의 값을 -1 씩하는 것이다. 그러면 0이 아닌 참가자가 정답이 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include #include #include #include using namespace std; string solution(vector participant, vector completion) { map dic; std::pair isFail; for(int i = 0; i

1. 문제 일차선의 다리의 길이, 다리가 견딜 수 있는 무게가 주어진다. 트럭이 주어진 순서대로 1초에 다리 길이 1 만큼 움직인다고 할때 최소 걸리는 시간을 구하여라. 2. 자료구조 queue 제한 무게 10인 다리에 트럭이 다음과 같은 순서로 온다고 해보자 7, 4, 5, 6 그럼 다음과 같이 나타낼 수 있다 7 7 0 7 0 4 7 0 4 5 7 0 4 5 0 7 0 4 5 0 6 7 0 4 5 0 6 0 7 0 4 5 0 6 0 0 답: 8 빨간색 이 다리위에 있는 트럭들을 보여준다. 결과로 나오는 배열 7, 0, 4, 5, 0, 6, 0, 0 의 크기가 정답이 됨을 알 수 있다. 그러므로 주어진 순서에 맞게 큐에 집어넣으면서 만약 무게가 초과되면 0인 더미 값을 집어넣고 길이가 초과되면 pop하..