[알고리즘 트레이닝] 2장. 프로그래밍 기법(2)

2.1.3 코드 짧게 만들기

자료형

typedef 명령어 이용

• long long 을 ll로 사용할 수 있다.

typedef long long ll;

long long a = 123456789;
ll a = 123456789;

복잡한 자료 형에서도 사용

typedef vector<int> vi;
typedef pair<int, int> pi;

매크로

#define지시문을 이용

코드를 컴파일 하기 전에 코드에 포함된 특정 문자열을 다른 문자열로 치환하는 규칙

#define F first
#define S second
#define PB push_back
#define MP make_pair

// 사용전
v.push_back(make_pair(y1, x1));
v.push_back(make_pair(y2, x2));
int d = v[i].first+v[i].second;

// 사용후
v.PB(MP(y1, x1));
v.PB(MP(y2, x2));
int d = v[i].F + v[i].S;

매크로 인자를 주는 경우

#define REP(i,a,b) for (int i = a; i <= b; i++)

// 사용전
for (int i = 1; i <=n; i++){
    search(i);
}

// 사용후
REP(i, 1, n){
    search(i);
}

---

2.2 재귀형 알고리즘

2.2.1 부분집합 생성하기

원소가 n개인 집합의 모든 부분집합을 생성하는 알고리즘을 살펴보자.

vector<int> subset; // 각 부분집합의 원소 저장

void search(int k){
    if(k== n+1){
        // 부분집합을 처리한다
    } else {
        // k 를 부분집합에 포함시킨다
        subset.push_back(k);
        search(k+1);
        subset.pop_back();
        //k를 부분집합에 포함시키지 않는다
        search(k+1);
    }
}

search 함수의 인자가 k일 때, 이 함수는 원소 k를 부분집합(subset)에 포함할지, 아니면 포함하지 않을지를 결정한다.

2.2.2 순열 생성하기

원소가 n개인 집합의 모든 순열을 생성하는 알고리즘이다.

• 함수를 호출 할 때마 새로운 원소를 순열에 추가하고 그 원소를 선택 여부를 chosen에 기록

vector<int> permutation; // 각 순열 저장
bool chosen[n+1]; // 각 원소를 순열에 포함했는지 여부 확인

void search(){
ir(permutation.size() == n){
    //순열을 처리한다.
} else{
    for(int i = 1; i <=n; i++){
        if(chosen[i]) continue;
        chosen[i] = true;
        permutation.push_back(i);
        search();
        chosen[i] = false;
        permutation.pop_back();
    }
  }
}

C++ 표준 라이브러리 순열

for (int i = 0; i <=n ;i ++){
    permutation.push_back(i);
}

do{
    // 순열처리
} while(next_permutation.begin(), permutation.end());

2.2.3 퇴각 검색

퇴각 검색(Backtracking) 은 비어 있는 해로 탐색을 시작하고, 단계마다 해를 확장해 나가는 방식의 알고리즘이다. 탐색과정에서 해를 생성하는 모든 방법을 재귀적으로 하나하나 살펴본다

nxn 인 체스판에 n개의 퀸을 서로 공격할 수 없도록 배치하는 방법

void search(int y){
    if (y == n){
        count ++; // 해의 개수
        return;
    }
    for (int x = 0; x < n ; x++){ // 해와 열의 번호가 0부터 n-1까지라고 가정
        if (col[x] || diag1[x+y] || diag2[x-y+n-1]) continue;
        col[x] = diag1[x+y] = diag2[x-y+n-1] = 1;
        search(y+1);
        col[x] = diag1[x+y] = diag2[x-y+n-1] = 0;
    }
}

• search(0)을 호출하면 탐색이 시작된다.
• 배열 col은 퀸이 포함된 열을 추적하기 위한 것이고, 배열 diag1, diag2 는 대각선을 추적하기 위한 것이다.
• 퀸은 이미 배치된 열, 혹은 대각선에 퀸을 추가로 배치할수는 없다.
• n이 증가할 때마다 가능한 방법의 수가 지수적으로 증가하기 때문에 탐색은 급격히 느려진다.

2.3 비트 연산

2.3.1 비트 연산

프로그램에서 사용되는 n비트 정수는 내부적으로 n개의 비트로 이루어진 이진수 형태로 저장된다.

C++ 의 int 는 32bit 자료형이며, 이는 모든 int 형 정수가 32개의 비트로 이루어진다는 의미이다.

• 부호가 있는 정수표현에서 제일 왼쪽 비트는 부호를 나타낸다.
  • 0은 음이 아닌 정수
  • 1은 음의 정수
• 부호가 없는 정수 표현은 음수가 아닌 정수만 표현 할 수 있지만, 더 큰 수 표현이 가능하다.

And 연산

x& y : x 와 y 에 공통으로 비트 1이 들어간 위치에 1이 들어있는 정수

Or 연산

x | y : x와 y 중 하나에라도 비트 1이 들어간 위치에 1이 들어 있는 정수

Xor 연산

x^ y : x와 y 중 딱 하나에만 비트 1이 들어간 위치에 1이 들어있는 정수

Not 연산

~x : x의 모든 비트를 뒤집어 놓은 정수

비트 시프트 연산

x << k : 오른쪽에 비트 0을 k개 덧붙이는 연산, x *( 2^k)

x >> k : 오른쪽에 비트 0을 k개를 제거하는 연산, x / (2^k) 후 정수내림

비트 마스크

비트 마스크 1 << k 번째 위치(1을 k번째로 민다.)에만 비트 1이 있고, 나머지 위치에는 비트 0이 있는 정수

비트 마스크를 사용하면 정수의 특정한 비트 하나에 접근할 수 있게 된다.

int 형 정수 x의 비트 표현을 출력하는 코드

for(int k = 31; k >=0; k--)
{
    if (x&(1<<k)) cout << "1";
    else cout << "0";
}

정수 x의 k번째 비트를 1로 바꾸는 공식

x|(1<<k)

정수 x의 k번째 비트를 0으로 바꾸는 공식

x&(1<<k)

정수 x의 k번째 비트를 뒤집는 공식

x^(1<<k)

정수 x의 가장 오른쪽 비트 1을 0으로 바꾸는 공식

x&(x-1)

정수 x의 모든 비트를 0으로 바꾸되 비트 1중에서 제일 오른쪽 것만 남기는 공식

x&-x

마지막 비트 1 다음에 나오는 모든 비트를 뒤집는 공식

x|(x-1)

양의 정수 x에 대해

x&(x-1) = 0

이면 x는 2의 거듭제곱이다.

비트 마스크를 사용할 때 주의할 점 중 하나는 1 << k 이 항상 int 형이라는 것이다.

long long 형 비트마스크를 사용하는 간단한 방법은 1LL << k를 이용하는 것이다.

그 외의 기능

g++ 컴파일러는 비트 수를 셀 때 사용할 수 있는 다음과 같은 함수를 제공한다.

이 함수들은 int 형만 지원한다.

함수 이름 뒤에 ll을 덧붙이면 long long 정수를 지원하는 함수로 이용할 수 있다.

• __builtin_clz(x) : 비트 표현의 왼쪽에 연속해서 있는 비트 0의 개수
• __builtin_ctz(x): 비트 표현의 오른쪽에 연속해서 있는 비트 0의 개수
• __builtin_popcount(x): 비트 표현에서 비트 1의 개수
• __builtin_parity(x): 비트 표현에서 비트 1의 개수에 대한 패리티(짝수 또는 홀수)

2.3.2 집합 표현하기

집합에 대한 연산

C++ 비트셋