※ Recursion (순환 / 재귀)

흔히들 재귀라 부르는 recursion은 함수가 자기자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.

보통 우리는 이렇게 반복을 요하는 문제에서는 반복문(for, while)을 사용하는 경우가 많다. 또한, 이런 반복문의 효율성은 무시하지 못할 것이다. 일반적으로 재귀보다는 반복문이 더욱 효율적이고 값 도출시간도 빠르다.

 

출처: https://www.scaler.com/topics/python/recursion-in-python/

 

 

§  최대공약수

auto gcd(int A, int B){
    if (B == 0)
        return A;
    else
        return gcd(B, A%B);
}

https://chan4im.tistory.com/58

 

[Baekjoon/백준] 13241번: [Recursion] (C/C++) ★★☆

※ 이번 문제에서 알게된 점 § 재귀함수로 구현하는 gcd, lcm 함수 // 최대공약수 auto gcd(long long A, long long B){ if (B == 0) return A; else return gcd(B, A%B); } // 최소공배수 auto lcm (long long A, long long B){ return A*B

chan4im.tistory.com

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

 

13241번: 최소공배수

정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다

www.acmicpc.net

 

 

 

 

 

 

 

 

 

※ 재귀를 사용하는 이유

이렇게 반복문보다 효율이 떨어지는 재귀를 도대체 우리는 사용하는 이유와 배워야 하는 이유가 무엇일까?

바로 재귀만이 갖는 자기자신의 호출로 특정 문제나 알고리즘에서 매우 강력(powerful)한 경우가 있다.

 

재귀로 짜면 간단하게 2~3줄로 나올 코드가 반복문으로 몇십줄이 넘어갈 수 도 있으니 말이다.

 

대표적인 예를 들어보자면 다음과 같다.

- 거듭제곱, 팩토리얼의 계산

백준 10872번: https://www.acmicpc.net/problem/10872

 

10872번: 팩토리얼

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

www.acmicpc.net

- 피보나치 수열의 계산

백준 2747번: https://www.acmicpc.net/problem/2747

 

2747번: 피보나치 수

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가

www.acmicpc.net

- 하노이탑 문제

백준 1914번: https://www.acmicpc.net/problem/1914

 

1914번: 하노이 탑

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로

www.acmicpc.net

 

 

#include <iostream>
using namespace std;

int fac(int num){
    if (num > 1)
        return num * fac(num-1);  // num: 해결된 부분  // fac(num-1): 남은부분
    else
        return 1;
}

int main() {
    int num;
    cin >> num;
    cout << fac(num);
}

이때, 재귀를 멈추는 부분 

if (num > 1)
    return num * fac(num-1);
else
    return 1;

위와 같은 재귀를 멈추는 부분이 없다면 시스템 stack을 모두 사용한 이후 Err가 발생하며 멈출 것이다. (stackoverflow)

 

 

이렇게 반복에 비해 알고리즘을 훨씬 명확하고 간결하게 나타낼 수 있다는 장점이 있으나 아래와 같이 수행속도면에서는 현저히 떨어지는 것을 볼 수 있다.

좌) for 반복문&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;우) 재귀함수

 

 

 

 

 

 

 

※ Recursion의 시간복잡도

재귀는 작은 동일한 문제들로 분해하여 해결하는 방법인 분할정복 알고리즘의 일종이다.

5! -> 4! -> 3! -> 2! -> 1! 으로 작은 문제 즉, 본래의 problem을 subproblem으로 나누어 최소 size부터 해결하는 방식이다.

최소 subproblem부터 다시 본래의 problem size로 돌아가면서 정복하는, 이런 방식을 분할정복 알고리즘이라 부른다.

 

그렇다면 이런 재귀함수의 시간복잡도 즉, 성능은 어떻게 될까?

이를 위한 예시는 피보나치 수열문제로 한다.

int fib(int num){
    if (num <= 1)
        return num; 
    else
        return fib(num-1) + fib(num-2);
}

위의 문제에서 피보나치식의 n번째 계산을 위한 연산횟수를 T(n)이라 하자.

T(0) = 1, T(1) = 1이므로 

T(n) = T(n-1) + T(n-2) + 1 > 2 x T(n-2) > 2x2 x T(n-4) > . . . 2 ^ (n/2) x T(0)이므로 

 

 

 

int fib(int num){
    int arr[100] = { 0, 1, };
    if (num < 2 || arr[num] != 0)
        return arr[num];
    else{
        arr[num] = fib(num-1) + fib(num-2);
        return arr[num];
    }
}

그렇다면 다음 예제는 어떨까?

이 기법은 이미 구한 값을 메모리에 저장해두고 다시 사용하는 메모이제이션 (memoization)을 채택한 방법이다.

위 방법의 시간복잡도를 구해보면

T(0) = 1, T(1) = 1이고

T(2) = T(1) + T(0) + 1 = 3

T(3) = T(2) + T(1) + 1 = 5

T(4) = T(3) + T(2) + 1에서 T(2)는 저장한 피보나치 수를 가져오기만 하면 되기 때문에 T(2) = 1이다.

T(3) + T(2) + 1 = 7이고, 같은 이유로 T(5) = T(4) + T(3) + 1에서 T(3) = 1이므로 T(5) = 9이다.

따라서 T(n) = 2n - 1이라고 할 수 이므로

 

 

 

※ 다중 순환 (multiple recursion)

재귀함수는 아래와 같이  3종류로 나눌 수 있다.

- 선형 순환 (linear recursion)

  ex) 팩토리얼계산, 거듭제곱 계산

- 이진 순환 (binary recursion)

  ex) 피보나치수열, 하노이탑 문제

- 다중 순환 (multiple recursion)

 

 

 

 

 

 

※ Queue

큐는 FIFO(First-In-First-Out) 입출력 형태, 즉 선입선출 방식을 가진 자료구조이다.

출처)https://velog.io/@awesomeo184/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%81%90Queue

 

enqueue와 dequeue의 시간복잡도는 둘 다 O(1)의 시간을 갖는다.

단, 탐색의 시간복잡도는 특정 data를 찾을 때까지 돌아야 하므로 O(n)의 시간을 갖는다.

 

 

 

※ queue Container (STL) ★

queue 컨테이너는 deque 클래스의 인터페이스를 제한해 전형적인 큐 메모리 구조의 인터페이스를 제공하는 형태이다.

출처)&nbsp;http://www.tcpschool.com/cpp/cpp_container_adapter

 

 

※ queue 선언방식

#include <queue>

queue<데이터타입> 이름;

 

 

 

[queue 관련 백준문제]

백준 10854번: https://www.acmicpc.net/problem/10854

 

10854번: Divisions

David is a young boy and he loves numbers. Recently he learned how to divide two numbers. David divides the whole day. He is happy if the result of the division is an integer, but he is not very amused if this is not the case. After quite a while he decide

www.acmicpc.net

백준 11866번: https://www.acmicpc.net/problem/11866

 

11866번: 요세푸스 문제 0

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

www.acmicpc.net

백준 1158번: https://www.acmicpc.net/problem/1158

 

1158번: 요세푸스 문제

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

www.acmicpc.net

백준 2164번: https://www.acmicpc.net/problem/2164

 

2164번: 카드2

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

www.acmicpc.net

 

백준 12789번(stack+queue): https://www.acmicpc.net/problem/12789

 

12789번: 도키도키 간식드리미

인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두

www.acmicpc.net

 

 

 

 

 

 

※ deque Container (STL) ★

deque 컨테이너는 double-ended queue를 의미하며 양쪽에 끝이 있는 큐이다.

이 컨테이너는 양 끝에서 빠르게 요소를 삽입, 삭제할 수 있다는 점에서 매우 powerful하다!

또한, 중간에서 원소를 추가, 삭제하는 경우(insert, erase), vector보다 효율이 좀 더 좋다.

(vector는 앞에서 원소를 추가하는 것이 불가능 하기 때문에 모든 원소를 뒤쪽으로 밀어야 하기 때문)

 

 

※ deque 선언방식

#include <deque>

deque<데이터타입> 이름;

 

[deque 관련 백준문제]

백준 10866번: https://www.acmicpc.net/problem/10866

 

10866번: 덱

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

www.acmicpc.net

백준 1021번: https://www.acmicpc.net/problem/1021

 

1021번: 회전하는 큐

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가

www.acmicpc.net

백준 2161번:

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

 

2161번: 카드1

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

www.acmicpc.net

백준 2346번: https://www.acmicpc.net/problem/2346

 

2346번: 풍선 터뜨리기

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선

www.acmicpc.net

백준 20301번: https://www.acmicpc.net/problem/20301

 

20301번: 반전 요세푸스

첫째 줄에 정수 $N$, $K$, $M$이 주어진다. ($1 \leq N \leq 5\ 000$, $1 \leq K, M \leq N$)

www.acmicpc.net

 

 

 

 

※ Queue 자료구조의 구현

위에서 STL 즉, 이미 구현되어 있는 자료구조를 사용한 것을 보았다. 우리는 그 자료구조가 어떻게 구현되어 있는지 뜯어볼 필요가 있다.

 

(pseudo code) 의사코드로 먼저 표현

 

 

 

※ Deque자료구조의 구현

위에서 STL 즉, 이미 구현되어 있는 자료구조를 사용한 것을 보았다. 우리는 그 자료구조가 어떻게 구현되어 있는지 뜯어볼 필요가 있다.

 

(pseudo code) 의사코드로 먼저 표현

 

 

 

 

 

§ 예제. 

 

 

 

 

 

 

 

 

vector / pair / stack ,queue, deque, priority queue / map / set  / algorithm / iterator / bitset

The C++ Programming Language 4th.Edition

 

vector(std::vector) _가변배열 / 가장 기본이 되는 컨테이너 (★)

 

#include <vector>
using namespace std;

vector<자료형> 변수명(숫자)    //숫자만큼 벡터 생성 후 0으로 초기화
vector<자료형> 변수명(숫자, 변수1);   //숫자만큼 벡터 생성 후 변수1으로 모든 원소 초기화
vector<자료형> 변수명{숫자, 변수1, 변수2, 변수3, ...};    // 벡터 생성 후 오른쪽 변수 값으로 초기화
vector<자료형> 변수명[]={ {변수1, 변수2}, {변수3, 변수4}, ...}   //2차원 벡터생성 (열은 고정, 행 가변)
vector<vector <자료형>> 변수명   //2차원 벡터생성 (열, 행 가변)

ex);
vector<int> vec1; // 크기가 0인 벡터 선언
vector<int> vec2(10); // 크기가 10인 벡터 선언
vector<int> vec3(10, 3); // 크기가 10이고 모든 원소가 3으로 초기화된 벡터
vector<int> vec4 = { 1,2,3,4,5 }; // 크기가 지정한 초기값으로 이루어진 벡터
vector<int> vec5[] = { {1,2},{3,4} }; // 벡터 배열 생성(행은 가변인지만, 열은 고정)
vector<vector<int>> vec6; // 2차원 벡터 생성(행과 열 모두 가변)

 

