[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x13강 - 이분탐색'

1. 이분탐색
2. Parametric Search
3. Q&A
4. 마치며

1. 이분탐색

• 이분탐색 : _정렬되어 있는 배열_에서 특정 데이터를 찾기 위해, 모든 데이터를 순차적으로 확인하는 대신, _탐색 범위를 절반_으로 줄여가며 찾는 탐색 방법. O(lg N).

1) 구현

이분탐색을 구현할 때 주의할 점은

1. 주어진 배열은 _정렬_되어 있어야 한다.

2. 무한 루프에 빠지지 않게 _mid값을 결정_해야 한다.

int binarysearch(int target){
    int st = 0, en = n - 1;
    while(st <= en){
        int mid = (st + en) / 2;
        if(a[mid] < target) st = mid + 1;
        else if(a[mid] > target) en = mid - 1;
        else return 1;
    }
    return 0;
}

직접 구현 대신 binary_search(a, a + n, t)로 대체 가능.

int lower_idx(int target, int len){
    int st = 0, en = len;
    while(st < en){
        int mid = (st + en) / 2;
        if(a[mid] >= target) en = mid;
        else st = mid + 1;
    }
    return st;
}

int upper_idx(int target, int len){
    int st = 0, en = len;
    while(st < en){
        int mid = (st + en) / 2;
        if(a[mid] > target) en = mid;
        else st = mid + 1;
    }
    return st;
}

직접 구현 대신 lower_bound, upper_bound로 대체 가능

2. Parametric Search

• Parametric Search : 조건을 만족하는 최소/최대값을 구하는 문제(최적화 문제)를 _결정 문제_로 변환해 이분탐색을 수행하는 방법

문제에서 _최소/최대 얘기_가 있고 _범위가 엄청 크다_거나 _시간복잡도에서 값 하나를 로그_로 떨굴 수 있을 때, 고려할 수 있는 방법.

1. 최적화 문제를 결정 문제로 바꿀 수 있는가?

2. 결정 문제로 얻어낸 함수가 감소 혹은 증가함수인가?

3. Q&A

-

4. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x13강 - 이분탐색'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x12강 - 수학'

1. 소수
2. 최대공약수
3. 연립합동방정식
4. 이항계수
5. Q&A
6. 마치며

1. 소수

• 소수 : 1과 자기 자신으로만 나누어지는 수 : 약수가 2개인 수

• 합성수 : 1과 자기 자신을 제외한 다른 약수를 가지고 있는 수

1) 소수 판정법

(1) 가장 기본적인 방법. O(N)

정의 그대로 1과 자기 자신으로만 나누어지는지, 2부터 N-1까지의 수 중에서 그 수를 나누는 다른 수가 없는지 확인!

다음 코드는, n을 i로 나누어보는 연산이 최대 n-2번이므로, 시간복잡도는 O(N).

bool isprime(int n){
    if(n == 1) return false;
    for(int i = 2; i < n; i++)
        if(n % i == 0) return false;
    return true;
}

(2) 발전된 방법. O(√N)

합성수 N에서 1을 제외한 가장 작은 약수는 √N이하이다.

예를 들어, N = 18일 때, 가장 작은 약수는 1을 제외한 '2'이다. √18 = 4.xxxx이고, 2는 √18이하이다.

Pf) 합성수 N에서 1을 제외한 가장 작은 약수를 x라고 하면, N / x 또한 1이 아닌 N의 약수가 될 것이다. 따라서 x <= (N / x)이다. 위의 식을 정리하면 x^2 <= N이므로, x <= √N이다.

따라서, 1번 방법에서는 2부터 N까지 나누었다면, 2번에서는 2부터 √N까지만 나눈다.

그렇다면 √N은 어떻게 구현을 하나. sqrt함수는 실수의 연산/저장 과정에서 반드시 오차가 발생하므로 사용하면 안된다.

따라서 for문의 조건을, i * i <= n으로 하면 된다.

bool isprime(int n){
    if(n == 1) return false;
    for(int i = 2; i * i <= n; i++)
        if(n % i == 0) return false;
    return true;
}

2) 범위 내의 소수 판정법

(1) 가장 기본적인 방법

2부터 N까지 소수 판별법을 적용.

소수 판별법은 O(√N), 이걸 N개에 대해 적용하므로 시간 복잡도는 O(N√N).

(2) 조금 발전된 방법

1번 방법에서 소수 판별법을 진행할 때, 2 ~ √N 사이의 모든 수를 나눔. 이 때, 모든 수가 아닌, 2 ~ √N 사이의 소수로만 나눔!!

(3) 에라토스테네스의 체. O(NlglgN)

2부터 시작해, 각 소수의 배수들을 지워나가 N까지 탐색하는 방식. (= 합성수를 제외하는 방식)

예를 들어, 2가 소수로 판별되면 2의 배수인 4, 6, 8, ...을 모두 false로 만듦. 다음으로 3이 소수로 판별되면 3의 배수인 6, 9, 12, ...을 모두 false로 만듦. 이 때, 이미 false로 판별된 수는 소수가 아니므로 제외하고 다음 수를 탐색한다.

이 때, 조금 더 발전시키면, 2를 통해, 4, 6, 8, 10, ... 3을 통해, 6, 9, 12, 15, ... 4를 통해, 8, 12, 16, 20, ...이 소수로 판별되었음. 5에서 탐색할 때, 10, 15, 20, 25, ...에서 25의 앞 10, 15, 20은 이미 앞의 과정을 통해 소수로 판별되었음. 이는 이 수들이 5보다 작은 소인수를 가지고 있음을 의미함. 따라서, 5에서 탐색할 때, 5^2 = 25부터 false로 바꿔가면 됨. (이는 5뿐만 아니라, 모든 수에서 적용가능함. 2, 3, 4, ...)

vector<int> sieve(int n){
    vector<int> primes;
    vector<bool> state(n + 1, true);
    state[1] = fasle;
    for(int i = 2; i * i <= n; i++){
        if(!state[i]) continue;
        for(int j = i * i; ij <= n; j += i)
            state[j] = false;
    }
    for(int i = 2; i <= n; i++)
        if(state[i]) primes.push_back(i);
    return primes;
}

참고로 state변수를 vector<bool 자료형임. 왜 bool배열로 하지 않은 이유는, 배열로 잡으면 시간이 꽤 느려짐. bool은 1byte를 차지하는데, 만약 vector<bool>로 두면 한 칸이 1byte가 아닌 1bit만 차지하도록 최적화됨. 덕분에 공간도 8배 적게 쓰고, cache hit rate가 올라가서 시간도 빨라짐.

이런 식의 최적화를 거치게 되면 시간복잡도는 O(NlglgN)인데, 거의 O(N)과 비슷함.

3) 소인수분해(Factorization)

• 소인수분해(Factorization) : 정수를 소수의 곱으로 나타내는 것

(1) 에라토스테네스의 채를 이용

에라토스테네스의 채를 이용해, N이하의 모든 소수를 N으로 나누어보는 방법

(2) 발전된 방법

N을 나누는 수를, 2부터 시작해 1씩 증가시켜, 나누어질 수 없을 때까지 나누는 방법.

(2.1) 방법의 정당성

이 방법이 소인수 목록을 잘 구하는가?

1. 소인수 목록에 적힌 수들을 모두 곱했을 때 N이 되는가?

2. 목록에 있는 수들이 전부 소수인가?

우선 1번은 당연한 것. 이 방법은 N에서 각각의 수를 나누었기 때문.

2번은 만족하는가? 나누는 수를 2에서부터 1씩 증가시키지만, 따로 소수인지 판별하지 않았음.

하지만 결론적으로 말하면 _반드시 다 소수_임!! 만약 소인수목록에 소수가 아닌 수가 있다고 가정을 해보자. 그 수는 소수가 아닌 반드시 _합성수_가 될 것. 합성수는 소수인 약수를 반드시 가짐. 만약 15라는 소인수목록이 있다면, 15는 3과 5라는 소수인 약수를 가짐. 하지만 15까지 가기 이전에 이미 3인 순간에서, N은 더 이상 3으로 나누어질 수 없을 때까지 나누어짐. 따라서 소인수목록으로 3의 배수의 15는 나올 수 없음.

위의 귀류법과 같은 논리로, 만약 소인수목록으로 합성수가 있다면, 그 합성수에는 소인수 p가 있을 것이지만, 이미 그 합성수로 가기 전에 N에는 p가 남아있지 않은 것이므로 모순임.

(2.2) 시간복잡도의 개선

일단, 시간복잡도는 N이 소수라면 중간에 나눠지는 과정 없이 i가 N까지 올라가야 하므로 O(N)의 시간복잡도를 가짐.

하지만 이를 O(√n)으로 만들 수 있음. 소수 판정 알고리즘과 비슷함. N을 i로 나누는 이유는 소인수 i를 빼내기 위함. 그렇다면 i * i가 N보다 커지게 되면 더 이상 나누는 작업을 할 필요가 없음. (이미 N에는 √n이하의 소인수가 없기 때문 = N은 소인수임)

예를 들어, 1100을 소인수분해 한다고 했을 때,

위와 같은 과정을 거친다.

이 때, 밑에서 3번째 과정을 보게 되면, i가 5이고, N은 11이다. i * i = 25 > N = 11을 만족하므로, N은 √N이하의 소인수가 없으므로(N은 소인수이므로), 소인수목록에 N(=11)을 뒤에 추가하면 된다. (3번째 과정의 뒤의 과정은 필요가 없게 된다.)

정리하면, _소수판정과 소수판별은 모두 O(√n)_임. 그리고 1부터 N까지 수 중에서 소수 목록을 구하는 것은 _에라토스테네스의 체_를 쓰면 됨.

2. 최대공약수(Greatest Common Divisor, GCD)

1) 약수

• 약수 : 어떤 수를 나누어떨어지게 하는 수 : 1부터 N까지 for문을 돌면서 다 나눠보면 구할 수 있음. O(N).

하지만 이 역시 마찬가지로 O(√n)에 가능. 18의 약수는 1, 2, 3, 6, 9, 18. 1 * 18, 2 * 9, 3 * 6로 표현 가능한데, 1, 2, 3만 구하면 나머지 약수는 자동으로 구해짐. 곱해서 N이 되는 두 수를 생각하면, 작은 수는 √n이하이므로, √n까지만 반복하면 됨. (단 N이 제곱수일 때, 예를 들어 N이 16일 때는 √16 = 4는 약수에 1번만 포함시켜야 함.)

vector<int> divisor(int n){
    vector<int> div;
    for(int i = 1; i * i <= n; i++)
        if(n % i == 0) div.push_back(i);
    for(int j = (int)div.size() - 1; j >= 0; j--){
        if(div[j] * div[j] == n) continue;
        div.push_back(n / div[j]);
    }
    return div;
}

두번째 for문에서 int로 형변환을 시켜줘야한다. 왜냐하면 size()함수는 unsigned를 반환하는데, 만약 size가 0이라면 0 - 1로 -1이 아닌 (unsigned int의 최댓값 - 1)을 값으로 가짐. (하지만, 이 상황에서 1은 반드시 포함되므로 size - 1을 해도 최소 0이 되므로, overflow가 발생하지만, 이를 int j에 넣을 때 다시 형변환이 일어나 j에 -1이 정상적으로 담김. 하지만 이상적이지는 않은 과정임.)

2) 최대공약수(Greatest Common Divisor, GCD)

• 약수 : 두 자연수의 공통된 약수 중 가장 큰 약수

1) 기본적인 방법

두 수의 약수 목록을 다 찾아서, 정렬을 하거나 또는 초기 상태에서 겹치는 약수를 찾고, 그 중 최댓값을 찾으면 됨.

2) 유클리드 호제법

• 유클리드 호제법 : 두 수 A, B에 대해 A를 B로 나눈 나머지를 r이라고 하면, _GCD(A, B) = GCD(B, r)_이다.

예를 들어, A를 20, B를 12로 하면, A를 B로 나눈 나머지는 8(= 20 % 12). GCD(20, 12) = GCD(12, 8) = GCD(8, 4) = GCD(4, 0)이다. 이 때, 0은 모든 수이 배수이므로, 최대공약수는 4가 된다.

int gcd(int a, int b){
    if(a == 0) return b;
    return gcd(b % a, a);
}

위에서는 재귀를 사용했지만, whlie을 이용해서 구현할 수도 있고, 시간복잡도도 O(log(max(a,b)))라서 굉장히 빠름. 그리고 C++17에서는 gcd함수가 numeric헤더 파일 안에 내장되어 있음.

3) 최소공배수(Least Common Multiple, LCM)

• 최소공배수 : A * B = GCD(A, B) * LCM(A, B)

int lcm(int a, int b){
    return a / gcd(a, b) * b;
}

위에서 overflow 방지를 위해 a를 먼저 gcd로 나누어줌.

3. 연립합동방정식

-

4. 이항계수

1) 기본적인 방법

int n, k; cin >> n >> k;
int ret = 1;
for(int i = 1; i <= n; i++) ret *= i;
for(int i = 1; i <= k; i++) ret /= i;
for(int i = 1; i <= n-k; i++) ret /= i;
cout << ret;

2) 발전된 방법

nCk = n-1Ck + n-1Ck-1

만약 5개 중에서 3개를 뽑는다고 하면 5C3.

1. 내가 찜한 상자 1개 + 나머지 4개 중에서 2개 픽
2. 내가 찜한 상자 0개 + 나머지 4개 중에서 3개 픽

이는 dp로 해결 가능. d[i][j] = iCj라 하면, d[i][j] = d[i-1][j-1] + d[i-1][j]로 표현 가능.

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

int comb[1002][1002];
int mod = 10007;

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

    for(int i = 1; i <= 1000; i++){
        comb[i][0] = comb[i][i] = 1;
        for(int j = 1; j < i; j++)
            comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % mod;
    }
    int n, m; cin >> n >> m;
    cout << comb[n][m];
}

5. Q&A

-

6. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x12강 - 수학'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x11강 - 그리디' : 'Jinhan's Note' 중 'Theme 10. 그리디 - (1)'

1. 그리디 알고리즘
2. Q&A
3. 마치며

1. 그리디(Greedy) 알고리즘

• 그리디(Greedy) 알고리즘 : 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 : 관찰을 통해 탐색 범위를 줄이는 알고리즘

1) 그리디 알고리즘을 푸는 과정

(1) 관찰을 통해 탐색 범위를 줄이는 방법을 고안

직관적으로 보이는 풀이의 시간복잡도로, 문제에서 제시한 시간 제한 안에 들어올 수 없을 때, 시간복잡도를 더 낮출 수 있는 방법을 관찰함.

(2) 탐색 범위를 줄여도 올바른 결과를 낼 수 있음을 수학적으로 증명

(3) 구현 후 해결!

하지만, 실제 코테에서는 시간이 촉박하므로, 수학적으로 꼼꼼히 증명하기가 힘듦. 따라서, 방법을 고안하고 대충 주어진 예제에서 잘 돌아가는지 확인 후 구현함.

이런 과정에서 절망적인 풀이 흐름은, 1번에서 잘못된 방법을 고안하고, 2번에서 잘못되었음을 증명하지 못하고, 3번에서 계속 틀리는 경우임. (잘못된 방법이라서 틀린건지, 구현이 잘못되었는지 알 수 없음.)

2) 코테 추천 전략

따라서 코테 추천 전략은!

(1) 거의 똑같은 문제를 풀었거나, 정말 간단한 문제여서, 풀이를 100% 확신할 때

답을 제출해 보고, 틀리면 빨리 손절!!!

(2) 100% 확신은 없지만, 맞는 것 같은 그리디 풀이를 찾았을 때

일단은 넘어가고, 다른 문제를 풀게 없거나 종료가 20 ~ 40분 정도 남은 시점에 코딩 시작!!!

