test

 test

Far Manager 세팅

1. SourceForge에서 mingw-w64 설치. 인터넷 다운로드 방식으로 받으면 에러가 뜨면서 안되는 경우가 많아서 직접 압축 파일로 받은 후, C 드라이브나 본인이 원하는 곳에 mingw-w64라는 이름의 폴더를 만든 후 그 안에 압축을 해제. 그리고 환경 변수에 압축을 해제한 곳에 있는 bin 폴더를 등록해준다.

2. Far Manager 및 Conemu 설치

3. True Template 3을 다운로드 받고(암호: yldbear), Far Manager가 설치된 폴더 - Plugins에 TrueTemplate 이름으로 폴더를 하나 만들고 그 곳에 압축 해제

4. Far Manager의 Option - Editor settings에서 탭 사이즈 4, 자동 들여쓰기 체크 그리고 Save Setup을 해줘야 설정이 저장됨

5. Commands - File associations에서 *.cpp 추가 후 Execute command 옵션에 g++ 실행 및 원하는 옵션 추가. 현재 사용 중인 옵션: g++ !.cpp -o !.exe -ggdb -DDEBUG -Wl,--stack=268435456 -O2 -std=c++14

6. TrueTemplate - templates - source 폴더에서 Blank.c를 열고 원하는 템플릿으로 수정

Visual C++ DLL 및 MFC 프로젝트 개발 전 준비 관련

개발을 진행하면 헤더(.h)와 소스 파일(.cpp)들을 필요에 따라 계속 만들게 되고, 폴더를 만들고 정리해두면 관리가 용이하고 보기에도 좋다. 사람마다 정리하는 방법이 다르겠지만 나는 아래와 같이 폴더 구조를 만든다.

/[프로젝트명] - 프로젝트 최상위 폴더
  /bin - 실행 파일
  /obj - 빌드 중간 생성 파일
  /include - 헤더 파일 (*.h)
  /src - 소스 파일 (*.cpp)
  /build/[프로젝트명] - *.vcxproj와 같은 프로젝트 설정 파일, 기본 생성되는 *.cpp 및 *.h
  /res - 리소스 파일

  *.sln - 솔루션 파일

현재 directx를 사용한 렌더링 엔진 및 해당 엔진을 사용한 모델 뷰어를 MFC로 개발하고 있다. 그래서 DLL 프로젝트 및 해당 DLL을 사용하는 MFC 프로젝트의 설정 방법을 예로 들어서 정리했다.

1. 폴더 생성 및 파일 이동

위에서 설명한 구조 또는 본인이 원하는 폴더 구조가 있다면 폴더들을 그에 맞게 생성한 후에 각 파일들을 옮겨준다.

2. 솔루션의 프로젝트 제거 및 추가 / 각 필터에서 항목들 모두 제거 후 다시 추가

프로젝트 설정 파일들의 위치를 변경하고 솔루션을 열면 경고창과 함께 프로젝트를 찾을 수 없다고 나오는데, 기존에 로드돼있던 프로젝트를 제거하고 솔루션 위에서 Add - Existing Project을 통해 옮긴 프로젝트 설정 파일을 새로 추가한다. 그리고 솔루션 익스플로러내 각 필터의 항목들은 프로젝트 파일에 위치가 기입돼있다. 폴더 구조를 새로 만들 것 이기 때문에, 해당 작업 이전에 모든 항목을 먼저 제거해야 한다. 제거하지 않으면 폴더 생성 후 이미 옮겨진 파일의 위치와는 다르게 계속 기존 위치를 가리키고 있어서 여러 에러가 발생한다. 프로젝트를 만들면 기본적으로 생성되는 필터들은 Header Files, Resource Files, Source Files가 있는데, 이 필터들과 본인이 추가적으로 만든 필터들이 있다면 그 필터들의 항목들도 두 프로젝트에서 모두 제거 시켜준 후 다시 추가해준다.

3. MFC 프로젝트 솔루션에 DLL 프로젝트 추가

MFC 프로젝트가 포함된 솔루션에 DLL 프로젝트를 추가한다. 솔루션 항목 위에서 마우스 우클릭 - Add - Existing Project로 추가할 수 있다.

4. 프로젝트 설정 변경