※ vector 요소 삽입, 제거, 변경

#include <vector>
using namespace std;

int main() {
    vector<int> vec; // 크기가 0인 벡터 선언

    vec.push_back(10);
    vec.push_back(20); // vec = {10, 20}

    vec.insert(vec.begin() + 1, 100);  // vec = {10, 100, 20}

    vec.pop_back();       // vec = {10,100}

    vec.emplace_back(1);   // vec = {10, 100, 1}
    vec.emplace_back(2);   // vec = {10, 100, 1, 2}
    vec.emplace(vec.begin() + 2, -50); // vec = {10, 100, -50, 1, 2}

    vec.erase(vec.begin() + 1);    // vec = {1, -50, 1, 2}
    vec.resize(6); // vec = {1, -50, 1, 2, 0, 0}
    vec.clear();   // vec = empty()
}

 

※ vector의 index 접근

※ vec.at(i)와 vec.[i]의 차이점

- at은 범위를 검사하여 범위 밖의 요소에 접근 시 예외처리를 발생시킨다. (std::out_of_range)

- [ ]은 범위검사를 하지 않으며 예외처리를 발생시키지 않는다. (범위 밖 요소에 접근하면 디버깅 발생)

 

vector는 효율에 중점을 두기에 보통 [ ]를 권장한다.

 

※ vector의 크기 size, capacity

- size: vector의 크기, 즉 벡터에 실제로 저장된 원소의 개수를 뜻한다.

- capacity: vector의 용량, 즉 벡터의 최대 할당 크기를 뜻한다.

 

만약 벡터의 크기가 용량을 초과한다면 재할당이 발생한다. (기존 값 새 메모리에 복사 후 파괴)

if (size > capacity) {
    reallocate <- 모든 값 새 메모리에 복사 후 기존 벡터 파괴
}

 

Problem 1. 새 메모리의 복사과정에서 복사생성자가 발생해 성능이 저하될 수 있다.

Solution 1. reserve()라는 함수를 사용해서 벡터의 용량을 충분히 크게 생성할 수 있다.

 

Problem 2. reserve()를 너무 크게 잡으면 벡터가 불필요하게 늘어나 메모리를 많이 차지할 수 있다.

Solution 2. clear()로 벡터의 값을 지울 때, 벡터의 요소를 삭제할 수 있다.

 

Problem 3. clear()로 벡터의 요소는 없어지지만 capacity는 그대로 남아있다.

Solution 3. 이를 해결하기 위해 swap()을 사용하는데 이는 아래와 같다.

 

#include <vector>
using namespace std;

int main() {
    vector<int> vec = { 1,2,3,4,5 };
    vec.clear();
    cout << vec.capacity() << endl;  // 5 출력
    vector<int>().swap(vec);
    cout << vec.capacity() << endl;  // 0 출력
}

 

https://chan4im.tistory.com/19?category=1076581 

 

this.code(1).DS_ Array, array container & Vector (STL)

※ Array (배열) ※ 1차원 배열 배열은 주로 여러 개의 동일한 자료형의 데이터를 한꺼번에 만들 때 사용된다. 예를 들어 a0, a1, a2, a3, a4, a5라는 6개의 정수형 변수를 A[6]으로 간단하게 선언할 수 있

chan4im.tistory.com

 

 

vector에 값 입력받기  (cin >> vec[i]는 안된다??)

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

vector<int> v;

int main() {
    int num;
    for (int i = 0; i < 5; i++){
        //cin >> v[i];  // Err!
        cin >> num;
        v.push_back(num);
    }
    vector<int>::iterator it;
    sort(v.begin(), v.end(), greater<int>());

    for (it = v.begin(); it != v.end(); it++){
        cout << *it << ' ';
    }
}

 

 

 

 

 

 

 

 

 

 pair

★★★개인적으로 굉장히 유용하다고 생각되는 라이브러리★★★

feat. vector, sort

  • 두 자료형을 하나의 쌍(pair)으로 묶는다.
  • 첫번째 데이터는 first, 두번째 데이터는 second로 접근, make_pair(val1, val2)로 pair를 생성해준다.
  • vector, algorithm 의 헤더파일에 include 하고 있기에 별도의 헤더를 include할 필요가 없다.
#include <iostream>
using namespace std;

#include <vector>

int main(){
    pair<int, int> p1;
    cout << p1.first << ' ' << p1.second << endl; // 0 0 출력

    p1 = make_pair(1, 2);
    cout << p1.first << ' ' << p1.second << endl; // 1 2 출력

    pair<pair<int, int>, pair<int, int>> p2 = make_pair(make_pair(1, 2), make_pair(3, 4));

    cout << p2.first.first << ' ' << p2.first.second << endl;   // 1 2 출력
    cout << p2.second.first << ' ' << p2.second.second << endl; // 3 4 출력
}

 

pair로  vector, typedef, sort  다루기

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    pair<int, int> p1;
    cout << p1.first << ' ' << p1.second << endl; // 0 0 출력

    p1 = make_pair(1, 2);
    cout << p1.first << ' ' << p1.second << endl; // 1 2 출력

    pair<pair<int, int>, pair<int, int>> p2 = make_pair(make_pair(1, 2), make_pair(3, 4));

    cout << p2.first.first << ' ' << p2.first.second << endl;   // 1 2 출력
    cout << p2.second.first << ' ' << p2.second.second << endl; // 3 4 출력

    //vector와 pair
    vector<pair<int, int>> v;
    v.push_back(make_pair(10, 20));
    v.push_back(make_pair(30, 40));
    v.push_back(make_pair(50, 60));
    cout << v[0].first << ' ' << v[2].second << endl;

    // typedef를 이용한 방식
    typedef pair<int, int> P;
    vector<P> v1;
    v1.push_back(make_pair(300, 500));
    v1.push_back(make_pair(600, 400));
    v1.push_back(make_pair(100, 200));

    // first 따로, second 따로 정렬
    sort(v1.begin(), v1.end());
    vector<P>::iterator it;

    for (int i = 0; i < 3; i++)
        cout << v1[i].first << " " << v1[i].second << endl;
}


 

 

 

 

 

 

※ stack

#include <stack>

stack<데이터타입> 이름;

https://chan4im.tistory.com/22?category=1076581 

 

this.code(2).DS_ Stack & Stack Container(STL)

※ Stack 스택은 LIFO(Last-In-First-Out) 입출력 형태, 즉 후입선출 방식을 가진 자료구조이다. 위의 그림에서 4, 5번째 그림을 보자. Last In: 3 / First Out: 3 즉, 가장 마지막에 들어온 data가 가장 먼저 나..

chan4im.tistory.com

 

 

 

 

 stack, queue, deque priority queue, priority queue

 

※ queue 선언방식

#include <queue>

queue<데이터타입> 이름;

 

 

※ deque 선언방식

#include <deque>

deque<데이터타입> 이름;

https://chan4im.tistory.com/29?category=1076581 

 

★this.code(3).DS_ Queue & (STL): queue, deque

※ Queue 큐는 FIFO(First-In-First-Out) 입출력 형태, 즉 선입선출 방식을 가진 자료구조이다. enqueue와 dequeue의 시간복잡도는 둘 다 O(1)의 시간을 갖는다. 단, 탐색의 시간복잡도는 특정 data를 찾을 때까.

chan4im.tistory.com

 

 

 

 

※ priority queue 선언방식

#include <queue>

priority_queue<int> pq;
priority_queue<int, vector<int>, greater<int> > pq;
priority_queue<int, vector<int>, less<int> > pq;

가장 기본적인 것 부터 시작해 여러 방식으로 변형하며 사용할 수 있다.

우측 사진 출처:&nbsp;http://www.tcpschool.com/cpp/cpp_algorithm_functor

 

 

 

 

 

 

 

 

 

 

map

map은 각 node가 [key - value] 의 쌍(pair)으로 이루어진 트리이다. 

특히나 map의 가장 큰 특징은 중복을 허용하지 않는다는 것이다! => key가 중복되면 insert가 수행되지 않음

 

C++의 map 내부구현은 삽입, 삭제, 검색의 시간복잡도가 O(logn) 인 레드블랙트리로 구성되어 있다.

unordered_map은 해시 테이블이다.

 

※ map 선언방식 (삭제)

#include <map>

map<key_type, value_type> 이름;

※ map 삭제

※ map에서 찾고자 하는 데이터 확인 (search, find)

map에서 원하는 값을 찾고자 할 때, iterator를 사용한다.

만약 끝까지 원하는 값을 찾지 못하면, iterator는 map.end()를 반환한다.

 

find(k) 로 사용하며 key값 k에 해당하는 iterator를 반환한다.

map<string, int> mapset;

if (mapset.find("V2LLAIN") != mapset.end()){
    cout << "find!" << endl;
}
else
    cout << "not find!" << endl;

 

※ 반복문 데이터 접근 (first, second)

※ index 기반 iterator 활용 예제

map<string, int> mapset;

for (auto it = mapset.begin(); it != mapset.end(); it++) {
    cout << it->first << " " << it->second << endl;
}
cout << endl;

※ 범위기반 반복문 활용 예제

map<string, int> mapset;

for (auto it : mapset){
    cout << it.first << " " << it.second << endl;
}

 

※  map 사용 예제 (insert, search, iterator 구현)

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

map<string, int> mapset;

int main() {

    mapset.insert({ "Alice", 100 });
    mapset.insert({ "Bob", 200 });

    if (mapset.find("Alice") != mapset.end())
    {
        cout << "find" << endl;
    }
    else {
        cout << "not find" << endl;
    }

    //인덱스기반
    for (auto iter = mapset.begin() ; iter !=  mapset.end(); iter++)
    {
        cout << iter->first << " " << iter->second << endl;
    }
    cout << endl;

    //범위기반
    for (auto iter : mapset) {
        cout << iter.first << " " << iter.second << endl;
    }
}

참고) https://life-with-coding.tistory.com/305?category=808106

 

 

 

 

 set

- set은 연관 컨테이너로 삽입, 삭제, 검색의 시간복잡도가 O(logn) 인 Binary Search Tree로 구현되어 있다.

- key라는 원소들의 "집합"으로 key값은 중복되지 않는다!

- insert()를 통한  자동적으로 오름차순 정렬이 가능하다.

중복을 피하면서 정렬까지 사용할 때 매우 유용하다!

 

insert(k) : 원소 k 삽입
begin() : 맨 첫번째 원소를 가리키는 iterator를 반환
end() : 맨 마지막 원소를 가리키는 iterator를 반환
find(k) : 원소 k를 가리키는 iterator를 반환
size() : set의 원소 수
empty() : 비어있는지 확인

 

 

 

 

 

algorithm

※ STL 알고리즘의 분류

find()는 2개의 입력 반복자로 지정된 범위에서 특정 값을 가지는 첫 번째 요소를 가리키는 입력 반복자를 반환 

for_each()는 2개의 입력 반복자로 지정된 범위의 모든 요소를 함수 객체에 대입한 후, 대입한 함수 객체를 반환 

 

