[코드모음]-정렬, 자료구조

/* merge sort */

void merge(int s, int m, int e){

        int i = s, j = m + 1;

        for (int k = s; k <= e; ++k)

               //왼쪽 a[i] 또는 오른쪽 a[j]임.

               //왼쪽의 경우는 i<=m 이면서 j>e 혹은 왼쪽게 오른쪽꺼보다 작은 경우. 나머지는 전부 오른쪽 

               buf[k] = (i <= m && (j>e || a[i] <= a[j])) ? a[i++] : a[j++];

}

void merge_sort(int s, int e){

        if (s >= e) return;

 

        int m = (s + e) / 2;

        merge_sort(s, m);      merge_sort(m + 1, e);

        merge(s, m, e);

        memcpy(a + s, buf + s, sizeof(int)* ((e - s) + 1));

}

/* quick sort */

- pivot을 random하게 정하고, 그것을 a[e]와 swap

- i=j=s놓고, j를 증가시키면서 a[j]와 a[e]를 비교하면서, a[j]<a[e]이면 swap(a[i++],a[j]) 수행

  이렇게 하면, i번째를 중심으로해서, 왼쪽은 a[e]보다 작은, 오른쪽은 a[e]보다 큰 값이 놓이게 됨.

  이제 a[e]에 있는 값의 위치가 i번째이기에, swap(a[i],a[e]) 수행

- 이렇게 하면 i번째 값이 정확하게 자리를 찾아간 것임. 이제 i를 기준으로 왼쪽에 대해, 그리고 오른쪽에 대해 동일루틴 수행

  q_sort(s,i-1);   q_sort(i+1,e);

  (a[e]값은 i을 부터 j=e부터 시작해서, a[i]와 a[j]를 a[p]와 비교하면서, i++ j--

srand((unsigned int)time(&t));

quick_sort(1, N);

void q_sort(int s, int e){

    int i,j,p; 

    if(s<e){    

        p = s+rand()%(e-s+1);          

        swap(a[p],a[e]);       

        i=s;

        for(j=s;j<e;++j) if(a[j]<=a[e]) swap(a[i++],a[j]);    

        swap(a[i],a[e]);

         

        q_sort(s,i-1);

        q_sort(i+1,e);

    }  

}

/* 지은이가 지은 집 – 구멍 너비 X, L1 + L2=X되는 L1,L2 찾기 */

- 소팅을 하고, -> O(n log n)

- 오른쪽을 고정하고 왼쪽에서 증가, 왼쪽을 고정하고 오른쪽에서부터 감소하면서 답이 있는 지 찾는다. : O(n)

while(1)

while(i<N-1 && a[i]+a[j]<X) i++;

while(j>0 && a[i]+a[j]>X) j--;

if(i>=j) break;

if(i!=j && a[i]+a[j]==X) break;

 

         sort(a, a + N); 

         for (i = 0, j = N - 1; ; ) {

                  while (i < N - 1 && a[i] + a[j] < x) i++;

                  while (j > 0 && a[i] + a[j] > x) j--;

                  if (i >= j) break;

                  if (i != j && a[i] + a[j] == x) break;

         } 

         if (i != j && a[i] + a[j] == x) printf("yes %d %d\n", a[i], a[j]);

/* K번째 수 찾기 - N개의 수중에서 K번째 작은 수 찾기 */

- 퀵소트 개념을 이용: O(N)

- 퀵소트를 해가는 과정에서, pivot은 최종 정렬된 수열에서의 자기자리를 항상 찾아간다는 원리 이용

- 퀵소트와 다르게 K가 존재하는 한 쪽 방향(왼쪽 혹은 오른쪽)으로만 재귀호출

   return (K<j) ? find(s,j-1) : find(j+1,e)

 

/* counting inversion – (3,2) (4,2) 처럼 내림차순으로 되어 있는 수 쌍 구하기 */

- 머지소트 이용 : O(NlogN)

- merge하는 과정에서, 왼쪽편에 값이 남아 있는 상태임에도 오른편에서 b가 선택되었다면,

왼쪽편에 남아있는 수들과 b와의 쌍은 카운트인버전.

buf[k] = (i <= m && (j>e || a[i] <= a[j])) ? a[i++] : a[j++], cnt+=(m-i+1);

/* Linked List */

struct List{

List* prev;

List* next:

int num;

}

 

//insert   

1)신규 노드 생성: f = new List(); //f: fresh

2)num 지정: f->num = x

3)신규노드의 prev 지정: f->prev = head->prev; //head->prev는 삽입되기 전 맨 마지막 노드를 가리키고 있음

4)신규노드의 next를 head로 지정: f->next=head

5)last였던 노드의 next 갱신: head->prev->next = f

6)헤드의 prev 갱신: head->prev=f

 

//delete