빌드 및 원활한 관리를 위해 각 프로젝트의 설정들을 모두 변경해야 한다. 공통적인 변경 사항에 대해 먼저 설명한다. 첫 번째로 프로젝트 속성을 열었을 때, 앞으로 변경할 내용들이 모든 모드에 적용될 수 있도록 All Configuration으로 바꾸는 것이다.
두 번째로 General에서 출력 파일과 중간 생성 파일들의 생성 경로를 설정해야 한다. 특히 출력 파일은 두 프로젝트 모두 동일하게 되도록 설정하는 것이 관리가 편하다. 다만, 경로 이름을 절대적으로 써넣는 것보다 VS에서 제공하는 매크로를 사용하는 것이 매우 유용하다.
세 번째로 C/C++ - General - Additional Include Directories에 폴더 구조에 따라 새로 변경된 헤더 파일들이 들어 있는 폴더 경로를 입력한다. 그리고 만약 솔루션을 빌드하게 된다면 두 프로젝트가 함께 빌드 되는데, MFC 프로젝트에서는 당연히 DLL 프로젝트의 헤더 파일들을 사용하게 됨에 따라 DLL 프로젝트의 헤더 파일 경로가 필요하다. 따라서 MFC 프로젝트 설정에는 DLL 프로젝트의 헤더 파일 경로를 별도로 넣어준다. 필요한 경우에는 리소스 파일을 위해 Resources - General - Additional Include Directories도 수정이 필요하다.
네 번째로 *.lib 파일을 위해서 Linker - General- Additional Library Directories를 입력한다. 두 번째 변경 사항에서 출력 파일 경로를 통일했다고 가정하면 추가 라이브러리 디렉토리는 출력 파일 경로와 동일하게 설정해주면 되고, 출력 파일 경로를 통일하지 않았다면 DLL 프로젝트의 출력 파일 경로와 동일하게 설정해주면 된다. 사용할 *.lib 파일 이름도 Linker - Input - Additional Dependencies에 넣어줄 수 있다. 이게 싫다면 헤더에 #pragma comment(lib, "*.lib")를 넣어줘도 된다.

5. Project Dependencies 관련

DLL 프로젝트보다 MFC 프로젝트가 먼저 빌드되면 빌드 에러가 발생한다. Project - Project Dependencies에서 프로젝트 종속성 설정을 해야 한다.

* Precompiled Headers 관련

1 - 5 과정을 진행하면 아무런 에러 없이 빌드 및 실행이 잘 된다. 그러나 pch.h와 pch.cpp 파일의 위치를 변경하면 빌드 시 매번 에러를 내뱉는다. 아예 미리 컴파일된 헤더 기능을 꺼버릴 수도 있지만, 당장의 해결 방법은 다른 설정은 그대로 두고 pch.cpp의 C/C++ - Precompiled Headers 속성만 Create (/Yc)로 변경해주는 것인데 근본적인 해결 방법은 나중에 다시 알아볼 생각이다.

[참고] https://www.bearpooh.com/63

DirectX 12를 이용한 Model Viewer 개발 시작

DirectX 11을 1년 전에 잠깐 공부하다가 사정이 생겨서 관뒀는데 여유가 생겨서 그래픽 쪽을 다시 공부하고 있다. 

low-level API나 ray tracing에 관심이 없다면 DirectX 12를 공부할 필요는 없다고 듣긴 했지만 11이 나온지도 13년 정도 됐고 그래픽을 계속 공부할 계획이라면 결국 새로운 버전을 익혀야 한다. 따라서 굳이 11을 할 필요는 없을 것 같아서 어려워도 12를 공부하여 모델 뷰어를 개발할 생각이다. 

초기 기능은 fbx 파일만 임포트 가능하게 만들어 모델 및 애니메이션을 화면에 표시해주고 가장 기본적인 라이팅(디퓨즈, 스페큘러, 앰비언트) 정도만 구현할 생각. 개발하면서 블로그에 정리하고 싶은 경우, 일지 형식으로 진행 상황을 가끔 올릴 수도 있을 듯 ...

BOJ 1038: 감소하는 수

* 하나의 정수는 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 집합 내의 숫자로 이루어진다.

* 단조감소는 고려하지 않기 때문에 최대 크기의 수는 9876543210이다.

* 위 집합의 부분집합에서 조건을 만족하는 수는 단 하나: 총 2¹⁰ - 1가지 경우의 수가 존재

