1. 문제 초단위로 기록된 주식 가격이 주어질때 가격이 떨어지지 않은 기간은 몇 초인지를 계산하여라 기록은 다음 기록이 있을시 1초가 지났다는걸 의미한다. 2. 스택 사용 모든 원소를 탐색하면서 스택에 넣는다 단, 스택에 넣기전에 top 보다 만약 해당 가격이 낮을 시 pop해주고 스택에 저장한 인덱스 벙보를 활용하여 몇초가 지났는지 파악한다. 이때 기록배열에 -1을 넣으면 자연스럽게 마지막 원소까지 해결된다. (단 -1일때 len의 길이는 -1 해줘야한다. 임의로 들어간 원소이기 때문이다.) 3. 코드 이것은 처음 제출한 코드인데, 인덱스 0을 따로 스택에 먼저 넣지 않아도 잘작동한다. 즉, 필요없는 코드를 작성했다는 것 이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

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