2. Q&A

-

3. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x11강 - 그리디' : 'Jinhan's Note' 중 'Theme 10. 그리디 - (1)'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x10강 - 다이나믹 프로그래밍' : 'Jinhan's Note' 중 'Theme 06. 다이나믹 프로그래밍 - 기초'

1. 다이나믹 프로그래밍
2. Q&A
3. 마치며

1. 다이나믹 프로그래밍(Dynamic Programming, DP)

• 다이나믹 프로그래밍(Dynamic Programming, DP) : 여러 개의 하위 문제를 먼저 푼 후, 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

예를 들어, 피보나치 수열의 경우

1. 재귀적으로 해결
2. DP로 해결

하는 방법이 있음.

// 1. 재귀적으로 해결
if(n <= 1) return 1;
return fibo(n-1) + fibo(n-2);

// 2. DP로 해결
f[0] = f[1] = 1;
for(int i = 2; i <= n; i++)
    f[i] = f[i-1] + f[i-2];
return f[n];

1번 방법은 O(1.618^N)의 시간복잡도를 가짐 반면 2번 방법은 O(N)의 시간복잡도를 가지므로 꽤나 극단적인 차이가 발생.

1) DP를 푸는 과정

DP 문제는 어렵게 하고자 하면 끝도 없이 어려워지지만, 코테 수준에서는 다음 3가지 과정만 지키면 크게 어렵지 않음.

(1) 테이블 정의하기

특별한 방법이 있는 것이 아닌, 경험적으로 익힘.

(2) 점화식 찾기

(3) 초기값 정하기

2. Q&A

-

3. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x10강 - 다이나믹 프로그래밍' : 'Jinhan's Note' 중 'Theme 06. 다이나믹 프로그래밍 - 기초'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x0E강 - 정렬 I' : 'Jinhan's Note' 중 'Theme 03. STL 알고리즘 _ sort'

1. 기본 정렬
2. 병합 정렬(Merge Sort)
3. 퀵 정렬(Quick Sort)
4. Counting Sort
5. Radix Sort
6. STL Sort
7. Q&A
8. 마치며

1. 기본 정렬

1) 선택 정렬(O(N²))

아이디어 / 구현이 가장 기초적인 정렬

원소 중 최댓값을 제일 앞 / 뒤로 순차적으로 이동시키는 정렬

int arr[5] = {3, 2, 7, 116, 62};
int n = 5;
for(int i = n - 1; i > 0; i--){
    int mxidx = 0;
    for(int j = 1; j <= i; j++){
        if(arr[mxidx] < arr[j]) mxidx = j;
    }
    swap(arr[mxidx], arr[i]);
}

int arr[5] = {3, 2, 7, 116, 62};
int n = 5;
for(int i = n - 1; i > 0; i--){
    swap(*max_element(arr, arr + i + 1), arr[i]);
}

2) 버블 정렬(O(N²))

구현이 가장 편한 정렬

앞에서부터 인접한 두 원소를 보면서, 앞의 원소가 더 클 때 자리를 바꾸는 정렬

int arr[5] = {-2, 2, 4, 6, 13};
int n = 5;
for(int i = 0; i < n; i++){
    for(int j = 0; j < n - 1 - i; j++){
        if(arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
    }
}

3) 삽입 정렬(O(N²))

2. 병합 정렬(Merge Sort) (O(NlgN))

(N이 10만정도일 때, O(N²)은 10초 ~ 1분, O(NlgN)은 겁나 빠름. N이 커지면 커질수록 격차는 더 커짐)

• 병합 정렬(Merge Sort) : 재귀적으로 수열을 나눠 정렬한 후 합치는 정렬

int idx1 = 0, idx2 = 0;
for(int i = 0; i < n + m; i++){
    if(idx1 >= n){c[i] = b[idx2++]; continue;}
    if(idx2 >= m){c[i] = a[idx1++]; continue;}

    if(a[idx1] > b[idx2]) c[i] = b[idx2++];
    else c[i] = a[idx1++];
}

병합 정렬의 단계는 3단계로 나눌 수 있음.

1. 주어진 리스트를 2개로 나눈다. O(N)
2. 나눈 리스트 2개를 정렬한다.
3. 정렬된 2개의 리스트를 합친다. O(Nk) = O(NlgN)

1) Stable Sort

만약 다음을 정렬한다고 해보자

20, 10(빨), 10(파), 10(초)

1. 10(빨) 10(파) 10(초) 20
2. 10(파) 10(빨) 10(초) 20
3. 10(초) 10(빨) 10(파) 20

위의 예시에서, 우선 순위가 같은 원소가 여러 개가 있음. 이 때, 우선 순위가 같은 원소들은 원래의 순서를 따라가게 하는 성질이 Stable Sort.

즉, 10(빨) 10(파) 10(초) 20이면, Stable Sort 성질을 가짐. 나머지 정렬은 Unstable Sort.

따라서, Merge Sort에서 Stable Sort를 만족시키려면, 앞의 리스트와 뒤의 리스트의 우선 순위가 같을 때, 앞의 리스트의 원소를 먼저 보내줘야 함.

3) 퀵 정렬(Quick Sort) (O(NlgN) ~ O(N²))

이름에서 알 수 있듯이, 거의 대부분의 정렬 알고리즘보다 빨라서 각종 라이브러리에서는 퀵 정렬을 바탕으로 만들어짐

하지만, 코테에서 STL을 못 쓴다면, 퀵 정렬이 아닌 반드시 Merge Sort를 사용해야 함. (만약, 힙을 알고 있다면 Heap Sort, 아니면 다른 O(NlgN) 정렬 사용)

• 퀵 정렬(Quick Sort) : pivot을 기준으로 왼쪽에는 pivot보다 작은 수, 오른쪽에는 pivot보다 큰 수가 오게끔 재귀적으로 정렬

int arr[8] = {6, -8, 1, 12, 8, 3, 7, -7};
int tmp[8];
int tidx = 0;
int pivot = arr[0];
for(int i = 1; i < 8; i++)
    if(arr[i] <= pivot) tmp[tidx++] = arr[i];
tmp[tidx++] = pivot;
for(int i = 1; i < 8; i++)
    if(arr[i] > pivot) tmp[tidx++] = arr[i];
for(int i = 0; i < 8; i++) arr[i] = tmp[i];

단, 위의 방식대로 코드를 작성하면 tmp라는 추가적인 공간이 필요함. 퀵 소트는 추가적인 공간을 사용하지 않고, pivot을 제자리에 보낼 방법을 고안해야함. (이렇게 추가적인 공간을 사용하지 않는 정렬을 'In-Place Sort'라고 함)

int arr[8] = {6, -8, 1, 12, 8, 3, 7, -7};
int pivot = arr[0];
int l = 1, r = 7;
while(1){
    while(l <= r && arr[l] <= pivot) l++;
    while(l <= r && arr[r] > pivot) r--;
    if(l > r) break;
    swap(arr[l], arr[r]);
}
swap(arr[0], arr[r]);

4. Counting Sort

• Counting Sort : 수열에서 등장한, 원소의 개수를 세어, 원소의 개수만큼 나열한 정렬

1 5 4 2 3 1 4 3 1 : 2번 2 : 1번 3 : 2번 4 : 2번 5 : 1번 -> 1 1 2 3 3 4 4 5

정말 쉬운 정렬이지만, 명확한 단점이 있음.

만약, 원소가 999,999,999라면 크기가 10억인 배열이 필요함.

이론적으로는 수의 범위가 0 ~ 1억까지라도 사용가능하지만, 실제적으로는 1000만 이하일 때에는 COunting Sort를 사용함.

5. Radix Sort

• Radix Sort 수열에서 등장한, 원소의 자리수를 세어, 원소의 자리수를 기준으로 정렬

012 421 046 674 103 502 007 100 021 545

각 수의 1의 자리를 기준으로 0 ~ 9의 리스트에 구분하여 넣습니다.

0 : 100 1 : 421 021 2 : 012 502 3 : 103 4 : 674 5 : 545 6 : 046 7 : 007 8 : 9 : -> 100 421 021 012 502 103 674 545 046 007

이후에는 0번 리스트부터 수를 보면서, 수열을 재배치함.

0 : 100 1 : 421 021 2 : 502 012 3 : 103 4 : 674 5 : 545 6 : 046 7 : 007 8 : 9 : -> 100 421 021 502 012 103 674 545 046 007

이후에는, 10의 자리를 기준으로 넣고 재배치.

0 : 100 502 103 007 1 : 012 2 : 421 021 3 : 4 : 545 046 5 : 6 : 7 : 674 8 : 9 : -> 100 502 103 007 012 421 021 545 046 674

마지막으로 100의 자리도 마찬가지.

0 : 007 012 021 046 1 : 100 103 2 : 3 : 4 : 421 5 : 502 545 6 : 674 7 : 8 : 9 : -> 007 012 021 046 100 103 421 502 545 674

1) Comparison Vs Non-Comparision

(1) Comparision Sort

Merge, Quick, Bubble Sort같이 원소들끼리 크기를 비교하는 정렬

(2) Non-Comparision Sort

Counting, Radix Sort같이 원소들끼리 크기를 비교하지 않는 정렬

6. STL sort

STL sort는 기본적으로 퀵 소트를 기반으로 하지만, 리스트가 불균등하게 나눠져 재귀의 깊이가 너무 깊어지면 O(NlgN)이 보장되는 정렬 알고리즘으로 나머지 처리.

STL sort는 Stable Sort가 아니기 때문에, Stable Sort가 필요하다면 stable_sort함수를 사용!(사용법 동일)

pair, tuple은 제일 앞의 원소의 대소를 비교하고, 만약 같다면 다음 원소의 대소를 비교함. pair1 : {2, 5}, pair2{3, -2} -> pair1 < pair2 tuple1 : {2, 1, 0}, tuple2{2, -2, 6} -> tuple1 > tuple2 따라서, 좌표를 정렬하거나 기타 속성이 있는 원소를 정렬할 때, 구조체보다는 pair나 tuple이 용이함.

1) 사용법

1. sort(시작, 끝) 2. sort(시작, 끝, 비교 함수)

2번에서 보듯이, 비교 함수를 사용자가 지정할 수 있음.

만약 배열을 정렬하고자 한다면 다음과 같이 하고

int a[5]  = {1, 4, 5, 2, 7};
sort(a, a+5);

주어진 배열에서, 5로 나눈 나머지 순으로, 나머지가 같다면 크기 순으로 정렬하고자 한다면

bool Cmp(int a, int b){
    if(a % 5 != b % 5) return a % 5 < b % 5;
    return a < b;
}

int a[5]  = {1, 4, 5, 2, 7};
sort(a, a+5);

2) 비교 함수의 주의 사항

(1) 두 값이 같거나 우선 순위가 같을 때, false를 반환

이 때, 비교함수에서는, a가 b의 앞에 와야할 때만 true를 반환해야하니, _두 값이 같거나 우선 순위가 같다면 반드시 false를 반환_해야 함.

-> 런타임에러를 발생시키기도 함.

(2) 인자로, STL 혹은 클래스 객체 전달시 reference를 사용

만약 reference로 전달하지 않으면, 값의 복사가 일어나게 되는데 불필요함. 그냥 reference로 전달하면 복사 과정이 일어나지 않음.

따라서 bool cmp(string a, string b)보다는 bool cmp(const string& a, const string& b)가 바람직함.

-> 수행 시간에서 약간의 차이는 있을 수 있겠지만, 에러는 발생하지 않음

따라서, 두 값이 같을 때는 반드시 false를 반환하자!!

7. Q&A

-

8. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x0E강 - 정렬 I' : 'Jinhan's Note' 중 'Theme 03. STL 알고리즘 _ sort'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x0D강 - 시뮬레이션' : 'Jinhan's Note' 중 'Theme 08. 구현 + 시뮬레이션'

1. 시뮬레이션
2. Q&A
3. 마치며

1. 시뮬레이션

이 유형은, BFS나 재귀와 같은 특정 자료구조, 알고리즘에 종속되어 있지 않고, 주어진 문제 상황을 구현하면 되지만, 이 때 구현이 빡세게 필요한 유형의 문제.

따라서, 배경 지식보다는, 구현력이 많이 필요함.

1) 연습문제 1 : BOJ15683(감시)

(1) 내 풀이

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int n, m;
int board[10][10]; // 원본 배열
vector<pair<int,int>> V; // cctv 장소를 담는 큐
int mn = 100;

void Up(int cur_x, int cur_y){ // ↑
    for(int i = cur_x - 1; i >= 0; i--){
        if(board[i][cur_y] == 6) return;
        if(board[i][cur_y] == 0) board[i][cur_y] = 7;
    }
}
void Down(int cur_x, int cur_y){ // ↓
    for(int i = cur_x + 1; i < n; i++){
        if(board[i][cur_y] == 6) return;
        if(board[i][cur_y] == 0) board[i][cur_y] = 7;
    }
}
void Left(int cur_x, int cur_y){ // ←
    for(int i = cur_y - 1; i >= 0; i--){
        if(board[cur_x][i] == 6) break;
        if(board[cur_x][i] == 0) board[cur_x][i] = 7;
    }
}
void Right(int cur_x, int cur_y){ // →
    for(int i = cur_y + 1; i < m; i++){
        if(board[cur_x][i] == 6) break;
        else if(board[cur_x][i] == 0) board[cur_x][i] = 7;
    }
}

void Solve(int k){
    if(k == V.size()){
        int cnt = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(board[i][j] == 0) cnt++;
        mn = min(mn, cnt);
        return;
    }

    int cur_x = V[k].first, cur_y = V[k].second;
    int temp[10][10];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) 
            temp[i][j] = board[i][j];

    if(board[cur_x][cur_y] == 1){
        for(int dir = 0; dir < 4; dir++){
            if(dir == 0) Up(cur_x, cur_y);
            else if(dir == 1) Down(cur_x, cur_y);
            else if(dir == 2) Left(cur_x, cur_y);
            else Right(cur_x, cur_y);
            Solve(k + 1);
            for(int i = 0; i < n; i++)
                for(int j = 0; j < m; j++)
                    board[i][j] = temp[i][j];
        }
    }
    else if(board[cur_x][cur_y] == 2){
        for(int dir = 0; dir < 2; dir++){
            if(dir == 0){
                Up(cur_x, cur_y);
                Down(cur_x, cur_y);
            }
            else{
                Left(cur_x, cur_y);
                Right(cur_x, cur_y);
            }
            Solve(k + 1);
            for(int i = 0; i < n; i++)
                for(int j = 0; j < m; j++)
                    board[i][j] = temp[i][j];
        }
    }
    else if(board[cur_x][cur_y] == 3){
        for(int dir = 0; dir < 4; dir++){
            if(dir == 0){
                Left(cur_x, cur_y);
                Up(cur_x, cur_y);
            }
            else if(dir == 1){
                Up(cur_x, cur_y);
                Right(cur_x, cur_y);
            }
            else if(dir == 2){
                Right(cur_x, cur_y);
                Down(cur_x, cur_y);
            }
            else{
                Down(cur_x, cur_y);
                Left(cur_x, cur_y);
            }
            Solve(k + 1);
            for(int i = 0; i < n; i++)
                for(int j = 0; j < m; j++)
                    board[i][j] = temp[i][j];
        }
    }
    else if(board[cur_x][cur_y] == 4){
        for(int dir = 0; dir < 4; dir++){
            if(dir == 0){
                Up(cur_x, cur_y);
                Down(cur_x, cur_y);
                Left(cur_x, cur_y);
            }
            else if(dir == 1){
                Up(cur_x, cur_y);
                Down(cur_x, cur_y);
                Right(cur_x, cur_y);
            }
            else if(dir == 2){
                Left(cur_x, cur_y);
                Right(cur_x, cur_y);
                Up(cur_x, cur_y);
            }
            else{
                Left(cur_x, cur_y);
                Right(cur_x, cur_y);
                Down(cur_x, cur_y);
            }
            Solve(k + 1);
            for(int i = 0; i < n; i++)
                for(int j = 0; j < m; j++)
                    board[i][j] = temp[i][j];
        }
    }
    else if(board[cur_x][cur_y] == 5){
        Up(cur_x, cur_y);
        Down(cur_x, cur_y);
        Left(cur_x, cur_y);
        Right(cur_x, cur_y);
        Solve(k + 1);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                board[i][j] = temp[i][j];
    }
}

