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


나무위키 최장증가부분수열


사람들이 각각 번호를 가지고 있고 그 번호 순서에 맞춰서 일렬로 정렬하려고 한다. 이때 움직인 사람들의 총 수를 최소로 하고 싶다면 어떻게 해야 하는가? (단, 초기에 사람들은 무작위로 일렬로 섞여 있고, 'A씨, 맨 뒤 / 맨 앞으로 가세요', 'A씨, B씨와 C씨 사이로 가세요' 꼴의 명령으로 사람들을 이동시킨다고 하자.)


이 문제는 전형적인 LIS 응용 문제이다. 움직인 사람들의 총 수가 최소가 된다는 말은 움직이지 않은 사람들의 수가 최대가 된다는 것이다.

사람들의 번호들의 수열에서 이미 오름차순으로 정리된 쌍이 있다면 그들은 움직이지 않아도 된다. 따라서 그 수열의 LIS를 이루는 사람들은 움직이지 않고, 나머지 사람들이 그들 사이로 적절히 배열된다면 정렬할 수 있다. 


정렬 -> LIS -> 전깃줄 개수 - 수열 크기


난최고야!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <algorithm>
 
struct wire
{
    int A;
    int B;
};
 
wire arr[101];
int dp[101];
 
bool cmp(wire& first, wire& second)
{
    if (first.A < second.A)
        return true;
    else
        return false;
}
 
int main()
{
    int N;
    std::cin >> N;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> arr[i].A >> arr[i].B;
    }
    std::sort(arr, arr + N, cmp);
    
    int back = 0;
    for (int i = 0; i < N; ++i)
    {
        int it = 0;
        for( ;dp[it] != 0++it)
        {
            if (dp[it] > arr[i].B)
            {
                dp[it] = arr[i].B;
                break;
            }
        }
        dp[it] = arr[i].B;
        back = back > it ? back : it;
    }
    std::cout << N - (back + 1);
    return 0;
}
cs


끼에에에에에에에에엒!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

nlogn으로 풀어본다고 개삽질하다가 지쳐서


n2으로 무식하게 오름차순 내림차순 다 계산해서 배열에 때려박은다음


계산된 배열 두개중 합친 값이 가장 큰걸 반환하게 했다.


솔찍히 시간초과 날줄알앗는데 으..응?으응???하니까 정답입니다!!...


아몰라 ㄹ풀었음댓지머


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
 
int seq[1010];
int highDp[1010];
int lowerDp[1010];
 
int main()
{
    int N;
    std::cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> seq[i];
        int m = highDp[0];
        for (int j = 0; j < i; ++j)
            if (seq[i] > seq[j] && highDp[j] > m)
                m = highDp[j];
        highDp[i] = m + 1;
        
    }
 
    for (int i = N; i >= 1--i)
    {
        int m = 0;
        for (int j = N + 1; j >= i; --j)
            if (seq[i] > seq[j] && lowerDp[j] > m)
                m = lowerDp[j];
        lowerDp[i] = m + 1;
    }
 
    int mx = 0;
    for (int i = 0; i <= N; ++i)
    {
        mx = lowerDp[i] + highDp[i] < mx ? mx : lowerDp[i] + highDp[i];
    }
    std::cout << mx - 1;
    return 0;
}
 
cs


으으 왤캐 깔끔하게 안풀리지?

'알고리즘' 카테고리의 다른 글