copy()는 2개의 입력 반복자로 지정된 범위의 모든 요소를 출력 반복자가 가리키는 위치에 복사

swap()은 2개의 참조가 가리키는 위치의 값을 서로 교환

transform()은 2개의 입력 반복자로 지정된 범위의 모든 요소를 함수 객체에 대입후, 출력 반복자가 가리키는 위치에 복사

 

sort()는 2개의 임의 접근 반복자로 지정된 범위의 모든 요소를 비교, 오름차순정렬.

stable_sort()는 2개의 임의 접근 반복자로 지정된 범위의 모든 요소를 비교, 값이 같은 요소들의 상대적인 순서는 유지,  오름차순으로 정렬합니다.

binary_sort()는 정렬되어있는 경우(오름차순)에 한해서 탐색효율이 매우 좋고 적은 시간에 소요된다.

 

accumulate()는 두 개의 입력 반복자로 지정된 범위의 모든 요소의 합을 반환합니다.

 

 

※ 벡터의 오름차순과 내림차순 정렬 (feat. greater<int> 키워드)

§ sort() 함수 형식

단, custom_func()은 0 또는 1이 나오도록 해야해서 보통 bool형 함수를 많이 넣는다.

sort(v.begin(), v.end()); //형식이나
sort(v.begin(), v.end(), custom_func); //형식으로 사용가능하다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main() {
    vector<int> v;
    for (int i = 0; i < 5; i++) {
        int num; cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());   // 오름차순
    sort(v.rbegin(), v.rend()); // 내림차순

    for (auto x: v) {
        cout << x;
    }
}

 

※ 벡터의 이진탐색 

 

http://www.tcpschool.com/cpp/cpp_algorithm_functor

 

 

 

 

 

 

 

iterator

STL에 저장된 요소를 반복적으로 순회해여 각각의 요소에 대한 접근을 제공하는 객체.

즉, 컨테이너의 구조,요소의 타입과 상관없이 컨테이너에 "저장된 요소"를 순회하는 과정을 일반화한 표현

 

[iterator를 쓰기 위한 요건]

1. 가리키는 요소의 값에 접근할 수 있어야 한다. => 참조 연산자(*)가 정의되어야 합니다.

2. 반복자 사이의 대입 연산, 비교 연산이 가능해야 합니다. => 대입, 관계 연산자가 정의되어야 합니다.

3. 가리키는 요소의 주변 요소로 이동할 수 있어야 합니다. => 증가 연산자(++)가 정의되어야 합니다.

int main() {
    vector<int> v(5);

    v.push_back(20);
    v.push_back(50);
    v.push_back(10);

    for (int i = 0; i < 5; i++)
        cin >> v[i];

    vector<int>::iterator it;
    for (it = v.begin(); it != v.end(); it++) {
        cout << *it << ' ';
    }
    
    //1 2 3 4 5 20 50 10 출력
}

 

 

 

표준 컨테이너 시간 복잡도 (The C++ Programming Language)

 

 

 

 

 

※ bitset

비트연산의 간편화를 위해 사용하는 라이브러리

#include <bitset>

int main() {
    bitset<100000> a(76),b(44); // 각각 76, 44의 비트가 입력됨
    cout << (a & b) << '\n';
    cout << (a | b) << '\n';
    cout << (a ^ b) << '\n';
    cout << (~a) << '\n';
    cout << (~b) << '\n';
    return 0;
}

※ C++11/14에서 새롭게 추가된  자동 타입 변환 키워드이다.

 

※ auto 사용 시 주의사항

  • auto 키워드는 함수 매개변수로 사용불가!
  • auto 키워드는 구조체나 클래스의 멤버 변수로 사용 불가( 객체 자료형 크기를 모르기 때문)
  • 가독성이 떨어짐으로 적절한 사용이 필요.

 

 

※ auto 키워드

선언된 변수의 초기화 식을 사용하는 것으로 컴파일러가 알아서 해당 타입을 추론 (type inference)하게 한다.

이 기능은 생성 시 변수를 초기화 할 때만! 작동한다. ( 초기화된 값을 기준으로 자료형을 선택해서)

※ auto를 이용한 자료형

int r = 20;
double PI = 3.14159265358979;

auto *pi = &PI;  // 포인터도 가능
auto &Pi = PI;  // 참조자도 가능

auto S = r*r*PI;  // double S
cout << S;  // 출력값: 1256.64

 

※ auto를 이용한 for문 출력

auto arr = { 1, 2, 3, 4 };
for (auto num : arr)
    cout << num << ' ';  // 1 2 3 4 출력
for (const auto&  p : photos) {
    wcout << "Photo location: " << (static_pointer_cast<Photo>(p))->location_ << endl;
}

 

※ auto를 이용한 함수

auto S(int r, double pi){
    return r*r*pi;
}

 

 

 

 

※ decltype 키워드

declared type 즉, 선언된 형식의 줄임말로 주어진 이름, 표현식의 구체적 타입을 알려주는 키워드이다.

이는 template에 기반한 제네릭 프로그래밍의 어려움을 해소하기 위해 도입되었다.

ex.

template<typename FirstType, typename SecondType>
??? AddArbitrary(FirstType first, SecondType second) {
    cout << first + second << endl;
}

int main() {
    AddArbitrary(1234, 'C');    // FirstType이 returnType
    AddArbitrary('C', 1234);    // SecondType이 returnType
}
template<typename FirstType, typename SecondType>
decltype(first+second) AddArbitrary(FirstType first, SecondType second) {  //Err!
    cout << first + second << endl;
}

 

§ auto vs decltype

- auto: 값에 상응하는 타입을 "컴파일러가" 추론하는 키워드

- decltype: 값으로부터 타입을 추출하는 키워드

template<typename FirstType, typename SecondType>
auto AddArbitrary(FirstType first, SecondType second) -> decltype(first+second){
    cout << first + second << endl;
}

auto +  ->decltype()을 이용해서 문제를 해결할 수 있다!

 

 

 

 

 

 

 

 

 

※ 범위기반 for문

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

vector<int> v;

int main() {
    int num;
    for (int i = 0; i < 5; i++){
        //cin >> v[i];  // 이건 왜 오류나는가
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end(), greater<int>());

    for (const auto& num : v)
        cout << num << " ";
}

C++11에서 새롭게 도입된 유형의 루프로 더 간단하고 안전하게 배열등의 모든 요소를 반복하는 방법이다.

§ 범위기반 for문의 가장 큰 특징

표현식 안의 모든 값에 대해 한번씩 루프를 실행!

범위기반 for문은 index 정보가 없고 배열요소를 변경할 수 없다.

즉, for문을 완전히 대체하지는 못한다.

따라서 컨테이너의 간단한 순회를 위해 사용된다!

보통 auto와 같이 사용되는 경우를 심심치 않게 볼 수 있기에 사용법을 알고 있는게 좋을 것이다.

 

※ 선언방법

for (자료형 변수 : 배열종류의 이름)

예를 들어 다음과 같이 선언할 수 있다.

순서는 다음과 같다.

int main() {
    int arr[] = { 1, 3 , 4, 5, 5, 8};
    for (int num :arr)
        cout << num << " ";
}

1. for문 실행, num에 arr의 첫 요소인 0이 할당

2. 그 후 0을 출력하는 cout 실행

3. 다시 for문 실행, 이 과정을 요소 8까지 반복

 

 

 

 

 

★ 배열에 대한 인덱스가 아닌, 배열의 요소값이 num에 할당된다!

여기서 자료형 변수 위치에 배열요소와 같은 자료형을 가져야 하기에 auto키워드로 자료형을 추론하게 하는 것이 좋다.

또한, 읽기 전용으로 사용하려할 때, (수정되지 않게끔) const 키워드를 붙여 다음과 같이 선언할 수 있다.

(성능상의 이유로 범위기반 for문에서 const 참조를 사용하는 것이 좋다.)

int main() {
    int arr[] = { 1, 3 , 4, 5, 5, 8};
    for (const auto& element :arr)
        cout << element << " ";
}

 

포인터로 변환된 배열 (array decay into pointer)의 경우, 배열의 길이를 몰라 범위기반 for문을 사용할 수 없다.

int sumArray(int array[]) {
    int sum = 0;
    for (const auto& number : array) // 컴파일 에러, 배열크기를 모름
        sum += number;

    return sum;
}

int main() {
    int array[5] = { 9, 7, 5, 3, 1 };
    cout << sumArray(array); // 배열이 포인터로 decay
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

※ 예외처리(Exception Handling): 예외를 처리하는 과정

예외(Exception): 프로그램 실행도중 일어나는 비정상적인 상황

예를 들자면 아래와 같은 함수에서 분모에 0을 넣은 것과 동일한 상황이다.

좌) 정상적인 종료                                   우) 비정상적인 종료

우측 컴파일부분을 보면 Process finished with exit code -1073741676 (0xC0000094)라 적혀있다.

즉, 정상적이지 않은 값이 나와 오류가 발생했다는 뜻이다.

 

이런 경우, 프로그램이 오류가 발생했을 때, 컴파일러가 강제로 종료되거나 사전에 방지하기 위해 다음과 같은 방식을 사용한다.

 

- if문과 같은 조건문을 통한 예외처리

int fun(int a, int b){
    if (b == 0)
        exit(0);
    else
        return a / b;
}

int main() {
    int x, y;
    cin >> x >> y;
    cout << fun(x, y) << endl;
}

위와 같이 if문을 통한 예외를 제어할 수도 있다. 이는 C에서도 가능한 방식이다.

하지만 if-else문을 통한 에러처리방식에러가 발생한 객체에 대해 수명이 유지되어 에러를 처리하는동안에도 발생한 객체를 참조하는 코드가 정상적으로 컴파일된다.

따라서 C++을 포함한 여러 언어들에서는 다음과 같은 방식을 많이 사용한다.

 

 

- try catch를 통한 예외처리

try-catch는 if문의 예외처리와 달리 지역 객체들의 소멸자가 자동호출되어 메모리 누수현상을 조금 해결할 수 있다.

다만 try-catch 블록을 유지해야할 정보도 많고 실제 예외가 발생했을 때, 해줘야 할 일이 많아서 코드 크기나

예외 발생시 처리 속도는 전통적인 if 조건문 반환 값을 통한 오류처리와는 비교하기 힘들다.

try/catch는 자동으로 해주는 일이 많기에 당연히 더 느리다.

 

※ try-catch문을 통한 예외처리 매커니즘

 

class Animal {
public:
    Animal() { cout << "생성자" << endl; };
    ~Animal() { cout << "소멸자" << endl; };
};

int main(){
    try {
        Animal a;
        throw (a);
    }
    catch(Animal& a){
        cout << "catch문" << endl;
    }
}