int main(){
    fastio;

    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> board[i][j];
            if(board[i][j] > 0 && board[i][j] < 6)
                V.push_back({i,j});
        }
    }
    Solve(0);
    cout << mn << '\n';
}

1. 입력을 받을 때, CCTV의 경우 V벡터에 좌표 저장

2. 백트래킹으로 해결 : CCTV를 만날 때 마다, 각각의 CCTV 경로를 탐색 : 이 때, 한 경로를 끝내면 이전 상태로 board를 초기화 해야함. 그래서 이전 상태를 temp에 저장하고, 경로 탐색을 마치면 board에 이전 상태가 저장된 temp를 복사해주었다. : 각각의 탐색이 끝나면 cnt에 사각지대를 저장하고, 최솟값을 구해주었다.

3. CCTV의 경로는 Up, Down, Left, Right 함수로 구현 (처음에는 Solve함수에 일일이 다 구현해서 코드가 300줄 가까이 되었다. 이를 함수로 구현)

(2) 바킹독님의 풀이

(바킹독님의 코드 - 바킹독님의 깃헙)

1. 변수들이 가질 수 있는 값이 여러개이고
2. 모든 조합을 다 확인하고 싶은데
3. 변수들끼리는 서로 독립적일 때
4. 백트래킹보다 나은 방법은?

-> 진법을 이용

각각의 CCTV는 1 / 2 / 4가지의 방법이 있음.

따라서, 가능한 방향의 종류가 최대 4개이므로,** 4진법에 대응**시킬 것.

이 때, 지수를 표현해주어야 함.

1. ^연산자? -> C에서는 XOR 비트연산이므로 사용 X

2. pow 함수 -> 인자로 실수를 받고, return도 실수이므로 바람직하지 않음. (double의 유효숫자는 15, long long은 19자리이므로, 정수의 정수 승에서 오차 발생할 수 있음)

3. for문 중첩 사용 -> 4중 for문 사용하면 됨.

4. Left Shift 사용

-> 1 << (2 * cctv.size()) == 4^(cctv.size()) -> 밑이 1이면, Left Shift한 만큼 2의 제곱수가 됨. --> 1(2) == 1(10) -> 100(2) == 4(10)

(2.1) 4진법으로 변환 후, 자리수 얻기

만약, 1번 CCTV가 3개일 경우, 경우의 수는 64(4 * 4 * 4). 0 ~ 63을 4진법으로 나타내면, 000 001 ~ 332 333. 그리고 각각의 자리수를 방향 3개에 대응시킴. 예를 들어, 39(10) = 213(4)이므로, 방향을 (2,1,3)으로 둘 수 있음. 이렇게 하면 64가지의 조합을 모두 확인할 수 있음.

그렇다면 10진법을 4진법으로 바꾸고 각 자리수를 얻어야 함.

• 10진법에서 각 자리수 얻기

1. 마지막 자리수 : 10으로 나눈 나머지
2. 나머지 자리수 : 10으로 나눈 후, 10으로 나눈 나머지

-> 4진법도 마찬가지로, 10대신 4를 사용하면 됨.

따라서, CCTV의 개수가 k개 일 때는, 0 ~ 4^k - 1까지에 대해 자리수를 얻으면 됨.

(2.2) 사각지대의 개수 세기

CCTV가 감시할 수 있는 칸마다 7이라는 수로 마킹해 둠. 이 후에 0인 칸만 세면 됨.

이건 나랑 아이디어는 똑같은데 코드가 살짝다름.

나는 if문을 사용했고

for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        if(board[i][j] == 0) cnt++;

바킹독님은 비교 연산자를 사용함.

for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        val += (board2[i][j] == 0);

사실 결과는 똑같지만 이런 방법도 있구나...

(2.3) 시간복잡도 계산

1. board2에 board1을 복사할 때 NM(최대 64칸)

2. upd함수의 호출 횟수 : 5번 CCTV가 8개일 때, 4 * 8

3. upd함수의 연산량 : 최대 8번

4. 빈 칸 확인 : NM(최대 64칸)

5. 방향의 개수 : 4^8

-> (64 + 488 + 64) * 4^8 = 25,165,824

약 2500만이므로 1초 안에 넉넉히 통과.

만약 계산결과가 5억 정도로 1초가 간당간당하다면, cctv가 2번 일 때, dir = 2, 3이라면 continue하고, cctv가 5번 일 때, dir != 0이면 continue하고, upd함수에서 7로 바꿀 때 cnt를 증가시켜, 빈칸을 확인하는 연산량을 줄이던가 해야함.

2) 연습문제 2 : BOJ18808(스티커 붙이기)

이 문제를 푸는 데 있어 핵심은 "도형의 회전"이었다.

이 회전을 구현 못해서 다른 블로그를 참고했다.

(1) 바킹독님의 풀이

(바킹독님의 코드 - 바킹독님의 깃헙)

(1.1) 스티커를 특정 영역에 붙일 수 있는지 확인하고 붙이기

노트북의 (x,y)에 스티커의 (0,0)을 기준으로 붙이기. 노트북에 올라가는 스티커의 모든 칸이 겹치는 칸이 있는지 확인하고 노트북에 값 갱신하기.

(1.2) 스티커 회전하기

B[x][y] = A[n - 1 - y][x] 여기서 n은 원래 배열(A)의 행의 개수.

그리고 행과 열이 바뀌기 때문에 swap(r,c)를 빼먹으면 안됨.

(1.3) 시간복잡도 계산

1. 노트북에 놓을 수 있는지 확인하는 위치의 개수 : 4 * 40 * 40 : 4개의 회전 방향과, 최대 칸의 개수 : 40 * 40

2. 모눈종이를 특정 위치에 놓을 수 있는지 확인하는 연산 : 10 * 10

3. 스티커의 개수 : 최대 100개

-> 4 * 40 * 40 * 10 * 10 = 64,000,000

6400만이므로 2초 안에 넉넉히 통과. (위의 경우는 최악의 경우를 계산한 것이므로, 일반적으로는 훨씬 더 빠르게 가능)

3) 연습문제 3 : BOJ12100(2048(Easy))

하... 이거 너무 어려워...

(1) 바킹독님의 풀이

(1.1) 게임판을 상하좌우로 기울이기

사실 난 처음에 숫자들을 각 방향으로 이동시키려고 했다. 그런데 풀이를 보니 한 방향으로 이동만 구현하고, 보드판 전체를 회전시켜 각 방향으로의 이동"처럼" 구현했다. (이런 걸 어떻게 생각할까....)

if(board2[i][j] == 0) continue;

if(temp[idx] == 0) temp[idx] = board2[i][j];
else if(temp[idx] == board2[i][j]) temp[idx++] *= 2;
else temp[++idx] = board2[i][j];

우선 보드의 값이 0이면 패스. 만약 값을 이동시킬 배열이 비어있으면, 값을 넣음. 만약 배열에 같은 값이 있고, 더한 적이 없으면, 값을 2배로 증가. 만약 다른 값이 있거나, 이전에 더한적이 있으면 새로운 인덱스에 추가

보드를 90도씩 회전하는 것은 앞선 문제와 동일.

(1.2) 5번 기울이는 방향 정하기

문제에서 최대 5번만 이동한다고 했으므로, 5번 각각의 경우에 어떻게 기울일지 정해야 함.

그렇다면 5번 각각의 경우마다 4번(상하좌우)로 기울일 수 있기 때문에 경우의 수는 4^5 == 1024.

즉, 1024개의 경우를 탐색해줘야 한다. tmp변수에 각 경우의 수를 저장하고, brute 변수에 진법을 이용해 표시한다.

for(int tmp = 0; tmp < 1024; tmp++){
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                board2[i][j] = board1[i][j];

        int brute = tmp;
        for(int i = 0; i < 5; i++){
            int dir = brute % 4;
            brute /= 4;
            Move(dir);
        }
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                mx = max(mx, board2[i][j]);
    }

(1.3) 시간복잡도 계산

1. 기울임 처리를 위한 연산 횟수 : 20 * 20 : 행과 열의 최대 길이가 20씩임.

2. 각각의 경우마다 기울이는 횟수는 5번

3. 모든 경우의 수는 1024개

-> (20 * 20 * 5) * 1024 = 2,048,000

3) 연습문제 4 : BOJ15686(치킨 배달)

사실 이 문제가 가장 쉬웠고, 바킹독님의 풀이와 거의 똑같았다. 그래서 내가 풀었던 방법대로 기술함. (엉엉 너무 좋아)

(1) 풀이

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#define X first
#define Y second
int n, m;
int city[51][51];  // 입력받을 원본 배열
vector<pair<int,int>> house; // 집의 좌표
vector<pair<int,int>> chicken; // 원본 치킨집 좌표

int main(){
    fastio;

    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){ 
            cin >> city[i][j];
            if(city[i][j] == 1) house.push_back({i,j});
            if(city[i][j] == 2) chicken.push_back({i,j});
        }
    }

    // 서로 다른 치킨집 개수(chicken1.size()) 중 m개를 골라 살아남김
    vector<int> v;
    for(int i = 0; i < chicken.size(); i++) v.push_back(i < m ? 0 : 1);

    int ans = INT_MAX;
    do{
        // 폐업이 안된 치킨집 좌표
        vector<pair<int,int>> alive;
        for(int i = 0; i < v.size(); i++)
            if(v[i] == 0)
                alive.push_back({chicken[i].X, chicken[i].Y});

        int sum_mn = 0;
        for(auto h : house){
            int dist_mn = 100;
            for(auto a : alive){
                int dist = abs(h.X - a.X) + abs(h.Y - a.Y);
                dist_mn = min(dist_mn, dist);
            }
            sum_mn += dist_mn;
        }
        ans = min(ans, sum_mn);
    }while(next_permutation(v.begin(), v.end()));

    cout << ans << '\n';
}

(1.1) 폐업시키지 않을 치킨집 M개 고르기

사실 이 부분이 핵심이었다. 각각의 경우마다 다 계산해주어야 하나? 백트래킹? 진법을 활용한 경우의 수 계산?

사실 이럴바엔 치킨집 N개 중에서 M개를 고르기만 하면 된다. -> 조합!!

백트래킹을 통한 조합의 구현보다는, next_permutation을 통한 구현이 훨씬 간단하기 때문에, 이를 통해 구현했다.

v라는 벡터를 이용해 조합을 구현했다.

vector<int> v;
for(int i = 0; i < chicken.size(); i++) v.push_back(i < m ? 0 : 1);

do{
    ...
}while(next_permutation(v.begin(), v.end()));

(1.2) 도시의 치킨 거리 구하기

나같은 경우는, 맨 처음에 입력을 받을 때, 집의 좌표와, 치킨집의 좌표를 각각의 벡터에 저장했다.

그렇게 해야, 치킨 거리를 구할 때, 집의 좌표나 치킨집의 좌표를 구하려고 전체 배열을 순회하는 것을 피할 수 있기 때문 (만약 전체 배열을 순회해야 한다면, 집의 좌표를 구하기 위해 O(N²), 각 집마다 최소 치킨 거리를 구하기 위해 또 치킨집을 찾아야하므로 전체 배열을 다시 순회해야한다 O(N²). 그러면 O(N⁴)이 된다...) (따라서, 각 경우를 벡터에 저장해주면, 집을 찾기 위해 전체 배열을 순회하지 않아도 된다. 집을 저장한 벡터만 순회하면 되므로 최대 O(N). 각각의 집마다 최소 치킨 거리를 찾아야 하므로, 치킨집이 저장된 벡터를 순회하면 되므로 O(N). 즉, O(N²)이 된다.)

for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){ 
        cin >> city[i][j];
        if(city[i][j] == 1) house.push_back({i,j});
        if(city[i][j] == 2) chicken.push_back({i,j});
    }
}

이후에, 폐업되지 않은 치킨집을 저장할 벡터를 선언해, 폐업되지 않은 치킨집의 좌표를 벡터에 저장한다. 그리고 이 벡터와 집이 저장된 벡터를 이용해 최소 거리를 구한다.

int ans = INT_MAX;
do{
    // 폐업이 안된 치킨집 좌표
    vector<pair<int,int>> alive;
    for(int i = 0; i < v.size(); i++)
        if(v[i] == 0)
            alive.push_back({chicken[i].X, chicken[i].Y});

    int sum_mn = 0;
    for(auto h : house){
        int dist_mn = 100;
        for(auto a : alive){
            int dist = abs(h.X - a.X) + abs(h.Y - a.Y);
            dist_mn = min(dist_mn, dist);
        }
        sum_mn += dist_mn;
    }
    ans = min(ans, sum_mn);
}while(next_permutation(v.begin(), v.end()));

(1.3) 시간 복잡도 계산

1. 각 집에 대해 모든 치킨집과의 거리를 다 계산해야 함 : 100 * 13
2. 폐업시키지 않을 치킨집을 뽑는 "최대" 경우의 수 : ₁₃C₆ : 조합에서 가장 큰 값을 가지려면, 뽑을 개수가 전체 개수의 절반에 최대한 가까워야 함.(따라서 6 또는 7일 때 최대)

-> 100 * 13 * ₁₃C₆ = 2,230,800

2. Q&A

-

3. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x0D강 - 시뮬레이션' : 'Jinhan's Note' 중 'Theme 08. 구현 + 시뮬레이션'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x0C강 - 백트래킹' : 'Jinhan's Note' 중 'Theme 07. 백트래킹(Backtracking)'

1. 백트랙킹(Backtracking)
2. STL next_permutation
3. Q&A
4. 마치며

1. 백트랙킹(Backtracking)

• 백트랙킹(Backtracking) : 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

(예제는, '바킹독님 블로그' 참조)

1) 가지 치기(pruning)

재귀 호출을 트리 구조로 생각했을 때, 가지치기는 트리 edge를 끊어서 해당 subtree는 탐색하지 않는 것을 의미.

1. naive한 재귀 풀이를 생각

2. 현재 상태에서 정답을 갱신할 수 있는지 확인하는 로직

3. 가지치기를 적용해 더 효율적으로 해결

2. STL next_permutation

int a[3] = {1, 2, 3};
do{
    for(int i = 0; i < 3; i++)
        cout << a[i];
    cout << '\n';
}while(next_permutation(a, a+3));
/*
123
132
213
231
312
321
*/

next_permutation은 현재의 수열을 사전 순으로 생각했을 때의, 다음 수열을 만들고 true를 반환하는 함수.

만약 다음 수열이 존재하지 않으면 false를 반환.

따라서 do-while문을 이용하면 코드가 깔끔해짐.

조합을 구할 때는, 원래의 수열에서 0과 1을 이용하면 구할 수 있음 위의 예시에서, 3개 중 2개를 뽑는다고 하면 배열 a를 {0,1,1}처럼 두면 됨.

3. Q&A

-

4. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x0C강 - 백트래킹' : 'Jinhan's Note' 중 'Theme 07. 백트래킹(Backtracking)'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x0B강 - 재귀' : 'Jinhan's Note' 중 'Theme 05. 재귀 / 분할정복(DnC)'