백준 9251: LCS(DP)  (0) 2019.08.26
백준 2565: 전깃줄(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22
백준 10844: 쉬운 계단 수(DP)  (0) 2019.08.19
백준 1463: 1로 만들기(DP)  (0) 2019.08.16

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


어제의 알고리즘 대실패는 나로 하여금 나 자신이 빡통이라는걸 절절히 인정하는 그러한 계기가 되었다.


그래서 오늘 문제는 바로 갓무위키를 찾아보았다.


부분수열이 뭔지 까먹었기도 하고ㅎ


꺼라위키 정의


어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다.

이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.


예를 들어 다음 수열이 주어졌다고 하자.


3 5 7 9 2 1 4 8


위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다.


3 7 9 1 4 8 (5, 2 제거)

7 9 1 8 (3, 5, 2, 4 제거)

3 5 7 8 (9, 2, 1, 4 제거)

1 4 8 (3, 5, 7, 9, 2 제거)


이들 중 세번째, 네번째 수열은 오름차순으로 정렬되어 있다. 이들을 '증가 부분 수열'이라고 한다.


그리고 이런 증가 부분 수열 중 가장 긴 수열을 '최장 증가 부분 수열 (LIS)'이라 한다.

부분수열 3 5 7 8은 LIS이다.


한 수열에서 여러 개의 LIS가 나올 수도 있다. 예를 들어 수열


5 1 6 2 7 3 8


에서 부분수열


1 2 3 8

5 6 7 8


은 모두 길이가 4인 LIS이다. 


부분수열은 간단히 말해서 임의의 수열 A에서 A의 원소를 포함하는 또다른 수열 B라고 보면 된다.


여기서 수열이라고 해서 좀 혼란스러웠는데, 수열은 보통 일정한 규칙이 존재하는 수의 집합이라고 봐야 하지만 여기선 없다고 봐도 상관 없다.


즉 걍 숫자 집합인데, 부분수열은 그냥 부분집합이다. 대신 숫자의 순서가 보장되어있는 집합이지


꺼라위키도 설명을 그지같이 했다. 몇 개의 숫자를 제거한다니, 제거하는 규칙이 있어야하는것마냥 설명해놓곤


걍 수열 A의 숫자 몇개 추려서 다른 수열 B 만들면 그게 A의 부분수열이다.(순서는 반드시 보장되어야 한다. 자세한 예시는 꺼라위키 정의 참고)


암튼, 그런 부분수열중에 오름차순으로 되어 있는 수열 x중 사이즈가 가장 큰 수열의 사이즈를 반환하는 문제다.


꺼라에서는 n제곱으로 푸는 방법과, n로그n으로 푸는 방법 둘 다 설명해놨는데 n제곱으로 풀어봤더니 통과된다.


알고리즘 푸는 방법은 혼자서 생각 못할 것 같아 어쩔 수 없이 봤지만...그래도 코드 구현은 직접 했다...


나도 똑똑해졌으면 좋겠구만


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <algorithm>
 
int seq[1010];
int dp[1010];
 
bool cmp(int first, int second)
{
    if (first > second)
        return true;
    else
        return false;
}
 
int main()
{
    int N;
    std::cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> seq[i];
        int m = dp[0];
        for (int j = 0; j < i; ++j)
            if (seq[i] > seq[j] && dp[j] > m)
                m = dp[j];
        dp[i] = m + 1;
    }
    std::sort(dp, dp + N + 1, cmp);
    std::cout << dp[0];
    return 0;
}
cs


여기서 sort를 사용했는데, 사실 max 변수 하나 만들어서 dp중 가장 큰 수를 max에 담아 출력하기만 하면 더 빠를 것이다


나는 그냥 좀 더 깔끔해보이려고 이렇게 뺐다. 문제는 없이 통과되던데


nlogn으로 푸는 방법


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
 
int seq[1010];
int dp[1010];
 
int main()
{
    int N;
    std::cin >> N;
    int back = 0;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> seq[i];
        int it = 1;
        while (dp[it] != 0)
        {
            if (dp[it] >= seq[i])
            {
                dp[it] = seq[i];
                break;
            }
            ++it;
        }
        if (dp[it] == 0)
        {
            dp[it] = seq[i];
            back = it;
        }
    }
    std::cout << back;
    return 0;
}
cs


설명은 귀찮아서 생략


일케 하면 빠른대신에 모든 데이터들의 증가부분수열을 저장할수는 없다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
 
unsigned int dp[101][10];
 