* 가능한 수들을 모두 조합하여 cand에 저장하고, 오름차순 정렬

#include <bits/stdc++.h>

using namespace std;

vector<long long> cand;

void dfs(long long num) {

  long long last = num % 10, new_cand = num * 10;

  for(int i = 0; i < last; ++i) {

    cand.push_back(new_cand + i);

    dfs(new_cand + i);

  }

}

int main(void) {

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n;

    cin >> n;

    for(int i = 0; i < 10; ++i) {

      cand.push_back(i);

      dfs(i);

    }

    sort(cand.begin(), cand.end());

    if(n < cand.size()) cout << cand[n] << '\n';

    else cout << "-1\n"; 

    return 0;

}

AtCoder Beginner Contest 172 업솔빙

대회 도중에 많이 고민했는데 못 풀었거나 관심이 생겨서 꼭 해결하고자 하는 문제들의 경우 에디토리얼을 보고 공부하였다. 본인 기준으로 수준이 너무 높다고 생각하여 도움이 되지 않을 것이라 판단한 문제들 혹은 그냥(?) 풀기 귀찮은 문제들은 대회 종료 후 별도로 공부하지 않았다. 업솔빙 관련 글도 올리고 싶은 경우에만 올릴듯.

C. Tsundoku (300 pt)

처음에 greedy 문제인줄 알고 삽질하다가 반례를 하나 발견하고나서 포기했던 문제이다. 풀이법은 구간합(prefix sum)과 탐색이다. a를 A의 구간합 배열, b도 B의 구간합 배열으로 정의하고 아래 방법으로 구한다.

a₀ = 0

a_N = A₁ + A₂ + ··· + A_N = a_N-1 + A_N

그렇다면 우리는 문제의 답을 "a_i + b_j ≤ K를 만족하는 최대의 i + j 값" 으로 생각할 수 있다. 이제, 조건을 만족하는 (i, j) 쌍을 어떻게 찾을 것인가? 완전 탐색은 시간 복잡도가 O(NM) 이므로 TLE가 날 것이다. 이렇게 시도해보자. i가 0일 때 b_j ≤ K - a_i 조건에 맞춰서 최대의 j 값을 찾는 상황을 가정하면, j = M, M - 1, M - 2, ... 순으로 탐색할 것이며 이때 탐색된 j 값을 best라고 하자. K는 조건 상 반드시 양수이며, 구간합 배열 a와 b는 단조 증가한다. 그렇다면, i가 1일때 최대의 j 값은 반드시 best 미만일 것이다. 이렇게 완전 탐색을 피해갈 수 있으며 시간복잡도 O(N + M) 내로 정답을 구할 수 있다. i와 j의 경우를 바꿔서 생각해도 동일하다.

#include <bits/stdc++.h>

using namespace std;

int main(void) {

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n, m, k;

    cin >> n >> m >> k;

    long long apsum[200001] = {0}, bpsum[200001] = {0};

    for(int i = 1; i <= n; i++) {

        cin >> apsum[i];

        apsum[i] += apsum[i - 1];

    }

    for(int i = 1; i <= m; i++) {

        cin >> bpsum[i];

        bpsum[i] += bpsum[i - 1];

    }

    long long ans = -1e9, j = m;

    for(int i = 0; i <= n; i++) {

        if(apsum[i] > k) {

            break;

        }

        while(bpsum[j] > k - apsum[i]) {

            j--;

        }

        ans = max(ans, i + j);

    }

    cout << ans << '\n';

    return 0;

}

D. Sum of Divisors (400 pt)

임의의 수 X의 약수의 개수를 O(√X) 내로 구할 수 있지만 정답을 구하기 위해 필요한 연산을 일일이 수행한다면 TLE가 발생한다. 그런데 이 문제는 각 수의 약수의 개수를 구하지 않고도 정답을 구할 수 있다! 문제가 요구하는 수식의 값을 구하는 의사코드는 에디토리얼에 나온 것처럼 아래와 같다.

ans = 0

for i = 1, ..., N:

   for j = 1, ..., N:

     if i % j == 0 then ans += i

print ans

그런데 위 코드는 모든 (i, j) 쌍에 대해 고려하기 때문에 결국 2, 3번째 줄을 바꿔서 아래와 같은 코드를 실행시켜도 같은 결과를 도출한다.

ans = 0