/*출력문*/
//생성자
//소멸자
//catch문
//소멸자
다음과 같이 객체를 throw할 수 있는데, nested block 즉, try{ }가 종료가 되었으므로
Animal a를 통해 만들어진 객체 a는 소멸자에 의해 소멸하게 된다.
Q. 그렇다면 왜 출력문에서 catch문 뒤에 소멸자가 한 번 더 출력된 것일까?
A. 그건 바로 catch(Animal& a)에서 생성자가 한 번 더 생성되었다는 것의 반증이 될 것이다.
생성자는 처음 객체생성되었을 때, 초기화를 위해 딱 한번만 호출된다는 것이 기본 개념이고, 핵심이기 때문이다.
따라서 catch 블록이 종료된 이후 Animal& a를 통해 생성된 객체를 다시 소멸자가 소멸해줘서 소멸자가 두번 출력된 것!

 

 

 

 

 

Exception 클래스 (예외 클래스)

Exception 클래스:  예외처리를 위해 exception 헤더에서 제공하는 클래스 (표준 라이브러리인 std namespace에 존재)

이런 예외클래스도 클래스이기에 상속은 물론 다형성, 생성자와 연산자에도 적용 가능하다.

 

§ what() 

what은 exception 클래스에서 하나의 문자열 포인터를 반환하는 가상멤버함수이다.

what()은 exception 클래스에서는 아무 의미가 없지만 파생클래스에서 원하는 문자열을 출력할 수 있게 재정의 해준다!

 

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

class NewException : public exception{ //새로운 Exception NewException은 exception클래스를 상속받음
public:
    const char* what() const noexcept override{ // what 함수의 오버라이딩 진행
        return "NewException";
    }
};

int main(){
    try{
        string str;
        str.resize(-100);
    }
    catch (exception& e){
        try {
            throw NewException(); // 예외 발생시 새로운 Exception throw
        }
        catch (const NewException& newException){
            cout << "My exception is " << newException.what() << endl; // NewException의 what()에서 전달받은 문자열 출력
        }
    }
}

 

 

 

 

 

§ 표준 Exception 클래스

#include <exception>는 exception 클래스로부터 파생된 다양한 표준 exception 클래스를 정의하고 있다.

[가장 기초클래스가 되는 2개의 클래스, logic과 runtime]

logic_error 클래스는 일반적인 논리에 관한 오류들을 처리

runtime_error 클래스프로그램 실행하는 동안 발생할 수 있는 다양한 오류들을 처리

출처) http://www.tcpschool.com/cpp/cpp_exception_class

 

 

 

 

 

 

※ Custom Exception (예외클래스의 설계)

예외발생을 알리기 위한 예외 객체의 생성을 위해 정의된 클래스로 기본 자료형 데이터 뿐만 아니라

클래스의 객체도.예외데이터가 될 수 있다. 또한 예외클래스도 상속의 관계를 구성할 수 있다

 

 

 

 

 

※ 예외클래스 전달방식의 주의사항

try 뒤를 이어 등장하는 catch가 2개 이상일 때, 다음과 같은 과정을 거친다.

 

윤성우의 열혈C++

 

int throwExceptions (int c) {
    if (c == 1){
        throw string("It's string!");
    }
    if (c == 2){
        throw 2;
    }
    if (c == 3){
        throw "hello world!";
    }
    if (c == 4){
        throw 'X';
    }
    return 0;
}

int main(){
    int c;
    while (true) {
        cin >> c;
        try {
            throwExceptions(c);
        }
        catch (string& s){
            cout << "string exception: " << s << endl;
        }
        catch (const char* s) {
            cout << "string literal exception: " << s << endl;
        }
        catch (char x) {
            cout << "char exception: " << x << endl;
        }
        catch (int x) {
            cout << "int exception: " << x << endl;
        }
    }
}

/*---------------출력문---------------*/
//1
//string exception: It's string!
//2
//int exception: 2
//3
//string literal exception: hello world!
//4
//char exception: X

 

 

 

 

 

 

※ noexcept (true)   (feat. move constructor)

예외가 생성되지 않음을 뜻하는 키워드

호출자가 noexcept 여부에 의존할 수 있으며 예외를 방출하지 않을 함수는 noexcept로 선언한다.

 

[장점]

1. user와 compiler에게 힌트가 됨.

2. code의 단순화

3. compiler의 최적화를 가능하게 함.

 

int funcA() noexcept {
    throw std::runtime_error("Exception!");
    return 0;
}

int main(){
    try { 
        funcA();
    } 
    catch (char c){
        cout << "catch char: " << c;
    }
}

 

 

※ 이동생성자와 noexcept

[이동생성자 사용 시 주의할 점]

1. 이동생성자에는 noexcept 키워드가 지정되어야 한다. (이동생성자 수행중, 예외가 없다는 것을 컴파일러가 인지해야함)

2. shallow copy가 일어나는 변수(포인터, 주소관련 변수)에 nullptr를 넣어줘야 함

3, 소멸자에서 메모리할당 관련 변수가 nullptr인지 확인해 줘야함.

Animal(Animal && a) noexcept { //이동생성자에 의한 얕은복사
    age = a.age;
    name = a.name;
    cout << "이동생성자" << endl;
    a.name = nullptr;
}

 

 

 

 

 

 

 

 

 

 

 

※ rethrowing

- throw를 다시 하여 예외를 부분적으로 다루기(handling) 위해서 사용.

int funcA() {
    throw std::runtime_error("Exception!");
    return 0;
}
int funcB() {
    try {
        funcA();
    }
    catch (std::runtime_error& e) {
        cout << "catch Exception: " << e.what() << endl;
        throw;
    }
}

int main(){
    try {
        funcB();
    }
    catch (std::runtime_error& e) {
        cout << "catch Rethrowed exception: " << e.what() << endl;
    }
}

/*---------------출력문---------------*/
//catch Exception: Exception!
//catch Rethrowed exception: Exception!

※ 템플릿 함수와 함수 템플릿

- C++에서 template은 다른 객체지향언어에서 부르는 "일반화를 뜻하는" 제네릭(generic)이다.

- template 사용은 약간의 비용(실행비용)이 발생하지만 전체적으로 프로그램의 크기와 난이도를 줄일 수 있다

 예를들어 int, double, char 타입에 대한 최솟값을 구하는 min 함수를 만들어 보자면 아래와 같이 3개의 함수가 필요하다.

int min (int a, int b) { return a < b ? a : b; }
double min (double a, double b) { return a < b ? a : b; }
char min (char a, char b) { return a < b ? a : b; }

 

하지만 template을 사용한다면 모든 data type에 대한 정의가 하나의 함수로 가능하다. 아래처럼 말이다.

template<typename T>

T min (T a, T b) { return a < b ? a : b; }

cf. 위의 T는 템플릿 매개변수라 부른다.

 

※ 템플릿 함수와 함수 템플릿

※  템플릿 함수

- 템플릿을 기반으로 컴파일러가 만들어 내는 함수(템플릿 기반의 함수임을 표기한 것)

- 즉, 템플릿 기반의 호출이 가능한 “함수”라는 점에서 차이가 있다.

 

 

※ 함수 템플릿

- 함수 템플릿은 함수를 만들어 낸다.(기능은 결정되어 있으나 자료형은 결정 X)

- 따라서 함수 템플릿으로 다양한 자료형의 함수를 만들 수 있다.

- 함수를 만드는데 사용되는 템플릿으로 호출이 가능한 함수가 아닌 “템플릿”이다

 

 

 

※ 템플릿의 종류

- 함수 템플릿함수의 오버로딩을 확장한 개념

template<typename T>

T min (T a, T b) { return a < b ? a : b; }

 

 

- 클래스 템플릿:클래스를 만드는 템플릿으로 내부의 멤버변수.함수의 data type 지정시 사용

- 템플릿 클래스: 클래스 템플릿을 기반으로 컴파일러가 만든 클래스이다.
다만, 클래스 템플릿 기반 객체생성에는 반드시 <int>와 같은 자료형을 명시해 줘야 한다!

template <typename T>
class Animal{
private:
    T num;
public:
    Animal(T num) : num(num) {}
    T eat(const T& ref);
};

template <typename T>
T Animal<T>::eat(const T& ref) {}

int main() {
    Animal<int> a(4);
    a.eat(4);
}

 

 

- 타입 템플릿using으로 data type을 템플릿으로 지정시 사용

template <typename T>
using ptr = T*;
ptr<int> x;  // int *x와 동일한 선언

 

- 변수 템플릿: 변수에 적용할 수 있는 템플릿 (C++14 이후부터 적용)

template <typename T>
constexpr T PI = T(3.141592653589793238462643L);

 

 

 

 

※ 템플릿의 특수화

- 특정 자료형으로 생성된 객체에 대해 구분이 되는 다른 행동양식 적용하기 위함

- 즉, 템플릿을 구성하는 멤버함수 일부 혹은 전체를 모두 다르게 행동시킬 수 있음

 

Q. 문자열 비교할 때, 사전순이 맞을까? 아니면 길이순이 맞을까?

A: 이런 특수 상황에 따라 예외가 필요하기에 사용하는 것이 바로 템플릿의 특수화이다.

 

 

 

※ 함수 템플릿과 static 지역변수

함수템플릿을 기반, 컴파일러는 ‘템플릿 함수’들을 만들어 낸다.

따라서 static 지역변수도 템플릿 함수 별로 각각 존재하게 된다.

 

※ 클래스 템플릿과 static 멤버변수

static멤버변수는 변수가 선언된 클래스의 객체간 공유가 가능.

따라서 클래스별 static 멤버변수를 유지하게 된다.

 

좌) 함수 템플릿과 static 지역변수&nbsp; &nbsp; &nbsp;우) 클래스 템플릿과 static 멤버변수

 

 

 

※ 템플릿기반 템플릿 클래스 객체를 저장하는 객체 생성

 

 

 

 

 

 

 

 

 

※ Advanced Template 

python에서 다음과 같이 print함수를 사용할 때, 인자로 전달되는 것들을 모두 출력할 수 있다.

print(1, 3.1, "abc")

그렇다면 C++에서도 이와 같은 방법으로 출력에서 인자에 대한 사전정보가 없을 때, 출력을 조금 더 유동적으로 하는 방법은 없을까?

 

 variadic template (가변길이 템플릿)

#include <iostream>
using namespace std;

template <typename T>
void print(T args) {
    cout << args << endl;
}

template <typename T, typename... Types>
void print(T arg, Types... args) {
    cout << arg << ", ";
    print(args...);
}

int main() {
    print(1, 3.1, "abc");
    print(1, 2, 3, 4, 5, 6, 7);
}
/*************** 출력 ***************/
// 1, 3.1, abc
// 1, 2, 3, 4, 5, 6, 7

 

- parameter pack

template <typename T, typename... Types>
void print(T arg, Types... args) {

typename 뒤에 ...으로 오는 것을 템플릿 파라미터 팩이라 부른다.

템플릿 파라미터 팩은 0개 이상의 템플릿 인자들을 나타낸다.

 

 

§ Fold Expression 

위에서 사용한 recursion진행 대신 사용하는 방법으로 variadic template에서 가변인자 처리를 위해 parameter pack을 사용하는데, 이때! C++17부터 fold expression이 제공되어 parameter pack을 더 쉽게 사용할 수 있게 된 것이다.

- 인자가 1개:

1) Unary right 
(E op ...)   ex_ (E1 op (... op (EN-1 op EN)))