int main()
{
    int N = 0;
    std::cin >> N;
    for (int i = 1; i <= 9++i)
        dp[1][i] = 1;
    for (int i = 2; i <= N; ++i)
        for (int j = 0; j < 10++j)
        {
            if (j == 0)
                dp[i][j] = dp[i - 1][j + 1];
            else if (j == 9)
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = (dp[i - 1][j - 1+ dp[i - 1][j + 1]) % 1000000000;
        }
    unsigned long long ans = 0;
    for (int i = 0; i < 10++i)
        ans += dp[N][i];
    std::cout << ans % 1000000000;
    return 0;
}
cs


십억을 중간과정에서 나머지연산하면 오버플로는 막겠지만 값이 변하지 않나..


하... 모르겠다...


그냥 전체적으로 조졌다... 왜 일케 하는지는 알겠는데 내가 직접 로직을 세우지도 못했고... 아직도 나머지연산은 이해가 안대고... DP빡고수라고 자화자찬 하자마자 개뚜드려맞았다...

특별하게 어렵거나 쉽다기보단... DP 쥐뿔도 모르는 내가 꾸역꾸역 풀어본 문제라서 올려봄


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
 
int dp[1000010];
 
int main()
{
    int input, N;
    int cnt = 0;
    std::cin >> input;
    dp[2= dp[3= 1;
    N = 4;
    while (N <= input)
    {
        if (N % 3 == 0)
        {
            if (dp[N - 1>= dp[N / 3])
                dp[N] = dp[N / 3+ 1;
        }
        if (N % 2 == 0)
        {
            if (dp[N - 1>= dp[N / 2])
            {
                if (dp[N] == 0)
                    dp[N] = dp[N / 2+ 1;
                else if(N % 3 == 0)
                    if(dp[N] > dp[N / 2])
                        dp[N] = dp[N / 2+ 1;
            }
        }
        if(dp[N] >= dp[N - 1+ 1 || dp[N] == 0)
            dp[N] = dp[N - 1+ 1;
        ++N;
    }
    int i = dp[input];
    std::cout << i;
    return 0;
}
cs


이건 겨우겨우 풀어댄 방법


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
int dp[1000010];
 
int main()
{
    int input, N;
    int cnt = 0;
    std::cin >> input;
    dp[2= dp[3= 1;
    for (int N = 4; N <= input; ++N)
    {
        dp[N] = dp[N - 1+ 1;
        if (N % 3 == 0)
            dp[N] = dp[N] > dp[N / 3+ 1 ? dp[N / 3+ 1 : dp[N];
        if (N % 2 == 0)
            dp[N] = dp[N] > dp[N / 2+ 1 ? dp[N / 2+ 1 : dp[N];
    }
    std::cout << dp[input];
 
    return 0;
}
cs


이건 훨씬 깔끔한 방법


DP의 핵심은, 반복문을 한큐에 끝낼 수 있는가


인듯.


브루트포스처럼 코드가 이리흐르고 저리흐르면 망한다는 것이다


그러기 위해선 이곳저곳으로 흘러흘러가는 코드보다는


처음부터 끝까지 우직하게 지나가는(저장하는) 방식이 동적배열에 더 맞지 않는가 싶다.



계단: 2579


피보나치: 1003


그래서 동적계획법은 대체 머 어케하는건데??했던 지난날보다는 성장했지만


여전히 약간 꼬아놓은 문제는 간단하게 풀어내기 힘들다.


간단하게 풀었던 다른 문제들에 비해

(피보나치 함수는 내가 쉽게 풀었던 것에 비해 정답률이 생각보다 낮아서.. 너무 좋았따...크큭....)


계단문제에서 주춤했다. 사실 똑같이 간단한 문제인데... 정답에 접근하는 방법도 거의 근접했는데


어느 순간 생각이 산으로 가버리고...


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
#define max(a,b)            (((a) > (b)) ? (a) : (b))
 
int dp[301];
int stair[301];
 
int main()
{
    int N = 0;
    std::cin >> N;
    std::cin >> stair[1>> stair[2];
    dp[1= stair[1];
    dp[2= stair[1+ stair[2];
    for (int i = 3; i <= N; ++i)
    {
        std::cin >> stair[i];
        dp[i] = max(dp[i - 2+ stair[i], dp[i - 3+ stair[i - 1+ stair[i]);
    }
    std::cout << dp[N];
    return 0;
}
cs


코드를 짜면서도 '이렇게 풀면 될 것 같은데?' 하자마자


'음 아닌것같은데' (사실 정답이었다)




이건 개망한 접근방법

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
 
int dp[301];
 
int main()
{
    int N = 0;
    std::cin >> N;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> dp[i];
    }
    int sum = 0;
    --N;
    int i = 2;
    while(N >= 0)
    {
        sum += dp[N];
        if (i == 2)
        {
            i = dp[N - 1> dp[N - 2] ? 1 : 2;
        }
        else if (i == 1)
        {
            i = 2;
        }
        N -= i;
    }
    std::cout << sum;
    return 0;
}
cs


개시발


폰노이만...


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


병합 정렬은 무한 츠쿠요미 함수를 이용한 정렬 방식이다.


1. 쪼갤 수 있는 만큼 쪼개면서 배열을 쪼갠다.

(실제로 쪼개는건 아니고, 2개의 피봇으로 시작과 끝의 구분을 두었다.)


2. 그러면 배열의 시작과 끝이 같은 곳을 보거나 그럴텐데, 그건 건너뛴다.


3. start와 end가 같은 재귀함수(39 : start < end)는 건너뛰고, start와 end가 1차이나는 재귀는 병합한다.


4. 병합은 그 대진표 형식으로 정렬시킨다. 솔직히 이거 설명만 들으면 아~ 하는데 막상 코드 첨보면 이게 뭔가 싶다.


5. start와 end가 1차이나는 재귀 배열은 서로 정렬이 되어서 합쳐지고, 이제 start와 end가 2차이나는 배열이 남는다.


6. 이제 1:1이 아니라 2:2 태그매치다. 누가 더 숫자가 낮은지 겨뤄서 다시 정렬한다.


7. 4:4... 8:8... 올라가면서 계속 정렬한다.


8. 홀수인 경우? 하나는 겨뤄봄직한 상대가 없어서 부전승을 치지만, 다음 매치에서 결국 정렬당한다.


9. 폰노이만....


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <string>
#include <vector>
 
struct member
{
    int age = 0;
    std::string name;
};
 
std::vector<member> tmpVec;
 
void _merge(std::vector<member>& members, int start, int end)
{
    int mid = (start + end/ 2;
    int i = start;
    int j = mid + 1;
    int k = start;
 
    while (i <= mid && j <= end)
    {
        if (members[i].age <= members[j].age)
            tmpVec[k++= members[i++];
        else
            tmpVec[k++= members[j++];
    }
 
    int tmp = i > mid ? j : i;
 
    while (k <= end)
        tmpVec[k++= members[tmp++];
 
    for (int i = start; i < k; ++i)
        members[i] = tmpVec[i];
}
 
void _mergesort(std::vector<member>& members, int start, int end)
{
    if (start < end)
    {
        int m = (start + end/ 2;
        _mergesort(members, start, m);
        _mergesort(members, m + 1end);
        _merge(members, start, end);
    }
}
 
int main()
{
    std::ios::sync_with_stdio(false);
    std::cout.tie(0);
    std::cin.tie(NULL);
    std::ios_base::sync_with_stdio(false);
    int N;
    std::cin >> N;
    std::vector<member> members;
    members.reserve(N);
    tmpVec.reserve(N);
    member input;
    for(int i = 0; i < N; ++i)
    {
        std::cin >> input.age >> input.name;
        members.push_back(input);
        tmpVec.push_back(input);
    }
    _mergesort(members, 0, N - 1);
    for (auto it : members)
        std::cout << it.age << ' ' << it.name << '\n';
    return 0;
}
cs



자매품.

stable_sort 함수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
bool cmp(std::pair<intstd::string> first, std::pair<intstd::string> second)
{
    if (first.first < second.first)
        return true;
    else
        return false;
}
 
int main()
{
    int N;
    std::cin >> N;
 
    std::vector<std::pair<intstd::string>> members;
    members.reserve(N);
 
    std::pair<intstd::string> input;
    for(int i = 0; i < N; ++i)
    {
        std::cin >> input.first >> input.second;
        members.push_back(input);
    }
 
    stable_sort(members.begin(), members.end(), cmp);
 
    for (auto it : members)
        std::cout << it.first << ' ' << it.second << '\n';
    return 0;
}
cs


비교함수만 만들면 되는 간단한 문제이지만 그래서는 공부라고 할 수 없다


암기...암기가 최고야...

열혈 C++을 기초해 작성됨




예외상황과 예외처리의 이해


우리가 알고 있는 예외의 처리는 if문을 이용하는 것이다.


if문을 통해 예외상황의 발생유무를 확인한 다음 그에 따른 처리를 진행한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
    int num1, num2;
    std::cin >> num1 >> num2;
 
    if(num2 == 0)
    {
        std::cout << "제수는 0이 될 수 없음!" << std::endl;
    }
    else
    {
        std::cout << num1 / num2 << std::endl;
        std::cout << num1 % num2 << std::endl;
    }
    return 0;
}
cs


일반적인 예외 처리 방식이다. 하지만 다른 사람들이 코드를 볼 때 if문이 예외 처리를 위한 분기문인지, 논리적인 기능을 위한 분기문인지 한눈에 보기 어렵다.




C++의 예외처리 메커니즘


C++의 예외처리 메커니즘 이해: try와 catch 그리고 throw의 이해


- try

- catch

- throw


try


try 블록은 예외검사의 범위지정 시 사용된다. try 블록 내에서 예외가 발생하면, C++의 예외처리 메커니즘에 의해 처리된다.


1
2
3
4
try
{
    . . . . .
}
cs


catch


catch 블록은 try에서 발생한 예외를 처리하는 코드가 담기는 영역으로, 그 형태가 마치 반환형 없는 함수와 유사하다.


1
2
3
4
catch(예외 종류 명시)
{
    . . . . .
}
cs


try블록과 catch블록


catch블록은 try블록 뒤에 이어 등장한다. try 블록에서 발생한 예외는 이곳 catch블록에서 처리된다.


1
2
3
4
5
6
7
8
9
try
{
    Application().run(std::unique_ptr<RendererInterface>{ renderer });
}
catch (const std::exception& e)
{
    std::fprintf(stderr, "Error: %s\n", e.what());
    return 1;
}
cs

작동 예


throw


throw는 예외가 발생했음을 알리는 문장의 구성에 사용된다.


throw expn;


expn은 변수, 상수, 그리고 객체 등 표현 가능한 모든 데이터지만, 예외상황에 대한 정보를 담은 데이터다. 위 문장의 expn의 위치에 오는 데이터를 예외라고 표현한다. 또한, 예외 데이터, 예외 객체라고 표현하기도 한다.


throw에 의해 던져진 예외 데이터는 예외 데이터를 감싸는 try 블록에 의해 감지가 되어, 이어서 등장하는 catch 블록에 의해 처리된다.


1
2
3
4
5
6
7
8
9
10
11
12
try
{
    . . . . .
    if(예외 발생)
    {
        throw expn;
    . . . . .
}
catch (type expn)
{
    . . . . . //예외 처리
}
cs


예외처리 메커니즘의 적용


아래 코드는 try catch를 이용한 예외처리 결과이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
    int num1, num2;
    std::cin >> num1 >> num2;
    
    try
    {
        if(num2 == 0)
        {
            throw num2;
        }
        std::cout << num1 / num2 << std::endl;
        std::cout << num1 % num2 << std::endl;
    }
 
    catch (int expn)
    {
        std::cout << "잘못된 값: " << expn << std::endl;
    }
    std::cout << "끝" << std::endl;
    return 0;
}
cs


입력

7 7

결과

1

0


입력

7 0

잘못된 값: 0


20 : 예외가 던져지는 상황이나, 던져지지 않는 상황이나 실행된 것이 보인다.

10 : num2 의 자료형은 int다

16 : catch로 받는 예외의 자료형 역시 int다


if문으로 구현한 예외처리와 비슷하지만 약간 다르게 작동하는 것이 보인다.

컴파일러가 throw를 만나면 그 이후부터 try 범위의 내부에 있는 다른 연산은 수행하지 않는다. 바로 catch로 넘어간다.

-> 예외가 발생한 지점 이후를 실행하는 것이 아니라, catch블록 이후가 실행된다.


try 블록을 묶는 기준


다음 규칙은 try의 실행 흐름이다.


- try 블록을 만나면 그 안에 삽입된 문장이 순서대로 실행된다.

- try 블록 내에서 예외가 발생하지 않으면 catch 블록 이후를 실행한다.

- try 블록 내에서 예외가 발생하면, 예외가 발생한 지점 이후의 나머지 try 영역은 건너뛴다.


try블록을 묶는 기준은 예외와 관련된 모든 문장을 함께 묶어서 하나의 일의 동작 단위로 구성하는 것이다.


1
2
3
4
5
6
7
8
9
try
{
    if(num2 == 0)
    {
        throw num2;
    }
    std::cout << num1 / num2 << std::endl;
    std::cout << num1 % num2 << std::endl;
}
cs

이렇게 코드가 짜여지지 않고


1
2
3
4
5
6
7
8
9
10
try
{
    if(num2 == 0)
    {
        throw num2;
    }
}
catch(int expn) { . . . . . }
std::cout << num1 / num2 << std::endl;
std::cout << num1 % num2 << std::endl;
cs

이렇게 되어 있다면 문제가 된다는 것이다.


try 블록 내에서 예외가 발생하면, 예외가 발생한 지점 이후의 나머지 try 영역은 건너뛴다.


사실 당연한 말이다. 근데 왜 이렇게 꼬아서 설명했는지 모르겠군


참고

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
    int num1, num2;
    std::cin >> num1 >> num2;
 
    try
    {
        if (num2 == 0)
        {
            throw num2;
        }
        std::cout << num1 / num2 << std::endl;
        std::cout << num1 % num2 << std::endl;
    }
    std::cout << "야후~\n";    //Error!
    catch (int expn)
    {
        std::cout << "잘못된 값: " << expn << std::endl;
    }
    std::cout << "끝" << std::endl;
    return 0;
}
cs

에러가 난다.

오류 C2317 줄 '6'에서 시작하는 'try' 블록에 catch 처리기가 없습니다.    - LINE 9

오류 C2318 이 catch 처리기와 관련된 try 블록이 없습니다.    - LINE 19




Stack Unwinding(스택 풀기)


예외의 전달


어떠한 함수 foo의 내부에서 throw절이 실행되었는데, 만약 try ~ catch 없이 실행된다면 어떻게 될까?


이러한 경우 예외처리에 대한 책임은 foo()를 호출한 영역으로 넘어간다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void foo(int num1, int num2)
{
    if (num2 == 0)
    {
        throw num2;
    }
    std::cout << num1 / num2 << std::endl;
    std::cout << num1 % num2 << std::endl;
}
int main()
{
    int num1, num2;
    std::cin >> num1 >> num2;
    try
    {
        foo(num1, num2);
        std::cout << "끝" << std::endl;
    }
    catch (int expn)
    {
        std::cout << "잘못된 값: " << expn << std::endl;
    }
    return 0;
}
cs


이러한 경우에, foo함수 내부에서 예외가 발생해 throw로 num2를 던지는 상황이 온다면, 예외 데이터(num2)는 함수를 호출한 main함수로 전달된다.


또한, 예외처리에 대한 책임 역시 foo를 호출한 main 함수로 넘어가게 된다(실행 중이던 함수를 종료하고, main함수에 프로그램 진행 흐름을 떠넘기겠다는 소리다.)


예외상황이 발생한 위치와 예외상황을 처리해야 하는 위치가 다른 경우


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int StoI(char* str)
{
    int len = strlen(str);
    int num = 0;
    for (int i = 0; i < len; ++i)
    {
        if (str[i] < '0' || str[i] > '9')
        {
            throw str[i];
        }
        num += (int)(pow((double)10, (len - 1- i) * (str[i] + (7 - '7')));
    }
    return num;
}
 
int main()
{
    char str1[100];
    char str2[100];
    while (true)
    {
        std::cin >> str1 >> str2;
        try
        {
            std::cout << str1 << " + " << str2 << " = " << StoI(str1) + StoI(str2) << std::endl;
            break;
        }
        catch (char ch)
        {
            std::cout << "잘못된 문자: " << ch << std::endl;
        }
    }
    return 0;
}
cs


함수 내에서 함수를 호출한 영역으로 예외를 전달하면, 해당 함수는 더 이상 실행되지 않고 종료된다.


스택 풀기


위와 같이 예외가 처리되지 않아 함수를 호출한 영역으로 예외 데이터가 전될되는 현상을 스택 풀기라고 한다.


왜 이러한 이름이 붙게 되었을까


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void firstfoo()
{
    std::cout << "1" << std::endl;
    secondfoo();
}
 
void secondfoo()
{
    std::cout << "2" << std::endl;
    thirdfoo();
}
 
void thirdfoo()
{
    std::cout << "3" << std::endl;
    throw -1;
}
 
int main()
{
    try
    {
        firstfoo();
    }
    catch (int expn)
    {
        std::cout << "예외코드: " << expn << std::endl;
    }
    return 0;
}
cs


16 : firstfoo의 secondfoo의 thirdfoo에서 예외를 던진다. 그러면 쌓여있던 함수 스택을 풀면서 try문이 있는 main함수까지 내려온다.


그렇다면 만약 try문이 없다면 어떻게 될까?


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void thirdfoo()
{
    std::cout << "3" << std::endl;
    throw -1;
}
 
void secondfoo()
{
    std::cout << "2" << std::endl;
    thirdfoo();
}
 
void firstfoo()
{
    std::cout << "1" << std::endl;
    secondfoo();
}
 
 
int main()
{
    std::cout << "시작\n";
    firstfoo();
    std::cout << "끝\n";
    return 0;
}
cs


결과

시작

1

2

3

그리고 에러가 나타난다.


예외가 처리되지 않아서 예외 데이터가 함수를 타고 타고 기본 함수인 main 함수까지 내려왔는데도, try문이 보이지 않으면 terminate 함수(프로그램을 종료시키는 함수)가 호출되면서 프로그램이 종료된다.


따라서 시스템 오류로 인해 발생한 예외가 아니고, 프로그램의 실행이 불가능한 예외가 아니라면 반드시 프로그래머가 예외 상황을 처리해야 한다.


자료형이 일치하지 않아도 예외 데이터는 전달됩니다.


예외 데이터의 자료형과 catch 매개변수는 자료형이 일치해야 한다. 그렇다면 그 둘이 일치하지 않는 경우에 대해 살펴보자.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void thirdfoo()
{
    std::cout << "3" << std::endl;
    int error = -1;
    throw -1;
}
 
void secondfoo()
{
    std::cout << "2" << std::endl;
    try
    {
        thirdfoo();
    }
    catch (char expn)
    {
        std::cout << "나는 char형 예외처리!\n";
    }
}
 
void firstfoo()
{
    std::cout << "1" << std::endl;
    secondfoo();
}
 
int main()
{
    firstfoo();
    return 0;
}
cs

결과

1

2

3

그리고 에러 (abort() has been called!)


자료형의 불일치로 예외는 처리되지 않는다. (자료형이 다른 변수가 매개변수가 일치하는 함수를 찾지 못하는 것 처럼)


하나의 try블록과 다수의 catch 블록


이러한 이유로 try 이후로 등장하는 catch는 여러개가 될 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int StoI(char* str)
{
    int len = strlen(str);
    int num = 0;
    if (len != 0 && str[0== '0')
    {
        throw 0;
    }
 
    for (int i = 0; i < len; ++i)
    {
        if (str[i] < '0' || str[i] > '9')
        {
            throw str[i];
        }
        num += (int)(pow((double)10, (len - 1- i) * (str[i] + (7 - '7')));
    }
    return num;
}
 
int main()
{
    char str1[100];
    char str2[100];
    while (true)
    {
        std::cin >> str1 >> str2;
        try
        {
            std::cout << str1 << " + " << str2 << " = " << StoI(str1) + StoI(str2) << std::endl;
            break;
        }
        catch (char ch)
        {
            std::cout << "잘못된 문자: " << ch << std::endl;
        }
        catch (int expn)
        {
            if (expn == 0)
            {
                std::cout << "0으로 시작하는 숫자는 입력 불가!\n";
            }
            else
            {
                std::cout << "잘못된 입력\n";
            }
        }
    }
    return 0;
}
 
cs


catch가 2개다.


전달되는 예외의 명시


함수를 정의할 때에는 함수 내에서 발생 가능한 예외의 종류를 명시할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int StoI(char* str) throw (intchar)
{
    . . . . .
}
 
int main()
{
    . . . . .
        try
        {
            std::cout << str1 << " + " << str2 << " = " << StoI(str1) + StoI(str2) << std::endl;
            break;
        }
        catch (char ch)
        {
            std::cout << "잘못된 문자: " << ch << std::endl;
        }
        catch (int expn)
        {
            if (expn == 0)
            {
                std::cout << "0으로 시작하는 숫자는 입력 불가!\n";
            }
            else
            {
                std::cout << "잘못된 입력\n";
            }
        }
    . . . . .
    return 0;
}
 
cs


1 : throw (int, char)가 보인다.


하지만 이것은 단순히 명시의 목적으로, 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int StoI(char* str) throw (int)
{
    . . . . .
}
 
int main()
{
    . . . . .
        try
        {
            std::cout << str1 << " + " << str2 << " = " << StoI(str1) + StoI(str2) << std::endl;
            break;
        }
        catch (char ch)
        {
            std::cout << "잘못된 문자: " << ch << std::endl;
        }
        catch (int expn)
        {
            if (expn == 0)
            {
                std::cout << "0으로 시작하는 숫자는 입력 불가!\n";
            }
            else
            {
                std::cout << "잘못된 입력\n";
            }
        }
    . . . . .
}
 
cs


위와 같은 코드를 작성해서 입력으로 잘못된 char를 전달해도 catch (char ch)는 정상적으로 잡아낸다.

(비주얼 스튜디오 C++ 2017 기준이다. 이전 버전에선 어떻게 작동하는지 모른다.)


하지만 이러한 코드를 짜면 혼날 것이다.


중요한 점은, throw의 예외 데이터와 자료형의 일치다. 

만약 다른 자료형이 전달될 경우 throw의 예외는 자신에게 맞는 catch를 찾아 저 멀리 떠나 결국 terminate 함수를 호출하게 될 것이다.


1
2
3
4
int foo() throw ()
{
    . . . . .
}
cs


이는 어떠한 예외도 전달하지 않음을 의미하고, 위의 함수가 예외를 전달할 경우 프로그램은 그냥 종료된다고


책에서는 전하고 있지만, msvc 2017에서는 throw - catch만 잘 매치되어 있다면 잘 동작한다.




덧)


terminate 함수는 이 함수에 존재한다.


1
unexpected();
cs

프로그램을 종료시키는 함수다. 


1
2
3
4
5
6
int main()
{
    unexpected();
    std::cout << "안녕?";
    return 0;
}
cs

결과

에러난다. 안녕?은 출력되지 않는다.


main함수가 프로그램의 가장 밑에서 돌아가는 것은 아니다. int main()에서 return 0의 0을 리턴받는 곳이 가장 밑바닥이다.


catch는 저곳까지 내려가 unexpected를 호출하는 것이다.




예외상황을 표현하는 예외 클래스의 설계


예외 클래스와 예외객체


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class DepositException
{
public:
    DepositException(int money) : reqDep(money)
    { }
    void ShowExceptionReason()
    {
        std::cout << "[예외 메시지: " << reqDep << "는 입금불가]" << std::endl;
    }
private:
    int reqDep;
};
 
. . . . . 
 
class Account
{
 
    . . . . .
 
public:
    void Deposit(int money) throw (DepositException)
    {
        if (money < 0)
        {
            DepositException expn(money);
            throw expn;
        }
 
        . . . . .
 
    }
};
 
int main()
{
    Account myAcc(. . . . .);
    try
    {
        myAcc.Deposit(-300);
    }
    catch (DepositException& expn)
    {
        expn.ShowExceptionReason();
    }
 
    . . . . .
 
    return 0;
}
 
cs


예외 클래스 역시 기본적인 원리는 예외처리와 같다. 하지만 코드가 복잡해보일 여지가 있으니 해당 예외상황을 잘 표현하고, 가능한 만큼 깔끔하게 정의해야 한다.


상속관계에 있는 예외 클래스


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class AccountException
{
public:
    virtual void ShowExceptionReason() = 0;
};
 
class DepositException : public AccountException
{
public:
    DepositException(int money) : reqDep(money)
    { }
    void ShowExceptionReason()
    {
        std::cout << "[예외 메시지: " << reqDep << "는 입금불가]" << std::endl;
    }
private:
    int reqDep;
};
 
class WithdrawException : public AccountException
{
public:
    WithdrawException(int money) : balance(money)
    { }
    void ShowExceptionReason()
    {
        std::cout << "[예외 메시지: 잔액부족, " << balance << " ]" << std::endl;
    }
private:
    int balance;
};
 
class Account
{
 
    . . . . .
 
public:
    void Deposit(int money) throw (AccountException)
    {
        if (money < 0)
        {
            DepositException expn(money);
            throw expn;
        }
 
        . . . . .
 
    }
    void Withdraw(int money) throw (AccountException)
 
    
    . . . . .
 
};
 
int main()
{
    Account myAcc(. . . . .);
    try
    {
        myAcc.Deposit(-300);
    }
    catch (AccountException& expn)
    {
        expn.ShowExceptionReason();
    }
 
    try
    {
        myAcc.Withdraw(50000);
    }
    catch (AccountException& expn)
    {
        expn.ShowExceptionReason();
    }
 
    . . . . .
 
    return 0;
}
cs


상속을 통해 예외 클래스를 묶어 예외의 처리를 단순하게 만들 수 있다.


항상 좋은 것은 아니다. 코드가 커지고 난잡해질 여지가 있지만, 유용한 경우 또한 존재할 것.


예외의 전달방식에 따른 주의사항


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class AAA
{
public:
    void Show() { std::cout << "AAA 예외!" << std::endl; }
};
 
class BBB : public AAA
{
public:
    void Show() { std::cout << "BBB 예외!" << std::endl; }
};
 
class CCC : public BBB
{
public:
    void Show() { std::cout << "CCC 예외!" << std::endl; }
};
 
void ExceptionGenerator(int expn)
{
    if(expn == 1)
        throw AAA();
    else if(expn == 2)
        throw BBB();
    else
        throw CCC();
}
 
int main()
{
    try
    {
        ExceptionGenerator(3);
        ExceptionGenerator(2);
        ExceptionGenerator(1);
    }
    catch(AAA& expn)
    {
        std::cout << "catch AAA" << std::endl;
        expn.Show();
    }
    catch(BBB& expn)
    {
        std::cout << "catch BBB" << std::endl;
        expn.Show();
    }
    catch(CCC& expn)
    {
        std::cout << "catch CCC" << std::endl;
        expn.Show();
    }
    return 0;
}
cs

결과

catch AAA

AAA 예외!


코드의 의도는 아마

catch CCC

CCC 예외!

catch BBB

BBB 예외!

catch AAA

AAA 예외!


를 생각했지 싶은데, 하지만 어림없다.


원인은 상속을 공부했다면 알 수 있는 내용이니 넘어간다.


해결 방법은 catch 순서만 바꿔주면 된다.




예외처리와 관련된 또 다른 특성들


new 연산자에 의해 발생하는 예외


new 연산으로 메모리 할당이 실패하면 std::bad_alloc이라는 예외가 발생한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
    int num = 0;
    try
    {
        while (1)
        {
            std::cout << num++ << std::endl;
            new int[10000][10000];
        }
    }
    catch (std::bad_alloc& bad)
    {
        std::cout << bad.what();
    }
    return 0;
}
cs


이러한 예외는 C++이 자체적으로 정의하고 있는 예외중 하나이다.


모든 예외를 처리하는 catch 블록


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void something()
{
    throw 1;
    throw 'a';
    throw 3.14;
    throw false;
}
 
int main()
{
    int num = 0;
    try
    {
        something();
    }
    catch (...)
    {
        std::cout << "몬가.. 몬가 문제가 있어용\n";
    }
    return 0;
}
cs

결과

몬가.. 몬가 문제가 있어용


catch (...) 는 try 내에서 전달되는 모든 예외가 자료형에 상관없이 걸려든다. 


(...)는 C++이 정한 규칙, 약속이다.


그래서 보통 마지막 catch에서 덧붙여지는 경우가 많다. 

어떠한 전달도, 종류도 구분이 불가능하지만, 예외가 발생했다는 것만 알 수 있다.


예외 던지기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void something()
{
    try
    {
        int error = 1;
    }
    catch (int expn)
    {
        throw expn;
    }
}
 
int main()
{
    int num = 0;
    try
    {
        something();
    }
    catch (int expn)
    {
        std::cout << expn << "받았음\n";
    }
    return 0;
}
cs


요렇게 짜는 것은 마지막 수단이다. 굳이 예외를 다시 던지려고 하지는 말자.



예외처리는 정말 느릴까?


https://yesarang.tistory.com/371


C++창시자인 스트...할아버지는 예외처리를 사용하라고 하고, 구글 C++ 스타일 가이드에서는 C++ 예외를 사용하지 말라고 하지만


알아서 잘 해야겠지


http://blog2928.kc39.net/textyle/13254



std::exception



1
2
3
4
5
6
7
8
try
{
 
}
catch (const std::exception&)
{
 
}
cs


msvc2017 try catch 기본구문이다.


std::exception은 new 연산자에 의해 발생되는 std::bad_alloc의 기본형, C++에서 정의해둔 클래스다.


bad_alloc의 클래스 내부는 이렇게 생겼다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class bad_alloc
    : public exception
{
public:
 
    bad_alloc() noexcept
        : exception("bad allocation"1)
    {
    }
 
private:
 
    friend class bad_array_new_length;
 
    bad_alloc(char const* const _Message) noexcept
        : exception(_Message, 1)
    {
    }
};
cs


2 : public exception이 보이셈??


다음으로는 exception의 내부 코드다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class exception
{
public:
 
    exception() noexcept
        : _Data()
    {
    }
 
    explicit exception(char const* const _Message) noexcept
        : _Data()
    {
        __std_exception_data _InitData = { _Message, true };
        __std_exception_copy(&_InitData, &_Data);
    }
 
    exception(char const* const _Message, int) noexcept
        : _Data()
    {
        _Data._What = _Message;
    }
 
    exception(exception const& _Other) noexcept
        : _Data()
    {
        __std_exception_copy(&_Other._Data, &_Data);
    }
 
    exception& operator=(exception const& _Other) noexcept
    {
        if (this == &_Other)
        {
            return *this;
        }
 
        __std_exception_destroy(&_Data);
        __std_exception_copy(&_Other._Data, &_Data);
        return *this;
    }
 
    virtual ~exception() noexcept
    {
        __std_exception_destroy(&_Data);
    }
 
    virtual char const* what() const
    {
        return _Data._What ? _Data._What : "Unknown exception";
    }
 
private:
 
    __std_exception_data _Data;
};
cs


 exception은 여러 종류의 예외처리 클래스를 갖는 std 클래스다.


예외처리 클래스 종류로는


https://en.cppreference.com/w/cpp/error/exception


이러케 많다.


생각보다 별거 없군.

'C++ > 열혈 C++' 카테고리의 다른 글

C++의 형 변환  (0) 2019.08.19
열혈 C++ / 14  (0) 2019.07.26
열혈 C++ / 13  (0) 2019.07.24
열혈 C++ / 12  (0) 2019.07.24
열혈 C++ / 11  (0) 2019.07.18

+ Recent posts