알고리즘

[C++] 백준 - 1202 : 보석 도둑

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 풀이 이 문제는 가장 가격이 높은 순서대로 보석들을 정렬해서, 높은 순서대로 가방에 넣으면 됩니다. 이 때 넣을 가방은 현존하는 가방중에서 1. 가장 작으면서 2. 보석을 담을 수 있어야 합니다. 배열에 담으면서 매번 정렬하면서 진행한다면, 시간초과가 날 것입니다. 시간제한은 1초이므로 O(NlogN) 의 시간복잡도를 가질 수 있게..

[C++] 백준 - 1655 : 가운데를 말해요

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 풀이 숫자가 주어질 때 지금까지의 숫자 중 중앙값을 출력해야하는 문제입니다. 단순히 숫자가 주어질때마다 정렬을 사용하면 시간초과가 날 것 입니다. 주어진 시간이 0.1초이기에 약 천만번(10000000)이고, N=100000 이기에 100N 정도의 연산이 가능합니다. 즉 NlogN의 연산으로 이를 해결해야합니다. N번의 숫자가 주어지기에 각 숫자가 주어질 때 마다 중앙값을 찾..

[C++] 백준 - 1181번 : 단어 정렬

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 주어진 문자열을 1. 길이 순 2. 길이가 같은 경우 사전 순 으로 정렬하여 출력하는 문제입니다. 풀이 벡터에 string을 넣고 sort 함수를 통해 정렬을 합니다. 첫번째 정렬 조건은 길이 순이고, 그 다음 조건이 사전 순이므로 둘을 비교할 수 있는 함수 두 개를 만듭니다. bool compareDic(string a, string b, int i) { if (int(a[i])..

[C++] 백준 - 11866번 : 요세푸스 문제 0 풀이

https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 풀이 이 문제는 Queue를 이용하여 풀 수 있습니다. 원형의 테이블을 펼쳐서 기다란 막대기에 넣는다고 생각합니다. 여기서 기다란 막대기가 Queue입니다. 1~N까지의 사람을 Queue에 넣습니다. Queue의 front를 pop하며 그 사람이 K번째인지 확인합니다 K번째가 맞다면 그대로 출력하고, 그렇지 않다면 다시 Queue에 넣습니다. Queue가 빌 때까지(=모든 사람들을 확인할 때까지) 위의 과정을 반복합니다. 아래는 위의 과정을 N=7일때로 하여 그림으로 표현한 것입니..