SELECT 
    NAME, 
    DATETIME
FROM 
    ANIMAL_INS 
ORDER BY 
    ANIMAL_ID DESC

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/59035

https://programmers.co.kr/events/7day-sql

SELECT 
    ANIMAL_ID, 
    ANIMAL_TYPE, 
    DATETIME, 
    INTAKE_CONDITION, 
    NAME, 
    SEX_UPON_INTAKE  
FROM 
    ANIMAL_INS  
ORDER BY 
    ANIMAL_ID

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/59034

https://programmers.co.kr/events/7day-sql

• MySQL 8.0.17 버전을 사용했습니다.

Database 생성하기

• DB_NAME은 각자 정해서 적습니다.

  mysql -uroot -p
  # 비밀번호 입력, mysql 진입.
  > create database DB_NAME;

Database 사용자 생성 및 권한 부여

• USER_NAME, USER_PASSWORD는 각자의 것을 적습니다.

  > CREATE USER 'USER_NAME'@'%' IDENTIFIED BY 'USER_PASSWORD';
  > GRANT ALL ON DB_NAME.* TO 'USER_NAME'@'%';
  > flush privileges;

생성한 Database에 접속

mysql -hHOST -uUSER_NAME -p DB_NAME

mysql -h127.0.0.1 -uUSER_NAME -p DB_NAME

기타 기본 명령어들

• MySQL 연결 종료

  QUIT
  exit

• MySQL 버전 출력

  SELECT VERSION();

• 현재 날짜 구하기

  SELECT CURRENT_DATE;

• DBMS에 있는 DB 확인

  SHOW DATABASES;

• DB 사용 선언

  USE ANOTHER_DB_NAME

• 현재 DB에 존재하는 테이블 확인

  SHOW TABLES;

BOJ 5430번 AC 문제

덱을 사용해서 푸는 문제인데 입력이 [1,2,3,4] 이런 식으로 주어져서 string을 정수로 변환하는 과정이 필요합니다. 한 자리수가 아니라 두 자리수 이상일 수 있으니 유의해서 풀어야합니다.

배열 원소 개수 n이 0일 때 출력을 신경써야합니다.

5430.cpp

#include <bits/stdc++.h>
using namespace std;
void printD(deque<int> q) {
    cout << '\n';
    for (auto s = q.begin(); s != q.end(); ++s)
        cout << *s << " ";
    cout << '\n';
}

void solve() {
    string func, arr;
    int size;
    cin >> func >> size >> arr;
    int arrSize = arr.size(), num = 0;
    deque<int> deq;

    if (size != 0) {
        for (int i = 1; i < arrSize; ++i) {
            if (arr[i] >= '0' && arr[i] <= '9') {
                num *= 10;
                num += (arr[i] - '0');
            } else {
                deq.push_back(num);
                num = 0;
            }
        }
    }
    int funcSize = func.size();
    bool forward = true;
    for (int i = 0; i < funcSize; ++i) {
        if (func[i] == 'R') {
            forward = !forward;
        } else if (func[i] == 'D') {
            if (deq.empty()) {
                cout << "error\n";
                return;
            }
            if (forward) {
                deq.pop_front();
            } else {
                deq.pop_back();
            }
        }
    }

    cout << "[";
    int deqSize = deq.size();
    if (forward) {
        for (int i = 0; i < deqSize; ++i) {
            cout << deq[i];
            if (i != deqSize - 1) {
                cout << ",";
            }
        }
    } else {
        for (int i = deqSize - 1; i >= 0; --i) {
            cout << deq[i];
            if (i != 0) {
                cout << ",";
            }
        }
    }
    cout << "]\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

BOJ 1021번 문제

덱을 사용해서 푸는 문제였습니다. 2번 연산과 3번 연산 중 어떤 연산을 통해 뽑아내는게 더 적은 연산을 하는지 계산하는 것만 신경 쓰면 풀 수 있었습니다.

1021.cpp

#include <bits/stdc++.h>
using namespace std;

void printD(deque<int> q) {
    cout << '\n';
    for (auto s = q.begin(); s != q.end(); ++s)
        cout << *s << " ";
    cout << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int size;
    cin >> size;
    deque<int> d;
    int count = 0;

    for (int i = 0; i < size; ++i) {
        d.push_back(i + 1);
    }

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int location;
        cin >> location;

        //printD(d);

        if (location == d.front()) {
            d.pop_front();
            continue;
        }
        int gap = 0;
        for (auto s = d.begin(); s != d.end(); ++s) {
            if (*s == location) {
                break;
            }
            gap++;
        }
        // 2를 하는게 최솟값
        if (gap <= (d.size() / 2)) {
            for (int j = 0; j < gap; ++j) {
                d.push_back(d.front());
                d.pop_front();
                count++;
                //cout << "2 ";
            }
            d.pop_front();
        }
        // 3을 하는게 더 최솟값
        else {
            gap = d.size() - gap;
            for (int j = 0; j < gap; ++j) {
                d.push_front(d.back());
                d.pop_back();
                count++;
                //cout << "3 ";
            }
            d.pop_front();
        }
    }
    cout << count;
}

정렬(2)

시간 복잡도가 O(N*log₂N)인 정렬 방법을 정리합니다.

• 퀵 정렬
• 병합 정렬
• 힙 정렬

퀵 정렬

Divide & Conquer 알고리즘.

최악의 경우 속도가 O(N²)가 될 수 있다.(정렬된 데이터에 pivot을 맨 우측으로 잡을 경우)

