'Programming Problems/Arrays'에 해당되는 글 12건

 [ 1 ]  [ 2 ] 
Programming Problems/Arrays

부분배열 내의 최대값-최소값이 2와 같거나 작은 인덱스 조합의 수

head-tail을 쓰면 되지 않을까?


아니면 minmax preprocessing 쓰던가.


 3 5 7 6 3

th

 t h


응 됨.


^^%

Programming Problems/Arrays

N개의 정수 배열에서 두개의 합이 target 이하인 모든 조합 찾기

// sort 후에 head tail 기법을 사용한다.


vector<pair<int,int>> findtwo(vector<int> & data, int target){

// sort

sort(data.begin(),data.end());

// go through array

int tail = 0;

vector<pair<int,int>> ret;

for(int i = 0 ; i < data.size() ; i++){

while(data[i]-data[tail]< target){

ret.push_back(pair<int,int>(data[tail],data[i]));

tail++;

}

}

return ret;

}


time complexity : O(NlogN), bucket sort 같은걸 사용 가능하면 O(N)..

Programming Problems/Arrays

모든 row와 column이 sorted 일때, K번쨰 작은 원소 찾기

저번에도 했었는데 자신보다 작으면서 가장 큰 n*(n-1)/2 를 찾는다. 그 다음 row에서 K-x 번째 원소를 찾는다.


time complexity : O(N) (!!!)

space complexity : O(1) (!!!)


구현하기 귀찮은데.. 내일이 면접이니 해볼까? 아니.. 후회할까? 글쎄.. 귀찮은데

코드를 짜면서 헤메면 보기 매우 안좋다. 코드는 정말 알고리즘 및 필요한 자료구조와 계산을 완벽히 정리한 후에

깃발 꽂는 용도로만 쓴다. 아주 구체적으로 알고리즘을 먼저 짜자.


int findKthelement(vector<vector<int>> & data, int K){

// find the matching diagonal index

int n = data.size();

int flag = 0;

// element to find in buffer

int tofind = 0;

K--;

int x,y;

if(K<=(n*(n+1)/2)){

y = (sqrt(1+8*K)-1/2);

x = 0;

tofind = K-y*(y+1)/2;

}else{

x = (sqrt(1+8*(n*n-K))-1/2);

tofind = x+1-(n*n-K-1-x*(x+1)/2);

y = data.size()-1;

}

vector<int> buffer;

while(x<data.size()&&y>=0){

buffer.push_back(data[x][y]);

x++;

y--;

}

return findKthpartition(buffer, tofind);

}

Programming Problems/Arrays

모든 단어가 포함된 최소 범위 찾기 Q

job : 5,9,17

in : 4,13,18

google : 8,19,21


>> 17,18,19 ans : 3


처음부터 최솟값을 하나씩 들어올리면서 길이를 재계산한다. 모두 마지막에 닿을 때까지


O(NlogN^K) ( 힙으로 최솟값을 트래킹한다 )


정당성 : 최솟값을 증가시키기 않고 다른 것을 증가시키면 최솟값이 그대로 남게 되어 결국 범위가 증가하거나 같게 된다. 

최솟값이 존재한다고 가정하면 최솟값이 아닌 것을 ...


모르겠다 더 생각해 보자


이런 경우 우리는 "이 검색 방식이 최솟값을 지나치지 않는다" 를 확인하면 된다.


만약 우리가 i -> k가 최솟값이라고 결론내렸는데 사실 i->k'가 최적의 솔루션이라고 생각해 보자. 이때, i,k,k' 중에 k'가 최솟값이 아니므로 k'를 k로 옮기지 않은 상태에서 i에 도달했을 것이다. 따라서, 이 검색 방식으로는 반드시 최적의 솔루션 i->k'를 지나치게 된다.

Programming Problems/Arrays

같은 길이의 증가 배열이 있을때, K번째로 작은 원소합 구하기 Q

두 배열이 있을때, 각 배열에서 하나씩 꺼낸 수의 합 중에서 K번째로 작은 원소합을 구해보자.


우선 나이브하게 : N^2 개의 원소가 존재하니 O(N^2) 가 상한이다.

( 합을 전부 나열한 뒤, partition select )


어 이거 근데 문제가 그 양방향 정렬 된 행렬에서 K번째 찾기랑 문제가 같네..!!


4 7 8 11 13

5 9 15 19 21


9 12 13 16 18

12 16 22 26 28

13 17 23 27 29

16 20 26 30 32

18 22 28 32 34


있으면,


이렇게 양방향 증가하는 수열은 왼쪽 끝 아래에서 시작해서, 는 아니였음.. ㅠㅠ


새롭게 관찰하니, 대각선 내의 순서는 정해지지 않지만, 대각선 단계별로 무조건 순서는 강제된다. 왜냐면 좌우 증가기 때문에 대각선 레벨이 달라지면 무조건 커지기 때문,,


그러니까 갯수를 세서, K 보다 작은 N*(N-1)/2 를 찾고 그 차이값을 N개의 숫자 중에서 찾는다 O(N).