1. 재귀
2. Q&A
3. 마치며

1. 재귀(Recursion)

• 재귀(Recursion) : 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

예를 들어, 다음은 1부터 n까지 출력하는 함수, 1부터 n까지의 합을 구하는 함수입니다.

void func1(int n){
    if(n == 0) return;
    cout << n << ' ';
    func1(n-1);
}

int func2(int n){
    if(n == 0) return 0;
    return n + func2(n-1);
}

1) 수학적 귀납법

예를 들어 도미노를 쓰러뜨릴 때, 왜 모든 도미노가 쓰러지는지 설명해야 함

1. 1번 도미노가 쓰러지면 2번도 쓰러짐 -> 2번이 쓰러지면 3번도 쓰러짐 -> ...

2. 수학적 귀납법 1번 도미노가 쓰러짐 -> k번 도미노가 쓰러지면 k+1번 도미노도 쓰러짐이 True! -> 따라서 모든 도미노가 쓰러짐.

앞으로는 1번 방식이 아닌, 2번 방식으로 바로 사고할 수 있도록 해야 함. (이전까지의 절차지향적 사고를 탈피해야 함!)

(1) 절차지향적 사고

다음은 위의 1부터 n까지 출력하는 함수.

void func1(int n){
    if(n == 0) return;
    cout << n << ' ';
    func1(n-1);
}

func1(3)을 호출하면 3을 출력하고 func1(2)를 호출함. func1(2)를 호출하면 2를 출력하고 func1(1)을 호출함. func1(1)을 호출하면 1을 출력하고 func1(0)을 호출함. func1(0은 조건문에 의해 걸려, 함수가 종료됨. 따라서 출력은 3 2 1이 됨.

(2) 귀납적 사고

1. func(1)은 1을 출력한다.

1번은 굉장히 자명함.

2. 그 다음은 'func1(k)가 k, k-1, k-2, ... , 1을 출력한다면, func1(k+1)가 k+1, k, k-1, ... ,1을 출력한다' 는 것을 보여야 함.

3. func1(k+1)을 호출하면, k+1을 출력하고 func1(k)를 호출함. 이 때, func1(k)는 위의 가정에 의해, k ~ 1까지를 출력한다고 했으므로, func1(k+1)은 (k + 1) ~ 1까지 출력함.

앞으로 모든 재귀는, 1번과 같은 절차지향적 사고가 아닌, 2번과 같은 귀납적 사고로 이해해야 함.

2) 재귀 함수의 조건

• 재귀 함수의 조건 : 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함(Base Condition, Base Case) : 모든 입력은 Base Condition으로 수렴해야 함.

void func1(int n){
    if(n == 0) return;
    cout << n << ' ';
    func1(n-1);
}

위의 코드에서, if문에서 n이 0이면 자기 자신을 호출하지 않고 종료됩니다. 따라서 이것이 Base Condition.

그리고 우리는 이 함수에 자연수만 넣을테니, 모든 입력은 n = 0(Base Condition)으로 수렴됨.

만약 이 두 조건 중 하나라도 지켜지지 않는다면, 재귀함수는 무한번 실행되다가 런타임 에러를 발생시킴.

3) 재귀에 대한 Tip

(1) 함수를 명확하게 정의한다!

정의라는 것은

1. 함수의 인자로 어떤 것을 받는가

2. 어디까지 계산한 후에, 자기 자신으로 넘겨주는가

를 의미함.

(2) 모든 재귀는 반복문만으로도 동일한 동작을 할 수 있다!

재귀는 상황에 따라 코드는 간결해지지만, 함수 호출 비용은 비용이 큰 연산이므로, 메모리와 시간에서 손해를 봄.

따라서, 재귀를 굳이 쓰지 않아도 되고 구현에 큰 어려움이 없으면 반복문으로 쓰는게 좋음.

하지만 반복문으로 구현했을 때 코드가 복잡해지면 재귀로 구현하는 게 나음.

(3) 재귀는 비효율적일 수 있다!

재귀 함수가 자기 자신을 여러 번 호출하면 예상과는 다르게 비효율적일 수 있음.

예를 들어 피보나치 수열을 재귀함수로 짜면, 시간복잡도는 지수함수 형태임 (n = 100만 되어도 2만년이 넘게 걸림)

그 이유는 다음과 같음. fibo(5)를 할 경우, fibo(4), fibo(3)을 호출 fibo(4)를 할 경우, fibo(3), fibo(2)를 호출 fibo(3)를 할 경우, fibo(2), fibo(1)을 호출

그러면 fibo(4)에서 나온 fibo(3)을 계산하고, 또 fibo(5)에서 나온 fibo(3)을 다시 계산해야 함.

이미 다른 과정에서 계산한 값을, 또 다른 과정에서 다시 계산하는 일이 일어남.

(4) 재귀 함수가 자기 자신을 부를 때, 스택 영역에 계속 누적된다!

만약 문제를 풀 때, 메모리 제한이 512MB라면, 프로그램이 점유하는 메모리가 최대 512MB여야 함. 일부 컴파일 환경에서는 스택 영역의 메모리가 별도로 1MB로 제한되어 있기도 함.

BOJ에서는 스택 메모리 제한이 없지만, swexpertacademy에는 있음. 따라서 후자처럼 스택 메모리 제한이 작게 제한된 곳에서는, 재귀를 깊게 들어가는 풀이라면 반복문으로 변환해야 함...

4) 예시 - 하노이 탑

(1) 귀납적 사고

1. n-1개의 원판을 기둥1에서 기둥 2로 옮긴다.
2. n번 원판을 기둥 1에서 기둥 3으로 옮긴다.
3. n-1개의 원판을 기둥2에서 기둥 3으로 옮긴다.

즉, 원판이 n-1개일 때 옮길 수 있으면 원판이 n개일 때도 옮길 수 있음.

귀납적 사고를 하면,

1. 원판이 1개 일 때 원하는 곳으로 옮길 수 있음.
2. 원판이 k개 일 때 원하는 곳으로 옮길 수 있으면, 원판이 k+1개 일 때에도 옮길 수 있음.

(2) 구현

(2.1) 함수의 정의

함수의 정의는, 함수가 어떤 역할을 수행하고 어떤 인자를 받는지 정하는 것.

void func(int n)

위의 정의는 틀림! 왜냐 하면, 우리는 n-1개를 기둥1에서 기둥 3으로 옮기는 것이 아닌, 기둥2로 옮겨야 하기 때문.

void func(int a, int b, int n)

원판 n개를 기둥a에서 기둥b로 옮기는 함수의 정의.

(2.2) Base Condition

n = 1일 때, a에서 b로 옮기면 됨.

(2.3) 재귀 식

1. n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮김

   func(a, 6-a-b, n-1);

2. n번 원판을 기둥a에서 기둥b로 옮김

   cout << a << ' ' << b << '\n';

3. n-1개의 원판을 기둥6-a-b에서 기둥b로 옮김

   func(6-a-b, b, n-1);

참고로, 옮긴 횟수도 생각할 수 있음. 만약 원판 k + 1개를 옮길 때, 원판 k개를 옮기기 위해 x번, 원판 k+1번을 옮길 때 1번, 원판 k개를 다시 옮길 때 x번으로, 총 2X + 1번의 이동이 일어남.

더욱이 초항이 1이므로, 수열의 일반한은 2^k - 1이 됨.

2. Q&A

-

3. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x0B강 - 재귀' : 'Jinhan's Note' 중 'Theme 05. 재귀 / 분할정복(DnC)'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x0A강 - DFS'

1. DFS
2. Q&A
3. 마치며

1. BFS

• DFS(Depth First Search) : 다차원 배열에서 각 칸을 방문할 때, 깊이를 우선으로 방문하는 알고리즘

1) 다차원 배열의 DFS의 방법

1. 시작하는 칸을 큐에 넣고, 방문했다는 표시를 남김

2. 스택에서 원소를 꺼내어, 그 칸의 상하좌우로 인접한 칸에 대해 3번을 진행

3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입

4. 스택가 빌 때까지 2번을 반복

DS의 시간복잡도는, 방문했다는 표시를 남기기 때문에 모든 칸은 스택에 1번씩만 들어가게 됨. 따라서 시간 복잡도는, 칸이 N개 일 때 O(N). 만약 행이 R개, 열이 C개라면 O(RC).

BFS에서 큐가 스택으로 변한 것 외에는 전부 똑같음. 즉, 큐를 쓰면 BFS, 스택을 쓰면 DFS.

2) 다차원 배열의 BFS의 구현

BFS와 동일하고, 큐가 스택으로만 바뀌면 됨.

(코드가 커서 '바킹독님의 깃헙 링크'를 참고)

3) BFS vs DFS

BFS와 DFS는, 큐와 스택을 쓴다는 차이점이 있지만, 원소 하나를 빼내고 주변을 살펴본다는 알고리즘의 흐름은 동일.

하지만 _방문순서_에서 가장 큰 차이가 있음.

BFS는 시작점을 중심으로, 동심원처럼 퍼져나감. (BFS의 성질, 거리 순으로 원소를 방문함) DFS는 한 방향으로 막힐 때까지 나아감.

따라서, BFS에서 사용한, "현재 칸으로부터 인접한 칸은 (현재 칸 + 1)이다"는 DFS에서는 성립하지 않음.

결국, 우리는 다차원 배열에서 DFS를 굳이 써야 하는 이유가 없음. Flodd Fill은 어느 것을 써도 되지만, 거리 측정은 BFS만 가능하므로 BFS가 더 용이.

대부분 다차원 배열을 순회하는 문제는 BFS를 사용할 것. (DFS는 그래프에서 더 다룰 것)

3. Q&A

-

4. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x0A강 - DFS'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x09강 - BFS'

1. BFS
2. BFS의 유형
3. Q&A
4. 마치며

1. BFS

• BFS(Breadth First Search) : 다차원 배열에서 각 칸을 방문할 때, 너비를 우선으로 방문하는 알고리즘

원래 BFS는 그래프 자료구조에서 모든 노드를 방문하기 위한 알고리즘. 따라서, BFS를 정확하게 이해하려면, 그래프 자료구조에 대해 알고 있어야 함.

여기서는, 다차원 배열에서의 BFS를 중심.

1) 다차원 배열의 BFS의 방법

1. 시작하는 칸을 큐에 넣고, 방문했다는 표시를 남김

2. 큐에서 원소를 꺼내어, 그 칸의 상하좌우로 인접한 칸에 대해 3번을 진행

3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입

4. 큐가 빌 때까지 2번을 반복

BFS의 시간복잡도는, 방문했다는 표시를 남기기 때문에 모든 칸은 큐에 1번씩만 들어가게 됨. 따라서 시간 복잡도는, 칸이 N개 일 때 O(N). 만약 행이 R개, 열이 C개라면 O(RC).

2) 다차원 배열의 BFS의 구현

우선 utility헤더의 pair라는 STL을 사용할 것. (BFS를 구현할 때, 큐에 좌표를 넣을 때 사용)

(코드가 커서 '바킹독님의 깃헙 링크'를 참고) (BFS의 정석적인 구현은, 거의 외우다시피 해야함.)

2. BFS의 유형

1) Flood Fill

어떤 칸과 연결된 영역을 찾는 유형

이중 for문으로 각각의 칸이 BFS의 시작점이 될 수 있는지 체크해주기. 시간복잡도는 칸의 개수. O(NM).

2) 거리 측정

_기존 배열을 -1로 초기화_하면, 굳이 vis 배열 없이 방문 여부 확인 가능.

3) 시작점이 여러 개일 때

1. 거리가 0인 칸들을 큐에 다 추가

2. 거리가 0인 칸들에 의해, 거리가 1인 칸들이 큐에 다 추가됨. 마지막으로 거리가 0인 칸들은 큐에서 모두 pop됨.

3. 마찬가지로, 거리가 1인 칸들에 의해, 거리가 2인 칸들이 큐에 다 추가됨. 마지막으로 거리가 1인 칸들은 큐에서 모두 pop됨.

4. ...

5. 즉, 전체적인 큐의 모양을 확인하면, _BFS를 돌 때 큐에 쌓이는 순서는 반드시 거리 순_인게 됨.

4) 시작점이 두 종류일 때

각각의 종류마다, BFS를 돌리면 됨.

두 종류면, 두 번의 BFS를 돌리기

5) 1차원에서의 BFS

2차원 BFS와 큰 차이 없음.

3. Q&A

-

4. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x09강 - BFS'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x08강 - 스택의 활용(수식의 괄호 쌍)'

1. 수식의 괄호쌍
2. 문제 해결
3. Q&A
4. 마치며

1. 수식의 괄호쌍

32-{6-(2+4)*7} -> { ( ) } : X 5+{6-(12+4}*7) -> { ( } ) : O

수식의 괄호쌍이란, 주어진 괄호 문자열이 올바른지 판단하는 문제.

2. 문제 해결

1) 문제 해결을 위한 관찰

(())()() : O ))(() : X ()())(() : X

해당 괄호쌍이 맞는지 아닌지 판단하는 '로직'에 대해 생각해보아야 함.

• 가장 보편적인 방법, 안쪽부터 짝맞추기를 해서 지워가는 방법. 짝이 다 맞으면 올바른 괄호쌍, 아니면 틀린 괄호쌍.

• )의 개수가 (개수를 넘지 않으면 됨.

• 괄호의 종류가 여러가지라면, 괄호의 갯수만으로 판단하기는 부족. ex) ({}) : O, ({)} : X

대신, 붙어있는 (), {}를 지우는 방법은 여전히 동작.

위 방법을 배열로 구현할 경우 최대 N번 중간에 있는 원소의 삭제가 발생하므로 O(N²), 연결 리스트의 경우 O(N). 그러나 스택은 더 간단하게 구현 가능.

따라서 스택으로 구현을 할텐데, 추가로 생각해야 하는 점이 있음.

• 닫는 괄호를, "남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령"이라고 생각해도 됨.

2) 문제 해결 방법

(1) 여는 괄호가 나오면 스택에 추가

(2) 닫는 괄호가 나왔을 경우,

(2.1) 스택이 비어있으면, 올바르지 않은 괄호쌍

(2.2) 스택의 top이 짝이 맞지 않는 괄호일 경우, 올바르지 않은 괄호쌍

(2.3) 스택의 top이 짝이 맞는 괄호일 경우, pop

(3) 모든 과정을 끝낸 후,

(3.1) 스택에 괄호가 남아있으면, 올바르지 않은 괄호쌍

(3.2) 스택에 괄호가 남아있지 않으면, 올바른 괄호쌍

3. Q&A

-

4. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x08강 - 스택의 활용(수식의 괄호 쌍)'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x07강 - 덱' : 'Jinhan's Note' 중 'Theme 02. STL 자료구조 _ deque'

1. 덱(Deque)
2. STL deque
3. Q&A
4. 마치며

1. 덱(Deque)

• 덱(Deque, Double Ended Queue) : 양쪽 끝에서 원소 넣거나 뺄 수 있는 자료구조

스택과 큐는 덱의 특수한 예시라고 볼 수도 있음.

1) 덱의 성질

(1) 원소의 추가 / 제거 O(1)

(2) 제일 앞 / 뒤의 원소 확인 O(1)

(3) 제일 앞 / 뒤가 아닌, 나머지 원소들의 확인 / 변경이 원칙적으로 불가능

단, STL deque는 인덱스로 원소에 접근 가능함.

2) 덱의 구현

const int MX = 1000005;
int dat[2*MX+1];
int head = MX, tail = MX;

dat배열에는 덱 원소들의 값이 들어가고, head는 제일 앞의 원소를 가리키고, tail은 제일 뒤의 원소 + 1을 가리키고 있음. 그리고 dat[head]부터 dat[tail - 1]까지 큐의 원소들이 있는 자리임. 그리고 큐의 크기는 tail - head로 계산 가능.