재귀 전 작업 때문에 재귀 오버헤드가 크다.

1. 배열의 한 원소를 고른다. (pivot이라고 부른다)
2. pivot보다 작은 원소는 pivot의 왼쪽으로, 큰 요소는 오른쪽으로 옮긴다.
3. pivot의 왼쪽 배열과 오른쪽 배열을 다시 1, 2 과정을 거치게 한다.
4. 배열의 크기가 0이나 1이 될때까지 반복한다.

void Quick_sort(int ary[], int low, int high) {
    if (low < high) {
        int pivot = Partition(ary, low, high);
        Quick_sort(ary, low, pivot - 1);
        Quick_sort(ary, pivot + 1, high);
    }
}
int Partition(int ary[], int low, int high) {
    int left = low, right = high;
    int pivot = ary[left];  // pivot을 가장 왼쪽으로 선택하기로 한다.
    while (left < right) {
        // pivot보다 큰 원소가 나올 때까지 left를 증가시킨다.
        while (ary[left] <= pivot)
            left++;
        // pivot보다 작은 원소가 나올 때까지 right를 감소시킨다.
        while (ary[right] > pivot)
            right--;
        if (left < right)
            swap(ary[left], ary[right]);
    }
    swap(ary[right], ary[low]);
    return right;
}

병합 정렬

공간복잡도가 O(N)이다. 공간이 더 필요하다.

퀵 정렬은 Big -> Small Scale로 정렬하지만, 병합 정렬은 Small -> Big Scale로 정렬하기 때문에 재귀 오버헤드가 없다.

결국에 하나씩 비교하기 때문에 입력 데이터의 사전 정렬에 영향을 받지 않는다.

1. 배열을 크기가 1이 될 때 까지 반으로 나눈다.
2. 반으로 나뉘어진 배열을 비교하면서 합친다.

void Merge_sort(int ary[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        Merge_sort(ary, left, mid);
        Merge_sort(ary, mid + 1, right);
        Merge(ary, left, mid, right);
    }
}
void Merge(int ary[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    int temp[SIZE];
    while (i <= mid && j <= right) {
        if (ary[i] <= ary[j])
            temp[k++] = ary[i++];
        else
            temp[k++] = ary[j++];
    }
    if (i > mid) {
        for (int l = j; l <= right; l++)
            temp[k++] = ary[l];
    } else {
        for (int l = i; l <= mid; l++)
            temp[k++] = ary[l];
    }
    for (int l = left; l <= right; l++)
        ary[l] = temp[l];
}

힙 정렬

우선순위 큐를 이용한 정렬 방법이다.

하나의 삽입, 삭제 과정이 O(logN)의 시간이 걸린다.

전체 데이터 삽입, 삭제 과정은 O(NlogN)의 시간이 걸린다.

정렬(1)

시간 복잡도가 O(N²)인 정렬 방법을 정리합니다.

• 버블 정렬
• 선택 정렬
• 삽입 정렬

버블 정렬

• 공간 복잡도 : O(1)

가장 큰 원소를 맨 뒤로 보내고 그 다음 원소를 그 앞, ... 을 반복한다.

void Bubble_sort(int ary[], int length) {
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length - 1 - i; j++) {
            if (ary[j] > ary[j + 1])
                swap(ary[j], ary[j + 1]);
        }
    }
}

개선된 버블 정렬 알고리즘이 있다. 두번째 for문에서 모두 정렬된 상태면 더 이상 살피지 않고 끝낸다.

void Bubble_sort_improved(int ary[], int length) {
    bool sorted = false;
    for (int i = 0; i < length; i++) {
        // 정렬된 상태
        if (sorted)
            break;
        sorted = true;
        for (int j = 0; j < length - 1 - i; j++) {
            if (ary[j] > ary[j + 1]) {
                // 정렬되지 않았으니 False 처리.
                sorted = false;
                swap(ary[j], ary[j + 1]);
            }
        }
    }
}

선택 정렬

• 공간 복잡도 : O(1)

가장 작은 원소를 맨 앞으로 보내고, 그 다음 원소를 그 다음으로 보낸다. 가장 작은 원소의 index를 저장해뒀다가 한번 훑은 뒤 swap을 하기 때문에 버블 정렬보다는 빠르게 가능하다.

void Selection_sort(int ary[], int length) {
    int min_index;
    for (int i = 0; i < length - 1; i++) {
        min_index = i;
        for (int j = i + 1; j < length; j++) {
            if (ary[min_index] > ary[j]) {![Image](https://i.imgur.com/jmdyU4f.png)
                min_index = j;
            }
        }
        swap(ary[i], ary[min_index]);
    }
}

삽입 정렬

• 공간 복잡도 : O(1)

두번째 원소부터 시작해서 왼쪽에 있는 원소와 비교한다. 왼쪽의 원소가 기준값보다 더 크면 오른쪽으로 보낸다. 왼쪽의 원소가 더 작거나(올바른 순서로 되어있거나) 배열의 맨 앞까지 오면 멈춘다.
데이터가 이미 어느정도 정리되어 있는 경우 유리하다.
루프 중간에 멈춰도 검사하지 않은 기존 데이터의 순서가 유지되어 안정적이다.

void Insertion_sort(int ary[], int length) {
    int i, j, current;
    for (i = 1; i < length; i++) {
        current = ary[i];
        for (j = i - 1; j >= 0 && ary[j] > current; j--) {
            ary[j + 1] = ary[j];
        }
        ary[j + 1] = current;
    }
}