그니깐 O(N) 알고리즘이 되는 것..

엌ㅋ 이거 논문을 쓴 내용이네 ㅋㅋㅋㅋㅋ 와 ㅋㅋ 나 좀 쩌는듯..


내가 생각이 안난다는건 실제로 어렵다는거니까 쫄지 말자. 면접관 힌트도 잘 얻고

Programming Problems/Arrays

2차원 행렬에서 0의 갯수 세기 Q

행렬은 행과 렬이 정렬되어 있고, 0 또는 1만 들어갈 수 있다.

0의 갯수는?


ex ) 

0 0 1

0 1 1

1 1 1

>> ans : 3


유명한 숫자찾기 문제처럼, 왼쪽 아래서 시작해서 0을 만날때까지 위로 올라가다가, 0을 만나면 오른쪽으로. 다시 위로 ... 이런 식으로 가면서 0의 갯수를 센다. 현재 위치가 행렬을 벗어나면 그만 세고 종결한다.


O(N)

Programming Problems/Arrays

좌는 작고 우는 큰 배열 내의 숫자들 찾기(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 = FindElement(arr, Math.Max(MaxTillNow, arr[currentIndex]), currentIndex + 1)
	if(arr[currentIndex] > MaxTillNow && arr[currentIndex] < minTillNow)
	{
		Console.WriteLine(arr[currentIndex]);
	}
	return Math.Min(minTillNow, arr[currentIndex]);
}


https://www.careercup.com/question?id=5738269695279104


다시 생각해 보니 쉬운 문제기도 하네.

각 점에 대해 그 점까지의 min과 max 값을 계산할 수 있으니까, 그걸 preprocessing 해서, 값이 맞으면 출력하는 방식으로 하면 O(N)이 되겠다.

각 점까지의 min과 max preprocessing은 제법 신박하네.


Programming Problems/Arrays

주어진 배열 패턴대로 배열 정렬하기

패턴은 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 < Xs.length; i++) {
            while(As[i] != i) {

                int a = As[i];

                // swap Xs
                int x = Xs[a];
                Xs[a] = Xs[i];
                Xs[i] = x;

                // swap As
                As[i] = As[a];
                As[a] = a;
            }
        }

        return Xs;
    }


알고리즘 요점은..


16 3 17 11 5 8

2  3  1   0  4 5


를 A에 맞춰서 정렬하면(counting sort와 같게 O(N) 이다)

11 17163  5  

0  1  2  3  4  5


안되는데 ..??


첫 행렬이 정렬되어 있다는 가정 아래 하는듯


아 내꺼가 그럼 훨신 간단하잖아 ............

뭐하는거야 이게 이상한 풀이 가지고 장난치네;;


https://www.careercup.com/question?id=4669539153346560

Programming Problems/Arrays

배열에서 주어진 값 보다 크면서 최소 길이인 부분배열 구하기

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) 주변에서 안된다고 해서 없는게 아니니까..

이건 complexity를 획기적으로 줄여주지는 않는다.

다만 최대한 효율적으로 만들자면 합을 1에 구할 수 있어서(sliding window)

최악의 경우 O(N^2) 인 알고리즘은 만들 수 있다.


N 알골이 존재할 수 있을까?


헤드 - 테일 기법으로 풀린다.

헤드를 하나씩 늘려가면서 sum보다 큰 최소 테일을 구한다. min과 비교한다.

헤드를 하나 늘린다. 테일을 맞춰서 줄인다. min과 비교한다.


최대 헤드 n, 테일 n , 비교 각 1회 있으므로 O(N) 알고리즘이다.


int findminsub(vector<int> & data, int sum){

// use head tail

int head = 0;

int tail = 0;

int curr = 0;

int ret = INT_MAX;

while(curr<sum){

curr+=data[head];

head++;

}


// go through array

int x = head;

for(int i = x+1 ; i < data.size() ; i++){

curr += data[i];

// make tail follow

while(curr>sum){

curr-= data[tail];

tail++;

}

tail--;

curr += data[tail];

if(ret>i-tail+1) ret = i-tail+1;

}


return ret;

}


space complexity : O(1)

time complexity : O(N)

Programming Problems/Arrays

배열에서 자신보다 오른쪽에 있으면서 더 큰 원소의 갯수 중 최댓값 찾기

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<int> & 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 ; i>=0 ; i--){

// make BST and count

int count = 0;

node * runner = root;

node * prev;

while(runner!=NULL){

prev = runner;

if(runner->value>data[i]){

count += runner->rank-(runner->left==NULL)?0:runner->left->rank;

runner->rank++;

if(runner->left==NULL){

runner->left = new node(data[i]);

}

runner = runner->left;

}else{

runner->rank++;

if(runner->right==NULL){

runner->right = new node(data[i]);

}

runner = runner->right;

}

}

if(ret<count) ret = count;

}

return ret;

}


time complexity : O(NlogN)

space complexity : O(N)