본문 바로가기

Programming Problems/Arrays

배열에서 주어진 값 보다 크면서 최소 길이인 부분배열 구하기 ex  ) [2,1,1,4,3,6], sum = 8 이면 답은 [3,6]의 2이다.만약 최소합을 구하는 문제였으면 psum을 구해서 전부 sum을 뺀 후에 정렬하고, 정렬된 것들 중에서 앞엣값 - 뒤엣값이면서 최소인 psum 차이를 구할 수 있을텐데 ( 앞뒤로 비교해 가면서 찾기 )최소 길이를 구하는 문제니 다르게 풀린다.모든 부분수열의 갯수가 N^2 개이고 그 합을 구하는게 N 이므로 대략 노가다로 하면 O(N^3) 이 상한이겠고하한은 한..
배열에서 자신보다 오른쪽에 있으면서 더 큰 원소의 갯수 중 최댓값 찾기 ex) [2,7,5,5,2,7,0,8,1] >> [5,1,2,2,2,1,2,0,0] >> 최댓값 : 5LIS와 비슷한 풀이법이 가능할지 한번 해보자.안된다. 대소비교는 본인 기준으로 상대적이기 때문이고, 숫자를 세는 데에 중복이 존재한다.그러면 결국에는 갯수 세는 BST를 만들면서 진행하는 것 밖에 없을 듯 하다.int findmax(vector<int> & data){struct node {node * rig..
배열에서 최대 연속 숫자 집합 찾기 연속된 숫자의 부분집합 중 최대를 구해보자.ex ) [1,6,10,4,7,9,5] >> {4,5,6,7}나이브 : 정렬을 해서 순회하면 O(NlogN) 에 가능하다!!좀 더 나은 방법이 없을까..방법은 순회하면서 군집을 만들어 나가는데, 해시맵에 각 군집의 전후를 기록해 둔다. 그리고 새로운 원소가 들어오면 군집을 필요에 따라 합치고 최대 길이를 확인한다!!vector<int> consecutivesequence(vector&l..
연속된 숫자 배열이 주어졌을 때, 숫자로 만든 합의 최소는? ex ) 1 2 7 8 9 의 최소합은 129+78 (순서 바꾸기 가능)나이브 솔루션 : 그냥 두 집합으로 쪼갠 후에 합을 구해 최소를 찾는다 > 각 합을 만드는 시간 O(N), 갯수 : 2^NO(N2^N) 솔루션성질을 더 이용해 보자. DP 하기에는 성질을 너무 많이 사용하고 앞의 값을 재활용하기 어렵다(?) 아닌데. 앞의 최소합이 있으면 새로운 원소가 들어오는 경우 둘 중 더 작은 값으로 가야하지 않나? 엌 greedy 방법이 여기잉네된다...