단, head와 tail의 초기값이 0이 아닌, MX임. 덱은 원소를 양쪽 끝에서 추가할 수 있기 때문에, head를 0으로 했을 때 왼쪽으로 확장할 수 없음. 따라서 중간지점에서 양쪽 끝으로 확장해 나가야 함.

const int MX = 1000005;
int dat[2*MX+1];
int head = MX, tail = MX;

void push_front(int x){
    dat[--head] = x;
}

void push_back(int x){
    dat[tail++] = x;
}

void pop_front(){
    head++;
}

void pop_back(){
    tail--;
}

int front(){
    return dat[head];
}

int back(){
    return dat[tail - 1];
}

3) 벡터와 덱

STL queue는 double ended queue보다는 vector의 느낌이 강함. pop_front, push_front, pop_back, push_front는 그렇다 하지만, insert, erase, 인덱스 접근도 가능.

(1) deque의 장점

(1.1) vector와 달리 push_front(), pop_front() 연산 제공

(1.2) capacity와 size가 같아지면 특정 크기의 chunk를 할당해서 크기를 늘려줌.

vector는 1.5 ~ 2배로 늘려서 전체를 재할당함.

따라서 vector에 비해 확장 비용을 줄여줌.

(2) deque의 단점

(2.1) 비연속적으로 메모리 상에 존재하기 때문에, cache hit rate가 떨어져 vector에 비해 느림.

(2.2) 비연속적으로 메모리 상에 존재하기 때문에, 원소들을 가리키는 포인터 간의 연산은 불가능.

단, iterator 간의 연산은 가능.

4) 덱과 스택, 큐

덱은 스택과 큐의 연산을 모두 지원. 따라서 스택과 큐는 덱으로 대체 가능.

그래도, push_back, pop_back 연산만 사용하면 stack, push_back, pop_front 연산만 사용하면 queue를 사용하는 것이 좋음. 이렇게 하면 해당 객체가 어떤 역할을 수행하는지 판단할 수 있으므로 가독성 향상!

단, 스택과 큐는 default container가 deque이기 때문에, 스택과 큐가 약간 느릴 수 있지만 큰 차이는 없음.

2. STL deque

1) 생성자

1. deque<int> DQ;
2. deque<int> DQ(n); 또는 deque<int> DQ(n, val);
3. deque<int> DQ(dq.begin(), dq.end());
4. deque<int> DQ{ 1, 2, 3}; 또는 deque<int> DQ = { 1, 2, 3 };

1. 비어있는 덱 생성
2. n개의 원소를 갖는 덱 생성 후자는 n개의 원소를 val값으로 초기화
3. 다른 컨테이너의 iterator를 받아온 뒤, 순회하며 덱에 해당 범위의 원소를 채워줌
4. initializer_list를 인자로 받는 생성자

2) 멤버 함수

// DQ = { }
deque<int> DQ;

// DQ = { 1, 2, 3, 4, 5 }
for (int i = 1; i <= 5; i++) DQ.push_back(i);
// DQ = { 10, 9, 8, 7, 6, 1, 2, 3, 4, 5 }
for (int i = 6; i <= 10; i++) DQ.push_front(i);

// DQ = { 7, 6, 1, 2, 3, 4, 5 }
for (int i = 1; i <= 3; i++) DQ.pop_front();
// DQ = { 7, 6, 1, 2 }
for (int i = 1; i <= 3; i++) DQ.pop_back();

(1) push_back / push_front

마지막 위치에 원소를 삽입. O(1)

시작 위치에 원소를 삭제. O(1)

emplace_back, emplace_front로 대체 가능.

(2) pop_back / pop_front

마지막 위치에 원소를 삭제. O(1)

시작 위치에 원소를 삭제. O(1)

반환값은 void.

(3) insert / erase

임의의 위치에 원소 삽입 / 삭제. O(n)

시간 복잡도가 O(n)이므로 deque는 n이 클 때 insert와 erase 연산을 여러번 하기 적합하지 않음.

// 4
cout << "DQ.size() : " << DQ.size() << '\n';
// 0
cout << "DQ.empty() : " << DQ.empty() << '\n' << '\n';

// DQ = { }
DQ.clear();
// DQ = { 0 }
DQ.resize(1);
// DQ = { 0, 2, 2 }
DQ.resize(3, 2);
// DQ = { 0, 1, 2 }
DQ[1] = 1;

(4) size / empty

deque의 크기를 size_t 자료형으로 반환.

deque가 비어있는지 여부를 bool 자료형으로 반환.

(5) resize / clear

deque의 크기를 변경

deque의 모든 원소를 삭제

deque의 크기를 변경. 변경될 크기가 원래의 크기보다 작은 경우, 뒤의 원소부터 차례로 지워지고, 원래의 크기보다 큰 경우, 두 번째 인자가 없는 경우 초기값, 있는 경우는 해당 값으로 남은 칸이 채워짐.

// 0 1 2
for (auto it = DQ.begin(); it != DQ.end(); it++) cout << *it << ' '; cout << '\n';
// 2 1 0
for (auto it = DQ.rbegin(); it != DQ.rend(); it++) cout << *it << ' '; cout << '\n';
// 0
cout << "DQ.front() : " << DQ.front() << '\n';
// 2
cout << "DQ.end() : " << DQ.back() << '\n';

(6) begin / end

deque의 첫번째 원소를 가리키는 iterator 반환

deque의 마지막 원소의 다음 칸을 가리키는 iterator 반환

(7) rbegin / rend

begin의 reserve_iterator 버전

end의 reserve_iterator 버전

(8) front / back

DQ[0]을 reference로 반환. O(1)

DQ[n-1]을 reference로 반환. O(1)

빈 vector에서 둘을 호출하는 것은 'UB(Undefined Behavior)'

3. Q&A

-

4. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x07강 - 덱' : 'Jinhan's Note' 중 'Theme 02. STL 자료구조 _ deque'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x06강 - 큐' : 'Jinhan's Note' 중 'Theme 02. STL 자료구조 _ queue'

1. 큐(Queue)
2. STL queue
3. Q&A
4. 마치며

1. 큐(Queue)

• 큐(Queue) : 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺼 수 있는 자료구조

스택은 구조적으로 제일 먼저 들어간 원소가 제일 나중에 나오게 됨. FILO(First in Last out) 자료구조.

큐는 먼저 들어간 원소가 제일 먼저 나오게 됨. FIFO(First in First out) 자료구조.

1) 큐의 성질

(1) 원소의 추가 / 제거 O(1)

스택에서는 원소가 추가되고 제거되는 곳을 top이라고 함. 그리고 원소가 위 아래로 배치된 것으로 생각함.

큐에서는 추가되는 곳을 rear(뒤쪽), 제거되는 곳을 front(앞쪽)이라고 함.

(2) 제일 앞 / 뒤의 원소 확인 O(1)

(3) 제일 앞 / 뒤가 아닌, 나머지 원소들의 확인 / 변경이 원칙적으로 불가능

2) 스택의 구현

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;

dat배열에는 스택 원소들의 값이 들어가고, head는 제일 앞의 원소를 가리키고, tail은 제일 뒤의 원소 + 1을 가리키고 있음. 그리고 dat[head]부터 dat[tail - 1]까지 큐의 원소들이 있는 자리임. 그리고 큐의 크기는 tail - head로 계산 가능.

push를 하게되면 tail이 증가, pop을 하면 head가 증가. 따라서 dat배열에서 큐의 원소들이 있는 장소는 오른쪽으로 점점 밀림. 그러면 pop을 여러 번 진행하면, 앞쪽에 쓸모없는 공간이 계속 생기게 됨. 이를 해결하기 위해서는, 큐의 언소가 들어갈 배열을 원형으로 만드는 것. 실제로 구현할 때는 head나 tail이 다시 0번지로 돌아오게끔 구현. 이러한 원형 배열로 만든 큐를 '원형 큐(Circular Queue)'라고 함.

그래서 실무에서 STL말고 큐를 직접 구현을 할 때는 원형 큐를 구현하는 것이 좋음.

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;

void push(int x){
    dat[tail++] = x;
}

void pop(){
    head++;
}

int front(){
    return dat[head];
}

int back(){
    return dat[tail - 1];
}

2. STL queue

queue는 보통 BFS나 Flodd Fill을 할 때 쓰게 됨. 둘 다 코테 단골 문제여서 queue를 쓸 일이 아주 많을 것.

1) 생성자

1. queue<int> Q;

1번은 비어있는 큐를 생성합니다.

(스택과 마찬가지로 queue는 내부적으로 queue 연산을 지원하는 deque, list 등을 이용해 구현되며, default값은 deque입니다.)

2) 멤버 함수

queue<int> Q;

// Q = [ 1(front), 2, 3, 4, 5(back) ]
for(int i = 1; i <= 5; i++) Q.push(i);
while(!Q.empty()){
    cout << Q.size() << ' ' << Q.front() << '\n';
    Q.pop();
}

(1) push / pop

back()쪽 위치에 원소를 삽입. O(1)

front()쪽 위치에 원소를 삭제. O(1)

push는 emplace로 대체 가능.

pop의 반환값은 void이며 front()가 아님.

(2) front / back

가장 먼저 들어온 원소를 reference로 반환. O(1)

가장 마지막에 들어온 원소를 reference로 반환. O(1) (잘 사용하지 않음)

(3) size / empty()

queue의 크기를 size_t 자료형으로 반환.

queue가 비어있는지 여부를 bool 자료형으로 반환.

(4) 참고

std::queue에는 clear라는 멤버 함수가 없음. 따라서 해당 동작을 하고자 하면

while(Q.size()){ Q.pop() }

으로 처리해야 함.

빈 Queue에서 pop, front, back을 호출하는 것은 'UB(Undefined Behavior)'이며 _런타임 에러를 발생_시킴.

일반적으로 큐의 원소에 접근할 때는 front()만을 이용하며, back()이 필요한 경우는 드뭄.

또한 deque와 달리 []연산자, iterator가 없으므로 front(), back() 이외의 원소에는 접근할 수 없음.

3. Q&A

-

4. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x06강 - 큐' : 'Jinhan's Note' 중 'Theme 02. STL 자료구조 _ queue'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x05강 - 스택' : 'Jinhan's Note' 중 'Theme 02. STL 자료구조 _ stack'

1. 스택(Stack)
2. STL stack
3. Q&A
4. 마치며

1. 스택(Stack)

• 스택(Stack) : 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조

스택은 구조적으로 제일 먼저 들어간 원소가 제일 나중에 나오게 됨. FILO(First in Last out) 자료구조.

스택, 큐 ,덱 모두 특정 위치에서만 원소를 넣거나 뺄 수 있음. 그래서 'Restricted Structure'라고 부름.

1) 스택의 성질

(1) 원소의 추가 / 제거 O(1)

(2) 최상단의 원소 확인 O(1)

(3) 최상단이 아닌, 나머지 원소들의 확인 / 변경이 원칙적으로 불가능

2) 스택의 구현

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

dat배열에는 스택 원소들의 값이 들어가고, pos는 다음 원소가 추가될 때 삽입해야하는 곳을 가리키고 있음. 그리고 pos의 값은 곧 스택의 길이, 즉 원소의 개수를 나타냄.

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

void push(int x){
    dat[pos++] = x;
}

void pop(){
    pos--;
}

int top(){
    return dat[pos-1];
}

3) 벡터와 스택

사실 벡터는 스택의 모든 기능을 대체할 수 있음. (마지막 원소의 추가 / 제거는 push_back(), pop_back(). 또한 []연산자를 통해 임의 위치에 접근 가능.)

하지만 그럼에도 불구하고 스택을 쓰는 경우가 있음. 바로, stack의 연산만을 이용하는 경우.(의미가 더 명확해짐) 하지만 벡터를 사용한다고 하더라도 성능 차이는 거의 없음.

(사실, push, pop, top연산이 정의된 자료구조는 모두 stack이라 부름(vector, string, deque, list). 하지만 c++에서 스택은 std::stack을 의미)

2. STL stack

1) 생성자

1. stack<int> S;

1번은 비어있는 스택을 생성합니다.

(스택을 내부적으로 stack의 연산을 지원하는 deque, vector 등을 이용해 구현되며, default값은 deque입니다.)

2) 멤버 함수

stack<int> S;

// S = { 1, 2, 3, 4, 5 }
for(int i = 1; i <= 5; i++) S.push(i);
while(!S.empty()){
    cout << S.size() << ' ' << S.top() << '\n';
    S.pop();
}

(1) push / pop

마지막 위치에 원소를 삽입 / 삭제. O(1)

push는 emplace로 대체 가능.

pop의 반환값은 void이며 마지막 원소가 아님(파이썬 list의 pop()과 다름)

빈 stack에서 둘을 호출하는 것은 'UB(Undefined Behavior)'이며 _런타임 에러를 발생_시킴.

(2) top

마지막 위치의 원소를 reference로 반환. O(1)

(3) size / empty()

stack의 크기를 size_t 자료형으로 반환.

stack이 비어있는지 여부를 bool 자료형으로 반환.

(4) 참고

std::stack에는 clear라는 멤버 함수가 없음. 따라서 해당 동작을 하고자 하면

while(S.size()){ S.pop() }

으로 처리해야 함.

또한 deque와 달리 []연산자, iterator가 없으므로 top()이외의 원소에는 접근할 수 없음.

3. Q&A

-

4. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x05강 - 스택' : 'Jinhan's Note' 중 'Theme 02. STL 자료구조 _ stack'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x04강 - 연결 리스트' : 'Jinhan's Note' 중 'Theme 02. STL 자료구조 _ list'
• iterator(반복자) : http://www.tcpschool.com/cpp/cpp_iterator_category

1. 연결 리스트(List)
2. STL list
3. Q&A
4. 마치며

1. 연결 리스트(List)

• 연결 리스트(List) : 원소들을 저장할 때, 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장한 자료구조

1) 연결 리스트의 성질

(1) k번째 원소를 확인 / 변경하기 위해 O(k)가 필요

예를 들어, 3 -> 13 -> 72 -> 5의 연결 리스트에서 72를 찾기 위해서는, 3을 거쳐 13을, 13을 거쳐 72로 가야함. 이는, 배열과 다르게 원소들이 연속적으로 위치하지 않기 때문.

(2) 임의의 위치에 원소를 추가 / 제거는 O(1)

(3) Cache hit rate가 낮음. 대신 메모리 할당은 쉬움

메모리 상에서 데이터가 연속적으로 위치하지 않음.

Cache hit rate는, 캐시된 데이터를 요청할 때 해당 키 값이 메모리에 존재하여 얼마만큼의 비율로 잘 찾았는지에 대한 비율.

2) 연결 리스트의 종류

(출처 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x04강 - 연결 리스트')

(1) 단일 연결 리스트(Singly Linked List)

각 원소가 자신의 _다음 원소_의 주소를 들고 있는 연결 리스트

(2) 이중 연결 리스트(Doubly Linked List)

각 원소가 자신의 _다음과 이전의 원소_의 주소를 들고 있는 연결 리스트.

STIL의 연결 리스트에서, 컨테이너의 이름은 list이고, 구조는 이중 연결 리스트입니다.

(3) 원형 연결 리스트(Circular Linked List)

처음과 끝이 연결된 연결 리스트.

이 때 연결 리스트는 단일 / 이중 연결 리스트이다.

3) 배열과 연결 리스트

배열과 연결 리스트는, 메모리 상에서 데이터를 놓는 방식은 다르더라도, _원소들 사이에 선후 관계가 일대일로 정의_됨

그래서 이 둘 자료형은, '선형 자료구조'라고 불림. 트리, 그래프, 해쉬 등은 '비선형 자료구조'라고 불림.

