본문 바로가기

Programming Problems/Arrays

(12)
배열에서 주어진 값 보다 크면서 최소 길이인 부분배열 구하기 ex ) [2,1,1,4,3,6], sum = 8 이면 답은 [3,6]의 2이다. 만약 최소합을 구하는 문제였으면 psum을 구해서 전부 sum을 뺀 후에 정렬하고, 정렬된 것들 중에서 앞엣값 - 뒤엣값이면서 최소인 psum 차이를 구할 수 있을텐데 ( 앞뒤로 비교해 가면서 찾기 ) 최소 길이를 구하는 문제니 다르게 풀린다. 모든 부분수열의 갯수가 N^2 개이고 그 합을 구하는게 N 이므로 대략 노가다로 하면 O(N^3) 이 상한이겠고하한은 한번은 가봐야 아니까 O(N) 이겠다 우선 최선부터 접근해 보자. 만약에 sum 보다 큰 원소가 있으면 1을 리턴하고 종료한다.근데 여기서 확장이 불가능한게 2개짜리에 만약 존재하는데, (5,5) 우리가 최대값인 (1,6,1) 주변에서 안된다고 해서 없는게 아니니까...
배열에서 자신보다 오른쪽에 있으면서 더 큰 원소의 갯수 중 최댓값 찾기 ex) [2,7,5,5,2,7,0,8,1] >> [5,1,2,2,2,1,2,0,0] >> 최댓값 : 5 LIS와 비슷한 풀이법이 가능할지 한번 해보자. 안된다. 대소비교는 본인 기준으로 상대적이기 때문이고, 숫자를 세는 데에 중복이 존재한다. 그러면 결국에는 갯수 세는 BST를 만들면서 진행하는 것 밖에 없을 듯 하다. int findmax(vector & data){struct node {node * right;node * left;int value;int rank;node(int v) : value(v), rank(1), left(NULL), right(NULL){}}int ret = 0;node * root = new node(data.back());for(int i = data.size()-1 ;..
배열에서 최대 연속 숫자 집합 찾기 연속된 숫자의 부분집합 중 최대를 구해보자. 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 하면 된다..