공부중의 블로그

head-tail을 쓰면 되지 않을까? 아니면 minmax preprocessing 쓰던가. 3 5 7 6 3th t h 응 됨. ^^%

// sort 후에 head tail 기법을 사용한다. vector findtwo(vector & data, int target){// sortsort(data.begin(),data.end());// go through arrayint tail = 0;vector ret;for(int i = 0 ; i < data.size() ; i++){while(data[i]-data[tail]< target){ret.push_back(pair(data[tail],data[i]));tail++;}}return ret;} time complexity : O(NlogN), bucket sort 같은걸 사용 가능하면 O(N)..

저번에도 했었는데 자신보다 작으면서 가장 큰 n*(n-1)/2 를 찾는다. 그 다음 row에서 K-x 번째 원소를 찾는다. time complexity : O(N) (!!!)space complexity : O(1) (!!!) 구현하기 귀찮은데.. 내일이 면접이니 해볼까? 아니.. 후회할까? 글쎄.. 귀찮은데코드를 짜면서 헤메면 보기 매우 안좋다. 코드는 정말 알고리즘 및 필요한 자료구조와 계산을 완벽히 정리한 후에깃발 꽂는 용도로만 쓴다. 아주 구체적으로 알고리즘을 먼저 짜자. int findKthelement(vector & data, int K){// find the matching diagonal indexint n = data.size();int flag = 0;// element to find..

job : 5,9,17in : 4,13,18google : 8,19,21 >> 17,18,19 ans : 3 처음부터 최솟값을 하나씩 들어올리면서 길이를 재계산한다. 모두 마지막에 닿을 때까지 O(NlogN^K) ( 힙으로 최솟값을 트래킹한다 ) 정당성 : 최솟값을 증가시키기 않고 다른 것을 증가시키면 최솟값이 그대로 남게 되어 결국 범위가 증가하거나 같게 된다. 최솟값이 존재한다고 가정하면 최솟값이 아닌 것을 ... 모르겠다 더 생각해 보자 이런 경우 우리는 "이 검색 방식이 최솟값을 지나치지 않는다" 를 확인하면 된다. 만약 우리가 i -> k가 최솟값이라고 결론내렸는데 사실 i->k'가 최적의 솔루션이라고 생각해 보자. 이때, i,k,k' 중에 k'가 최솟값이 아니므로 k'를 k로 옮기지 않은 상태..

두 배열이 있을때, 각 배열에서 하나씩 꺼낸 수의 합 중에서 K번째로 작은 원소합을 구해보자. 우선 나이브하게 : N^2 개의 원소가 존재하니 O(N^2) 가 상한이다.( 합을 전부 나열한 뒤, partition select ) 어 이거 근데 문제가 그 양방향 정렬 된 행렬에서 K번째 찾기랑 문제가 같네..!! 4 7 8 11 135 9 15 19 21 9 12 13 16 1812 16 22 26 2813 17 23 27 2916 20 26 30 3218 22 28 32 34 있으면, 이렇게 양방향 증가하는 수열은 왼쪽 끝 아래에서 시작해서, 는 아니였음.. ㅠㅠ 새롭게 관찰하니, 대각선 내의 순서는 정해지지 않지만, 대각선 단계별로 무조건 순서는 강제된다. 왜냐면 좌우 증가기 때문에 대각선 레벨이 달라..

행렬은 행과 렬이 정렬되어 있고, 0 또는 1만 들어갈 수 있다.0의 갯수는? ex ) 0 0 10 1 11 1 1>> ans : 3 유명한 숫자찾기 문제처럼, 왼쪽 아래서 시작해서 0을 만날때까지 위로 올라가다가, 0을 만나면 오른쪽으로. 다시 위로 ... 이런 식으로 가면서 0의 갯수를 센다. 현재 위치가 행렬을 벗어나면 그만 세고 종결한다. O(N)

배열 내의 어느 숫자에 대해 그 왼쪽의 숫자들은 더 작고, 오른쪽의 숫자들은 더 큰 숫자들을 찾아보자. BST 2개를 만들어서 서로 주고 받는다 >> O(NlogN) 저번에 사용했던 min(max) 값 추적할 수 있는 스택을 사용하면..!!O(N) 알고리즘을 얻을 수 있다. 재귀적으로 해결 가능하다고 합니다 FindElement(int[] arr, int MaxTillNow, int currentIndex) { if(currentIndex == 0) { return FindElement(arr, arr[currentIndex], currentIndex + 1); } if(currentIndex == arr.Length-1) { return arr[currentIndex]; } int minTillNow ..

패턴은 1 ... N 의 값의 조합 배열으로 주어진다.배열은 서로 다른 N개의 값이다.패턴대로 배열을 정렬해 보자. O(N^2), O(1) 은 partition 해가면서 각 K번째 원소를 찾으면 가능하다. 근데 O(NlogN) O(1) 알고리즘이 있대.. 조합 배열을 정렬한 후에 패턴 배열에 원하는 값을 입히고 패턴 배열을 출력한다.. 추가 공간은 안 쓰는 듯? 더 좋은 O(N) O(1) 알고리즘이 있대.. public static int[] sort2(int[] Xs, int[] As) { for (int i = 0; i

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 ;..