헤드를 삭제해 나가는 방법임

1)헤드를 가리키는 임시 노드 생성: List* tmp = head;

2)last->prev 갱신: head->prev->next = head->next

3)head바로 다음에 있던 노드의 prev 갱신: head->next->prev=head->prev

 

/* 상호 배타적 집합 */

//init

for (int i = 1; i <= N; ++i) p[i] = i;

 

//find

int find_parent(int a) {

         if (p[a] == a) return a;

         p[a] = find_parent(p[a]);

         return p[a];

}

 

//merge

int pa = find_parent(a);

int pb = find_parent(b);

p[pa] = pb;

 

/* 세그먼트 트리 */

-주어진 값: arr[1..n]

-트리 배열: tree[1..4n]  //n에 가장 가까운 2의 멱승으로 올림한 값이 정확. 대충은 4n

1)init: 주어진 배열을 가지고 tree를 형성해 둔다.

int init(node, s,e)

if(s==e) return tree[node]=arr[s]

int m = (s+e)/2

return tree[node] = init(2*node,s,m) + init(2*node+1,m+1,e)

//만약 min tree라면 min( init(2*node,s,m), init(2*node+1,m+1,e)

 

2)query

ll query(node, s,e,i,j) //i~j까지의 합

if(i>e || j<s) return 0                              //1. 범위 밖이면.

if(i<=s && j>=e) return tree[node]    //2. i~j가 node가 표현하는 집합을 완전히 포함

int m = (s+e)/2

return query(2*node,s,m,i,j)  + query(2*node+1,m+1,e) //3. 왼쪽 재귀 + 오른쪽 재귀

 

3)update

void update(node,s,e,i,diff) //diff:i노드에 diff만큼 더한다. 관련노드들을 diff만큼 더해야기 때문.

if(i<s || i>e) return;        //1. 범위 밖

tree[node] = tree[node] + diff;       //2. if(s==e)이면 현재노드만 갱신. 즉, leaf까지 내려온경우.

if(s != e)                    //3. if(s!=e)이면, 자신도 갱신하고, 자식 노드들도 갱신

                       int m = (s+e) / 2;

update(2*node,s,m,i,diff)

update(2*node+1,m+1,e,i,diff)

 

 

/* 울타리 잘라내기 (스택 버전)– N개 판자로 된 울타리내 최대 직사각형 넓이*/

- 왼쪽에서 오른쪽으로 가면서, 현재 판자에서 왼쪽 끝까지 사각형 가능한 판자수 w[i] 구하고,

  오른쪽에서 왼쪽으로 가면서, (현재판자~오른쪽끝까지 가능 판자수 – 1)을 w[i]에 가산

- 이렇게 구한 w[i]는, 각 판자 위치 i에서 h[i]를 가지고 사각형 그릴 수 있는 최대 판자 수가 됨

//1. left: 현재위치 i에서 왼쪽끝까지 가능 너비

               for (int i = 1; i <= N; ++i){

                       //stack에서 현재높이보다 높은 것은 pop

                       while (!left.empty() && (h[left.top()] >= h[i]))     left.pop();

 

                       if (left.empty()) w[i] = i; //왼쪽끝까지 가능

                       else w[i] = i - left.top(); //left.top()이 있는 곳까지 가능

 

                       left.push(i);

               }

 

 

               //2. right

               for (int i = N ; i >= 1; --i){

                       //stack에서 현재높이보다 높은 것은 pop

                       while (!right.empty() && (h[right.top()] >= h[i]))   right.pop();

 

                       if (right.empty()) w[i] += (N - i); //0~N-1까지 가능. 자기자신은 제외(left와 중복)

                       else w[i] += (right.top() - i - 1); //오른쪽끝까지 - 1

 

                       right.push(i);

               }
- 각 i에 대해 w[i]에 h[i]를 구하면서 최대값 찾으면 됨

               int multi = 1, maxVal = 0;

               for (int i = 0; i < N; ++i){

                       multi = h[i] * w[i];

                       maxVal = max(maxVal, multi);

               }

/* 울타리 잘라내기 (분할정복으로 풀기) */

int getMaxRange(int left, int right){

        if (left == right)     return mH[left];

 

        int mid = (left + right) / 2;

        int ret = max(getMaxRange(left, mid), getMaxRange(mid + 1, right));

 

        int lo = mid, hi = mid + 1;

        int height = min(mH[lo], mH[hi]);

        ret = max(ret, height * 2);

 

        while (lo > left || hi < right){

               if (hi<right && (lo == left || (mH[lo - 1] < mH[hi + 1]))){

                       ++hi;          height = min(height, mH[hi]);

               }

               else{

                       --lo;          height = min(height, mH[lo]);

               }

               ret = max(ret, height * (hi - lo + 1));

        }

        return ret;

}

-끝-