공부중의 블로그

연속된 숫자의 부분집합 중 최대를 구해보자. ex ) [1,6,10,4,7,9,5] >> {4,5,6,7} 나이브 : 정렬을 해서 순회하면 O(NlogN) 에 가능하다!! 좀 더 나은 방법이 없을까.. 방법은 순회하면서 군집을 만들어 나가는데, 해시맵에 각 군집의 전후를 기록해 둔다. 그리고 새로운 원소가 들어오면 군집을 필요에 따라 합치고 최대 길이를 확인한다!! vector consecutivesequence(vector & data){// make a hashmap for start and end pointsunordered_map buffer; // go through dataint currmax = 0;int curri = 0;for(int i = 0 ; i < data.size() ; i++)..

ex ) 1 2 7 8 9 의 최소합은 129+78 (순서 바꾸기 가능) 나이브 솔루션 : 그냥 두 집합으로 쪼갠 후에 합을 구해 최소를 찾는다 > 각 합을 만드는 시간 O(N), 갯수 : 2^NO(N2^N) 솔루션 성질을 더 이용해 보자. DP 하기에는 성질을 너무 많이 사용하고 앞의 값을 재활용하기 어렵다(?) 아닌데. 앞의 최소합이 있으면 새로운 원소가 들어오는 경우 둘 중 더 작은 값으로 가야하지 않나? 엌 greedy 방법이 여기잉네된다. greedy. 나머지가 이미 최소값인 조합으로 구성되어 있기 때문에, 새로운 숫자를 더 작은쪽에 붙이면 된다. 알고리즘뒤에서부터 숫자를 만들어 나간다. 그때그때 대소비교를 O(1)에 할 수 있도록 알고리즘을 짜면작은 쪽의 맨 앞에 숫자를 append 하면 된다..