https://www.acmicpc.net/problem/10799

문제 설명

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.

이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.

레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다. 위 예의 괄호 표현은 그림 위에 주어져 있다.

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

입출력

• 입력 한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.

• 출력 잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.

풀이

• 사용한 자료구조
  • stack<char> s : 괄호의 쌍을 찾기 위해 사용하는 자료구조
• 풀이 입력한 문자열의 처음부터 끝까지 탐색
  • 문자가 여는 괄호(()일 경우 스택에 push
  • 문자가 닫는 괄호())일 경우
    • 바로 이전 문자가 여는 괄호(()였을 경우 ➡️ 레이저 스택에서 pop() 수행 ➡️ 현재 스택의 사이즈를 결과 값에 더하기 스택에서 pop을 수행하고 size 값을 더하는 것은 top의 괄호는 레이저의 괄호여서 제외해야 하기 때문에 위와 같은 순서로 구함
    • 바로 이전 문자가 여는 괄호가 아닌 경우 ➡️ not 레이저 스택에서 pop() 수행 ➡️ 결과값에 1더하기 쇠막대기가 끝남으로써 조각 1개가 더해짐

• 코드 처음 작성한 코드 ➡️ 괄호 쌍이 없는 괄호가 있는 문자열이 입력되는 경우를 고려

  #include <iostream>
  #include <stack>
  #include <string>
  using namespace std;
  

int main() { cin.tie(0); ios::sync_with_stdio(0);

stack<char> s;
string str;
int ans = 0;

cin >> str;
for (int i = 0; i < str.length(); i++)
{
    if (str[i] == '(') // 여는 괄호인 경우
        s.push('(');
    else // 닫는 괄호인 경우(레이저인 경우/레이저가 아닌 경우)
    {
        if (i > 0 && str[i - 1] == '(' && s.top() == '(') // 레이저인 경우
        {
            s.pop();
            ans += s.size();
        }
        else // 레이저가 아닌 경우
        {
            // 스택이 비지 않은 경우
            if (!s.empty() && s.top() == '(')
            {
                ans += 1;
                s.pop();
            }
        }
    }
}
cout << ans;

}

만약, 입력되는 문자열내 괄호가 모두 괄호쌍을 가진다고 제한된다면 아래와 같이 코드를 작성해도 된다. 
또한, 문자열 내의 문자가 여는 괄호(`(`), 닫는 괄호(`)`)로 제한되기 때문에 `else` 문 하위 문들에서 `s.top() == '('` 은 제외해도 되는 조건이다. 
```cpp
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);

    stack<char> s;
    string str;
    int ans = 0;

    cin >> str;
    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] == '(') // 여는 괄호인 경우
            s.push('(');
        else // 닫는 괄호인 경우(레이저인 경우/레이저가 아닌 경우)
        {
            if (str[i - 1] == '(') // 레이저인 경우
            {
                s.pop();
                ans += s.size();
            }
            else // 레이저가 아닌 경우
            {
                s.pop();
                ans++;
            }
        }
    }
    cout << ans;
}

https://www.acmicpc.net/problem/4949

문제 설명

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다. 정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입출력

• 입력 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다. ➡️ string 라이브러리에 속하는 getline 을 통해 문자열을 입력 받음

• 출력 각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

풀이

• 사용한 자료구조
  • stack<char> s ➡️ 문자열내 문자를 하나씩 돌면서 여는 괄호가 나오면 저장
• 풀이 내용

1. 여는 괄호((, [)가 나오면 스택에 추가(push)
2. 닫는 괄호가 나왔을 경우, 2-1. 스택이 비어있으면 올바르지 않은 괄호 쌍(empty) 2-2. 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍 2-3. 스택의 top이 짝이 맞는 괄호일 경우 pop
3. 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍

• 코드

  #include <iostream>
  #include <string>
  #include <stack>
  using namespace std;
  

bool check(string ipt) { stack s; for (auto word : ipt) { if (word == '(' || word == '[') // 1. 여는 괄호인 경우 스택에 push s.push(word); else if (word == ')') // 2. 닫는 괄호인 경우 스택에서 pop(쌍이 맞는 경우) { if (!s.empty() && s.top() == '(') s.pop(); else return false; } else if (word == ']') { if (!s.empty() && s.top() == '[') s.pop(); else return false; } }

if (s.empty()) // 3. 스택이 비지 않은 경우(-> 짝을 짓지 못한 괄호가 있음)
    return true;
else
    return false;

} int main() { cin.tie(0); ios::sync_with_stdio(0);

string ipt;

while (true)
{
    getline(cin, ipt);
    if (ipt == ".")
        break;
    bool ans = check(ipt);
    if (ans)
        cout << "yes" << '\n';
    else
        cout << "no" << '\n';
}

}

- **개선한 코드**
`check` 함수를 제외한 다른 부분은 위 코드와 동일
```cpp
bool check(string ipt)
{
    stack<char> s;
    for (auto word : ipt)
    {
        if (word == '(' || word == '[') // 1. 여는 괄호인 경우 스택에 push
            s.push(word);
        else if (word == ')') // 2. 닫는 괄호인 경우 스택에서 pop(쌍이 맞는 경우)
        {
            if (s.empty() || s.top() != '(')
                return false;
            s.pop();
        }
        else if (word == ']')
        {
            if (s.empty() || s.top() != '[')
                return false;
            s.pop();
        }
    }

    if (s.empty()) // 3. 스택이 비지 않은 경우(-> 짝을 짓지 못한 괄호가 있음)
        return true;
    else
        return false;
}

스택이 비어있는지에 대한 여부를 먼저 검사하는 이유

1. 스택이 비어있는데 pop()을 수행하면 런타임 에러가 발생하기 때문에
2. 첫번째 조건의 결과에 따라 두번째 조건을 확인하지 않아도 결과가 정해지도록 선행 조건으로 스택이 비어있는지 검사 (Short-circuit evaluation)

코드의 길이를 좀 더 짧게 하기 위해 기존 조건에서 드모르간 법칙을 적용하여 OR(||) 조건으로 변경하였다.

• 정의

  메모리 상에 원소를 연속하게 배치한 자료구조

• 성질

| 동작 | 시간복잡도 |
| --- | --- |
| k번째(임의 위치) 원소 확인 및 변경 | O(1) |
| 원소를 마지막에 추가 | O(1) |
| 마지막 원소 제거 | O(1) |
| 임의 위치에 원소 추가 | O(N) |
| 임의 위치의 원소 제거 | O(N) |
- 추가적으로 소모되는 메모리의 양(=오버헤드)가 거의 없음
- Cache Hit Rate가 높음
- 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

기능과 구현

• 배열 선언

    int test[5];

  → 배열 요소가 5개인 배열 선언

• 배열 값 접근

    test[1] 

  → [] 안에 첨자(인덱스;index)를 넣어 특정 요소를 참조할 수 있다.

  → 배열의 인덱스는 0에서 시작해서 마지막 첨자는 요소 수 - 1 이 된다.

• 값 대입 및 출력

    배열명[첨자] = 식;

• 전체를 특정 값으로 초기화할 때

    int a[21];
    int b[21][21];
  
    // 1. memset
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
  
    // 2. for
    for(int i = 0; i < 21; i++)
        a[i] = 0;
    for(int i = 0; i < 21; i++)
        for(int j = 0; j < 21; j++)
            a[i][j] = 0;
  
    // 3. fill
    fill(a, a+21, 0);
    for(int i = 0; i < 21; i++)
        fill(b[i], b[i] + 21, 0)

• 동적 배열

  배열의 크기를 나타내는 값은 const로 선언된 상수 변수 혹은 리터럴 상수만 들어갈 수 있다.

    int n;
    cin >> n;
    int* arr = new int[n]

  배열의 크기를 미리 알지 못할때는 배열의 크기를 너무 크게 잡기에도 메모리 낭비이고 너무 작게 잡아도 나중에 indexOutOfRange 예외가 발생해 쓰레기 값에 접근하게 된다. (→ vector 로 이 한계를 극복)

STL vector

• 배열과 거의 동일한 기능을 수행하는 자료구조로 배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있다.
• 동적으로 크기를 확장/축소 할 수 있다는 장점이 있다.

https://www.acmicpc.net/problem/1935

문제 설명

후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.

입출력

• 입력 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. 3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 100보다 작거나 같은 자연수이다.

  후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같은 입력만 주어진다.

• 출력 계산 결과를 소숫점 둘째 자리까지 출력한다.

풀이

• 사용한 자료구조
  • vetor<int> operand(26) : 입력되는 피연산자 저장
  • stack<double> st : 중간 계산 결과 저장
• 풀이 내용

1. 후위표기식 문자 단위로 처음부터 끝까지 탐색
   • 연산자인 경우 스택에서 2개의 숫자를 꺼내 계산후 계산 결과를 push(두번째 pop 되는 숫자를 기준으로 연산)
   • 피연산자인 경우 스택에 추가
2. 스택의 top 출력

• 코드

  #include <iostream>
  #include <string>
  #include <vector>
  #include <stack>
  using namespace std;
  

int main(void) { ios::sync_with_stdio(0); cin.tie(0);

int N;          // 피연산자 개수
string postfix; // 후위 표기식

vector<int> operand(26); // 입력한 피연산자
stack<double> st;

cin >> N >> postfix;

for (int i = 0; i < N; i++)
{
    cin >> operand[i];
}

// 후위표기식의 길이 만큼 반복
for (int i = 0; i < postfix.length(); i++)
{
    // 피연산자인 경우
    if (postfix[i] >= 'A' && postfix[i] <= 'Z')
    {
        st.push(operand[postfix[i] - 'A']);
    }
    else // 연산자인 경우
    {
        if (!st.empty())
        {
            double temp = st.top();
            st.pop();
            switch (postfix[i])
            {
            case '+':
                temp = st.top() + temp;
                break;
            case '-':
                temp = st.top() - temp;
                break;
            case '*':
                temp = st.top() * temp;
                break;
            case '/':
                temp = st.top() / temp;
                break;
            }
            st.pop();
            st.push(temp); // 계산한 결과 push
        }
    }
}
// 소수점 둘째 자리까지 출력
cout << fixed;
cout.precision(2);
cout << st.top() << '\n';

} ```

https://www.acmicpc.net/problem/1158

문제 설명

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입출력

• 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

• 출력 예제와 같이 요세푸스 순열을 출력한다.

풀이

• 사용한 자료구조 : 연결리스트
• 풀이 내용 iterator를 입력한 K-1번 만큼 이동 iterator가 end인 경우 begin으로 변경해줘야 한다.
• 코드

  #include <iostream>
  #include <list>
  using namespace std;
  

int N, K;

int main(void) { ios::sync_with_stdio(0); cin.tie(0);

cin >> N >> K;

list L;

// 1~N 까지의 숫자 리스트에 추가 for (int i = 1; i <= N; i++) L.push_back(i); list::iterator t = L.begin();

cout << "<"; int temp; while (L.size()) { for (int i = 1; i < K; i++) { if (++t == L.end()) { t = L.begin(); continue; } } if (L.size() == 1) cout << *t; else cout << *t << ", ";

t = L.erase(t);
// 삭제한 원소 자리가 이미 end인 경우 begin으로 보내줌
t = (t == L.end()) ? L.begin() : t;

}

cout << ">"; }

```

https://www.acmicpc.net/problem/1874

문제 설명

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입출력

• 입력 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

• 출력 입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

풀이

• 사용한 자료구조 : 스택, 벡터

  • 스택 : 수열을 만들 수 있는지 확인하기 위해 활용하는 자료구조
  • 벡터 : 수열을 만들 수 있을 때 필요한 연산들을 저장하는 자료구조

• 풀이 내용

  • 초기 설정 : 스택에 0 push

    초기에 스택에 0을 push 하는 이유? while 반복문에서 스택의 top을 반복 조건으로 활용하는데 0을 push하지 않으면 스택에 아무 원소도 없는 상황이 발생한다. 이렇게 될 경우 반복 조건에서 top 함수를 사용할 때 문제가 발생하게 된다.

  1. 사용자가 입력한 수와 스택의 top이 같아질때까지 push

  2. push작업을 완료한 뒤 pop작업 2-1. top = 사용자가 입력한 num 인 경우 pop 작업 수행 2-2. top != 사용자가 입력한 num 인 경우 valid를 false로 변경

     *valid를 false로 변경하는 이유? * 스택의 제일 위 원소가 입력한 원소보다 큰 경우에는 수열을 만들 수 없다.

  3. valid 값에 따라 출력

     • valid = true 필요한 연산을 저장한 벡터 원소 출력
       • valid = false NO 출력

• 코드

  #include <iostream>
  #include <stack>
  #include <vector>
  using namespace std;
  

stack sequence; vector ans; int n; int cur_num;

int main(void) { ios::sync_with_stdio(0); cin.tie(0);

sequence.push(cur_num);
cur_num++;

int num;
bool valid = true;

cin >> n;


for (int i = 0; i < n; i++) {
    cin >> num;
    // stack 의 top이 num과 같아질때까지 반복
    while (sequence.top() < num) {
        sequence.push(cur_num);
        cur_num++;
        ans.push_back('+');
    }
    if (sequence.top() == num) {
        sequence.pop();
        ans.push_back('-');
    }
    else {
        valid = false;
    }
}

if (!valid) {
    cout << "NO" << '\n';
}
else {
    for (auto ch : ans) {
        cout << ch << '\n';
    }
}

} ```

https://www.acmicpc.net/problem/108664

문제 설명

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

push_front X: 정수 X를 덱의 앞에 넣는다. push_back X: 정수 X를 덱의 뒤에 넣는다. pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 덱에 들어있는 정수의 개수를 출력한다. empty: 덱이 비어있으면 1을, 아니면 0을 출력한다. front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입출력

• 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

• 출력 출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이

• 사용한 자료구조 : 덱
• 풀이 내용 STL deque 기본 함수를 이용하여 구현
• 코드

  #include <iostream>
  #include <deque>
  using namespace std;
  

const int MX = 100005; int dat[MX]; int N; int main(void) { ios::sync_with_stdio(0); cin.tie(0);

deque<int> dq;


string comm;
int num;

cin >> N;
for (int i = 0; i < N; i++) {
    cin >> comm;
    if (comm == "push_front") {
        cin >> num;
        dq.push_front(num);
    }
    else if (comm == "push_back") {
        cin >> num;
        dq.push_back(num);
    }
    else if (comm == "pop_front") {
        if (!dq.size()) {
            cout << -1 << '\n';
        }
        else {
            cout << dq.front() << '\n';
            dq.pop_front();
        }
    }
    else if (comm == "pop_back") {
        if (!dq.size()) {
            cout << -1 << '\n';
        }
        else {
            cout << dq.back() << '\n';
            dq.pop_back();
        }
    }
    else if (comm == "size") {
        cout << dq.size() << '\n';
    }
    else if (comm == "empty") {
        if (dq.empty()) {
            cout << 1 << '\n';
        }
        else {
            cout << 0 << '\n';
        }
    }
    else if (comm == "front") {
        if (dq.empty()) {
            cout << -1 << '\n';
        }
        else {
            cout << dq.front() << '\n';
        }
    }
    else if (comm == "back") {
        if (dq.empty()) {
            cout << -1 << '\n';
        }
        else {
            cout << dq.back() << '\n';
        }
    }
}

}

https://www.acmicpc.net/problem/2164

문제 설명

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, (1) 제일 위에 있는 카드를 바닥에 버린다. 그 다음, (2) 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입출력

• 입력 첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.
• 출력 첫째 줄에 남게 되는 카드의 번호를 출력한다.

풀이

• 사용한 자료구조 : 큐 카드 묶음에서 위에서는 카드를 버리는 동작만, 아래에서는 카드를 추가하는 동작만 발생하므로 큐를 선택
• 풀이 내용
  1. 1부터 사용자가 입력한 N까지 큐에 추가
  2. 큐에 남은 원소가 1개가 될때까지 반복 동작 중에 원소가 1개가 되는 경우가 있기 때문에 동작 중간에((1), (2) 중간) 원소가 1개가 되었는지 확인

• 코드

  #include <iostream>
  #include <queue>
  using namespace std;
  

int N; int main(void) { ios::sync_with_stdio(0); cin.tie(0);

cin >> N;
queue<int> deck;


for (int i = 1; i <= N; i++) {
    deck.push(i);
}
while (deck.size() > 1) {
    // 1. 제일 위 카드 버리기
    deck.pop();
    if (deck.size() == 1) break; // 제일 위의 카드 버렸는데 1장 남았으면 동작 종료
    // 2. 제일 위의 카드 제일 아래로 옮기기 
    // 2-1. 제일 위의 원소 뒤에 push
    deck.push(deck.front());
    // 2-2. 제일 위의 원소 pop
    deck.pop();
}
cout << deck.front() << '\n';

} ```

https://www.acmicpc.net/problem/18258

문제 설명

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입출력

• 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

• 출력 출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이

1. 배열로 구현

• 사용한 자료구조 : 배열
• 풀이 내용
  • front : 큐의 제일 앞부분
  • rear : 큐의 제일 뒷부분
  • 초기 상태
    • front : 0
    • rear : 0
  • push 하는 경우 front는 변하지 않고 rear는 이전보다 1 증가
    • front(t+1) : front(t)
    • rear(t+1) : rear(t) + 1
  • pop 하는 경우 rear는 변하지 않고 front는 이전보다 1증가
    • front(t+1) : front(t) + 1
    • rear(t+1) : rear(t) + 1
• 코드

  #include <iostream>
  using namespace std;
  
  

const int MX = 100005; int dat[MX]; int front, rear; int N; int main(void) { ios::sync_with_stdio(0); cin.tie(0);

string comm;


cin >> N;
for (int i = 0; i < N; i++) {
    cin >> comm;
    if (comm == "push") {
        int num;
        cin >> num;
        dat[rear++] = num;
    }
    else if (comm == "pop") {
        if ((rear - front) == 0) {
            cout << -1 << '\n';
        }
        else {
            cout << dat[front++] << '\n';
        }
    }
    else if (comm == "size") {
        cout << rear - front << '\n';
    }
    else if (comm == "empty") {
        if ((rear - front) == 0) {
            cout << 1 << '\n';
        }
        else {
            cout << 0 << '\n';
        }
    }
    else if (comm == "front") {
        if ((rear - front) == 0) {
            cout << -1 << '\n';
        }
        else {
            cout << dat[front] << '\n';
        }

    }
    else if (comm == "back") {
        if ((rear - front) == 0) {
            cout << -1 << '\n';
        }
        else {
            cout << dat[rear-1] << '\n';
        }
    }
}

}

### 2. STL queue로 구현
- 사용한 자료구조 : 큐
- 풀이 내용
    STL queue 기본 함수들을 이용하여 구현
- 코드
```cpp
#include <iostream>
#include <queue>
using namespace std;


int N;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    queue<int> myqueue;
    string comm;


    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> comm;
        if (comm == "push") {
            int num;
            cin >> num;
            myqueue.push(num);
        }
        else if (comm == "pop") {
            if (myqueue.empty()) {
                cout << -1 << '\n';
            }
            else {
                cout << myqueue.front() << '\n';
                myqueue.pop();
            }
        }
        else if (comm == "size") {
            cout << myqueue.size() << '\n';
        }
        else if (comm == "empty") {
            cout << (int)myqueue.empty() << '\n';
        }
        else if (comm == "front") {
            if (myqueue.empty()) {
                cout << -1 << '\n';
            }
            else {
                cout << myqueue.front() << '\n';
            }
        }
        else if (comm == "back") {
            if (myqueue.empty()) {
                cout << -1 << '\n';
            }
            else {
                cout << myqueue.back() << '\n';
            }
        }
    }
}

https://www.acmicpc.net/problem/9012

문제 설명

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

입출력

• 입력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

• 출력 출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

풀이

• 사용한 자료구조 : stack
• 풀이 내용
  1. '(' 일 때 stack에 push
  2. ')' 일 때
     • stack이 비어있지 않다면 pop
     • stack이 비어있다면 "NO"
  3. 입력으로 온 문자열 확인 마친 경우
     • stack이 비어있는 경우 "YES"
     • stack이 비어있지 않은 경우 "NO"
• 코드 괄호 문자열을 판단하는 것을 함수로 구현

#include <iostream>
#include <stack>
using namespace std;


int T;

string checkVPS(string input) {
    stack<char> ps;
    for (int i = 0; i < input.size(); i++) {
        if (input[i] == '(') {
            ps.push('(');
        }
        else {
            if (ps.empty()) return "NO";
            ps.pop();
        }
    }
    if (ps.empty()) {
        return "YES";
    }
    else {
        return "NO";
    }
}
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string ps;

    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> ps;
        cout << checkVPS(ps) << '\n';
    }
}

https://www.acmicpc.net/problem/10828

문제 설명

정수를 저장하는 스택을 구현하여 입력으로 주어지는 명령을 처리하는 프로그램을 작성

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입출력

• 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

• 출력 출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이

1. 배열로 구현

• 배열로 구현한 스택에서 top은 dat[pos-1]로 조회할 수 있다.
• 스택에 담긴 아이템의 개수는 pos로 조회할 수 있다.

  #include <iostream>
  using namespace std;
  

const int MX = 100005; int dat[MX]; int pos = 0;

int main(void) { ios::sync_with_stdio(0); cin.tie(0);

int N; cin >> N;

string s; int x; for (int i = 0; i < N; i++) { cin >> s; if (s == "push") { cin >> x; dat[pos++] = x; } else if (s == "pop") { if (!pos) cout << -1 << '\n'; else { pos--; cout << dat[pos] << '\n'; } } else if (s == "size") { cout << pos << '\n'; } else if (s == "empty") { if (pos) cout << 0 << '\n'; else cout << 1 << '\n'; } else if (s == "top") { if (!pos) cout << -1 << '\n'; else cout << dat[pos - 1] << '\n'; } } }

### 2. STL list로 구현
```cpp
#include <iostream>
#include <list>
using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    list<int> mystack;
    int N;    // 명령의 수
    int num; // push 명령에서 입력으로 주어지는 수
    string command; // 입력으로 주어지는 명령


    cin >> N;

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

        if (command == "push") {
            cin >> num;
            mystack.push_back(num);
        }
        else if (command == "pop") {
            if (mystack.empty()) {
                cout << -1 << '\n';
            }
            else {
                cout << mystack.back() << '\n';
                mystack.pop_back();
            }
        }
        else if (command == "size") {
            cout << mystack.size() << '\n';
        }
        else if (command == "empty") {
            if (mystack.empty()) {
                cout << 1 << '\n';
            }
            else {
                cout << 0 << '\n';
            }
        }
        else if (command == "top") {
            if (mystack.empty()) {
                cout << -1 << '\n';
            }
            else {
                cout << mystack.back() << '\n';
            }
        }
    }

}