for j = 1, ..., N:

   for i = 1, ..., N:

     if i % j == 0 then ans += i

print ans

위 코드의 동작을 관찰했을 때, "N 이하 모든 j의 배수들의 합을 g(j)으로 정의하면, j = 1, 2, ..., N일 때 모든 g(j)의 합"을 구하는 것으로 이 문제를 다시 정의 해볼 수 있다. g(X)를 구하기 위해서 Y = ⌊N/X⌋ 으로 정의하면, g(X) = X + 2X + ··· + YX = (1 + 2 + ··· + Y)X = Y(Y + 1)X/2 로 표현할 수 있으며, 결국 정답을 O(N) 내로 구할 수 있다.

#include <bits/stdc++.h>

using namespace std;

int main(void) {

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n;

    cin >> n;

    long long ans = 0;

    for(int i = 1; i <= n; i++) {

        long long y = floor(n / i);

        ans += (i * y * (y + 1)) / 2;

    }

    cout << ans << '\n';

    return 0;

}

고등학교를 졸업한 이후로 수학을 하지 않았고 지금까지도 수학적 사고를 전혀 한 적이 없다. 그래서 문제 조건 속에서 수학적 사실을 도출하여 수식을 변형하는 작업이 필요하다거나 수학 지식이 필요한 경우 너무 풀기가 힘들고 자꾸 이상한 방향으로 생각이 빠진다. 계속 문제들을 열심히 풀어서 수학 문제의 경우는 모르는 개념을 하나씩 알아나가고 풀이 방향에 대한 감각을 익혀야 겠다. 물론 업솔빙도 열심히 하고.

LIS를 구하는 두 가지 방법

LIS(Longest Increasing Subsequence) 문제를 해결하기 위하여 잘 알려진 방법으로는 두 가지 방법(동적 계획법, 이진 탐색)이 있다. 여기서 전체 배열의 길이가 n 일때, 동적 계획법을 사용할 경우 시간 복잡도는 O(n²)이며 이진 탐색을 사용할 경우 시간 복잡도는 O(nlog₂n)이다. 세그먼트 트리를 사용해서도 LIS 문제를 해결할 수 있으나 시간 복잡도가 이진 탐색을 사용할 경우와 같으므로 아래에서는 동적 계획법과 이진 탐색만을 각각 사용하여 LIS 문제를 어떻게 해결하는지 살펴보겠다.

1. 동적 계획법

구현하기 가장 쉬우며 n이 그리 크지 않은 경우에만 사용할 수 있다. 길이가 6인 배열 A가 있다고 가정해보자. 그리고 메모이제이션을 위한 배열 dp도 함께 생각해보자. dp의 각 원소는 모두 1로 초기화되어 있다. 아래에서는 동적 계획법을 사용하여 어떻게 문제를 해결하는지에 대해 설명하였다.

A: 10 20 10 30 20 50  /  dp: 1

A의 첫 번째 원소 A₁(10) 앞에는 아무런 원소가 없다. 따라서 아무런 변화가 일어나지 않는다.

A: 10 20 10 30 20 50  /  dp: 1 2

A₂부터는 앞 원소와 크기를 비교해가며 메모이제이션을 진행한다.

A₂(20)의 앞에는 10이 있으며 10 < 20 이므로 "A₁(10)의 부분 수열 길이 + 1"을 저장한다. (1 → 2)

A: 10 20 10 30 20 50  /  dp: 1 2 1

A₁(10)과 비교하면 10 = 10 이므로 아무런 변화가 없다.

A₂(20)과 비교하면 20 > 10 이기 때문에 아무런 변화가 없다.

A: 10 20 10 30 20 50  /  dp: 1 2 1 3

A₁(10)과 비교하면 10 < 30 이므로 "A₁(10)의 부분 수열 길이 + 1"을 저장한다. (1 → 2)

A₂(20)과 비교하면 20 < 30 이므로 "A₂(20)의 부분 수열 길이 + 1"을 저장한다. (2 → 3)

A₃(10)과 비교하면 10 < 30 이지만 현재 dp 값(3)이 "A₃(10)의 부분 수열 길이 + 1"(2)보다 크기 때문에 아무런 변화가 없다.

A: 10 20 10 30 20 50  /  dp: 1 2 1 3 2

A₁(10)과 비교하면 10 < 20 이므로 "A₁(10)의 부분 수열 길이 + 1"을 저장한다. (1 → 2)

