티바이트

VS2013에서 SDL2와 SDL_Image, openGL을 사용하기 위해

개발환경을 설정하는 단계를 포스팅해봅니다.

1 .SDL 홈페이지(https://www.libsdl.org)에서 SDL2 다운로드 페이지로 들어간다.

2. Windows용Development Libraries zip 파일을 다운받아서 압축을 푼다

3. 비주얼스튜디오를 열고 win32 콘솔 프로그램 프로젝트를 만든다.

4. 프로젝트 속성 창을 열고 Configuration Properties의 VC++ Directories로 들어간다.

5. Include Directories 항목에는 SDL2의 헤더파일(.h)이 있는 폴더를 지정하고,

   Library Directories 항목에는 SDL2의 lib파일이 있는 폴더를 지정한다.

  여기서 32비트와 64비트가 있는데 32비트로 진행하였다.

6. 이제 링커 설정에서 라이브러리 의존성을 지정해야 한다.

  5번과 같은 속성창에서 Linker - Input - Additional Dependencies에

라이브러리 파일의 이름을 추가해도 되지만 여기서는 소스코드에 직접 넣었다.

소스코드의 윗부분에 #pragma comment로 lib파일을 쓰면 된다.

SDL2.lib과 SDL2main.lib을 추가한다.

경우에 따라 라이브러리파일의 이름이 SDL2.lib이 아니라 SDL.lib일 수도 있으니 주의.

7. 이제 SDL의 이미지파일 처리 등을 도와주는 SDL_Image 라이브러리를 설치한다.

 https://www.libsdl.org/projects/SDL_image/에서

2번과 같이 Development Libraries zip파일을 받는다.

5번에서처럼 Include Directories와 Library Directories를 각각 추가한다.

*다른 SDL 관련 추가 라이브러리도 이와 같은 방법으로 추가하면 된다.

8. 사용할 라이브러리와 헤더파일들을 소스코드에 명시한다.

opengl함수들을 직접 사용하기 위해서는 opengl32.lib 파일을 링크해야 한다.

※ 실행시 SDL.dll을 찾을 수 없다는 오류가 난다면

다운받은 라이브러리 폴더에 있는 SDL2.dll과 SDL2_image.dll을 복사하여

프로젝트 폴더 내의 Debug 혹은 Release폴더에 넣는다.

아래는 간단하게 작성해본 테스트용 코드..

프로젝트 디렉토리에 res 라는 폴더가 있고

그 폴더에 있는 img.png 파일(512x512)을 로드하여 화면에 표시한다.

(SDL의 함수들만 사용해도 이미지를 띄울 수 있지만

opengl함수들을 사용해보기 위해 아래와 같이 작성하였습니다.)

실행결과

자세한 코드 내용은 다음 포스트에 계속돱니다

http://tibyte.kr/232

문제 주소 : https://algospot.com/judge/problem/read/BOARDCOVER

(알고스팟)

문제 이해

격자 모양의 게임판이 주어진다.

입력으로 주어지는 게임판에는 검은 칸과 흰 칸이 있으며

이 중에서 흰 칸을 아래 4가지 모양의 블록으로 채울 때

남은 칸을 모두 채울 수 있는 경우의 수를 구하는 문제이다.

가능한 답을 완전탐색(exhaustive search)해야 한다.

전략

흰 칸을 블록으로 모두 채운 경우에서

이 중 하나의 블록을 제외하여도 나머지 블록은 칸을 모두 채우고 있는 것을 볼 수 있다.

블록이 4가지 모양에 따라 가지를 뻗어 나가면서 탐색한다.

블록 하나를 배치한 뒤 남은 흰 칸을 재귀호출로 넘긴다.

다시 블록 하나를 배치하고 남은 흰 칸을 재귀호출로 넘긴다.

만약 칸을 더 이상 채울 수 없다면 재귀에서 탈출한다.

그리고 다음 단계에서 다른 모양으로(블록은 회전 때문에 4가지 모양이 있다)

흰 칸 채우기를 수행하기 위해 다시 재귀호출을 한다.

만약 칸을 모두 채웠다면 1을 반환한다.

재귀 구조에서 이 수를 누적하여 계산한다.

풀이

가능한 블록의 모양이 위 그림과 같으므로

함수의 구조는 대략 이렇게 될 것이다.

insert (map, free) {  //2차원배열, 남은 흰 칸 수

    int count = 0;

    if (남은 칸이 3의 배수가 아니면) {

        return 0;

    if (남은 칸이 3이고, 채울 수 있는 형태이면) {

        return 1;

    }

    if (남은 칸이 3이고, 채울 수 없는 형태이면) {

        return 0;

    }

    if (1번 블록을 채울 수 있으면) {

        1번 블록을 채운다;

        count += insert(map, free-3);

        1번 블록을 해제한다:

    }

    if (2번 블록을 채울 수 있으면) {

        2번 블록을 채운다;

        count += insert(map, free-3);

        2번 블록을 해제한다:

    }

    if (3번 블록을 채울 수 있으면) {

        3번 블록을 채운다;

        count += insert(map, free-3);

        3번 블록을 해제한다:

    }

    if (4번 블록을 채울 수 있으면) {

        4번 블록을 채운다;

        count += insert(map, free-3);

        4번 블록을 해제한다:

    }

    return count;

}

이 때 생각해 볼 점은, 처음에 블록을 어디부터 채우고,

그 다음에는 또 어디부터 채울 것이냐다.

여기서는 상단, 좌측을 우선하여 블록을 채우기로 했다.

블록을 채우는 순서는 경우의 수에 영향을 미치지 않기 때문에 하단부터 채워도 결과는 같다.

상단,좌측을 우선하여 블록을 채울 때

기준이 되는 점(초록색)과 추가로 검사해야 하는 점(회색)은 아래그림과 같다.

소스코드(C++)

(설명의 블록 번호와 아래 소스코드의 블록 번호는 다릅니다)

문제 링크 : https://www.algospot.com/judge/problem/read/POTION

(알고스팟)

문제 이해

어떤 약을 한 단위 만드는 데 필요한 n개의 재료들의 양과

현재 넣은 재료의 양이 입력된다.

이 때 약을 만들기 위해 더 넣어야 하는 재료들의 양을 구하는 문제이다.

입력값은 모두 정수이고,

약을 최소한 1단위 이상은 만들어야 한다.

풀이

완성한 약의 양이 꼭 정수단위일 필요가 없다는 점에 주의해야 한다.

따라서 필요한 재료들의 양을 최대공약수로 나누어

들어가야 하는 재료들의 비를 구했다.

예를 들어 들어가야 하는 3가지 재료의 양이 각각 2 4 6 이라면

최대공약수 2로 나누어 1 2 3 라는 비율을 구한다.

이제 들어가야 하는 재료의 양은 1 2 3 의 정수배인

1 2 3

2 4 6

3 6 8

4 8 10

...

...

과 같이 된다.

(정수배인 이유는 입력되는 재료의 양이 정수이므로)

그런데 문제에서 완성 약을 한 단위 이상 만들어야 한다는 조건이 있으므로

2 4 6 다음부터 검사하면 되는것이다.

여기서 현재 넣은 재료가 3 6 7 이라면

재료추가로 만들 수 있는 값이 위 정수배들 중에서 3 6 8 이므로

약을 완성시키기 위해 0 0 1 만큼의 재료를 더 넣어야 하는 것이다.

최대공약수를 구하는 부분은 유클리드 알고리즘을 사용하였고,

n개 수의 GCD를 구하기 위해 해당 알고리즘을 n-1번 반복하였다.

(관련글 : http://www.tibyte.kr/224)

코드

#include <cstdio>

#include <cmath>

using namespace std;

//GCD계산 (유클리드)

int calcGcd(int n1, int n2)

{

int temp;

if (n1 < n2) {

temp = n1;

n1 = n2;

n2 = temp;

}

while (n2 != 0) {

temp = n1%n2;

n1 = n2;

n2 = temp;

}

return n1;

}

int main(void)

{

int numTry;

scanf("%d",&numTry);

while (numTry--)

{

int numElem;

scanf("%d",&numElem);

int *ideal = new int[numElem];

int *curr = new int[numElem];

int gcd;

double curMul = 0;

double maxMul = 0;

int mul;

//비율값 입력받음

for (int i = 0; i < numElem; i++) 

scanf("%d", &ideal[i]);

//비율값의 gcd계산

gcd = ideal[0];

for (int i = 1; i < numElem; i++) 

gcd = calcGcd(gcd, ideal[i]);

//ideal값 재계산

for (int i = 0; i < numElem; i++)

ideal[i] = ideal[i]/gcd;

//현재넣은값 입력받음

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

scanf("%d", &curr[i]);

curMul = (double)curr[i] / ideal[i];

if (curMul >maxMul ) maxMul = curMul;

}

mul = ceil(maxMul);

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

ideal[i] *= mul;

printf("%d ", ideal[i] - curr[i]); 

}

printf("\n");

}

return 0;

}

두 직사각형이 평면상에 놓여져 있을 때 아래와 같이 7가지로 나누어 생각해 볼 수 있다.

회색 사각형을 기준으로

1. 한쪽 귀퉁이를 덮음

2. 한 변을 덮음

3. 자신의 한 변이 모두 덮임

4. 교차

5. 자신이 포함됨

6. 다른 사각형을 모두 덮음

7. 겹치지 않음

각각의 경우를 나누어 처리할 수도 있으나

1~6의 겹치는 영역(직사각형)을 보면 모두 공통적인 특징이 있다.

겹치는 영역(Intersection)의

왼쪽 변은, 기존 두 사각형의 왼쪽 변 중에서 더 오른쪽에 있는 것

오른쪽 변은, 기존 두 사각형의 오른쪽 변 중에서 더 왼쪽에 있는 것

위쪽 변은, 기존 두 사각형의 위쪽 변 중에서 더 아래쪽에 있는 것

아래쪽 변은, 기존 두 사각형의 아래쪽 변 중에서 더 위쪽에 있는 것

이 된다는 것을 확인할 수 있다.

화면 좌측상단이 원점인 좌표계를 기준으로  코딩할 때 사각형 구조체를 x, y, width, height로 정의한다면, 겹치는영역의

(왼쪽 변) x는 기존 두 사각형의 x중에서 큰 것
(오른쪽 변) width는 기존 두 사각형의 x+width 중에서 작은 것 - x좌표

(위쪽 변) y는 기존 두 사각형의 y중에서 큰 것

(아래쪽 변) height는 기존 두 사각형의 y+height 중에서 작은 것 - y좌표

으로 하면 된다.

-x, -y 가 붙어있는 이유는 해당 속성이 각각 너비와 높이이기 때문.

아래는 Javascript 코드로 작성해 본 것이다.

코드를 보면 두 사각형이 겹치지 않은 경우를 걸러내는 부분이 추가되었다.

이 문제에 대해 조금 다르게 생각해 볼 수도 있는데,

너비가 w이고 높이가 h인 screen이 있을 때

임의의 점에 대하여

그 점이 screen 안에 있을 때는 그대로 표시하고,

screen 밖에 있을 때는 screen의 안쪽 변 끝에 두는 간단한 식이 있다.

x' = min(w, max(0, x))

y' = min(h, max(0, y))

이 식을 한 사각형의 4 꼭지점(초록색)에 각각 적용한다면,

두 사각형의 겹치는 부분이 만드는 새로운 사각형의 4 꼭지점(파란색)을 얻을 수 있다.

연관글 :

자바스크립트로 구현한 결과는 여기에 올림.

문제 링크 : http://judge.koreatech.ac.kr/problem.php?id=1007

32bit 크기의 정수 N개 (N은 1<=N<100001인 홀수)가 입력으로 주어진다.

하나를 제외한 나머지 수는 모두 짝이 있다. (짝수 번 중복된다.)

예시 

입력 : -1 2 0 -1 2

출력 : 0

입력 : 2 2 2 2 5

출력 : 5

입력 : 2 2 2 2 2

출력 : 2

(2와 2가 짝, 다시 2와 2가 짝이 되면 2 하나가 남는다.)

생각 1

integer범위 길이만큼의 배열을 만들어서 각각 몇 번 나왔는지 센다.

=> 메모리 용량 4GB가 필요하므로 비효율적

생각 2

입력이 들어올 때마다 리스트에 넣는다.

리스트에 넣을 때, 리스트를 선형탐색하여 자신과 같은 수가 있으면 그 수를 뺀다.

마지막에 남은 수를 출력한다.

시간복잡도 : O(n^2)

공간복잡도 : O(n)

생각 3

생각2에서 리스트 대신 트리를 사용한다.

시간복잡도 : O(nlogn)

공간복잡도 : O(n)

생각 4

임의의 정수 a, b, c에 대해 a xor b xor c xor b = a xor c 인 성질을 이용한다.

(어떤 정수에 임의의 정수를 짝수 번 xor 하면 원래대로 돌아온다.)

문제에서 한 수를 제외한 나머지 수들은 모두 짝수 번 반복되므로

들어오는 입력을 모두 xor연산하여 누적시키면 답이 나올 것이다.

시간복잡도 : O(n)

공간복잡도 : O(1)

소스코드 (C++)

#include <cstdio>

using namespace std;

int main(void)

{

int numTry;

scanf("%d",&numTry);

while (numTry--)

{

int leng;

scanf("%d",&leng);

int acc = 0;

int num;

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

scanf("%d",&num);

acc ^= num;

}

printf("%d\n", acc);

}

return 0;

}