2) Unary left
(... op E)   ex_ (((E1 op E2) op ...) op EN)

unary right fold

E1 op ( ... op ( En-1 op En))

- 전달받은 parameter pack을 위와 같은 표현식으로 변경
뒤에 있는 인자 부터 먼저 순차적으로 연산해서 결과 값을 생성

template<typename... Args>
auto sum(Args... args) { 
    return (args + ...); 
}

 

unary left fold

((E1 op E2) op ...) op En

- 전달받은 parameter pack을 위와 같은 표현식으로 변경
앞에 있는 인자 부터 순차적으로 연산해서 결과 값을 생성

template<typename... Args>
auto sum(Args... args) { 
    return (... + args); 
}

 

 

 

 

- 인자가 2개

3) Binary right
(E op ... op I)   ex_ (E1 op (... op (EN−1 op (EN op I))))

4) Binary left
(I op ... op E)   ex_ ((((I op E1) op E2) op ...) op EN)

 

binary right

E op ... op I
- 전달받은 parameter pack을 위와 같은 표현식으로 변경
- 단항을 사용하는 문법과 다르게 parameter pack과 별개로 초기 연산할 값을 추가할 수 있다.

template<typename ...Args>
int sum(Args... args) {
    return (args + ... + (1 * 2));
}

 

binary left

I op ... op E
- 전달받은 parameter pack을 위와 같은 표현식으로 변경

template<typename ...Args>
int sum(Args... args) {
    return ((1 * 2) + ... + args);
}

 

 

 

§ Functor (Function Object, 함수객체) 

다음과 같이 함수처럼 동작하는 클래스를 Functor, 함수객체라 부른다.

struct AddFunction {
    int operator()(const int& num1, const int& num2) {
        return num1 + num2;
    }
    double operator()(const double& num1, const double& num2) {
        return num1 + num2;
    }
};

int main() {
    auto num1 = 1.32, num2 = 12.34;
    AddFunction add;
    auto result = add(num1, num2);
    cout << result << endl;
    return 0;
}

이런 functor는 기존의 함수보다 더 flexible 즉, 유연한데, 객체를 이용하기에 임의의 상태에 대한 정보를 전달가능하다.

functor를 사용하면 기능조작이 쉽고 컴파일러가 기능 자체를 inline화 시켜 매우 빠르게 작업할 수 있다.

1) Unary right 
(E op ...)   ex_ (E1 op (... op (EN-1 op EN)))

2) Unary left
(... op E)   ex_ (((E1 op E2) op ...) op EN)

 

 

 

 

 

 

 

 

 

 

 

※ 스마트 포인터 

// int *ptr=new int;    delete ptr;
std::unique_ptr<int> ptr = make_unique<int>();

//int *ptr=new int[5];
auto ptr=make_unique<int[]>(5);

//void (*ptr)()
std::function<void(void)>

C++ 프로그램에서 new 를 사용해 동적할당한 메모리는, 반드시 delete로  해제해야 한다.

 

C++에서는 메모리 누수(memory leak)로부터 프로그램의 안전성을 보장하기 위해 스마트 포인터를 제공 (memory 헤더).

 

스마트 포인터란 포인터처럼 동작하는 클래스 템플릿으로, 사용이 끝난 메모리를 자동으로 해제한다. (delete 자동 수행)

 

이는 new로 기본포인터(raw pointer)가 실제 메모리를 가리키도록 한 후

스마트 포인터 (smart pointer)에 기본포인터를 대입하여 사용한다.

이렇게 정의된 스마트 포인터의 수명이 다하면, 소멸자는 delete 키워드를 사용하여 할당된 메모리를 자동으로 해제한다.

 

 

※ 스마트 포인터의 종류

<C++11 이전>

auto_ptr (삭제됨)

 

<C++ 이후>

 

§ 참조 카운트 (reference count): 해당 메모리를 참조하는 포인터가 몇 개인지 나타내는 값

 

1. unique_ptr: 하나의 스마트포인터만이 객체를 가리킬 수 있도록 함

                        (reference cnt1을 넘길 수 없음)

2. shared_ptr: 하나의 특정 객체를 참조하는 스마트포인터의 개수를 참조

                        (reference cnt1씩 증가or감소, 참조횟수가 0이되면 delete되어 자동 해제)

3. weak_ptr: 하나 이상의 shared_ptr가 가리키는 객체를 참조 

                         (reference cnt늘리지 않음으로 shared_ptr 객체사이 순환참조를 제거하기 위함)

 

unique_ptr  (활용도: ★★★★★) 

사람이 실수할 수 있기에, unique와 move를 이용해 최대한 shared사용을 자제하는 것이 좋다.

unique_ptr 객체는 move() 멤버함수로 소유권을 이전할 수 있다. (단, 복사는 불가능!)

소유권이 이전되면 이전 unique_ptr 객체는 더이상 해당 객체를 소유하지 않게 재설정 된다.

 

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

int main() {
    unique_ptr<int> ptr1(new int(10));
    //unique Pointer 초기화와 함께 int형 값 10으로 동적할당

    auto ptr2 = move(ptr1);
    //auto 키워드로 ptr2는 ptr1의 타입을 추론(unique_ptr<int> 타입)
    //move 키워드는 ptr1에서 ptr2로 메모리의 소유권을 이전하기 위해 사용된다.

    unique_ptr<int> ptr3 = ptr1; // Err
    //애초에 ptr1이 소멸되어 접근이 불가하다.
    //대입 연산자를 이용한 복사는 오류를 발생시킨다.

    if (ptr1 == nullptr) {
        cout << "I'm Dead. Call ptr2 instead." << endl;
        cout << ptr1 << endl;   // *ptr1이라 써주지 않아서 Err
    }
    cout << *ptr2 << endl;

    ptr2.reset();
    ptr1.reset();
    //reset 함수로 메모리 영역을 삭제할 수 있다.
}

 

 

<make_unique()함수를 이용>

- 전달받은 인수를 사용해 지정된 타입의 객체를 생성

- 생성된 객체를 가리키는 unique_ptr을 반환하여 예외발생에 대해 안전히 대처가능

#include <iostream>
#include <memory>
#include <string>

using namespace std;

class Animal {
public:
    string name = "";
    Animal() { cout << "construct" << endl; };
    Animal(string name) {
        this->name = name;
        cout << "construct" << endl;
    }
    ~Animal() { cout << "destruct" << endl; };

    void setName() {
        cout << name << " : Grrr!" << endl;
    }
};

int main() {
    // Animal 객체 생성
    unique_ptr<Animal> a = make_unique<Animal>("Tiger");
    a->setName();
}

//------------출력------------//
//construct
//Tiger : Grrr!
//destruct

 

 

shared_ptr

shared_ptr은 하나의 특정 객체를 참조하는 스마트 포인터가 총 몇 개인지 를 참조하는 스마트 포인터

reference count는 특정 객체에 새로운 shared_ptr이 추가될 때마다 1씩 증가하고, 수명이 다하면 1씩 감소하며

추가되었던 shared_ptr이 해제되어 참조 카운트가 0이 되면 delete 가 자동으로 진행, 메모리를 자동해제한다.

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

int main() {
    shared_ptr<double> ptr1(new double(123.456));
    cout << ptr1.use_count() << endl;

    auto ptr2(ptr1);
    cout << ptr2.use_count() << endl;

    auto ptr3(ptr2);
    cout << ptr3.use_count() << endl;
}

//------------출력------------//
// 1
// 2
// 3

 

 

<make_shared()함수를 이용>

- shared_ptr의 객체를 안전하게 만들 수 있다.

- 전달받은 인수를 사용해 지정된 타입의 객체를 생성, 생성된 객체를 가리키는 shared_ptr을 반환.

- 이 함수도 예외 발생에 대해 안전하다.

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

class Monster {
public:
    Monster() { cout << "construct" << endl; }
    ~Monster() { cout << "destruct" << endl; }
};

int main()
{
    shared_ptr<Monster> mst_ptr1 = make_shared<Monster>();
    cout << mst_ptr1.use_count() << endl;

    auto mst_ptr2 = mst_ptr1;
    cout << mst_ptr1.use_count() << endl;

    mst_ptr2.reset();
    cout << mst_ptr1.use_count() << endl;
}

//------------출력------------//
// construct
// 1
// 2
// 1
// destruct

 

 

 

 

weak_ptr

shared_ptr은 참조 카운트를 기반으로 동작하는 스마트 포인터

 

하나 이상의 shared_ptr 객체가 소유하는 객체에 대한 접근을 제공하지만, 참조 카운트에 포함되지 않는다.

 

만약에 서로가 상대를 가르키는 shared_ptr을 가지고 있다면, 참조 횟수는 절대 1 이하로 내려가지 않기 때문에,

0이 되어야 자동으로 해제되는 스마트 포인터에 가장 크리티컬한 문제가 된다.

이렇게 서로가 상대를 참조하는 상황을 순환 참조(Circular Reference)라고 한다.

 

weak_ptr은 바로 이러한 shared_ptr 인스턴스 사이의 순환 참조를 제거하기 위해서 사용한다.

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

class Monster {
public:
    weak_ptr<Monster> otherMonster; 
    // shared_ptr로 선언할 경우 순환 참조 발생하기에 weak_ptr로 선언하여 순환 참조를 예방
    Monster() { cout << "생성" << endl; }
    ~Monster() { cout << "소멸" << endl; }
};

int main() {
    //철수와 민수에 대한 shared_ptr을 선언
    shared_ptr<Monster> chul_su = make_shared<Monster>();
    shared_ptr<Monster> min_su = make_shared<Monster>();

    // reference count : 참조 카운트
    cout << "철수 reference count : " << chul_su.use_count() << endl;
    cout << "철수 reference count : " << min_su.use_count() << endl;

    chul_su->otherMonster = min_su;
    min_su->otherMonster = chul_su;

    cout << "철수 reference count : " << chul_su.use_count() << endl;
    cout << "민수 reference count : " << min_su.use_count() << endl;
}

//------------출력------------//
// 생성
// 생성
// 철수 reference count : 1
// 철수 reference count : 1
// 철수 reference count : 1
// 민수 reference count : 1
// 소멸
// 소멸

 

 

 

 

 

 

 

※ 스마트 포인터 형변환(typecasting)

- static_pointer_cast

- dynamic_pointer_cast

- const_pointer_cast

 

포인터를 사용할 때, 다른 포인터 타입으로의 캐스팅은 용이했다.

하.지.만! shared_ptr 등의 스마트 포인터는 그렇지가 않다.

이를 위해서 ((AnotherClass*)(ptr.get())) 와 같이 강제로 포인터를 얻어 캐스팅을 해줄 수 있지만 전혀 C++ 답지 못하다.

 

따라서 static_pointer_cast  /  dynamic_pointer_cast  / const_pointer_cast 가 추가되었다.

이를 통해 안전하고도 편한 스마트 포인터 캐스팅이 가능해진 것이다.

vector<shared_ptr<MediaAsset>> assets;