A₂(20)과 비교하면 20 = 30 이므로 아무런 변화가 없다.

A₃(10)과 비교하면 10 < 20 이지만 현재 dp 값(2)가 "A₃(10)의 부분 수열 길이 + 1"(2)와 같기 때문에 아무런 변화가 없다.

A₄(30)과 비교하면 30 > 20 이므로 아무런 변화가 없다.

A: 10 20 10 30 20 50  /  dp: 1 2 1 3 2 4

A₁(10)과 비교하면 10 < 50 이므로 "A₁(10)의 부분 수열 길이 + 1"을 저장한다. (1 → 2)

A₂(20)과 비교하면 20 < 50 이므로 "A₂(20)의 부분 수열 길이 + 1"을 저장한다. (2 → 3)

A₃(10)과 비교하면 10 < 50 이지만 현재 dp 값(3)이 "A₃(10)의 부분 수열 길이 + 1"(2)보다 크기 때문에 아무런 변화가 없다.

A₄(30)과 비교하면 30 < 50 이므로 "A₄(30)의 부분 수열 길이 + 1"을 저장한다. (3 → 4)

A₅(20)과 비교하면 20 < 50 이지만 현재 dp 값(4)가 "A₅(20)의 부분 수열 길이 + 1"(3)보다 크기 때문에 아무런 변화가 없다.

for (int i = 1; i <= n; i++) {

    dp[i] = 1;

    for (int j = 1; j < i; j++) {

        if (A[j] < A[i]) {

            dp[i] = max(dp[i], dp[j] + 1);

        }

    }

    ans = max(ans, dp[i]);

}

cout << ans << '\n';

최종적으로 dp 배열에서 가장 큰 값인 4가 최장 증가 수열의 길이 값이다.

2. 이진 탐색
위 1번 방법으로 LIS 풀이를 시도하면 LIS의 길이 값은 얻을 수 있지만, LIS를 구성하는 실제 원소들은 얻을 수 없다. 그리고 n이 10000이 넘어가기 시작하면 빠른 시간 내에 답을 얻기가 힘들다. 이진 탐색을 사용하면 시간 복잡도를 O(nlog₂n)으로 줄이면서 실제 LIS도 얻을 수 있다. 실제 LIS를 얻을 수 있으므로 LIS 길이 값은 당연히 따라온다. 1번 방법때처럼 길이가 6인 배열 A가 있다고 가정하며 메모이제이션을 위한 벡터 dp도 함께 생각해보자. dp는 처음에 완전히 비어있는 벡터이다. 아래에서는 이진 탐색을 사용하여 어떻게 문제를 해결하는지에 대해 설명하였다.

LIS의 길이를 구하기 위해서 배열 A의 각 원소 A_i를 처음부터 끝까지 훑으며 아래의 조건에 따라 dp 벡터에 값을 넣는다.

1) dp 벡터의 맨 끝값이 A_i 미만인 경우 → dp 벡터의 맨 끝에 A_i를 삽입

2) dp 벡터의 맨 끝값이 A_i 이상인 경우 → dp 벡터의 lower_bound(A_i) 자리에 A_i를 삽입

A: 10 20 10 30 20 50  /  dp: 10

A: 10 20 10 30 20 50  /  dp: 10 20

A: 10 20 10 30 20 50  /  dp: 10 20

A: 10 20 10 30 20 50  /  dp: 10 20 30

A: 10 20 10 30 20 50  /  dp: 10 20 30

A: 10 20 10 30 20 50  /  dp: 10 20 30 50

최종적으로 dp 벡터의 길이 값(4)가 최장 증가 수열의 길이 값이다. 다만, dp 벡터의 내용(10, 20, 30, 50)이 반드시 LIS는 아니다. 왜냐하면, dp 벡터의 중간에 위치한 값들은 배열 A의 끝에 도달하기 전에 계속해서 바뀔 수 있기 때문이다. 위의 예에서는 운이 좋아서 실제 LIS가 도출되었지만 실제로는 위의 방법만으로 LIS를 구할 수 없다. 즉, 추가적인 과정이 필요하다. dp 벡터에 새로운 값이 들어갈 때 바로 앞 원소의 인덱스를 저장하는 backtrace 벡터를 새로 생성한다. 이후 dp 벡터에 새로운 값을 넣을 때 자신의 앞 원소의 인덱스를 backtrace 벡터에 저장하면 된다.