둘 다 선형 자료구조이므로, 면접에서 둘을 비교하라는 내용이 나오기도 하니 알고있어야 함!

(1) k번째 원소의 접근

• 배열 : O(1)
• 연결 리스트 : O(k)

(2) 임의의 위치에 원소 추가 / 제거

• 배열 : O(N)
• 연결 리스트 : O(1)

사실 엄밀히 말하면, 연결 리스트에 원소를 추가 / 제거 하는 경우, 임의 위치까지 찾아간 후에 O(1) 연산을 하는 것이므로 주의!

(3) 메모리 상의 배치

• 배열 : 연속적
• 연결 리스트 : 비연속적

(4) 추가적으로 필요한 공간(Overhead)

• 배열 : 필요 없음
• 연결 리스트 : O(N)

배열의 경우 데이터만 저장하면 되니 추가 공간 필요 없음 (굳이 따지자면, 길이 정보를 저장할 int 1개가 필요할 수 있지만 미미하므로 신경 쓸 필요 없음)

연결 리스트의 경우, 데이터 뿐만 아니라, 다음 / 이전 원소의 주소값을 가지고 있어야 하므로, 32비트 체제의 경우 4N(32비트)바이트, 64비트 체제의 경우 8N(64비트)바이트가 추가적으로 필요. 즉, N에 비례하는 만큼 메모리를 추가로 쓰게 됨.

즉, 임의의 위치에 원소를 추가하거나 제거하는 연산을 많이 해야하는 경우, 연결 리스트의 사용을 고려할 수 있음.

3) 연결 리스트의 직접 구현

(1) 정석적인 구현

struct NODE{
    struct NODE *prev, *next;
    int data;
};

코테에서는 STL list를 사용하기. 만약 STL이 사용불가하면 2번 방법을 활용하기.

위의 코드 경우 면접에서 손코딩을 시키거나 질문을 하는 경우가 있기 때문에 알고는 있어야 함.

(2) 코테에서 STL 사용이 불가할 때

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1;

void traverse(){
    int cur = nxt[0];
    while(cur != -1){
        cout << dat[cur] << ' ';
        cur = nxt[cur];
    }
    cout << '\n\n';
}

void insert(int addr, int num) {
    // 1. Write new element
    dat[unused] = num;
    pre[unused] = addr;
    nxt[unused] = nxt[addr];

    // 2. Fix pre & nxt element's information
    if(nxt[addr] != -1) pre[nxt[addr]] = unused;
    nxt[addr] = unused;

    // 3. Fix unused
    unused++;
}

void erase(int addr){
    // 1. Fix pre & nxt element's information
    nxt[pre[addr]] = nxt[addr];
    if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr];

    // 2. Fix unused
    unused--;
}

int main (){
    fastio;
    fill(pre, pre + MX, -1);
    fill(nxt, nxt + MX, -1);
}

원소를 배열로 관리하고, pre와 nxt에 이전 / 다음 원소의 포인터 대신, 배열 상의 인덱스를 저장하는 방시긍로 구현한 연결 리스트.

메모리 누수 때문에 실무에서는 사용할 수 없지만, 구현 난이도가 낮고 시간복잡도도 동일해 코테에서는 활용 가능.

코드 상에서, dat[i]는 i번지 원소의 값, pre[i]는 i번지 원소에 대해 이전 원소의 인덱스, nxt[i]는 i번지 원소에 대해 다음 원소의 인덱스. 만약 pre와 nxt의 값이 -1인 경우 이전 / 다음 원소는 존재하지 않는 경우임. unused는 현재 사용되지 않는 인덱스, 즉 새로운 원소가 들어갈 수 있는 인덱스이고 원소가 추가된 이후에는 1씩 증가시킴. 특별히 0번지는 연결 리스트의 시작 원소로 고정되어 있음. 따라서 값이 들어가지 않고 시작점을 나타내기 위한 dummy node. 0번지의 dat값은 -1, pre는 -1, nxt는 다음 원소의 번지 인덱스를 적으면 됨. (dummy node를 만들어야 예외 처리가 쉬워짐. 만약 원소가 없는 경우, 원소 추가 / 삭제를 생각할 때 dummy node가 있는게 쉬움)

만약 길이 정보가 필요하면 len변수를 선언하고 추가 / 제거 될때 1씩 증가 / 감소시키면 됨.

2. STL list

st::list는 Doubly Linked List로 구현되어 있습니다. 임의의 위치에 원소를 삽입 / 삭제(O(1) : 해당 원소의 위치를 알 고 있을 때만... 모르면 해당 위치로 일일이 찾아가야 함...)할 수 있지만, []연산자를 이용해 접근할 수 없으며, 처음부터 하나씩 접근해야만 합니다.

따라서, list는 1) 중간 위치에서 삽입, 삭제가 빈번하게 일어나고, 2) 데이터에 랜덤하게 접근하지 않는 경우가 많을 때 사용됩니다.

1) 생성자

1. list<int> L;
2. list<int> L(n); 또는 list<int> L(n, val);
3. list<int> L{1, 2, 3}; 또는 list<int> L = {1, 2, 3};

1. 비어있는 리스트를 생성합니다.
2. n개의 원소를 갖는 리스트를 생성합니다. 후자는 n개의 원소를 val값으로 초기화합니다.
3. initializer_list를 인자로 받는 생성자

2) 멤버 함수

// L = { 1, 2, 3 }
list<int> L = { 1, 2, 3 };

auto it1 = next(L.begin()); // *it1 == 2

// L = { 1, 10, 2, 3 }, *it1 == 2, *it2 == 10
auto it2 = L.insert(it1, 10);
// L = { 1, 2, 3 }, *it2 == 2
it2 = L.erase(it2);

(1) push_back / push_front

마지막 / 시작 위치에 원소를 삽입. O(1)

emplace_back, emplace_front로 대체 가능.

(2) pop_back / pop_front

마지막 / 시작 위치의 원소를 삽입. O(1)

반환값은 void.

(3) insert / erase

매개변수로 받은 itertor의 위치의 앞에 원소를 삽입. O(1) insert는 emplace로 대체 가능.

매개변수로 받은 iterator 위치의 원소를 삭제 후, 원래 위치의 다음 원소의 itertator 반환. O(1)

이 때, erase의 인자로 전달한 iterator는 무효화(invalidated)되기 때문에 *it, it++ 등으로 사용하면 UB를 발생시킴. 그래서 일반적으로, it = erase(it)으로 사용하여 이를 방지함.

// L = { 1, 2, 3 }
list<int> L = { 1, 2, 3 };

// *** Result : 3 ***
cout << L.size();

// *** Result : 1 2 ***
L.resize(2);
for(auto i : L) cout << i ;

// *** Result : False ***
cout << L.empty();

// *** Result : True ***
L.clear();
cout << L.empty();

(4) size / resize

list의 크기를 size_t 자료형으로 반환.

list의 크기를 변경.

list의 크기를 변경 변경될 크기가 원래의 크기보다 작은 경우, 뒤의 원소부터 차례로 지워지고, 원래의 크기보다 큰 경우, 두 번째 인자가 없는 경우 초기값, 있는 경우는 해당 값으로 남은 칸이 채워짐.

(5) empty / clear

list가 비어있는지 여부를 bool 자료형으로 반환.

list의 모든 원소를 삭제

// L = { 1, 2, 3 }
list<int> L = { 1, 2, 3 };

// *** Result : 1 3 ***
cout << *L.begin() << ' ' << *L.end();

// *** Result : 3 1 ***
cout << *L.begin() << ' ' << *L.rend();

// *** Result : 1 3 ***
cout << L.front() << ' ' << L.back();

// *** Result : 1 2 3 4 5 ***
L = { 3, 1, 2, 4, 5 };
L.sort();
for(auto i : L) cout << i << ' ';

(6) begin / end

list의 첫번째 원소를 가리키는 iterator 반환

list의 마지막 원소의 다음 칸을 가리키는 iterator 반환

(7) rbegin / rend

begin의 reserve_iterator 버전

end의 reserve_iterator 버전

(8) front / back

list의 첫번째 원소를 reference로 반환. O(1)

list의 마지막 원소를 reference로 반환. O(1)

빈 vector에서 둘을 호출하는 것은 'UB(Undefined Behavior)'

(9) sort

list 내의 원소를 정렬. O(nlogn) sort는 merge sort로 구현.

첫 번째 인자로 cmp를 넣어줄 수 있으며, 생략한 경우 less<>{}가 default parameter로 들어감.

list의 원소를 정렬할 경우, std::sort 대신 L.sort()를 사용해야 함. (random access iterator가 없기 때문)

(10) 참고

list의 iterator는 random access iterator가 아니라, bidirectional iterator임

따라서, L.begin() + 3과 같은 + 연산을 지원하지 않음.

따라서, iterator를 이동시키기 위해서는, it++, it--와 같은 _증감연산자를 사용_해야함.

이 떄 증감연산자 대신, _std::prev, std::next함수_를 이용할 수 있음. 만약 여러 칸을 이동해야 하면, _std::advance_를 사용할 수도 있음. 단, std::advance의 시간복잡도는 O(n)임에 주의.

또한, list의 iterator는 iterator 간의 -연산을 지원하지 않아서, it - v.begin() 등으로 인덱스를 구할 수 없음.

이 떄는, O(n)의 시간복잡도를 가지는 std::distance를 사용 (보통 이러한 연산은 피하는게 나음)

3. Q&A

1) iterator(반복자)

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

4. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x04강 - 연결 리스트' : 'Jinhan's Note' 중 'Theme 02. STL 자료구조 _ list'
• iterator(반복자) : http://www.tcpschool.com/cpp/cpp_iterator_category

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x03강 - 배열' : 'Jinhan's Note' 중 'Theme 02. STL 자료구조 _ array, vector'

1. 배열(Array)
2. 벡터(Vector)
3. range-based for loop
4. Q&A
5. 마치며

1. 배열(Array)

• 배열(Array) : 메모리 상에 원소를 연속하게 배치한 자료구조 ex) int arr[10]

1) 배열의 성질

(1) 원소의 접근 및 수정은 []연산자를 통해 O(1)에 수행

(2) 다른 자료구조와 다르게, 추가적으로 소모되는 메모리의 양(Overhead)가 거의 없음

(3) Cache hit rate가 높음

Cache hit rate는, 캐시된 데이터를 요청할 때 해당 키 값이 메모리에 존재하여 얼마만큼의 비율로 잘 찾았는지에 대한 비율.

(4) 메모리 상에서 연속된 구간을 잡아야 하므로, 할당에 제약

2) 배열의 기능과 구현

(1) 임의의 위치에 있는 원소의 확인 / 변경 : O(1)

(2) 원소를 배열의 끝에 추가 : O(1)

(3) 마지막 원소를 제거 : O(1)

(4) 임의의 위치에 원소를 추가 : O(N)

만약 n번째 위치에 원소를 추가하게 되면, n+1부터 뒤의 칸들은 한 칸씩 밀림.

따라서, 추가하는 위치가 끝에 가까울수록 시간을 줄어들고, 앞에 가까울수록 늘어남 그러면 평균적으로 N/2개를 밀어야하므로 O(N)으로 표현가능함.

void insert(int idx, int num, int arr[], int& len){
    for(int i = len; i > idx; i--){
        arr[i] =  arr[i-1];
    }
    arr[idx] = num;
    len++;
}

위의 코드는 insert를 구현한 코드. 배열의 맨 끝부터 하나씩 오른쪽으로 당김.

이 때, i > idx에서 >=이 되면 안됨. 만약, idx가 0일 경우, 밑의 코드에서 arr[0] = arr[-1]이 되기 때문.

(5) 임의의 위치에 있는 원소를 제거 : O(N)

4번과 마찬가지로 n번쨰 원소를 삭제 후 n+1부터 뒤 칸들을 한 칸씩 앞당겨야 함. 그러므로 O(N)

만약 제거 후 당기지 않으면 어떡하나? -> 메모리 상에서 원소가 연속적으로 존재하지 않으므로 배열이라고 볼 수 없으며, k번쨰 원소를 O(1)에 찾을 수 없게 됨.

void erase(int idx, int arr[], int& len){
    for(int i = idx; i < len; i++){
        arr[i] = arr[i+1];
    }
    len--;
}

위의 코드는 erase를 구현한 코드. 4번과 마찬가지로 배열의 맨 끝부터 하나씩 오른쪽으로 당김.

3) 사용 팁

(1) 원소 전체를 특정값으로 초기화

(1.1) memset함수 -> 비추천!!!

int a[21];
int b[21][21];

memset(a, 0, sizeof a);
memset(b, 0, sizeof b);

cstring 헤더의 memset함수를 이용.

하지만 실수할 여지가 많음. 0이나 -1외의 값을 넣으면 오작동. 2차원 이상의 배열을 인자로 넘겨 그곳에서 memset을 사용하면 실수할 여지가 있음.

(1.2) for문 이용 -> 무난함

int a[21];
int b[21][21];

for(int i = 0; i < 21; i++){
    a[i] = 0;
}
for(int i = 0; i < 21; i++){
    for(int j = 0; j<21; j++){
        b[i][j] = 0;
    }
}

for문을 이용해 원소 하나하나를 수정하는 방식.

투박하지만 실수할 여지가 없으므로 무난함.

(1.3) fill함수 -> 추천!!!

int a[21];
int b[21][21];

fill(a, a+21, 0);
for(int i = 0; i < 21; i++){
    fill(b[i], b[i]+21, 0);
}

algorithm헤더의 fill함수를 이용

fill함수는 실수할 여지도 별로 없고, 코드도 짧으므로 추천!

2. 벡터(Vector)

• 벡터(Vector) : 가변 길이의 배열

vector<Type> name;    // 1차원
vector<vector<Type>> name;    //2차원

1) 생성자

1. vector<int> v;
2. vector<int> v(n); 또는 vector<int> v(n, val);
3. vector<int> v(w); 또는 vector<int> v = w; //단, w는 vector<int>
4. vector<int> v(w.begin(), w.end());
5. vector<int> v{1,2,3}; 또는 vector<int> v = {1,2,3};

1. 비어있는 벡터를 생성합니다.
2. n개의 원소를 갖는 벡터를 생성합니다. 후자는 n개의 원소를 val값으로 초기화합니다.
3. copy constructor로, 다른 vector와 동일한 벡터를 복사 생성할 때 사용됩니다.
4. 다른 컨테이너의 iterator를 받은 후, 순회하며 vector에 해당 범위의 원소를 채워주는 생성자
5. initializer_list를 인자로 받는 생성자

2) 멤버 함수

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int main(void) {
    fastio;
    // v = { 0, 0, 0 }
    // t = { 5, 5 }
    // w = { { -1, -1, -1 }, { -1, -1, -1 }}
    vector<int> v(3), t(2, 5);
    vector<vector<int>> w(2, vector<int>(3, -1));

    v.push_back(1); // v = { 0, 0, 0, 1 }
    v.pop_back();    // v = { 0, 0, 0 }

    // insert 2 at v[0], v = { 2, 0, 0, 0 }
    v.insert(v.begin(), 2);
    // insert { 4, 4, 4 } at v[2], v = { 2, 0, 4, 4, 4, 0, 0, 0 }
    v.insert(v.begin() + 2, 3, 4);
    // insert [t.begin(), t.end()] at v.begin(), v = { 5, 5, 2, 0, 4, 4, 4, 0, 0 }
    v.insert(v.begin(), t.begin(), t.end());

    // erase v[4], v = { 5, 5, 0, 4, 4, 4, 0, 0 }
    v.erase(v.begin() + 2);
    // erase [v[0], v[6]), v= { 0, 0 }
    v.erase(v.begin(), v.begin()+6);

    cout << "v.size() : " << v.size() << '\n'; // 2
    cout << "v.empty() : " << v.empty() << '\n' << '\n'; // 0

    v.clear(); // v = { }
    v.resize(1); // v = { 0 } 
    v.resize(3, 2); // v = { 0, 2, 2 }
    v[1] = 1; // v = { 0, 1, 2 }
}

