본문 바로가기

Programming Problems/Arrays

(12)
부분배열 내의 최대값-최소값이 2와 같거나 작은 인덱스 조합의 수 head-tail을 쓰면 되지 않을까? 아니면 minmax preprocessing 쓰던가. 3 5 7 6 3th t h 응 됨. ^^%
N개의 정수 배열에서 두개의 합이 target 이하인 모든 조합 찾기 // 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)..
모든 row와 column이 sorted 일때, K번쨰 작은 원소 찾기 저번에도 했었는데 자신보다 작으면서 가장 큰 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..
모든 단어가 포함된 최소 범위 찾기 Q 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번째로 작은 원소합 구하기 Q 두 배열이 있을때, 각 배열에서 하나씩 꺼낸 수의 합 중에서 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 있으면, 이렇게 양방향 증가하는 수열은 왼쪽 끝 아래에서 시작해서, 는 아니였음.. ㅠㅠ 새롭게 관찰하니, 대각선 내의 순서는 정해지지 않지만, 대각선 단계별로 무조건 순서는 강제된다. 왜냐면 좌우 증가기 때문에 대각선 레벨이 달라..
2차원 행렬에서 0의 갯수 세기 Q 행렬은 행과 렬이 정렬되어 있고, 0 또는 1만 들어갈 수 있다.0의 갯수는? ex ) 0 0 10 1 11 1 1>> ans : 3 유명한 숫자찾기 문제처럼, 왼쪽 아래서 시작해서 0을 만날때까지 위로 올라가다가, 0을 만나면 오른쪽으로. 다시 위로 ... 이런 식으로 가면서 0의 갯수를 센다. 현재 위치가 행렬을 벗어나면 그만 세고 종결한다. O(N)
좌는 작고 우는 큰 배열 내의 숫자들 찾기(min/max preprocessing) Q 배열 내의 어느 숫자에 대해 그 왼쪽의 숫자들은 더 작고, 오른쪽의 숫자들은 더 큰 숫자들을 찾아보자. 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