#include <bits/stdc++.h>

using namespace std;

bool cmp(const pair<int, int>& a, const pair<int, int>& b) {

    return a.first < b.first;

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n;

    cin >> n;

    vector<pair<int, int>> A;

    for (int i = 0; i < n; i++) {

        int tmp;

        cin >> tmp;

        A.push_back({ tmp, i });

    }

    const int max_sz = 1e6 + 1;

    vector<pair<int, int>> dp(1, { -2e9, -1 });

    vector<int> backtrace(max_sz, -1);

    for (auto& p : A) {

        if (dp.back().first < p.first) {

            backtrace[p.second] = dp.back().second;

            dp.push_back(p);

        }

        else {

            auto iter = lower_bound(dp.begin(), dp.end(), p, cmp);

            backtrace[p.second] = (iter - 1)->second;

            *iter = p;

        }

    }

    cout << dp.size() - 1 << '\n';

    vector<int> ans;

    for (int i = dp.back().second; i >= 0; i = backtrace[i]) {

        ans.push_back(A[i].first);

    }

    for (int i = ans.size() - 1; i >= 0; i--) {

        cout << ans[i] << ' ';

    }

    cout << '\n';

    return 0;

}

이런 방법이 가능한 이유는 dp 배열에 A_i가 삽입되는 자리의 바로 앞 값을 끝으로 하는 가장 긴 수열이 backtrace 벡터에 저장된 인덱스를 따라 이어져 있을 것이기 때문이다.

연쇄 행렬 곱셈 (Matrix chain multiplication)

행렬곱은 어떤 방향으로 결합하느냐에 따라 필요한 곱셈 횟수가 달라진다. 예를 들어, 크기가 각각 A = 2 x 5, B = 5 x 3, C = 3 x 4인 행렬이 있는 경우 A의 행과 열을 d₀, d₁, B의 행과 열을 d₁, d₂, C의 행과 열을 d₂, d₃으로 정의한다면 A(BC)와 (AB)C의 곱 연산 횟수는 아래와 같으며 곱 연산의 최소 횟수는 54이다.

A(BC) = d₀d₁d₃ + d₁d₂d₃ = 40 + 60 = 100

(AB)C = d₀d₁d₂ + d₀d₂d₃ = 30 + 24 = 54

동적 계획법을 이용하면 행렬의 개수가 n일때 수행될 곱 연산의 최소 횟수를 시간복잡도 O(n³)이내에 구할 수 있다. 점화식은 아래와 같다. dp[i][j]는 행렬 i에서 j까지 곱 연산의 최수 횟수이며, 만약 i = j일 경우 0으로 처리한다. 위의 A, B, C 행렬곱의 최소 연산 횟수가 계산되는 과정을 점화식과 함께 나타냈다.

dp[i][j] = min_i≤k≤j-1(dp[i][k] + dp[k+1][j] + d_id_kd_j-1)

dp[1][2] = min_1≤k≤1(dp[1][1] + dp[2][2] + d₀d₁d₂) = 0 + 0 + 30 = 30

dp[2][3] = min_2≤k≤2(dp[2][2] + dp[3][3] + d₁d₂d₃) = 0 + 0 + 60 = 60

dp[1][3] = min_1≤k≤2(dp[1][k] + dp[k+1][3] + d₀d_kd₃) = min(dp[1][1] + dp[2][3] + d₀d₁d₃, dp[1][2] + dp[3][3] + d₀d₂d₃)

아래는 동적 계획법으로 최소 곱 연산 횟수를 구하는 소스코드이다. 행렬의 최대 개수를 500개로 설정하였다.

#include <bits/stdc++.h>

 

using namespace std;

 

int main(void)

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n;

    cin >> n;

    int d[501];

    for(int i = 0; i < n; i++) {

        cin >> d[i] >> d[i + 1];

    }

    int dp[501][501] = { 0 };

    for(int len = 2; len <= n; len++) {

        for(int i = 1; i <= n - len + 1; i++) {

            int j = i + len - 1;

            dp[i][j] = INT_MAX;

            for(int k = i; k <= j - 1; k++) {

                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + (d[i - 1] * d[k] * d[j]));

            }

        }

    }

    cout << dp[1][n] << endl;

    return 0;

}

