(TIL) 20210608

📕Facts(한 것)

---

• 알고리즘 복습
• 운동하기
• 프로그래머스 문제 풀기
• 수업듣기

 

📕Findings(배운 것)

---

오늘은 퀵정렬과 다이나믹 프로그래밍에 대해서 복습했다.

퀵정렬의 partition과 sort 두 부분으로 나뉜다.

(사실상 partition이 전부다)

 

partition은 퀵정렬의 정수인데,

왼쪽에는 pivot보다 작은값을, 오른쪽에는 pivot보다 큰 값을 정렬해준다

그리고 pivot을 작은값과 큰 값 사이에 넣으면 완성이다.

 

이 partition 알고리즘을 재귀적으로 호출하면 결국 퀵정렬이 된다.

 

퀵정렬은 평균적으로 O(nlogn)의 시간복잡도를 보장하지만, 최악의 경우에는 O(N^2)의 시간복잡도를 가진다.

최악의 경우는 배열이 모두 같은 수로 이루어진 경우인데, 

이를 보완하기 위해서 3-way 퀵정렬이 존재한다.

 

3-way퀵정렬은 피봇보다 작은수, 같은 수, 큰 수 이렇게 세부분으로 분류한다.

그렇기 때문에 같은 수로 이루어진 배열도 O(n)의 시간복잡도로 정렬이 가능하다.

 

아래는 C로 작성된 퀵정렬 코드이다.

#include <stdio.h>

int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
int n = 10;

void swap(int *a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

int partiton(int* a, int left, int right) {
    int p = a[left];
    int i = left + 1;
    for(int j = left + 1; j <= right; j++) {
        if(a[j] < p) {
            swap(a, j, i);
            i++;
        }
    }
    swap(a, left, i-1);
    
    return i-1;
}

void sort(int* a, int left, int right) {
    if(right <= left) {
        return ;
    }
    int p = partiton(a, left, right);
    sort(a, left, p - 1);
    sort(a, p + 1, right);
}

int main() {
    sort(target, 0, n-1);
    for(int i = 0; i < n; i++) {
        printf("%d ", target[i]);
    }
    return 0;
}

📕Feeling(느낀 점)

---

시험 공부 도중에 머리 식힐겸 프로그래머스  문제를 몇 개 풀었다.

'프린터' 문제를 풀면서 처음으로 우선순위 큐를 사용해 봤다.

 

아래는 '프린터' 코드이다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    queue<pair<int, int>> q;
    priority_queue<int> pq;
    
    for(int i = 0; i < priorities.size(); i++) {
        q.push(make_pair(i, priorities[i]));
        pq.push(priorities[i]);
    }
    while(!q.empty()) {
        int i = q.front().first;
        int p = q.front().second;
        q.pop();
       
        if(p == pq.top()) {
            pq.pop();
            answer += 1;
            if(i == location) {
                break;
            }
        } else {
            q.push(make_pair(i,p));
        }
     }
    
    return answer;
}

📕Affirmation(자기 선언)

---

• 日日新又日新
• 순간에 최선을

 

📕여담

---

아침에 일어나서 애플 WWDC21 을 시청했다.

맥의 마우스와 키보드로 아이패드를 제어할 수 있는 기능이 이제야 들어간 것이 반가웠다.

하지만 M1 아이패드 프로가 나온 이 시점에서

오히려 ipad OS가 아이패드의 성능을 제한한다는 생각이 든다.