어흥

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/84325 코딩테스트 연습 - 4주차 개발자가 사용하는 언어와 언어 선호도를 입력하면 그에 맞는 직업군을 추천해주는 알고리즘을 개발하려고 합니다. 아래 표는 5개 직업군 별로 많이 사용하는 5개 언어에 직업군 언어 점수를 부 programmers.co.kr 1. 주의할 점 - 차례대로 완벽하게 구현한다 - 우선순위큐와 Map을 활용한다 2. 구현 - Table 벡터에 있는 정보들을 각각 V 벡터와 M[] 맵에 담는다. 맵에 담는 이유는, M[][언어]를 검색했을 때, 보다 빠르게 검색이 되기 때문이다 - 5개의 직업군에 대해 각각의 언어와 선호도를 계산하여 우선순위큐에 넣는다. 이때, 우선순위큐는 총점..

문제 링크: https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 1. 주의할 점 - 홀수번째마다 정렬해서 중앙값을 구하지 않는다 2. 구현 - 2가지의 우선순위 큐를 사용한다(오름차순 정렬, 내림차순 정렬 각각 1개씩) - 중앙값을 기준으로 왼쪽에는 내림차순으로 정렬된 Left 우선순위큐를, 오른쪽에는 오름차순으로 정렬된 Right 우선순위큐가 있다고 가정한다 - 홀수번째마다 Right와 Left의 크기를 비교하며 만약..

문제 링크: https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 1. 주의할 점 - Int의 범위를 벗어날 수 있다 2. 구현 - 우선순위큐를 사용한다. 이때, 오름차순 정렬을 적용시킨다 - 값이 가장 낮은 2개를 더하는 것이 최소의 값을 가지므로 우선순위큐의 앞 2개 원소를 빼서 더하고 추가한다 #include #include #include using namespace std; int main() { ios..

문제 링크: https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 1. 주의할 점 - TLE가 나지 않도록 한다 2. 구현 - 덱이나 우선순위큐를 사용하여 해결한다 - 모든 원소를 입력받을 때, 삽입을 수행한다 - 우선순위 큐의 크기가 Len만큼 길지 않다면, 출력만 수행한다 - 우선순위 큐의 크기가 Len보다 크거다 같다면, While문을 통해 우선순위큐에서 제거작업을 수행한다. 이때, Top에 존재하는 원소가 현재..

문제 링크: www.acmicpc.net/problem/15971 15971번: 두 로봇 입력에서 두 번째 줄에 주어지는 방번호는 1과 2, 세 번째 줄에 주어지는 방 번호는 2와 3, …, i번째 줄에 주어지는 방 번호는 i-1과 i, …, N번째 줄에 주어지는 방 번호는 N-1과 N이다 (아래 입력과 www.acmicpc.net 1. 주의할 점 - 다익스트라 알고리즘에 대해 알고 있어야 한다 - O(NlgN)에 끝내도록 한다 2. 구현 - 같은 통로에 있을때까지 이동한다 → A에서 B까지 이동한다 - 1개의 변을 뺀다 → 빼는 1개의 변이 최단경로중 가장 값이 크면 움직인 거리가 최소가 된다 → 다익스트라 알고리즘 + 변의 최장 길이 저장 - Dist[] 배열을 통해 시작지점에서 각 지점까지의 최단거..

문제 링크: www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 1. 주의할 점 - 모든 강의에 대한 정보와, 현재 진행중인 강의를 어떻게 정렬할 것인지 잘 계획한다 2. 구현 - 모든 강의를 우선순위 PQ에 담는다. PQ의 경우, 시작시간이 빠른순으로 정렬하며, 시작시간이 같은 경우 종료 시간이 빠른 순으로 정렬한다. 종료시간을 1순위로 할 경우, 아래 TC에서 오답을 받게된다 TC #1 6 1 9 2 11 3 11 4 11 12 15 9 17 Answer: 4 - 현재 강의중인 강의실을 PQ2로 설정하고,..

문제 링크: www.hackerrank.com/challenges/primsmstsub/problem?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign Prim's (MST) : Special Subtree | HackerRank Learn to use Prim's algorithm ! www.hackerrank.com 1. 주의할 점 - MST중에서 프림 알고리즘에 대해서 알고 있어야 한다(Edge수가 Node수보다 월등히 많을 때 유리. 반대의 경우, 크루스칼이 유리) 2. 구현 - 간선에 대한 정보를 V[] 벡터에 모두 저장한다 - 간선의 가중치를 기준으로 오름차순으로 정렬되는 우선순위큐 PQ를 생성한..

문제 링크: www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1≤N≤1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점이 주어진다. 선택한 지점은 -1,000,000,000 이상 1,000,000,000 이하의 정수이다. www.acmicpc.net 1. 주의할 점 - 왼쪽에 대한 오름차순으로 정렬 이후, 오른쪽에 대한 오름차순 정렬을 진행한다 - 입력 받을때, 처음 받는 수가 항상 왼쪽에 위치한다고 보장할 수 없다 2. 구현 - S(Start)에 대해서 오름차순으로 정렬 -> E(End)에 대해서 오름차순 정렬을 진행하는 우선순위큐를 생성한다 - 각 점에 대해서 입력받을 때, 작은 값을 S, 큰 값을 E에 할당한 이후 ..