assets.push_back(shared_ptr<Song>(new Song(L"Himesh Reshammiya", L"Tera Surroor")));
assets.push_back(shared_ptr<Song>(new Song(L"Penaz Masani", L"Tu Dil De De")));
assets.push_back(shared_ptr<Photo>(new Photo(L"2011-04-06", L"Redmond, WA", L"Soccer field at Microsoft.")));

vector<shared_ptr<MediaAsset>> photos;

copy_if(assets.begin(), assets.end(), back_inserter(photos), [] (shared_ptr<MediaAsset> p) -> bool {
    // Use dynamic_pointer_cast to test whether
    // element is a shared_ptr<Photo>.
    shared_ptr<Photo> temp = dynamic_pointer_cast<Photo>(p);
    return temp.get() != nullptr;
});

for (const auto&  p : photos) {
    // We know that the photos vector contains only
    // shared_ptr<Photo> objects, so use static_cast.
    wcout << "Photo location: " << (static_pointer_cast<Photo>(p))->location_ << endl;
}

 

 

 

 

코드출처) 

https://bbagwang.com/programming/cpp/%EC%8A%A4%EB%A7%88%ED%8A%B8-%ED%8F%AC%EC%9D%B8%ED%84%B0-smart-pointer/

 

https://ence2.github.io/2020/11/c-%EC%BA%90%EC%8A%A4%ED%8C%85-%EC%B4%9D%EC%A0%95%EB%A6%AC%EC%8A%A4%EB%A7%88%ED%8A%B8%ED%8F%AC%EC%9D%B8%ED%84%B0-%EC%BA%90%EC%8A%A4%ED%8C%85-%ED%8F%AC%ED%95%A8/

※ Type Casting이란?

변수의 type을 강제로 다른 type으로 변경하는 것으로 자료형간 || 포인터간 형변환시 사용된다.

C/C++은 변수의 type을 변경해 처리해야 하는 경우가 빈번하게 발생한다.

Q. 외부 library 사용시, 인자로 넘겨야할 변수가 char인데 외부의 library가 unsigned char를 사용한다면?
A: 개발자는 unsigned char로 변경해서 넘겨주어야 컴파일 에러가 발생하지 않는다.
int print(unsigned char *str){
    cout << str << endl;
}

int main() {
    char str[20] = "Hello, world!";

    print(str); // type casting이 필요 (Err)
    print(reinterpret_cast<unsigned char*>(str));
}

 

 

 

※ Type Casting의 종류

캐스트는 크게 2가지로 나눌 수 있다.

 

- 묵시적 캐스트 (implicit cast): 캐스트 연산자를 사용하지 않고 형변환이 이뤄지는 경우
- 명시적 캐스트 (explicit cast): 캐스트 연산자를 사용하여 형변환이 이뤄지는 경우

 

 

 

 

 

 

※ static_cast

[사용시기]: 논리적으로 변경가능한 경우

- static_cast의 특성은 묵시적 캐스트와 비슷하다 보면 된다.

- 묵시적 캐스트는 컴파일 시점에서 '무결성'을 검사하는데 이때, '허용'과 '컴파일러에 의한 값 변환' 두 관점이 있다.

- static_cast는 형변환에 의한 타입 확인compile 시간에 정적으로 수행한다.

 

§ 명시적 형변환 §

float f;
int a = static_cast<int>(f);

char *str = static_cast<char*>(f);  // Err!

 

 

 

 

※ const_cast

[사용시기]: 포인터, 참조형에서만 사용가능 const 및 volatile 제거할 때 사용된다!

- const_cast는 상수성이나 volatile(최적화 제외 변수)의 속성을 제거할 때 사용한다.

 

§ 명시적 형변환 §

int x = 10;

const int *pt_const_x = new int(10);
int *ptx;

ptx = const_cast<int*>(pt_const_x);
*ptx = 20; // 20에서 10으로 값 변경


const int &rt_const_x = x;
int& rtx = const_cast<int&>(rt_const_x);

 

 

 

 

 

※ reinterpret_cast

[사용시기]: 명시적 변환과 동작이 동일해 대신 사용된다. 단, const 사용 변환대상은 불가!

- 어떤 포인터 타입도 어떤 포인터 타입으로든 변환이 가능!

- [정수 -> 포인터] 타입도, [포인터 -> 정수]타입으로도 가능하다.

- 강력한 casting 같지만 특수 케이스가 아닌이상 사용을 잘하지 않는 것을 추천 (포인터가 강제 형변환되서)

 

§ 명시적 형변환 §

int *ptr = new int(10);
char *str;

str = reinterpret_cast<char*>(ptr);
*str = 20; // 10 -> 20으로 값변경

 

§ const 지정자 사용시, 명시적 형변환 §

const int *ptr = new int(10);
char *str;

str = reinterpret_cast<char*>(const_cast <int*> (ptr));
*str = 20; // 10에서 20으로 값변경

 

 

 

 

※ dynamic_cast

[사용시기]: class의 포인터, 참조변수간 형변환 시 안전하게 down casting을 위해 사용. 

Runtime conversions로 RTTI(Requires Runtime Type Information)

단, parent에 virtual 함수가 존재해야 정상작동!

- run time에 동적으로 상속계층관계를 가로지르거나 down casting시 사용됨

- 기본클래스에 virtual 멤버함수가 하나도 없다면, 다형성을 갖는게 아님(단형성)

따라서 dynamic_cast는 다형성을 띄지 않은 객체간 변환은 불가능!

 

§ 명시적 형변환 §

#include <iostream>
using namespace std;

class Blog {
public:
    Blog() { cout << "Blog()\n"; };
    virtual ~Blog() { cout << "~Blog()\n"; };

    void Show() { cout << "This is Blog Class\n"; }
};

class Tistory : public Blog {
public:
    Tistory() { cout << "Tistory()\n"; };
    virtual ~Tistory() { cout << "~Tistory()\n"; };

    void Show() { cout << "This is Tistory Class\n"; }
};

int main(void) {
    Blog* pBlog = new Blog();
    pBlog->Show();

    Tistory* pTistory = dynamic_cast<Tistory*>(pBlog);

    if (pTistory == nullptr) { //티스토리 클래스의 포인터가 nullptr이 나올떄.
        cout << "Runtime Error\n"; 
    }
    else {
        pTistory->Show();
    }

    delete pBlog;
    system("pause");
}

 

 

※ static_cast   VS   dynamic_cast

[static_cast]: 정적으로 형변환을 해도 아무 문제가 없다 (= 이미 어떤 녀석인지 알고 있다는 뜻), Fast

[dynamic_cast]: 동적으로 형변환을 시도 해본다는 뜻 (= 이녀석의 타입을 반드시 알아봐야 한다는 뜻), Slow (RTTI)

 

따라서 dynamic_cast를 이용해 Runtype의 해당 타입을 명확히 알아봐야 하고 (RTTI, Requires Runtime Type Info)

그렇지 않은 경우, static_cast를 이용해 변환 비용을 줄이는 것이 좋다. (동적타입체크를 안해도 되서)

 

// 비행기에 여러 직군의 사람들이 탑승했다.
// 한 승객이 갑자기 급성 맹장염에 걸려 의사가 급하게 수술을 해야 한다.
class Passenger {...};
class Student : public Passenger{
    ...
    void Study();
};
class Teacher : public Passenger{
    ...
    void Teach();
};
class Doctor : public Passenger{
    ...
    void Treat();
    void Operate();
};

int main() {
    typedef vector<Passenger *> PassengerVector;
    PassengerVector passengerVect;

    Passenger* pPS = new Student();
    if (pPS){
        passengerVect.push_back( pPS );
        // 비행기 타자마자 공부한다고 치고~
        // pPS가 명확하게 어느 클래스의 인스턴스인지 알고 있다.
        // 이 경우엔 굳이 비용이 들어가는 dynamic_cast가 아닌, static_cast를 쓰는게 낫다.
        Student* pS = static_cast<Student *>( pPS );
        pS->Study();
    }

    Passenger* pPT = new Teacher();
    if ( pPT ){
        passengerVect.push_back( pPT );
    }

    // Doctor 역시 비슷하게 추가.
    ...

    // 응급 환자 발생. passengerVect 중 의사가 있다면 수술을 시켜야 한다.
    PassengerVect::iterator bIter(passengerVect.begin());
    PassengerVect::iterator eIter(passengerVect.end());
    for( ; bIter != eIter; ++bIter ) {
        // Passenger 포인터로 저장된 녀석들 중 누가 의사인지 구분해야 한다.
        // 런타임 다형성 체크에 의해 Doctor가 아닌 녀석들에 대한 형변환 결과는 NULL
        Doctor* pD = dynamic_cast<Doctor *>(*bIter);
        if (pD){
            pD->Operate();
        }
    }
}

위 예제는 static_cast와 dynamic_cast를 구분해서 언제 쓰는게 좋은지 알 수 있는 예제이므로 잘 분석해보자.

Q. 만약, 위 코드의 전체 승객 중 의사를 찾아내는 과정에서 dynamic_cast가 아니라, static_cast를 사용하였다면 어떻게 될까?

static_cast는 동적 타입체크를 하지 않고, Student와 Teacher는 Person의 파생 클래스이므로 
변환 연산 규정에도 위배되지 않으므로, 그냥 타입 변환이 일어난다.
하지만, 변환 결과는 애초 기대했던 바와 전혀 다릅니다. 실제 Student 클래스 타입이지만,
Doctor 클래스 타입으로 타입 변환이 되면서Doctor 클래스 고유 멤버 함수에 대한 접근이 불가능해진다.

포인터가 가리키는 메모리 내용을 Doctor 클래스에 맞춰서 해석하기에
Student의 내용 중 일부가 Doctor 멤버 필드에 엉뚱하게 들어가거나, 슬라이스 문제가 발생할 수 있다.

다시 말해, 껍데기만 Doctor 클래스이지 내용은 전혀 Doctor의 것이 아니게 되는데,
멤버 필드에 접근시 엉뚱한 값이 들어가 있거나, 런타임 Err가 발생할 수 있다.

코드 및 설명 출처) https://ence2.github.io/2020/11/c-%EC%BA%90%EC%8A%A4%ED%8C%85-%EC%B4%9D%EC%A0%95%EB%A6%AC%EC%8A%A4%EB%A7%88%ED%8A%B8%ED%8F%AC%EC%9D%B8%ED%84%B0-%EC%BA%90%EC%8A%A4%ED%8C%85-%ED%8F%AC%ED%95%A8/

※ Stack

스택은 LIFO(Last-In-First-Out) 입출력 형태, 즉 후입선출 방식을 가진 자료구조이다.

https://images.app.goo.gl/aei6cA:jvUhK2WN86

위의 그림에서 4, 5번째 그림을 보자.    Last In: 3  /  First Out: 3

즉, 가장 마지막에 들어온 data가 가장 먼저 나가는 것을 알 수 있다.

 

push와 pop의 시간복잡도는 둘 다 O(1)의 시간을 갖는다.