3. STL stack으로 구현

• stackname.empty()는 스택이 비어있으면 True, 스택이 비어있지 않다면 False를 반환
  • empty 명령에 대한 출력은 stackname.empty()를 int형으로 형변환하여 출력한다.

    #include <iostream>
    #include <stack>
    using namespace std;
    

int main(void) { ios::sync_with_stdio(0); cin.tie(0);

stack S; int N; cin >> N;

string s; while (N--) { cin >> s; if (s == "push") { int t; cin >> t; S.push(t); } else if (s == "pop") { if (S.empty()) cout << -1 << '\n'; else { cout << S.top() << '\n'; S.pop(); } } else if (s == "size") cout << S.size() << '\n'; else if (s == "empty") cout << (int)S.empty() << '\n'; else // top { if (S.empty()) cout << -1 << '\n'; else cout << S.top() << '\n'; } } } ```

인덱스는 검색 연산의 최적화를 위해 데이터베이스 내 열에 대한 정보를 구성한 데이터 구조이다.

• 인덱스를 통해 전체 데이터의 검색 없이 필요ㅛ한 정보에 대해 신속한 조회가 가능하다.
• INSERT, UPDATE, DELETE 등과 같은 DML 작업은 테이블과 인덱스를 함께 변경해야 하기 때문에 오히려 느려질 수 있다는 단점이 존재한다.

1.1 트리 기반 인덱스

DBMS 에서 가장 일반적인 B-트리 인덱스

• 브랜치 블록 중에서 가장 상위에 있는 블록을 루프 블록이라고 한다.
• 브랜치 블록은 다음 단계의 블록을 가리키는 포인터를 가지고 있다.
• 리프 블록은 트리의 가장 아래 단계에 존재한다.
• 리프 블록은 (컬럼 데이터, 해당 데이터 행의 위치-RID)로 구성된다.
• 인덱스 데이터는 인덱스를 구성하는 컬럼의 값으로 정렬된다.
• 리프 블록은 양방향 링크를 가지고 있다. (오름차순/내림차순 검색을 쉽게 할 수 있다.)
• B-트리 인덱스는 =로 검색하는 일치검색과 BETWEEN, > 등과 같은 연산자로 검색하는 범위검색에 모두 적합하다.

Oracle 에서 트리 기반 인덱스에는 B-트리 인덱스 외에도 비트맵 인덱스, 리버스 키 인덱스, 함수 기반 인덱스 등이 존재한다.

1.2 클러스터형 인덱스(SQL Server)

SQL Server에서는 저장 구조에 따라 클러스터형 인덱스와 비클러스터형 인덱스가 있다.

클러스터형 인덱스

• 인덱스의 리프 페이지가 곧 데이터 페이지이다. 클러스터형 인덱스의 리프 페이지를 탐색하면 해당 테이블의 모든 컬럼 값을 곧바로 얻을 수 있다.
• 리프 페이지의 모든 로우(데이터)는 인덱스 키 컬럼 순으로 물리적으로 정렬되어 저장된다.
• 클러스터형 인덱스는 물리적으로 한가지 순서로만 정렬될 수 있다. 테이블당 한개만 생성할 수 있다.

2. 전체 테이블 스캔과 인덱스 스캔

2.1 전체 테이블 스캔

테이블에 존재하는 모든 데이터를 읽어 가면서 조건에 맞으면 결과로서 추출하고 조건에 맞지 않으면 버리는 방식으로 검색한다.

전체 테이블 스캔 방식은 테이블에 존재하는 모든 블록의 데이터를 읽기 때문에 시간이 오래 걸릴 수 있다.

2.2 인덱스 스캔

• 인덱스의 리프 블록 : 인덱스 구성 컬럼 + 레코드 식별자(RID)
• 인덱스는 인덱스 구성 컬럼의 순서로 정렬되어 있다.

1. 인덱스 유일 스캔 : 유일 인덱스(Unique Index)를 사용하여 단 하나의 데이터를 추출하는 방식, 중복을 허락하지 않음
2. 인덱스 범위 스캔 : 인덱스를 이용하여 한 건 이상의 데이터를 추출하는 방식
3. 인덱스 역순 범위 스캔 : 인덱스 리프 블록의 양방향 링크를 이용하여 내림 차순으로 데이터를 읽는 방식

조인이란? 2개 이상의 테이블을 하나의 테이블로 만드는 연산

• 종류
  • NL Join
  • Sort Merge Join
  • Hash Join

1. NL Join

두개의 테이블을 중첩된 반복문처럼 조인을 수행한다. 반복문 외부에 있는 테이블을 선행 테이블 또는 외부테이블이라고 한다. 반복문 내부에 있는 테이블을 후행 테이블 또는 내부테이블이라고 한다.

for 선행 테이블 읽음 
    for 후행 테이블 읽음
        (선행 테이블과 후행 테이블 조인)

선행 결과값을 줄이기 위해 결과 행의 수가 적은 테이블을 선행 테이블로 선택한다.

2. Sort Merge Join

조인 컬럼을 기준으로 데이터를 정렬하여 조인한다. 넓은 범위의 데이터를 처리할 때 주로 이용한다. 정렬 데이터가 많을 경우 성능이 떨어질 수 있다.(디스크 I/O로 인한 부하 발생) 비동등 조인에 대해서도 조인이 가능하다. 인덱스를 사용하지 않아 인덱스가 존재하지 않을 경우에 사용할 수 있다.

3. Hash Join

해싱 기법을 이용하여 조인을 수행한다. NL Join 의 랜덤 액세스 문제와 Sort Merge Join 의 정렬 작업의 부하를 해결하기 위한 대안으로 사용된다. 조인 컬럼의 인덱스가 존재하지 않을때에도 사용할 수 있다. 해시 함수를 사용하기 때문에 동등 조인만 가능하다. 해시 테이블의 크기가 메모리에 적재할 수 있는 크기보다 커지면 디스크를 사용한다.

SQL을 가장 빠르고 효율적으로 수행할 최적의 처리 경로를 생성해주는 DBMS 내부의 핵심 엔진

최적의 실행 방법을 실행꼐획(Execution Plan)이라고 한다.

1.1 옵티마이저 유형

1.1.1 규칙기반 옵티마이저

• 인덱스를 이용한 액세스 방식이 전체 테이블 액세스 방식보다 우선수위가 높다.
• 조인 순서를 결정할 때 조인 컬럼의 인덱스 존재 유무가 중요한 판단의 기준이 된다.
  • 조인 컬럼에 대한 인덱스가 양쪽에 존재 : 우선순위가 높은 테이블이 선행 테이블
  • 한쪽에만 인덱스 존재 : 인덱스가 없는 테이블이 선행 테이블
  • 모두 인덱스 존재 안함 : FROM 절 뒤에 나열된 테이블이 선행 테이블
  • 우선순위가 동일 : FROM 절에 나열된 테이블의 역순으로 선행 테이블 선택

1.1.2 비용기반 옵티마이저

• 질의 변환기 : 사용자가 작성한 SQL문을 처리하기에 보다 용이한 형태로 변환하는 모듈
• 대안 계획 생성기 : 동일한 결과를 생성하는 다양한 대안 계획을 생성하는 모듈

• 대안 계획이 많아질수록 최적화를 수행하는데 시간이 오래 걸린다.

• 비용 예측기 : 생성된 대안 계획의 비용을 예측하는 모듈

• 인덱스를 사용하는 비용이 전체 테이블 스캔 비용보다 크다고 판단되면 전체 테이블 스캔을 수행하는 방법으로 실행계획을 생성할 수 있다.
• 통계정보, DBMS 버전, DBMS 설정 정보등의 차이로 인해 동일 질의문도 서로 다른 실행 계획이 생성될 수 있다.

2. 실행 계획

SQL에서 요구한 사항을 처리하기 위한 절차와 방법, 실행계획마다 실행 시간(성능)은 다를 수 있음

• 실행계획 구성요소
  • 조인순서
  • 조인기법
  • 액세스 기법
  • 최적화 정보
  • 연산

3. SQL 처리 흐름도

SQL의 내부적인 처리 절차를 시각적으로 표현한 도표

일반적인 개발 언어처럼 SQL 언어에서도 절차 지향적인 프로그램이 가능하도록 하는 트랜잭션 언어이다.

• Oracle : PL(Procedural Language)/SQL

• SQL Server : T-SQL

• DB2 : SQL/PL

• 종류

  1. 프로시저 : 일련의 쿼리들을 마치 하나의 함수처럼 실행하기 위한 쿼리의 집합
  2. 사용자 정의함수 : 일련의 SQL 처리를 수행하고, 수행 결과를 단일 값으로 반환할 수 있는 절차형 SQL
  3. 트리거 : 데이터베이스 시스템에서 삽입, 갱신, 삭제 등의 이벤트가 발생할 때마다 관련 작업이 자동으로 수행되는 절차형 SQL

2. PL/SQL 개요

블럭 구조로 되어 있고 블럭 내에는 DML문장과 Query 문장, 그리고 절차형 언어(IF, LOOP) 등을 사용할 수 있으며 절차적 프로그래밍을 가능하게 하는 트랜잭션 언어이다.

• PL/SQL 구조
• 선언부(DECLARE) : 프로시저의 명칭, 변수와 인수 그리고 그에 대한 데이터 타입을 정의하는 부분
• 시작/종료부(BEGIN/END) : 프로시저의 시작과 종료를 표현
• 제어부(CONTROL) :
• 예외부(EXCEPTION) : BEGIN~END 절에서 실행되는 SQL 문이 실행될 때 예외 발생 시 예외 처리 방법을 정의하는 처리부

2.1 프로시저

• 프로시저 문법

  CREATE [OR REPLACE] PROCEDURE 프로시저명
  (파라미터명 [IN|OUT|INOUT] 데이터타입, ... ... ) 
  IS 
    변수선언
  BEGIN
    명령어;
  [COMMIT|ROLLBACK]
  END;

  • [OR REPLACE] : 기존 프로시저 존재시 현재 컴파일 하는 내용으로 덮어씀
  • [IN|OUT|INOUT] : 변수의 입출력 구분, (운영체제에서 프로시저로 값을 전달하는 모드/프로시저에서 처리된 결과를 운영체제로 전달하는 모드/두가지 기능을 동시에 수행)
  • BEGIN : 프로시저의 시작
  • COMMIT : 하나의 트랜잭션이 성공적으로 끝나고, 데이터베이스가 일관성 있는 상태에 있을 때 하나의 트랜잭션이 끝났을 때 사용하는 연산
  • ROLLBACK : 하나의 트랜잭션이 비정상적으로 종료되어 트랜잭션 원자성이 깨질 경우 처음부터 다시 시작하거나, 부분적으로 연산을 취소하는 연산
  • END : 프로시저의 끝

2.2 사용자 정의함수

• 기본적인 사항은 프로시저와 동일하고 반환에서의 부분만 프로시저와 다르다.
• 사용자 정의함수 문법

  CREATE [OR REPLACE] FUNCTION 함수명
  (파라미터명 IN 데이터타입, ... ... ) 
  RETURN 데이터타입
  IS 
    변수선언
  BEGIN
    명령어;
       RETURN 변수;
  [COMMIT|ROLLBACK]
  END;

• RETURN 데이터타입 : 사용자 정의함수가 반환하는 데이터 타입을 정의
• RETURN 데이터값 : 사용자 정의함수가 종료될 때 반환하는 단일 값을 정의

2.3 트리거

• 데이터베이스 시스템에서 삽입, 갱신, 삭제 등의 이벤트가 발생할 때마다 관련 작업이 자동으로 수행되는 절차형 SQL이다.

• 이벤트는 전체 트랜잭션 대상과 각 행에 의해 발생하는 경우 모두를 포함할 수 있으며 테이블과 뷰, DB 작업을 대상으로 정의할 수 있다.

• 목적

  • 데이터 무결성 유지 및 로그 메시지 출력 등의 별도 처리를 위해 트리거 사용
  • 이벤트와 관련된 테이블의 데이터 삽입, 추가, 삭제 작업을 DBMS가 자동적으로 실행시키는 데 활용

• 종류

  • 행 트리거 : 데이터 변화가 생길 때마다 실행
  • 문장 트리거 : 트리거에 의해 단 한 번 실행

• 트리거 문법

  CREATE [OR REPLACE] TRIGGER 트리거명
  [BEFORE|AFTER] 유형 ON 테이블명
  [FOR EACH ROW]
  BEGIN
  END;

• [BEFORE|AFTER] : DML과 트리거가 실행되는 순서의 전후 관계를 결정

• [FOR EACH ROW] : 매번 변경되는 데이터 행의 수만큼 실행을 위한 명령어

프로시저와 트리거의 차이점

• 데이터 제어어는 데이터베이스 관리자가 데이터 보안, 무결성 유지, 병행 제어, 회복을 위해 관리자(DBA)가 사용하는 제어용 언어이다.

• DCL 유형

• Oracle과 SQL Server의 사용자에 대한 차이점
  • Oracle : 유저를 통해 데이터베이스에 접속하는 형태, 아이디와 비밀번호 방식으로 인스턴스에 접속하고 그에 해당하는 스키마에 오브젝트 생성 등의 권한을 부여 받음
  • SQL Server : 인스턴스에 접속하기 위해 로그인을 생성하며 인스턴스 내에 존재하는 다수의 데이터베이스에 연결하여 작업하기 위해 유저를 생성한 후 로그인과 유저를 매핑, 특정 유저는 특정 데이터베이스 내의 특정 스키마에 대해 권한을 부여받을 수 있음

• 유저 생성과 시스템 권한 부여 유저를 생성하고 데이터베이스에 접속한다. 하지만 데이터베이스에 접속했다고 해서 데이터베이스 오브젝트를 생성할 수는 없다. 사용자가 실행하는 모든 DDL문장은 그에 해당하는 적절한 권한이 있어야 실행할 수 있다.

• GRANT

  GRANT 권한 ON 테이블 TO 사용자;

• REVOKE

  REVOKE 권한 ON 테이블 FROM 사용자;

• 윈도 함수는 데이터베이스를 사용한 온라인 분석 처리 용도로 사용하기 위해서 표준 SQL에 추가된 함수이다.
• 윈도 함수를 OLAP 함수라고 한다.
• 행과 행간의 관계를 쉽게 정의하기 위해 만든 함수이다.

1.1 윈도 함수 구문

SELECT 함수명(파라미터)
    OVER
   ([PARTITION BY 컬럼1, ...]
   [ORDER BY 컬럼A, ...])
   FROM 테이블명

• OVER 구문이 필수적으로 필요
• PARTITION BY(선택 항목)은 순위를 정할 대상 범위의 컬럼을 설정(이를 통해 구분된 레코드 집합을 윈도라고 함)
• ORDER BY 뒤에는 SORT 컬럼을 입력(어떤 열을 어떤 순서로 순위를 정할지를 지정)

1.2 윈도 함수 종류

2. 순위 함수

SELECT NAME, SALARY,
RANK() OVER(ORDER BY SALARY DESC) A,
DENSE_RANK() OVER(ORDER BY SALARY DESC) B,
ROW_NUMBER() OVER(ORDER BY SALARY DESC) C
FROM EMP;

3. 행순서 함수

SELECT NAME, SALARY,
    FIRST_VALUE(NAME) OVER(ORDER BY SALARY) A,
    LAST_VALUE(NAME) OVER(ORDER BY SALARY) B,
    LAG(NAME) OVER(ORDER BY SALARY DESC) C,
    LEAD(NAME) OVER(ORDER BY SALARY DESC) D
FROM EMP;

4. 그룹 내 비율 함수

SELECT NAME, SALARY,
    RATIO_TO_REPORT(SALARY) OVER() A,
    PERCENT_RANK() OVER(ORDER BY SALARY DESC) B
FROM EMP;

데이터 분석 함수

총합, 평균 등의 데이터 분석을 위해서는 복수 행 기준의 데이터를 모아서 처리하는 것을 목적으로 하는 다중행 함수이다.

• 특성

  • 단일행을 기반으로 산출하지 않고 복수행을 그룹별로 모아 놓고 그룹당 단일 계산 결과를 반환
  • GROUP BY 구문을 사용해 복수행을 그룹핑
  • SELECT, HAVING, ORDER BY 등의 구문에 활용

• ANSI/ISO SQL 표준은 데이터 분석을 위해 다음 세가지 함수를 정의한다.

2. 집계 함수

여러 행 또는 테이블 전체 행으로부터 하나의 결괏값을 반환하는 함수

• 집계 함수 구문

  SELECT 컬럼1, 컬럼2, ..., 집계함수
  FROM 테이블명
  [WHERE 조건]
  GROUP BY 컬럼1, 컬럼2, ...
  [HAVING 조건식(집계함수 포함)]

• GROUP BY 에서 주의할 점
  • NULL 값은 제외하고 산출한다.
  • SELECT 절에서 처럼 ALIAS 사용이 불가하다.
  • 집계함수 구문을 사용할 수 없다.

집계함수는 NULL이 포함된 경우 없는 데이터로 판단한다.

3. 그룹 함수

테이블의 전체 행을 하나 이상의 컬럼을 기준으로 컬럼 값에 따라 그룹화하여 그룹별로 결과를 출력하는 함수

3.1 ROLLUP 함수

• ROLLUP 에 의해 지정된 컬럼은 소계(소그룹의 합계) 등 중간 집계 값을 산출하기 위한 그룹 함수이다.
• 지정 컬럼 수보다 하나 더 큰 레벨만큼의 중간 집계 값이 생성된다.
• ROLLUP의 지정 컬럼은 계층별로 구성되기 때문에 순서가 바뀌면 수행 결과가 바뀐다.

SELECT 컬럼1, 컬럼2, ..., 집계 함수
FROM 테이블명
[WHERE ...]
GROUP BY [컬럼...] ROLLUP 컬럼
[HAVING ...]
[ORDER BY ...]

SELECT 뒤에 포함되는 컬럼이 GROUP BY 또는 ROLLUP 뒤에 기재되어야 한다.

• 예시

  SELECT DEPT, JOB, SUM(SALARY)
  FROM DEPT_SALARY
  GROUP BY ROLLUP(DEPT, JOB);

3.2 CUBE 함수

• CUBE는 결합 가능한 모든 값에 대해 다차원 집계를 생성하는 그룹 함수 이다.
• 연산이 많아 시스템에 부담을 준다.

SELECT 컬럼1, 컬럼2, ..., 집계 함수
FROM 테이블명
[WHERE ...]
GROUP BY [컬럼...] CUBE(컬럼명 a, ..)
[HAVING ...]
[ORDER BY ...]

3.3 GROUPING SETS 함수

• 집계 대상 컬럼들에 대한 개별 집계를 구할 수 있으며, ROLLUP이나 CUBE와는 달리 컬럼 간 순서와 무관한 결과를 얻을 수 있는 그룹함수이다.
• 다양한 소계 집합을 만들 수 있다.
• ORDER BY를 사용해서 집계 대상 그룹과의 표시 순서를 조정하여 체계적으로 보여줄 수 있다.
• 계층구조와 달리 인수들이 평등한 관계라 순서에 상관없이 동일한 결과를 볼 수 있다.

  SELECT 컬럼1, 컬럼2, ..., 집계 함수
  FROM 테이블명
  [WHERE ...]
  GROUP BY [컬럼...] GROUPING SETS(컬럼명 a, ..)
  [HAVING ...]
  [ORDER BY ...]

• GROUPINT SETS 함수 사용시 UNION ALL을 사용한 일반 그룹함수를 사용한 SQL과 같은 결과를 얻을 수 있으며, 괄호로 묶은 집합 별로 집계를 구할 수 있다.
• GROUPING SETS의 경우 일반 그룹함수를 이용한 SQL과 결과 데이터는 같으나 행들의 정렬 순서는 다를 수 있다.

SQL 문 안에 포함된 또 다른 SQL 문이다.

• 주의사항
  • 서브쿼리를 괄호로 감싸서 사용한다.
  • 서브쿼리는 단일 행 또는 복수 행 비교 연산자와 함께 사용 가능하다.
  • 서브쿼리에서는 ORDER BY 절을 사용하지 못한다. ORDER BY 절은 SELECT 절에서 오직 한 개만 올 수 있기 때문에 ORDER BY 절은 메인 쿼리의 마지막 문장에 위치해야 한다.

• 서브쿼리가 SQL 문에서 사용 가능한 곳
  • SELECT 절 스칼라 서브쿼리는 한 행, 한 컬럼만을 반환하는 서브쿼리이다. 결과가 2건 이상 반환되면 SQL 문은 오류를 반환한다.
  • FROM 절 FROM 절에서 사용되는 서브쿼리를 인라인 뷰라고 한다. 인라인 뷰는 SQL문이 실행될 때 임시적으로 생성되는 동적인 뷰이기 때문에 데이터베이스에 해당 정보가 저장되지 않는다. 그래서 일반적인 뷰를 정적뷰라고 하고 인라인 뷰를 동적뷰라고 한다.
  • WHERE 절
  • HAVING 절 그룹함수와 함께 사용될때 그룹핑된 결과에 대해 부가적인 조건을 주기 위해 사용한다.
  • ORDER BY 절
  • INSERT 문의 VALUES 절
  • UPDATE 문의 SET 절

• 서브쿼리의 유형
  • 동작 방식에 따른 서브쿼리의 종류
  • 반환되는 데이터의 형태에 따른 서브쿼리의 종류
  • 위치 기준

1. 단일행 서브쿼리

서브쿼리가 단일 행 비교 연산자(=, <, <=, >, >=, <>)와 함께 사용할 때 서브쿼리의 결과 건수가 반드시 1건 이하여야 한다.

2. 다중행 서브쿼리

3. 다중 컬럼 서브쿼리

서브쿼리의 결과로 여러 개의 컬럼이 반환되어 메인쿼리의 조건과 동시에 비교되는 것을 의미한다.

4. 연관 서브쿼리

연관 서브쿼리는 서브쿼리 내에 메인쿼리 컬럼이 사용된 서브쿼리이다.

뷰

테이블은 실제로 데이터를 가지고 있는 반면 뷰는 실제 데이터를 가지고 있지 않다. 뷰는 단지 뷰 정의만을 가지고 있다. 질의에서 뷰가 사용되면 뷰 정의를 참조해서 DBMS 내부적으로 질의를 재작성하여 질의를 수행한다. 뷰는 실제 데이터를 가지고 있지 않지만 테이블이 수행하는 역할을 수행하기 때문에 가상 테이블이라고도 한다.

• 뷰 생성

  CREATE VIEW [뷰 이름] AS
  [SELECT 문];

• 뷰 삭제

  DROP VIEW [뷰 이름];

테이블에 계층형 데이터가 존재하는 경우 데이터를 조회하기 위해 계층형 질의(Hierarchical Query) 사용

계층형 데이터

동일 테이블에 계층적으로 상위와 하위 데이터가 포함된 데이터, 엔티티를 순환관계 데이터 모델로 설계할 경우 계층형 데이터 발생

• 루트 노드(루트 데이터) 가장 최상위의 데이터
• 리프 노드(리프 데이터) 가장 최하위의 데이터

기본적인 계층형 질의 형태

SELECT ...
FROM ...
WHERE 조건
START WITH 조건
CONNECT BY [NOCYCLE] 조건
[ORDER SIBLINGS BY 컬럼명1, 컬럼명2...];

가. Oracle 계층형 질의

• 계층형 질의에서 사용되는 가상 컬럼

• 계층형 질의에서 사용되는 함수

나. SQL Server 계층형 질의

2000 버전 까지는 계층형 질의를 작성할 수 있는 문법을 지원하지 않았다. 조직도처럼 계층적 구조를 가진 데이터는 저장 프로시저를 재귀 호출하거나 While 루프 문에서 임시 테이블을 사용하는 등 순수한 쿼리가 아닌 프로그램 방식으로 전개한다. 하지만 SQL Server 2005 버전부터 하나의 질의로 원하는 결과를 얻을 수 있다.

• 재귀적 쿼리의 처리 과정

1. CTE 식을 앵커 멤버와 재귀 멤버로 분할
2. 앵커 멤버를 실행하여 첫 번째 호출 또는 기본 결과 집합 생성
3. Ti는 입력으로 사용하고 Ti+1은 출력으로 사용하여 재귀 멤버 실행
4. 빈 집합이 반환될 때까지 3단계 반봅
5. 결과 집합을 반환. 이것을 T0~Tn까지 UNION ALL