15460-My Cow Ate My Homework 수열 arr가 주어지고 소는 수열의 숫자를 앞에서부터 최소 1개부터 최대 n개까지 먹어서 없앨 수 있다. 그리고 없앤 뒤의 수열들 중에서 가장 작은 수 하나를 삭제한 뒤 나머지 값들의 평균(합/개수)을 구해서 그 평균의 값이 가장 크게 되도록 하려면 질문을 몇 개 먹어야 하는지를 묻고 있다.(그 개수가 여러개라면 오름차순으로 모두 출력한다)단순 구현문제로, 루프로 1개 없애는 경우부터 n개 없애는 경우까지 모두 살펴봐서 평균값을 계산해보면 된다. 일단 평균을 구하기 위해서는 먹어치운 k개를 제외한 나머지 (k+1)~n번째에서 가장 작은 값을 제외한 나머지의 합을 구한 뒤, 개수로 나눈 값이 평균이 되고, 평균의 최대값을 저장하는 변수와 일일이 비교해서 ..
15465-Milk Measurement(Bronze)(set) 각 날짜마자 소의 우유 생산 변동량이 제시되고, 그동안 우유 생산량이 가장 많은 소는 변동이 총 몇 번 일어나는지 묻고있다. 우선 day를 오름차순으로 정렬한 뒤, 매 변동량을 update해준다.여기서 우유 생산량이 가장 많은 소가 둘 이상일 수도 있다. 그럴 때는 여러 소를 동시에 포함해야 하므로 stl set을 사용했다. 따라서 내가 고려해야할 문제는 매 day마다 set의 원소가 이전 day보다 같은지 아닌지만 확인하면 된다. 처음에 두 set의 원소가 일치하는 지의 여부를 직접 구현했는데, 찾아보니 단순하게 == 연산자를 쓰면 된다고 한다. set(a) == set(b) 는 set인 a와 b의 원소가 모두 일치하면 true, 하나라도..
15464-The Bovine Shuffle(Bronze) 셔플 규칙 수열과 이 규칙을 기준으로 3번 셔플된 후의 order를 알려주고, 이 결과를 바탕으로 셔플 하기 전인 처음 상태의 order를 유추하는 문제다. 3번 셔플된 후를 알고 있으니 거꾸로 거슬러 올라가면서 2번->1번->처음 이렇게 order를 갱신해주면 된다.만약 3번 셔플의 결과가 a b c d e 이고,셔플 규칙이 1 3 4 5 2이면 그 직전(2번 셔플)은 a c d e b가 되는 식이다. 12345678910111213141516171819202122232425262728#include#define SIZE 101int n,arr[SIZE];int order[4][SIZE];int main(){ scanf("%d",&n); for..
임의의 n개의 수 중에서 k번째로 큰 수(혹은 작은 수)를 찾으려면 어떻게 해야 할까? 가장 단순한 방법으로는 n개를 모두 정렬한 뒤 앞이나 뒤에서부터 k번째 있는 수를 찾으면 된다. 아니면 크기가 k짜리의 최소 힙(최대 힙)을 이용할 수도 있다. 그런데 사실 이것들은 조금 꼼수같다는 기분이 든다. 꼼수부리지 않는 정석적인 알고리즘이 바로 Quick Selection 알고리즘이다. 이 알고리즘은 Quick Sort 알고리즘을 약간 변형시킨 알고리즘이다. Quick Sort 알고리즘은 pivot을 하나 정해서 자신의 위치를 찾아서 고정시키고 그 앞뒤로 다시 재귀호출을 통해서 수를 정렬시키는데, Quick Selection은 이때 앞뒤로 2번의 재귀 호출이 아닌 본인에게 필요한 딱 1번의 재귀호출만 하는 함..