단, 탐색의 시간복잡도는 특정 data를 찾을 때까지 돌아야 하므로 O(n)의 시간을 갖는다.

 

그렇다면 Stack을 왜 사용하는 것일까?

 

※ Stack의 사용이유

undo 즉, Ctrl+z라는 키워드처럼 최근에 실행한 명령어를 취소해야 하기 때문이라는 예를 들 수 있다.

 

조금 더 Computer Science적으로 접근해보면 OS에서 process가 바라보는 memory 영역은 크게 4가지로 나뉜다.

- Code: process가 실행할 코드와 매크로 상수가 기계어로 저장된 공간

- Data: 전역변수, static변수 등의 변수들이 저장된 공간

- Heap: malloc, calloc, realloc, new 와 같은 동적할당을 위한 메모리 공간으로 사용한 후 반드시 해제해야한다!

- Stack: heap에 비해 할당할 수 있는 메모리공간이 적지만 포인터로 접근해야하는 heap에 비해 data처리속도가 빠르다.

 

여기서 Stack Segment의 data를 기록하고 종료하는 메커니즘이 후입선출방식(LIFO)으로 이루어진다.

 

 

 

 

 

 

※ Stack Container (STL) ★

stack 컨테이너는 vector 클래스의 interface를 제한해 전형적인 stack메모리 구조의 interface를 제공한다.

stack 컨테이너는 stack 헤더파일에 정의되어 있다. 

http://www.tcpschool.com/cpp/cpp_container_adapter

stack 컨테이너는 stack 메모리구조 표현을 위해 다음과 같은 멤버 함수를 제공한다.

http://www.tcpschool.com/cpp/cpp_container_adapter

 

 

※ Stack 선언방식

#include <stack>

stack<데이터타입> 이름;

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

int main() {
    stack<int> intStack1;
    stack<int> intStack2;

    intStack1.push(1);
    intStack1.push(2);
    intStack1.push(3);

    intStack2.push(10);
    intStack2.push(20);
    intStack2.push(30);

    swap(intStack1, intStack2);

    while (!intStack1.empty()) {
        cout << intStack1.top() << endl;
        intStack1.pop();
    }
}

/*
 * 출력결과
 * 30
 * 20
 * 10
 */

출처: https://life-with-coding.tistory.com/406 [코딩젤리:티스토리]

 

 

 

[Stack 관련 백준문제]

백준 10828번: https://www.acmicpc.net/problem/10828

 

10828번: 스택

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

www.acmicpc.net

백준 1874번: https://www.acmicpc.net/problem/1874

 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net

백준 3986번: https://www.acmicpc.net/problem/3986

 

3986번: 좋은 단어

이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에

www.acmicpc.net

백준 1725번: https://www.acmicpc.net/problem/1725

 

1725번: 히스토그램

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은

www.acmicpc.net

 

 

 

 

 

 

 

 

 

 

※ Stack 자료구조의 구현

위에서 STL 즉, 이미 구현되어 있는 자료구조를 사용한 것을 보았다. 우리는 그 자료구조가 어떻게 구현되어 있는지 뜯어볼 필요가 있다.

 

(pseudo code) 의사코드로 먼저 표현

 

 

§ 배열로 구현

#include <iostream>
using namespace std;

inline void Err (char* ErrMessage){
    printf("%s\n", ErrMessage);
    exit(1);  // 실패상태코드로 프로그램 강제 종료
}

const int Max_Stack_Size = 10;

class stack{
private:
    int top;
    int arr[Max_Stack_Size];
public:
    bool isEmpty();
    bool isFull();
    int push(int data);
    void pop();
    void show();
    void Quit();

    stack() { top = -1; }
    ~stack(){ }
};

bool stack::isEmpty() {
    return top == -1;
}
bool stack::isFull() {
    return top == Max_Stack_Size - 1;
}

int stack::push(int data) {
    if (isFull())
        Err("Stack is Full");
    arr[++top] = data;
}
void stack::pop(){
    if (isEmpty())
        Err("Stack is Empty");
    arr[--top];
}

void stack::show(){
    if (isEmpty())
        cout << "Empty Stack" << endl;
    if (isFull())
        cout << "Full Stack" << endl;
    for (int i = 0; i <= top; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;
}

void stack::Quit(){
    exit(0);
}

int main() {
    stack stack;
    int arr[Max_Stack_Size], i=0;
    int data;
    int num;  // 1. isEmpty  /  2. isFull / 3. push / 4. pop / 5. show / 6. Quit
    while (true){
        cout << "1. push / 2. pop / 3. isEmpty  / 4. isFull / 5. show / 6. Quit"<< endl;
        cin >> num;
        if (num == 1) {
            cout << "push할 숫자를 입력하세요" << endl;
            cin >> data;
            stack.push(data);
        }
        if (num == 2)
            stack.pop();
        if (num == 3)
            stack.isEmpty();
        if (num == 4)
            stack.isFull();
        if (num == 5)
            stack.show();
        if (num == 6)
            stack.Quit();
    }
}

 

 

 

feat. 백준 9012번: https://www.acmicpc.net/problem/9012

 

9012번: 괄호

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고

www.acmicpc.net

§ 예제. 괄호검사 알고리즘. 

조건 1): 왼쪽과 오른쪽 괄호 개수 동일

조건 2): 왼쪽이 먼저 나와야 함

조건 3): 서로 다른 타입의 왼쪽과 오른쪽 괄호쌍을 교차하지 말것.

 

Ex. 

C++로 쉽게 풀어쓴 자료구조 / 천인국.최영규 저

 

(pseudo code) 의사코드로 먼저 표현

 

※ STL을 포함한 stack 실전 구현

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

bool checkBracket(char* s){
    stack<char> stack;  // 괄호를 검사하기 위해 사용할 stack
    map<char, char> bracketMap = {{')', '('},
                                  {']', '['},
                                  {'}', '{'}};

    for(int i=0; s[i]!='\0'; i++){
        // 왼쪽 괄호를 만나는 경우 stack에 push
        if(s[i]=='(' || s[i]=='[' || s[i]=='{'){
            stack.push(s[i]);
        }
        // 오른쪽 괄호를 만나는 경우 stack의 top과 비교
        if(s[i]==')' || s[i]==']' || s[i]=='}'){
            if(stack.empty()){
                return false;   // stack이 비어있는 경우 false
            }else{
                if(bracketMap.find(s[i])->second != stack.top()){
                    return false;   // stack의 top과 괄호의 짝이 맞지 않는 경우 false
                }else{
                    stack.pop();    // stack의 top과 괄호의 짝이 맞는 경우 pop
                }
            }
        }
    }

    // 최종적으로 stack이 empty된 경우 true, 아닌경우 flase
    if(stack.empty()){
        return true;
    }else{
        return false;
    }
}

int main() {
    char* c1 = "1. {A[(i+1)]=0;}";
    char* c2 = "2. if((i==0)&&(j==0)";
    char* c3 = "3. A[(i+1])=0;";

    cout << c1 << " : " << (checkBracket(c1) ? "True" : "False") << endl;
    cout << c2 << " : " << (checkBracket(c2) ? "True" : "False") << endl;
    cout << c3 << " : " << (checkBracket(c3) ? "True" : "False") << endl;
    return 0;
}

 

※ 형식연역 (type deduction)

형식연역이 일어나는 방식을 확실히 이해하지 않는다면 Modern C++에서 효과적인 프로그래밍은 불가능하다.

1장에서는 이런 형식연역의 작동방식과 형식연역에 기초한 auto와 decltype의 작동방식에 대해 알아본다.

필요성 : 템플릿 형식 연역 규칙들이 auto의 문액에 적용 될 때 덜 직관적이며
auto를 잘 활용하려면 템플릿 형식 연역을 이해하고 있어야 한다.

 

 

 

 

 

User가 System의 작동방식을 알지 못해도 System의 일에 만족한다면, 잘 설계되었다라고도 할 수 있다.

 

그런 프로그래머라면 좋은 소식과 나쁜 소식이 있다.

- Positive: Modern C++은 아주 강한 기능 중 하나인 auto가 template 형식영역을 기반으로 작동한다는 것이다.

- Negative: template형식 연역규칙들이 auto의 문맥에 적용될 때 template에 비해 덜 직관적인 경우가 있다.

 

∴ 따라서 auto를 잘 활용하려면 auto가 기초하는 template 형식연역의 면모를 제대로 이해해야한다.

 

 

 

※ 함수 template

template<typename T>
void f(ParamType param);

// 어떤 표현식으로 f를 호출
f(expr);

컴파일 도중 expr을 이용해 2가지의 형식을 연역한다.

1. T에 대한 형식

2. ParamType에 대한 형식

 

이 두 형식이 다른 경우가 많은데 이는 ParamType에 흔히 const 같은 참조한정사 수식어가 붙기 때문이다.

template<typename T>
void f(const T& param); //ParamType은 const T&

int x = 0;

f(x); // int로 f를 호출

이 경우, T는 int로 연역되지만 ParamType은 cosnt int& 로 연역된다. (x는 int이고 T는 int로 연역된다.)

 

T에 대해 연역된 형식이 함수에 전달된 인수의 형식과 같다고 생각했다면 그것이 항상 그러지는 않는다.

=> T에 대해 연역된 형식은 expr의 형식에 의존할 뿐만 아니라 ParamType의 형태에도 의존한다.

그 형태에 따라 총 3가지 경우로 나뉜다.

1. ParamType이 포인터, 참조형식이지만 보편참조는 아닌 경우.
2. ParamType이 보편참조인 경우
3. ParamType이 포인터, 참조 모두 아닌 경우

따라서 3가지 형식 연역 시나리오에 대해 살펴봐야 한다.

 

다음과 같은 일반적인 형태의 템플릿과 그 호출에 기초해 3가지 시나리오를 생각해보자.

template<typename T>
void f(ParamType param);

f(expr);  // expr로부터 T와 ParamType을 연역

 

 

Case 1. ParamType이 포인터, 참조형식 이지만 보편참조는 아님.

1. 만약 expr이 참조형식이면 참조부분을 무시한다.

2. 그 후 expr의 형식을 ParamType에 대해 pattern-matching방식으로 대응시켜 T의 형식을 결정한다.

template<typename T>
void f(T& param);  // param은 참조형식

int x = 27;        // x는 int
const int cx = x;  // cx는 const int
const int& rx = x; // rx는 const int인 x에 대한 참조

/* 여러 호출에서 param과 T에 대해 연역된 형식 */
f(x);  // T는 int, param의 형식은 int&
f(cx); // T는 const int, param의 형식은 const int&
f(rx); // T는 cosnt int, param의 형식은 const int&

위 f(cx), f(rx)의 param은 const값이고, 이는 그 객체가 수정되지 않을 것이라 기대한다.

즉, 해당 매개변수가 const에 대한 참조일 것이라 기대한다. (T& 매개변수를 받는 템플릿에 const객체를 전달해도 안전한 이유)

 

f(rx)에서 비록 rx의 형식이 참조이지만 T는 비참조로 연역된 것에 주목하면 이는 형식연역과정에서 rx의 참조성이 무시되기 때문임을 알 수 있다.