이전글 : 유클리드 호제법(http://www.tibyte.kr/224)

이진 최대공약수 알고리즘(binary GCD algorithm은 스테인 알고리즘(Stein's algorithm)이라고도 하며 비트연산을 이용하여 컴퓨터에서 최대공약수를 (나머지연산을 사용하는 유클리드 알고리즘보다) 빠르게 구할 수 있는 알고리즘이다.

이 알고리즘으로 36과 24의 최대공약수를 구하는 예시를 보면 다음과 같다.

36 → 18 →9 →9 →6 →3 →3 

24 → 12 →6 →3 →3 →3 →0

여기서 이런 규칙을 볼 수 있다.

- 두 수가 짝수일 때는 2로 나눈다.

- 한 수만 짝수일 때는 그 수를 2로 나눈다.

- 두 수가 홀수일 때는 큰 수에서 작은 수를 뺀다.

- 0이 되는 수가 있으면 종료한다.

여기서 최대공약수를 얻는 방법은

두 수가 짝수여서 2로 나누는 계산을 할 때마다, 변수 a를 1씩 증가시킨다.

그리고 마지막에 남은 0이 아닌 수를 b라고 하면

를 계산하는 것이다.

두 수가 모두 2로 a번 나눠진다는 것은

두 수의 공약수에 2가 a번 포함되어있기 때문이라고 생각하면 이해하기가 쉽다.

36과 24의 경우에서, 마지막에 3이 남았다는 것은

바로 전 단계에 두 수에 모두 3이 포함되어있는 것이기 때문에 이 역시 곱해준다(위 식에서는 b)

규칙에서 두 수가 홀수일 때 값을 빼는 것은 유클리드 알고리즘과 관련있는 부분이다.

C언어 코드

int calcGcd(int n1, int n2)
{
    int exp = 0;
    int n;

    while (((n1|n2)&1) == 0) {
        ++exp;
        n1 >>= 1;
        n2 >>= 1;
    }

    while (n1!=0 && n2!=0) {
        while ((n1&1) == 0)
            n1 >>= 1;
        while ((n2&1) == 0)
            n2 >>= 1;

        if (n1 > n2)
            n1 = n1-n2;
        else
            n2 = n2-n1;
    }
    if (n1!=0)
        n = n1;
    else
        n = n2;

    return n<<exp;

}

관련글 : 유클리드 호제법(http://www.tibyte.kr/224)

유클리드 호제법(Euclidean algorithm)으로 최대공약수를 구할 수 있다.

두 정수 m과 n (m>n)의 최대공약수를 구하는 문제를

m-n과 n의 최대공약수를 구하는 문제로 줄일 수 있다.

왜냐하면 m과 n의 최대공약수를 G라 하면 다음과 같이 나타낼 수 있는데

m = Ga

n = Gb

m-n = G(a-b)와 같이 묶을 수 있기 때문이다. (a와 b는 서로소(relatively prime))

예를 들어 94와 30이 있을 경우 아래와 같은 단계를 거쳐 문제를 줄여가면서

최대공약수인 2를 구할 수 있는 것이다.

94    30   (A)

64    30   (A)

34    30   (A)

 4     30   (A) (B)

 4     26   (B)

 4     22   (B)   

 4     18   (B)

 4     14   (B)

 4     10   (B)

 4      6    (B)

 4      2    (B)

 2      2

 2      0

위 단계에서 (A)부분과 (B)부분을  잘 보면 뺄셈 연산을 여러 번 수행한 결과가 결국 나머지 값이라는 사실을 알 수 있다. 따라서 코드로 작성할 때 나머지연산(%)을 사용하면 다음과 같이 단계를 줄일 수 있다.

94   30

 4    30

 4     2

 2     2

 2     0

아래는 C언어로 작성한 코드이다.

int gcd(int n1, int n2)
{
    int temp;
    if (n1 < n2) {
        temp = n1;
        n1 = n2;
        n2 = temp;
    }
    while (n2 != 0) {
        temp = n1%n2;
        n1 = n2;
        n2 = temp;
    }
    return n1;
}

관련글 : 이진 최대공약수 알고리즘 (http://www.tibyte.kr/225)

한글로 주석을 작성하고  javac로 컴파일할 때 인코딩 문제 때문에

다음과 같은 에러 메시지를 볼 수 있다.

unmappable character for encodig MS949

해결방법 : javac의 기본 인코딩 설정을 ms949에서 utf-8로 바꿔주면 된다.

예시 : javac Project1.java -encoding UTF-8

▷ 30도, 45도, 60도

▷ 42도, 43도, 44도, 45도, 46도

▷ 위 그림에서 낙하지점을 확대한 모습.

(오른쪽으로)멀리 간 궤적부터 각각 42도, 43도, 44도, 45도, 46도 입니다.

수식을 통한 계산은 다음 포스트에...