C++에서 유용한 print debugging 방법

문제를 해결할 때, VS의 디버깅 툴이나 gdb를 사용하지 않고 빠르게 오류를 잡아낼 수 있는 능력이 중요하다. 그 방법 중 가장 기본적인 것으로는 오류가 있다고 의심되는 변수의 값을 찍어보는 방법이 있는데, 아래는 print debugging을 편리하게 해줄 코드 snippet 이다.

string to_string(string s) {

  return '"' + s + '"';

}

string to_string(const char* s) {

  return to_string((string) s);

}

 

string to_string(bool b) {

  return (b ? "true" : "false");

}

 

template <typename A, typename B>

string to_string(pair<A, B> p) {

  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";

}

template <typename A>

string to_string(A v) {

  bool first = true;

  string res = "{";

  for (const auto &x : v) {

    if (!first) {

      res += ", ";

    }

    first = false;

    res += to_string(x);

  }

  res += "}";

  return res;

}

void debug_out() { cerr << endl; }

 

template <typename Head, typename... Tail>

void debug_out(Head H, Tail... T) {

  cerr << " " << to_string(H);

  debug_out(T...);

}

#ifdef LOCAL

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

#else

#define debug(...) 42

#endif

작성된 코드의 여러 부분에서 debug() 함수를 호출하여 변수 값들을 출력하고 오류를 잡아냈다면 코드를 최종 제출하기 위해서는 여러 군데 위치해 있는 debug() 함수들을 다시 지워야 한다. 이는 굉장히 번거롭기 때문에 이 과정을 거치지 않고도 바로 제출하기를 원할 것이다. 이를 위해서 "LOCAL" 매크로가 존재하는 경우에만 debug() 함수의 동작을 정의한다. 코드를 제출할 환경이 컴파일 시에 "LOCAL" 매크로를 포함하지 않는다면, debug() 함수를 호출한 흔적을 없애지 않고 그대로 제출해도 문제가 없을 것이다. 컴파일러마다 다르겠지만 예를 들어 g++을 이용한다면, 컴파일 할때 -D 옵션을 사용하여 "LOCAL" 매크로를 선언해주어야 한다. (그게 아니라면 코드 내에 "LOCAL" 매크로를 선언해야 함) 이 코드 snippet은 tourist가 작성한 소스 코드로부터 가져왔다.

g++의 유용한 built-in 함수

* bit operation

1) 

__builtin_ffs(x)

x의 least significant 1-bit에 1을 더해준 값을 반환한다. x는 기본적으로 int 이며, suffix "l"을 주면 long 인자, "ll"을 주면 long long 인자로 대입된다.

e.g. __builtin_ffs(10) = 2. 10은 2진수로 "1010"인데 오른쪽에서부터 왼쪽으로 오면서 최초로 나타나는 1-bit는 인덱스 1에 (0-based) 위치해있기 때문이다.

2)

__builtin_clz(x)

MSB로부터 시작하는 x의 leading-0 비트 수를 반환한다. x는 기본적으로 unsigned int 이며, suffix "l"을 주면 unsigned long 인자, "ll"을 주면 unsigned long long 인자로 대입된다.

e.g. __builtin_clz(16) = 27. 인자가 unsigned int 이므로 32비트 크기를 가지고 있고 16은 2진수로 "...10000" 이기 때문에 32 - 5 = 27.

3)

__builtin_ctz(x)

LSB로부터 시작하는 x의 trailing-0 비트 수를 반환한다. x는 기본적으로 unsigned int 이며, suffix "l"을 주면 unsigned long 인자, "ll"을 주면 unsigned long long 인자로 대입된다.

e.g. __builtin_ctz(16) = 4. 16은 2진수로 "10000" 이므로 trailing-0 비트 수는 4이다.

4)

__builtin_popcount(x)

x의 비트 1의 개수를 반환한다. x는 기본적으로 unsigned int 이며, suffix "l"을 주면 unsigned long 인자, "ll"을 주면 unsigned long long 인자로 대입된다. (__builtin_popcountl, __builtin_popcountll)

e.g. __builtin_popcount(14) = 3. 14는 2진수로 "1110" 이므로 비트 1의 개수는 3이다.

* 그 외

1)

__gcd(a, b)

a와 b의 최대공약수(gcd)를 구해준다.

e.g. __gcd(18, 27) = 9