만약 f의 매개변수 형식을 T&에서 const T&로 바꾸게 된다면 상황이 달라지지만 큰 변화는 없다.
cx와 rx의 const성은 유지되며 단, param이 const에 대한 참조로 간주되므로  
const가 T의 일부로 연역될 필요는 없다.
template<typename T>
void f(const T& param);  // param이 cosnt에 대한 참조

int x = 27;        // x는 int
const int cx = x;  // cx는 const int
const int& rx = x; // rx는 const int인 x에 대한 참조

/* 여러 호출에서 param과 T에 대해 연역된 형식 */
f(x);  // T는 int, param의 형식은 const int&
f(cx); // T는 int, param의 형식은 const int&
f(rx); // T는 int, param의 형식은 const int&

이전처럼 rx의 참조성은 형식연역과정에서 무시된다.

 

이는 아래처럼 param을 참조가 아닌 포인터, const를 가리키는 포인터라도 형식연역은 본직적으로 같은 방식을 취한다.

template<typename T>
void f(T* param);  // param이 cosnt에 대한 참조

int x = 27;        // x는 int
const int *px = x; // px는 const int로 x를 가리키는 포인터

/* 여러 호출에서 param과 T에 대해 연역된 형식 */
f(&x);  // T는 int, param의 형식은 int*
f(px); // T는 const int, param의 형식은 const int*

 

여기까지는 너무 쉬워서 하품이 날 지경이라고 한다.(물론 저자가 그런거지 난 아니다. 어려워 죽을거 같다.)

 

 

 

 

 

 

Case 2. ParamType이 보편참조임.

템플릿이 보편참조매개변수를 받는 경우, 상황이 불투명해진다.

그런 매개변수 선언은 rvalue 참조와 같은 모습이다. (보편참조의 선언형식은 T&&이다.)

l-value가 전달되면 r-value참조와는 다른 방식으로 행동한다.

 

- 만약 expr이 l-value면, T와 ParamType 둘 다 l-value 참조로 연역된다. (비정상적 상황)

  i) 템플릿 형식 연역게서 T가 참조형식으로 연역되는 경우, 이것이 유일

  ii) ParamType의 선언구문은 r-value 참조와 같지만 연역된 형식은 l-value참조이다.

- 만약 expr이 r-value면, '정상적인' 규칙들이 적용된다. (Case 1의 규칙들.)

template<typename T>
void f(T&& param);  // 이번에는 param이 보편 참조

int x = 27;         // x는 int
const int cx = x;   // cx는 const int
const int& rx = x;  // rx는 const int인 x에 대한 참조

f(x);  // x는 l-value, 따라서 T는 int&, param 형식도 int&
f(cx); // cx는 l-value, 따라서 T는 const int&, param 형식도 const int&
f(rx); // rx는 l-value, T는 const int&, param 형식도 const int&
f(27); // 27은 r-value, 따라서 T는 int, param 형식은 int&&

나중에 item 24에서 설명될 것이고, 지금은 보편참조매개변수에 관한 형식연역 규칙들이

l-value참조나 r-value참조 매개변수들에 대한 규칙들과는 다르다는 점만 기억하면 된다.

특히 보편참조가 관여하는 경우, l-value와 r-value에 대해 서로 다른 연역규칙이 적용된다. (보편참조가 아니면 발생X)

 

 

 

 

 

 

 

Case 3. ParamType이 포인터도 아니고 참조도 아님

ParamType이 포인터도 참조도 아닌 경우, 인수가 함수에 값으로 전달되는 pass-by-value인 상황이다.

template<typename T>
void f(T param);     // param이 값으로 전달된다.

따라서 param 주어진 인수의 복사본 (즉, 완전히 새로운 객체)이다.

param이 새로운 객체라는 사실 때문에 expr에서 T가 연역되는 과정에서 다음과 같은 규칙들이 적용된다.

1. 이전처럼, 만약 expr의 형식이 참조라면, 참조부분은 무시된다.
2. expr의 참조성을 무시한 후 만약 expr이 const라 해도 그 const 역시 무시한다.

만약 volatile객체라도 그것도 무시한다.   (volatile객체는 흔하지 않기에 (장치구동기 구현시 사용) item 40 참고)

 

다음은 이 규칙들이 적용되는 예이다.

template<typename T>
void f(T&& param);  // 이번에는 param이 보편 참조

int x = 27;         // x는 int
const int cx = x;   // cx는 const int
const int& rx = x;  // rx는 const int인 x에 대한 참조

f(x);  // T와 param의 형식 둘 다 int
f(cx); // 여전히 T와 param의 형식 둘 다 int
f(rx); // 여전히 T와 param의 형식 둘 다 int

이때, cx와 rx는 const값이지만, param은 const가 아님을 주목하자.

param은 cx, rx의 복사본이므로 (param은 cx, rx와 달리 완전히 독립적인 객체이므로) 당연한 결과이다.

cx, rx가 수정될 수 없다는 점(const)은 param의 수정가능 여부와는 무관하기 때문이다.

param의 형식을 연역하는 과정에서 expr의 const성이 무시되는 이유가 바로 이것이다.

expr을 수정할 수 없다해서 그 복사본까지 수정할 수 없는 것은 아니기 때문이다.

 

여기서 명심할 점은, const가 값 전달 매개변수에 대해서만 무시된다는 점이다.

즉, const에 대한 참조나 포인터 매개변수의 경우, 형식연역과정에서 expr의 const성이 보존된다.

 

 

그러나 expr이 cosnt객체를 가리키는 const포인터이고 param에 값으로 전달되는 경우는 어떨까?

template<typename T>
void f(T param);                    // 인수는 param에 여전히 값으로 전달됨

const char* const ptr = "V2LLAIN";  // ptr은 const 객체를 가리키는 const 포인터

f(ptr);                             // const char* const 형식의 인수를 전달

포인터 선언 오른쪽 const로 ptr 자체가 const가 된다. (const char* const ptr)

즉, ptr을 다른 장소를 가리키도록 변경불가능! (nullptr도 배정할 수 없다.)

 

포인터 선언 왼쪽 const가 가리키는 것은 문자열이 const인 것을 의미한다. (const char* const ptr)

 

ptr을 f에 전달하면 그 포인터를 구성하는 bit들이 param에 복사되며 포인터자체(ptr)는 값으로 전달된다.

형식연역과정에서 ptr의 const성은 무시되며 따라서 param에 연역되는 형식은 const char*이다.

즉, 형식연역과정에서 ptr이 가리키는 것의 const성은 보존되나

ptr 자체의 const성은 ptr을 복사해 새 포인터 param을 생성하는 도중 사라진다!

 

 

 

※ 템플릿 연역과정에서 배열이나 함수이름에 해당하는 인수는 포인터로 붕괴(decay)한다.

(단, 그런 인수가 참조를 초기화하는데 사용되면, 그 경우에는 포인터로 붕괴하지 않는다.)

 

§ 배열과 포인터를 구분하지 않고 사용가능하지만, 배열형식은 포인터 형식과 다르다는 사실!

- 배열과 포인터를 맞바꿔 쓸 수 있는 것처럼 보이는 환상의 주된 원인은 많은 문맥에서 배열이 배열의 첫 원소를 가리키는 포인터로 붕괴한다(decay)는 점이다.

이런 붕괴때문에 아래와 같은 코드는 오류가 없이 컴파일 된다.

const char name[] = "V2LLAIN";
const char* ptrname = name;

 

그런데 배열을 값 전달 매개변수로 받는 template에 전달하면 어떻게 될까?

우선 배열형식의 함수 매개변수라는 것은 없다!

물론 아래와 같은 구문 자체는 가능하다.

void myFunc(int param[]);

하지만 이 경우 배열선언은 하나의 포인터 선언으로 취급되므로 사실상 아래와 동일하게 취급된다.

void myFunc(int *param);  // 위와 동일한 함수

 

따라서 아래 예시를 보면 name은 배열이지만 T는 const char*로 연역되어 버린다.

const char name[] = "V2LLAIN";

template<typename T>
void f(T param);      
f(name);             // name은 배열이지만 T는 const char*로 연역됨

 

 

그런데 한가지 교묘한 요령이 있는데, 함수의 매개변수를 진짜 배열로 선언은 못하지만,

배열에 대한 참조로 선언할 수는 있다!

 

즉, 다음과 같이 템플릿 f가 인수를 참조로 받도록 수정하고 함수에 배열을 전달하면

T에 대해 연역된 형식은 배열의 실제형식이 된다!

const char name[] = "V2LLAIN";

template<typename T>
void f(T& param);      // 참조 전달 매개변수가 있는 템플릿
f(name);               // 배열을 f에 전달

 

배열에 대한 참조선언을 이용하면 배열에 담긴 원소들의 개수를 연역하는 템플릿을 만들 수 있다!

 

[item 15]에서 더 자세히 나오지만 이 함수를 constexpr로 선언하면 함수 호출의 결과를 컴파일 도중 사용할 수 있다!

그렇게 되면 기존 배열과 같은 크기의 새 배열을 선언하는 것이 가능하게 된다.

template<typename T, std::size_t N>

constexpr std::size_t arraySize(T (&) [N]) noexcept { return N; }

int Vals[] = {1, 2, 3, 4 ,5, 6, 7};  // Vals의 원소개수는 7
int mapVals[arraySize(Vals)];  // mapVals의 원소 개수 역시 7개

/*물론, modern C++ 개발자라면 std::array나 vector를 더 선호할 것이다.*/
std::array<int, arraySize(Vals)> mapVals;  // mapVals의 크기는 7

이때, arraySizenoexcept 선언한 것은 컴파일러가 더 나은 코드를 산출하는데 도움을 주기 위한 것이다. (item 14)

 

 

물론, C++에서 포인터로 붕괴하는 것이 배열만 있는 것은 아니다.

앞에서 배열에 대한 형식연역과 관련된 모든것은 함수포인터로의 붕괴에 적용된다.

void someFunc(int, double);

template<typename T>
void f1(T param);       // f1의 param은 값 전달 방식

template<typename T>
void f2(T& param);      // f2의 param은 참조 전달 방식

f1(someFunc);           // param은 함수포인터로 연역됨 // void (*)(int, double)
f2(someFunc);           // param은 함수참조로 연역됨   // void (&)(int ,double)

 

 

 

 

 

 

◈ Remind ◈

- 템플릿형식 연역 중 참조형식의 인수들은 비참조로 취급된다. 즉, 참조성이 무시된다.
- 보편참조 매개변수에 대한 형식 연역과정에서 l-value들은 특별하게 취급된다.
- 값 전달방식의 매개변수에 대한 형식연역과정에서 const, volatile 인수는 비 const, 비 volatile 인수로 취급된다.
- 템플릿형식 연역과정에서 배열이나 함수이름에 해당하는 인수는 포인터로 붕괴한다.
  단, 그런 인수가 참조를 초기화하는데 쓰이는 경우, 포인터로 붕괴하지 않는다.

+ Recent posts