(1) push_back / pop_back

마지막 위치에 원소를 삽입 / 제거. O(1)

(2) insert / erase

임의의 위치에 원소를 삽입 / 제거. O(n)

O(n)이므로, n이 클 떄 해당 함수들을 여러 번 적용하기는 적합하지 않음.

(3) size / resize

vector의 크기를 size_t 자료형으로 반한 (return값은 unsigend int이므로, v.size() - 1의 연산 시 언더플로우 위험 주의)

vector의 크기를 변경 변경될 크기가 원래의 크기보다 작은 경우, 뒤의 원소부터 차례로 지워지고, 원래의 크기보다 큰 경우, 두 번째 인자가 없는 경우 초기값, 있는 경우는 해당 값으로 남은 칸이 채워짐.

(4) capacity / reserve

vector의 capacity를 size_t 자료형으로 반한 (return값은 unsigend int이므로, v.capacity() - 1의 연산 시 언더플로우 위험 주의)

vector의 capacity를 변경 reserve를 잘 이용하면 메모리를 절약할 수 있음. : 만약 size와 capacity가 각각 6일 때, 하나의 원소를 추가해보자. size는 7이 되지만, size는 capacity보다 클 수 없기 때문에 capacity가 늘어난다. 이 때 capacity는 자동적으로 1.5 ~ 2배 정도 늘어난다. 그러면 12가 될 것이다. 그러나 남은 공간 5(12 - 7)은 사실 필요가 없는 공간이다. 따라서 reserve(7)로 해주면 size도 만족하고, 용량도 절약할 수 있다.

(capacity는 vector의 원소들을 담을 수 있는 메모리가 할당되어 있는 공간의 용량, size는 실제 유효 원소들의 개수)

(5) empty

vector가 비어져 있는지 bool자료형으로 반환

(6) clear

vector의 모든 원소를 삭제

(7) begin / end

vector의 첫번째 원소를 가리키는 iterator 반환

vector의 마지막 원소의 다음 칸을 가리키는 iterator 반환

iterator(반복자)는 포인터처럼, 자료구조의 원소를 가리키는 자료형.

(8) rbegin / rend

begin의 reserve_iterator 버전

end의 reserve_iterator 버전

(9) front / back

v[0]을 reference로 반환

v[n-1]을 reference로 반환

빈 vector에서 둘을 호출하는 것은 'UB(Undefined Behavior)'

3. range-based for loop

vector<int> v = {1,2,3,4,5,6};

// 1. ranged-based for loop (since C++11)
for(int e : v) { cout << e << ' '; }
for(int& e: v) { cout << e << ' '; }

// 2. not bad
for(int i = 0; i < v.size(); i++) { cout << v[i] << ' '; }

// 3. **Wrong**
for(int i = 0; i <= v.size() - 1; i++) { cout << v[i] << ' '; }
}

1번의 방법은 C++11부터 적용가능한 range-based for loop 위의 방법은 v의 각 원소의 복사값이 e에 들어감. 따라서 for문 내에서 e를 바꿔도 원본 v에는 아무런 영향이 없음 그러나 아래의 방법은 v의 각 원소의 _참조_를 통해 e에 들어감. 따라서 for문 내에서 e를 바꾸면 원본 v의 값이 바뀜.

이 방법은 나중에 배울 list, map, set에도 지원.

만약 위 방법이 익숙치 않으면, 2번 3번을 사용해도 됨.

그러나 3번처럼 사용하면 안됨. vector의 size는 unsigned int나 unsigned long long을 반환함 만약 v가 빈 벡터일 경우, unsigned int 0에서 1을 뺴는 것이므로, -1이 아닌 4294967295이 됨. unsigned int overflow가 발생함.(런타임에러)

4. Q&A

-

5. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x03강 - 배열' : 'Jinhan's Note' 중 'Theme 02. STL 자료구조 _ array, vector'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I' : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 II' : 'Jinhan's Note' 중 'Theme 01. 입출력 _ cin, cout' : 'Jinhan's Note' 중 'Theme 01. 입출력 _ stringstream' : 'Jinhan's Note' 중 'Theme 01. 입출력 _ FastIO'

1. 시간, 공간복잡도
2. 정수 자료형
3. 실수 자료형
4. STL과 함수 인자
5. 표준 입출력
6. FastIO
7. Q&A
8. 마치며

1. 시간∙공간복잡도

1) 시간복잡도

• 시간복잡도(Time Complexity) : 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계

  
  

• 빅오표기법(Big-O Notation) : 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법

• 컴퓨터는 1초에 대략 3~5억개의 연산 처리 가능

(출처: '바킹독'님의 블로그 중 '[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I')

• O(1) : 상수 시간 O(lg N) : 로그 시간 O(N) : 선형 시간 lgN이나 N의 거듭제곱끼리의 곱 : 다항 시간 O(2ⁿ) : 지수 시간

• 지수 시간은 N이 25이하 정도로 굉장히 작은게 아니면 시간 제한을 통과하기 힘듦 팩토리얼은 지수 시간보다 훨씬 가파르기 때문에, 11이하 정도로 굉장히 작은게 아니면 시간 제한을 통과하기 힘듦

+ |N의 크기|허용 시간복잡도| |:-----:|:------------:| |N ≤ 11|O(N!)| |N ≤ 25|O(2ⁿ)| |N ≤ 100|O(N⁴)| |N ≤ 500|O(N³)| |N ≤ 3,000|O(N²lgN)| |N ≤ 5,000|O(N²)| |N ≤ 1,000,000|O(NlgN)| |N ≤ 10,000,000|O(lgN), O(1)|

문제 1. N 이하의 자연수 중에서 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 함수 func1(int N)을 작성하라. N은 5만 이하의 자연수이다.

int func1(int N){
    int sum = 3*(N/3 * (N/3 + 1))/2 +
              5*(N/5 * (N/5 + 1))/2 -
              15*(N/15 * (N/15 + 1))/2;
    return sum;
}

원래는 1부터 N까지 순회하는 O(N)으로 코드를 작성. 그런데 본문에 O(1)로 할 수 있다는 내용을 참고하여 위 코드로 작성함. (3의 배수의 합) + (5의 배수의 합) - (15의 배수의 합)을 이용

문제 2. 주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성하라. arr의 각 수는 0이상 100 이하이고 N은 100이하이다.

int func2(int n){
    for(int i = 0; i < N; i++){
        for(int j = i+1; j < N; j++){
            if(arr[i] + arr[j] == 100){
                return i;
             }
         }
     }
    return sum;
}

문제 3. N이 제곱수이면 1을 반환하고, 제곱수가 아니면 0을 반환하는 함수 func3(int N)을 작성하라. N은 10억 이하의 자연수이다.

int func3(int N){
    for(int i = 0; i<= N; i++){
        if(i*i == N) return 1;
    }
    return 0;
}

문제 4. N이하의 수 중에서 가장 큰 2의 거듭제곱수를 반환하는 함수 func4(int N)을 작성하라. N은 10억 이하의 자연수이다.

int func4(int N){
    int i = 1;
    while(2 * i <= N) { i *= 2;}
    return i;
}

2) 공간복잡도

• 공간복잡도(Space Complexity) : 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계

• 512MB = 1.2억개의 int

• 보통 코딩테스트의 경우, 공간복잡도의 문제보다는, 시간복잡도 떄문에 문제를 많이 틀림.

2. 정수 자료형

+ |자료형|범위| |-----|----| |unsigned char|02^8-1 (255)| |char|-2^7 ~ 2^7-1 (-128127)| |short|2^15-1(32,767)| |int|-2^31 ~ 2^31-1 (-21억 ~ 21억 사이)| |long long|-2^63 ~ 2^63-1|

• Integer Overflow : 정수형의 자료형으로 표현할 수 있는 수의 범위를 넘어갈 때 발생하는 오류

3. 실수 자료형

• 실수의 저장/연산 과정에서 _반드시 오차가 발생_할 수 밖에 없다. (float는 상대 오차 10^(-6)까지, double은 10^(-15)까지 안전. 즉, 참값이 1인 경우, 1 - 10^(-15)부터 1+10^(-15)사이의 값을 가짐) : 실수자료형은 오차가 필연적으로 발생하므로, 문제에서 절대/상대 오차를 허용한다는 단서를 줌. 없으면 정수에서 해결할 수 있는 문제.

• 두 자료형의 차이가 크기 떄문에, 실수 자료형을 사용해야할 경우 float 대신, _double_형을 써야함!

• double에 _long long 범위의 정수_를 함부로 담으면 안된다.(int는 상관 없음) : double은 유효 숫자가 15자리인데, long long은 최대 19자리니까 1과 1 + 10^18을 구분할 수 없어, 같은 값으로 저장.

• 실수를 비교할 때는 _등호_를 사용하면 안된다. : 0.1 + 0.1 + 0.1 != 0.3

4. STL과 함수 인자

• 함수인자로 숫자/구조체/STL은 값의 복사가 일어나고, 배열은 주소값을 이용

+

bool cmp1(vector<int> v1, vector<int> v2, int idx){
    return v1[idx] > v2[idx];
}

: 해당 코드의 시간복잡도는 O(1)이 아닌, O(N). v1과 v2를 인자로 이용하여 복사본을 만드는 비용이 추가되어야 함.

+

bool cmp2(vector<int>& v1, vector<int>& v2, int idx){
    return v1[idx] > v2[idx];
}

: 해당 코드는 인자를 reference로 사용. 따라서 호출될 때 복사본을 만들지 않고, 참조 대상의 주소 정보만 넘기므로 시간복잡도는 O(1).

5. 표준 입출력

• C++에는 cin, cout함수가 있음.

• cout은 공백을 포함한 문자열을 받을 때 사용하기 힘듦 : 줄바꿈(\n)이 나오기 전까지 입력을 받는다고 명시하기 : gets함수 사용하기. 그러나 보안상의 이유로 제거됨 : _getline_을 사용. 대신 type이 C++ string이어야 함.

• ios::sync_with_stdio(0), cin.tie(0)을 입력해야만, 시간초과를 막을 수 있음.

• ios::sync_with_stdio(0) : 기본적으로 C stream(scanf, printf)와 C++ stream(cin, cout)은 분리되어 있음. 하지만 코드의 출력을 위해 두 stream은 동기화되어 있음. 그러나 만약 두 stream을 동시에 쓰지 않고 하나의 stream만을 사용한다면 굳이 동기화가 필요 없음. (참고로, VS 2017/2019에서는 해당 명령어를 무시하고 무조건 동기화 유지. 하지만 채점 서버는 gcc이므로 차이가 있음)

• cin.tie(0) : cin명령어를 수행하기 전에 cout 버퍼를 비우지 않도록 하는 명령어

• endl 사용하지 않기 : endl은 개행문자(\n)를 출력하고 출력 버퍼를 비우는 명령 : 어차피 judge는 프로그램이 종료될 때 출력이 어떻게 생겼는지로 채점하기 때문에 중간에 버퍼를 비울 필요가 없음

• string stream(istringstream + ostringstream)을 이용하면, 문자열로부터 입력을 받아올 수 있음. 또한 출력값을 문자열로 저장할 수 있음 : istringstream형 변수를 선언한 후, 생성자 또는 str 함수를 이용해 스트림으로 이용할 문자열 이용

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int main(){
    fastio;
    istringstream in_1("123 456 789");
    int n;
    while (in_1 >> n) cout << n << '\n';

    istringstream in_2;
    string s = "hi my name is jinhan", t;
    in_2.str(s);
    cout << in_2.str() << '\n';
    while (in_2 >> t) cout << t << '\n';
}

: ostringstream형 변수를 선언한 뒤 cout처럼 사용

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int main(){
    fastio;
    ostringstream out;
    out << "Hello World!" << "\n";
    out << setw(5) << setfill('0') << 123 << "\n";
    out << fixed << setprecision(10) << 123.456789 << "\n";
    string s = out.str();
    cout << s << "\n";
}

6. FastIO

• cin, cout은 scanf, printf보다 빠르지만 그래도 느림 : 1) 입력, 출력 외에 다른 기능을 제공하기 위해 추가적 연산 수행. 2) 일반적인 경우의 입력을 위해 작성되었기 때문에 모든 case를 고려함(ex 0 이상의 정수가 입력될 때 -를 확인). 3) 입출력 버퍼의 크기가 작음 : 1, 2번은 어쩔 수 없지만, _3번은 개선_할 수 있음

• 3번은 방법은, 더 큰 char[] 버퍼에 입∙출력값을 한 번에 많이 읽고 보내면 됨. : 이 때 char 배열에 보내고 읽을 떄 read, write와 같은 Low-Level I/O 함수가 사용됨 : 하지만, cin, cout과 같이 다양한 자료형을 처리하는 기능은 결여. 따라서 직접 파싱하면서 자료형을 변환해야 함(밑의 코드는 이 과정을 구현한 코드. 따라서 코드 최상단에 복붙하여 사용하면, cin, cout이 mmap, wrtie로 구현된 빠른 입출력 함수로 대체)

  #include <bits/stdc++.h>
  #include <sys/stat.h>
  #include <sys/mman.h>
  #include <unistd.h>
  using namespace std;
  

///////////////////////////////////////////////////////////////////////////////////////////// /*

• Author : jinhan814
• Date : 2021-05-06
• Source : https://blog.naver.com/jinhan814/222266396476
• Description : FastIO implementation for cin, cout. (mmap ver.)
• / constexpr int SZ = 1 << 20;

class INPUT { private: char* p; bool END_FLAG, GETLINE_FLAG; public: explicit operator bool() { return !END_FLAG; } INPUT() { struct stat st; fstat(0, &st); p = (char*)mmap(0, st.st_size, PROT_READ, MAP_SHARED, 0, 0); } bool IsBlank(char c) { return c == ' ' || c == '\n'; } bool IsEnd(char c) { return c == '\0'; } char ReadChar() { return *p++; } char ReadChar() { char ret = ReadChar(); for (; IsBlank(ret); ret = _ReadChar()); return ret; } template T ReadInt() { T ret = 0; char cur = _ReadChar(); bool flag = 0; for (; IsBlank(cur); cur = _ReadChar()); if (cur == '-') flag = 1, cur = _ReadChar(); for (; !IsBlank(cur) && !IsEnd(cur); cur = _ReadChar()) ret = 10 * ret + (cur & 15); if (IsEnd(cur)) __END_FLAG = 1; return flag ? -ret : ret; } string ReadString() { string ret; char cur = ReadChar(); for (; IsBlank(cur); cur = ReadChar()); for (; !IsBlank(cur) && !IsEnd(cur); cur = _ReadChar()) ret.push_back(cur); if (IsEnd(cur)) __END_FLAG = 1; return ret; } double ReadDouble() { string ret = ReadString(); return stod(ret); } string getline() { string ret; char cur = ReadChar(); for (; cur != '\n' && !IsEnd(cur); cur = ReadChar()) ret.push_back(cur); if (__GETLINE_FLAG) END_FLAG = 1; if (IsEnd(cur)) GETLINE_FLAG = 1; return ret; } friend INPUT& getline(INPUT& in, string& s) { s = in.getline(); return in; } } _in;

