알고리즘19 [BOJ1168] 조세퍼스 문제2 N명의 사람이 원을 이루며 앉아있고 M번째 사람을 제거하면서 진행할 때 제거되는 순서에 따른 순열을 출력하는 문제이다. 합을 저장하는 세그먼트트리를 구현한 후 합을 출력하는 squery 와 해당번쨰를 가리키는 값을 출력하는 query 를 구현한다. 환형임을 생각해야하므로 %modi 를 해주며 제거할 때 마다 인원수가 감소하므로 modi-- 를 해준다. 따라서 해당 위치를 제거해가며 res 배열에 답을 담아 출력한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include #include #include using namespace std;i.. 2017. 1. 22. [BOJ5012} 불만정렬 iAk를 만족하는 경우의 수를 세는 문제입니다. 가운데를 기준으로 생각할 때 (왼쪽에서는 자신보다 큰수의 개수) * ( 오른쪽에서 자신보다 작은 수의 개수) 를 n개의원소마다구해서 더해준다면 답이 될것입니다. 따라서 우리는 먼저 n번 자신보다 왼쪽에있는 수중에 큰 수를 구해봅시다. 왼쪽에서부터 시작해서 세그먼트트리를 업데이트하면서 자신보다 큰수의 개수를 query 하면서 a 배열에 저장합니다. seg배열을 리셋한 후 반대방향으로 자신보다 작은 수의 개수를 query 하면서 b배열에 저장합니다. 따라서 a[i]*b[i] 의 합이 답이 됩니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505.. 2017. 1. 22. [BOJ9426] 중앙값 측정 n개의 수열이 있을 때 K의 연속 부분 수열의 중앙값의 합을 구하는 문제이다. 앞에서부터 K개의 수를 업데이트 시켜준 뒤에 앞에서 1개 지우고 뒤에서 1개씩 업데이트하면서 중앙값을 구해나가면 된다. 이 떄 중앙값은 앞에서부터 (k+1)/2 번째 수이다. 앞에서부터 K개의 수를 세그먼트 트리에 업데이트 시켜준 후 N까지 1개씩 지우고 업데이트 시켜주면서 중앙값을 구해주면 된다. 중앙값은 앞에서부터 (k+1)/2 수를 찾으면 된다. 이 때 세그먼트트리는 k번째 수를 찾는 문제처럼 각 노드의 값이 1 또는 0 으로 되어있는 sum - segment - tree 를 구현한다. 주의할점 ! 좌표를 기준으로 값을 저장했으니 좌표가 중복될 수 있다. 따라서 업데이트 시에 현재값 +1 또는 -1 로 업데이트한다. 12.. 2017. 1. 19. 이전 1 2 3 4 5 다음