class OUTPUT { private: char write_buf[SZ]; int write_idx; public: ~OUTPUT() { Flush(); } explicit operator bool() { return 1; } void Flush() { write(1, write_buf, write_idx); write_idx = 0; } void WriteChar(char c) { if (write_idx == SZ) Flush(); write_buf[write_idx++] = c; } template int GetSize(T n) { int ret = 1; for (n = n >= 0 ? n : -n; n >= 10; n /= 10) ret++; return ret; } template void WriteInt(T n) { int sz = GetSize(n); if (write_idx + sz >= SZ) Flush(); if (n < 0) write_buf[write_idx++] = '-', n = -n; for (int i = sz; i --> 0; n /= 10) write_buf[write_idx + i] = n % 10 | 48; write_idx += sz; } void WriteString(string s) { for (auto& c : s) WriteChar(c); } void WriteDouble(double d) { WriteString(to_string(d)); } } _out;

/* operators / INPUT& operator>> (INPUT& in, char& i) { i = in.ReadChar(); return in; } INPUT& operator>> (INPUT& in, string& i) { i = in.ReadString(); return in; } template<typename T, typename std::enable_if_t<is_arithmetic_v> = nullptr> INPUT& operator>> (INPUT& in, T& i) { if constexpr (is_floating_point_v) i = in.ReadDouble(); else if constexpr (is_integral_v) i = in.ReadInt(); return in; }

OUTPUT& operator<< (OUTPUT& out, char i) { out.WriteChar(i); return out; } OUTPUT& operator<< (OUTPUT& out, string i) { out.WriteString(i); return out; } template<typename T, typename std::enable_if_t<is_arithmetic_v>* = nullptr> OUTPUT& operator<< (OUTPUT& out, T i) { if constexpr (is_floating_point_v) out.WriteDouble(i); else if constexpr (is_integral_v) out.WriteInt(i); return out; }

/* macros */ #define fastio 1 #define cin _in #define cout _out #define istream INPUT #define ostream OUTPUT /////////////////////////////////////////////////////////////////////////////////////////////

```

7. Q&A

-

8. 마치며

이번에는 자료구조&알고리즘 입니다.

사실 책을 사야하나 아님 온라인 강의를 사서 들어봐야 하나 고민하고 있었는데...

정말 좋은 블로그를 발견했습니다.

1. '바킹독'님 블로그
2. 'Jinhan's Note'님 블로그

입니다.

이 두 분의 글들을 참고하며 알고리즘 공부를 해보려고 합니다.

두 분의 강의는 정말 자세하고 저같은 초보자가 이해하기 큰 무리 없이 정말 섬세하게 구성되어 있습니다. (감동ㅠㅠ) 그리고 각 강의마다 백준 연습문제들도 직접 선정해서 제공해주고 있습니다. 그리고 다 무료!!!!!!!!!!!!!!!!!!!!!!!!!! 진짜 들숨에 무한한 건강과 날숨에 엄청난 재력을 얻으시길...(매일 밤마다 기도할게용😉)

두 분의 커리큘럼(?)도 비슷하고 워낙 유명하신 분들이라 신뢰감이 뿜뿜하네요😎

또 열심히 해보겠습니다!!

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I' : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 II' : 'Jinhan's Note' 중 'Theme 01. 입출력 _ cin, cout' : 'Jinhan's Note' 중 'Theme 01. 입출력 _ stringstream' : 'Jinhan's Note' 중 'Theme 01. 입출력 _ FastIO'

첫번째 강의을 시작한게 22/10/18이네요. 두달 조금 넘게 공부했습니다.

사실 중간중간 놀고 쉬고 한 거 생각하면, 두 달을 안채우고도 마무리 할 수 있었을텐데.... 뭐 지나갔으니 어쩔 수 없죠😂

비교적 쉽고 기초적인 내용으로 구성된 첫 번쨰 로드맵이었지만, 공부하는 동안 얼마나 힘들었는지 모릅니다... 정말 구글링하면서 짜증도 나고 욕도 하고(ㅎㅎ...) 후회도 하고 좌절도 하고 그랬네요..

사실 로드맵을 완주한 지금도 모든 내용이 완전하게 숙지된 것은 아닙니다. 아마 "아 이런 것들이 있구나!" 정도죠.

그래도 뒤를 돌아보면, 미약하지만 발전이 눈에 보이기도 합니다. 정말 아무것도 몰랐던 해킹에 대해, 어떻게 공부를 해야하는지 조차 몰랐던 해킹에 대해, 나름 조금씩이나마 파악하고 공부하고 있는 중이라는 것은 저한텐 엄청난 발전이라고 생각합니다. (그렇게나마 생각해야 안 우울할 거 같아요😊)

_드림핵_이라는 사이트를 몰랐다면 정말 여기까지 할 수 없었을겁니다. 지금까지 시작도 못하고 있을 수도 있겠네요. 드림핵을 만들어준 개발자분들에게 정말 절이라도 하고 싶습니다🐶 그리고 이 사이트를 발견하고 공부를 시작해보자라는 마음을 먹은 과거의 저에게도 맛있는 걸 하나 주고 싶군요 (오늘도 이렇게 다이어트는 미룹니다. 그딴 거 알 바 아니죠😎)

이제는 무엇을 공부할지 사실 고민 중입니다. 시스템 해킹 두 번째 로드맵을 할까 아님 알고리즘을 공부할까 아님 웹 해킹을 공부할까....

사실 시스템 해킹 두 번째 로드맵을 공부해보고 싶습니다만, 몇 달 있으면 복학을 하기 때문에 알고리즘도 공부해야 할 것 같습니다...

그래서 아마 시스템 해킹 두 번째 로드맵과 알고리즘을 병행하지 않을까 생각합니다. (한 번 해보고 너무 힘들면 하나만 하겠죠? 그건 미래의 저한테 맡깁니다.)

해킹이라는 막연한 분야를 손쉽게 큰 장벽 없이 공부할 수 있게 해준 드림핵과, 지금껏 힘들지만 고생해준 과거의 저에게 감사하고, 앞으로 더 고생해줄 드림핵과 저에게 화이팅을 주고 싶네용😊

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : 'DreamHack' 중 'System Hacking' 중 'Logical Bug: Path Traversal'

1. 서론
2. 리눅스 경로
3. Path Traversal
4. Q&A
5. 마치며

1. 서론

리눅스 프로그램은 파일 시스템에 접근하여 어떤 파일의 데이터를 읽거나, 파일에 데이터를 쓸 수 있습니다. 예를 들어, 리눅스의 기본 유틸리티인 cat으로 파일의 데이터를 출력하게 하면, cat은 파일을 열고, 읽은 다음에 stdout에 데이터를 출력합니다.

로컬 파일 시스템에 접근하는 서비스를 외부에 공개할 때는 접근할 수 있는 파일의 경로에 제한을 두어야 합니다. 예를 들어, 사용자에게 각자의 디렉토리를 생성해주고, 그 디렉토리를 자유롭게 활용할 수 있게 해주는 서비스가 있다고 합시다. 이런 서비스를 개발할 때는 당연히 사용자 자신의 디렉토리만 접근할 수 있게 해야 합니다. 악의적인 사용자가 다른 사용자의 디렉토리에 접근하면 악용이 될 수 있기 때문이죠.

'Path Traversal'은 위와 같은 서비스가 있을 때, _사용자가 허용되지 않은 경로에 접근할 수 있는 취약점_을 말합니다. _사용자가 접근하려는 경로에 대한 검사가 미흡_하여 발생하며, 임의 파일 읽기 및 쓰기의 수단으로 활용될 수 있습니다.

2. 리눅스의 경로

리눅스에는 파일의 경로를 지정하는 두 가지 방법으로

1. 절대 경로(Absolute Path)
2. 상대 경로(Relative Path)

두 가지가 있습니다.

1) 절대 경로(Absolute Path)

• 절대 경로(Absolute Path) : 루트 디렉토리(/)부터 파일에 이를 때까지 거쳐야 하는 디렉토리 명을 모두 연결하여 구성 : 각 디렉토리는 /로 구분되며, 끝에 대상 파일의 이름을 추가하여 완성

리눅스 파일 시스템에서, 한 파일에 대응되는 절대 경로는 유일하며, 그 파일만의 고유한 값입니다. 그래서 현재 사용자가 어떤 디렉토리에 있더라도, 절대 경로를 사용하면 대상 파일을 가리킬 수 있습니다.

/a/b/target

2) 상대 경로(Relative Path)

• 상대 경로(Relative Path) : 현재 디렉토리를 기준으로, 다른 파일에 이르는 경로를 상대적으로 표현한 것 : 리눅스에서 ..은 이전 디렉토리, .은 현재 디렉토리를 의미하고, 이를 이용하여 상대 경로를 구성

절대 경로와 다르게, 어떤 파일을 가리키는 상대 경로의 수는 무한합니다.

../c/target
../../../a/b/c/target

3. Path Traversal

• Path Traversal : 권한이 없는 경로에 프로세스가 접근할 수 있는 취약점

여기서의 '권한'은 리눅스 파일 시스템에서의 권한이 아닌, _서비스 로직 관점에서의 권한_을 의미합니다. (앞서 서론에서 예시로 든 예제에서 알 수 있습니다.)

아래의 예시는 Path Traversal 취약점이 있는 예제 코드입니다.

// Name: path_traversal.c
// Compile: gcc -o path_traversal path_traversal.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int kMaxNameLen = 0x100;
const int kMaxPathLen = 0x200;
const int kMaxDataLen = 0x1000;
const char *kBasepath = "/tmp";

int main() {
  char file_name[kMaxNameLen];
  char file_path[kMaxPathLen];
  char data[kMaxDataLen];
  FILE *fp = NULL;

  // Initialize local variables
  memset(file_name, '\0', kMaxNameLen);
  memset(file_path, '\0', kMaxPathLen);
  memset(data, '\0', kMaxDataLen);

  // Receive input from user
  printf("File name: ");
  fgets(file_name, kMaxNameLen, stdin);

  // Trim trailing new line
  file_name[strcspn(file_name, "\n")] = '\0';

  // Construct the `file_path`
  snprintf(file_path, kMaxPathLen, "%s/%s", kBasepath, file_name);

  // Read the file and print its content
  if ((fp = fopen(file_path, "r")) == NULL) {
    fprintf(stderr, "No file named %s", file_name);
    return -1;
  }

  fgets(data, kMaxDataLen, fp);
  printf("%s", data);

  fclose(fp);

  return 0;
}

위의 코드에서 /etc/passwd라는 파일을 읽기 위해서는 파일 이름이 ../etc/passwd가 되면 됩니다.

이를 통해 알 수 있듯이, Path Traversal은 서버의 중요한 데이터를 공격자에게 노출시키는 취약점입니다. 만약 파일에 데이터를 쓸 수 있다면, /etc/passwd를 조작하여 root의 비밀번호를 제거하거나 ssh의 설정을 변경하는 등 서버에 위협되는 행위도 할 수 있습니다.

4. Q&A

-

5. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : 'DreamHack' 중 'System Hacking' 중 'Logical Bug: Path Traversal'

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : 'DreamHack' 중 'System Hacking' 중 'Logical Bug: Command Injection'

1. 서론
2. Command Injection
3. Q&A
4. 마치며

1. 서론

프로그램을 만들다보면 스스로 코드를 작성하기보다, 이미 설치된 소프트웨어를 사용하는 것이 필요한 경우가 있습니다.

C/C++으로 프로그래밍할 때는 system함수를 사용하기도 합니다. 이 함수는 함수에 전달된 인자를 셸 프로그램에 전달해 명령어를 실행시킵니다. system("cat /etc/passwd")를 호출하면, 셸 프로그램으로 cat /etc/passwd를 실행한 것과 같습니다.

이러한 이점도 있지만, 그와 동시에 함수의 인자를 셸 명령어로 전달한다는 점에서 치명적인 취약점으로 이어지기도 합니다.

2. Command Injection

• 인젝션(Injection) : 악의적인 데이터를 프로그램에 입력하여, 이를 시스템 명령어, 코드, 데이터베이스 쿼리 등으로 실행되게 하는 기법 : 이 중, 사용자의 입력을 시스템 명령어로 실행하게 하는 것을 'Command Injection'이라고 함

Command Injection은 명령어를 실행하는 함수에 사용자가 임의의 인자를 전달할 수 있을 때 발생합니다. 사용자가 입력한 임의 IP에 ping을 전송하고 싶다면 system("ping [user-input]"), 임의 파일을 읽고 싶다면 system("cat [user-input]")등의 형태로 system함수를 사용할 수 있습니다.

하지만, 이러한 호출 과정에서 _사용자의 입력을 제대로 검사하지 않으면 임의 명령어가 실행_될 수도 있습니다. 이는 리눅스 셸 프로그램이 지원하는 여러 메타 문자 때문입니다.

system함수는 셸 프로그램에 명령어를 전달하여 실행합니다. 셸 프로그램은 다양한 메타 문자를 지원하기도 하죠.

아래의 예제에서는, 사용자가 입력한 IP를 ping의 인자로 전달합니다. (ping은 특정 IP의 서버가 작동하는지 확인하려고 자주 사용합니다.)

// Name: cmdi.c
// Compile: gcc -o cmdi cmdi.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int kMaxIpLen = 36;
const int kMaxCmdLen = 256;

int main() {
  char ip[kMaxIpLen];
  char cmd[kMaxCmdLen];

  // Initialize local vars
  memset(ip, '\0', kMaxIpLen);
  memset(cmd, '\0', kMaxCmdLen);
  strcpy(cmd, "ping -c 2 ");

  // Input IP
  printf("Health Check\n");
  printf("IP: ");
  fgets(ip, kMaxIpLen, stdin);

  // Construct command
  strncat(cmd, ip, kMaxCmdLen);
  printf("Execute: %s\n",cmd);

  // Do health-check
  system(cmd);
  return 0;
}

IP로 127.0.0.1을 입력하면 다음과 같이 작동합니다.

$ ./cmdi
Health Check
IP: 127.0.0.1
Execute: ping -c 2 127.0.0.1

PING 127.0.0.1 (127.0.0.1) 56(84) bytes of data.
64 bytes from 127.0.0.1: icmp_seq=1 ttl=64 time=0.019 ms
64 bytes from 127.0.0.1: icmp_seq=2 ttl=64 time=0.032 ms

--- 127.0.0.1 ping statistics ---
2 packets transmitted, 2 received, 0% packet loss, time 1065ms
rtt min/avg/max/mdev = 0.019/0.025/0.032/0.008 ms

만약, 악의적인 사용자라고 하면, 코드 상에서 아무런 검사가 없다는 점을 파악해 Command Injection을 시도할 수 있습니다.

다음은 ;를 메타문자로 사용하여 셸을 실행시키는 예제입니다. ping이 정상적으로 실행된 후, /bin/sh가 이어서 실행됩니다.

$ ./cmdi
Health Check
IP: 127.0.0.1; /bin/sh
Execute: ping -c 2 127.0.0.1; /bin/sh

PING 127.0.0.1 (127.0.0.1) 56(84) bytes of data.
64 bytes from 127.0.0.1: icmp_seq=1 ttl=64 time=0.020 ms
64 bytes from 127.0.0.1: icmp_seq=2 ttl=64 time=0.046 ms

--- 127.0.0.1 ping statistics ---
2 packets transmitted, 2 received, 0% packet loss, time 1059ms
rtt min/avg/max/mdev = 0.020/0.033/0.046/0.013 ms

$ id
uid=1000(dreamhack) gid=1000(dreamhack) groups=1000(dreamhack)

따라서 개발자는 이러한 취약점을 막기 위해, 입력값에 대해 _메타 문자의 유무를 철저히 검사_해야합니다. 또한, 꼭 필요한 상황이 아니면 _system과 같은 함수의 사용을 자제_해야 합니다. 이러한 함수는 memory corruption과 관련된 익스플로잇에도 사용될 수 있기 때문입니다.

3. Q&A

-

4. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용 : 'DreamHack' 중 'System Hacking' 중 'Logical Bug: Command Injection'