어느 게임 개발자의 기록

프록시 패턴이란, 특정 객체에 접근하고자 할 때 직접 접근하는 것이 아니라 대리자를 통해 접근하도록 하는 패턴이다.

프록시 패턴 (대리자 패턴)

아래의 코드를 보자.

class A
{
public:
    void Death() {}
    void Attack() {}
}

int main()
{
    A* NewA = new A():
    
    if(NewA != nullptr)
    {
        NewA->Attack();
    }
    
    if(NewA != nullptr)
    {
        NewA->Death();
        delete NewA;
        NewA = nullptr;
    }
    
    return 0;
}

먼저, A객체를 동적으로 생성해주었다.

이후, nullptr체크를 한 뒤 Attack함수를 호출해 주었다.

다음으로, nullptr체크를 한 뒤, Death함수를 호출한 뒤, NewA의 메모리를 해제하고 NewA가 가리키는 포인터를 nullptr로 변경해주었다.

이 코드에서 문제점을 찾아보자.

1. A객체를 알아야 한다.

2. 매번 nullptr 검사를 해주어야 한다.

3. 실제로 객체의 기능을 사용하기 이전부터 객체가 메모리에 존재한다.

A객체를 생성하고 그 멤버함수를 호출하기 위해선 당연히 A객체를 알아야 한다.

현재는 main함수에서 A객체의 멤버함수를 호출하고 있지만, 만약 B라는 다른 객체에서 A의 멤버함수를 호출하게 된다면 A객체와 B객체간의 결합도가 높아진다고 할 수 있다.

또한, A객체를 값으로 알고 있는 것이 아니라 주소값으로 알고 있기 때문에, 주소값에 접근할 때마다 nullptr검사 등의 유효성 검사를 매번 해주어야 한다. 이는 프로그래머 입장에선 상당히 번거로운 일이라고 할 수 있다.

또한, NewA가 실제로 사용되기 이전부터 객체를 생성하여 메모리에 존재하게 되는데, 위의 코드에선 생성한 뒤 바로 Attack함수를 호출하고 있지만, 그 시기가 늦어진다면 Attack 함수가 호출되기 이전까지 의미없는 데이터가 메모리 용량을 차지하고 있게 되는 것이다.

이러한 문제점들을 해결하기 위해 프록시 패턴을 사용할 수 있다.

아래의 코드를 보자.

class A
{
public:
    void Death() {}
    void Attack() {}
};

class AProxy
{
public:
    void Attack()
    {
        if(NewA == nullptr)
        { 
            NewA = new A();
        }
        
        NewA->Attack();
    }
    
    void Death()
    {
        if(NewA == nullptr)
        {
            std::cout << "A객체가 생성되지도 않았는데, 파괴하려 하였습니다." << std::endl;
            return;
        }
        
        NewA->Death();
        delete NewA;
        NewA = nullptr;
    }
    
private:
	A* NewA = nullptr;    
};

int main()
{
    AProxy* NewProxy = new AProxy();

    NewProxy->Attack();
    NewProxy->Death();

    return 0;
}

A의 기능을 사용하기 위해, A의 멤버함수를 직접 호출하는 것이 아니라 AProxy의 멤버함수를 호출하고 있다.

AProxy는 내부에서 A의 기능에 필요한 전처리를 한 뒤 A의 함수를 호출하고 있으며, 함수가 끝난 뒤 후처리가 필요하다면 후처리 또한 실행해주고 있다.

이로 인해, A의 기능을 사용할 때 매번 번거롭게 nullptr 검사 등의 전처리 코드를 작성할 필요가 없어지며, A의 객체를 직접 몰라도 AProxy 객체를 통해 A의 기능을 사용할 수 있게 된다. 이로 인해, A객체와 낮은 결합도를 유지한 채로 기능을 사용할 수 있게 된다.

또한, 전처리 과정에서 A 객체의 기능을 사용하고자 하는 객체의 권한을 파악하여 접근 허용 여부를 판별하게 되면, 보안 측면의 이점도 노려볼 수 있다. 

또한, AProxy의 Attack함수가 호출될 때 A객체를 생성하기 떄문에 A 객체의 생성 시점을 최대한 미룰 수 있으며, 이로 인해 조금 더 효율적인 메모리 사용이 가능해진다.

이처럼 A에 직접 접근하여 기능을 사용하지 않고, 다른 객체를 한 단계 거쳐서 A의 기능을 사용하는 디자인 패턴이 프록시 패턴이다. 

프록시 패턴에는 위와 같은 장점들이 있지만, 단점도 분명 존재한다.

1. 함수 호출 과정에 한 단계가 추가되는 만큼, 성능이 하락할 수 있다.

2. A객체 뿐만 아니라 AProxy 객체도 메모리에 존재해야 하므로, 메모리 사용량 측면에선 비효율적일 수 있다.

3. 함수 호출 과정에 한 단계가 추가되는 만큼, 코드가 복잡해지고 가독성이 떨어질 수 있다.

프록시 패턴의 장단점

 

.과 #으로 이루어진 2차원의 배열이 주어진다. 행의 길이는 n이며, 열의 길이는 m이다.

좌측상단의 좌표는 (1,1)이며, 우측 하단의 좌표는 (n, m)이다.

이 그리드 안에는 맨해튼 원이 존재한다. 맨해튼 원의, 중심을 (h, k)라고 하자.

이 때, (a, b)의 좌표를 지닌 점이, |h - a| + |k - b| < r 을 만족한다면 (a, b)는 맨해튼 원의 내부에 있는 것이다.

맨해튼 원의 내부에 속한 점을 #로 표시한 2차원 배열이 주어졌을 때, 맨해튼 원의 중심 좌표를 구하여 출력하면 된다.

문제 풀이

문제 해결은 간단하다.

가장 좌측의 점과 우측의 점 혹은 가장 상단의 점과 하단의 점을 구하면 된다.

맨해튼 원을 그려보면, 항상 마름모의 꼴을 나타내고 해당 마름모는 중심점을 기준으로 대칭을 이룬다.

또한, 원의 중심을 지나며 x축과 수평인 직선에 대해서도 대칭이며, 원의 중심을 지나며 y축과 수평인 직선에 대해서도 대칭을 이룬다.

맨해튼 원 내부의 점중 가장 좌측에 있는 점과 가장 우측에 있는 점 또한 원의 중심점을 기준으로 대칭을 이룬다.

그렇다면, 맨해튼 원 내부의 점중 가장 좌측에 있는 점과 우측에 있는 점의 중심점이 원의 중심이 될 것이다. 

풀이 코드

int Height = 0;
int Width = 0;

std::cin >> Height >> Width;

먼저, 배열의 행과 열의 크기를 입력받아주자.

std::pair<int, int> LeftPos = { 9999999,9999999 };
std::pair<int, int> RightPos = { -9999999, -9999999 };

맨해튼 원 내부의 점중 가장 좌측에 있는 점과 우측에 있는 점을 구하기 위해 선언해주자.

for (int i = 0; i < Height; i++)
{
    for (int j = 0; j < Width; j++)
    {
        char Input = 0;
        std::cin >> Input;

        if (Input == '#')
        {
            if (LeftPos.second > j)
            {
                LeftPos = { i, j };
            }

            if(RightPos.second < j)
            {
                RightPos = { i, j };
            }
        }
    }
}

입력을 받아 주면서, 현재 좌표에 대해 LeftPos와 RightPos를 계속 갱신해주자.

std::pair<int, int> Answer = { LeftPos.first + RightPos.first + 2, LeftPos.second + RightPos.second + 2};

Answer.first /= 2;
Answer.second /= 2;

최종적으로 구해진 leftPos와 RightPos의 중심점을 구해주자.

(첫번쨰 줄을 보면, LeftPos.first + RightPos.first에 2를 추가로 더해주고 있는데, 정답으로 출력될 좌표는 (1,1)을 시작으로 하기 때문에 각 좌표에 1씩 더해준 것이다.)

std::cout << Answer.first << " " << Answer.second << "\n";

구한 정답을 출력해주면 된다.

코드 전문

#include <iostream>
#include <vector>
#include <algorithm>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumCase = 0;
    std::cin >> NumCase;

    for (int Case = 0; Case < NumCase; Case++)
    {
        int Height = 0;
        int Width = 0;

        std::cin >> Height >> Width;

        std::pair<int, int> LeftPos = { 9999999,9999999 };
        std::pair<int, int> RightPos = { -9999999, -9999999 };

        for (int i = 0; i < Height; i++)
        {
            for (int j = 0; j < Width; j++)
            {
                char Input = 0;
                std::cin >> Input;

                if (Input == '#')
                {
                    if (LeftPos.second > j)
                    {
                        LeftPos = { i, j };
                    }

                    if(RightPos.second < j)
                    {
                        RightPos = { i, j };
                    }
                }
            }
        }

        std::pair<int, int> Answer = { LeftPos.first + RightPos.first + 2, LeftPos.second + RightPos.second + 2};
        
        Answer.first /= 2;
        Answer.second /= 2;

        std::cout << Answer.first << " " << Answer.second << "\n";
    }


    return 0;
}

 

{A1, A2, A3, .... An} 처럼 n개의 원소를 가진 배열이 있다고 해보자.

특정 원소를 Ak를 제외한 나머지 원소를 모두 더한 값이 Ak가 되는 Ak가 존재한다면, 해당 Array는 Good이라고 한다.

예를 들어, {1, 6, 3, 2}에서 6을 제외한 나머지 원소의 합은 6이 된다. 그러므로, 이 배열은 Good이라고 할 수 있다.

{A1, A2, A3, ..., An}과 같이 n개의 원소로 이루어진 배열이 있다고 해보자.

{A1}, {A1, A2}, {A1, A2, A3} ... 등 배열의 가장 앞에서부터 잘라낸 배열을 Prefix라고 할 것이다.

An에 대한 모든 Prefix중 Good인 Array가 몇 개인지를 구하여 출력하자.

문제 풀이

배열에서 특정 원소 Ak를 제외한 나머지 원소의 총 합이 Ak가 된다면, 해당 배열은 Good이라고 할 수 있다.

그렇다면, 해당 배열에서 Ak가 될 수 있는 후보는 어떤 숫자가 있을까?

Ak가 될 수 있는 값은, 해당 배열의 원소중 최대값이다.

{1, 2, 3, 6}이라는 배열이 있다고 해보자. 여기서, 최대값은 6이다. 이 배열에서 만약 Ak를 최대값이 아닌 다른 값으로 잡는다면, (Ak = 최대값 + 다른 원소) 의 공식이 성립해야 한다. 즉, Ak는 배열의 원소중 최대값보다 더 큰 값이어야 한다는 것인데 이는 모순되는 말이므로 Ak는 반드시 배열의 원소중 최대값이어야 한다.

즉, (배열의 최대값 = 나머지 원소의 총합)이 성립한다면 해당 배열은 Good이라고 할 수 있으며, 성립하지 않는다면 Good이 아니라고 할 수 있다.

그렇다면, 주어진 배열의 모든 Prefix 에 대해 Good을 판단할 수 있게 된다.

std::vector<int> Array;

for(int i = 0; i < Array.size(); i++)
{    
    int Max = 0;
    int Sum = 0;
    
    for(int j = 0; j <= i; j++)
    {
        Max = std::max(Max, Array[j]);
        Sum += Array[j];
    }
    
    if(Max - Sum == Sum)
    {
        //Array is Good!
    }
}

위와 같이 이중 반복문을 사용해 모든 Prefix 배열에 대해 Good을 판별할 수 있다.

하지만, 이렇게 무식하게 판별을 하게 되면 시간초과가 발생할 것이다.

그러므로, 판별 과정을 조금 더 단순하게 만들 필요가 있다.

결국 배열이 Good인지 판단하기 위해 중요한 것은 배열의 원소의 총 합과 최대값이다.

(배열의 원소의 총 합 - 최대값 = 최대값) 을 만족한다면 배열은 Good이라고 할 수 있기 때문이다.

생각해보면, Prefix 배열의 원소 총 합과 최대값을 구하기 위해서 매번 Prefix 배열의 사이즈만큼 반복문을 돌 필요는 없다.

모든 Prefix배열은 입력으로 주어진 가장 앞에서부터 시작하며, size가 K인 Prefix배열은 size가 (k - 1)인 배열의 가장 뒤에 Ak를 추가한 형태일 뿐이기 때문이다.

즉, size가 k인 배열의 원소 총 합은 size가 (k - 1)인 배열의 원소 총 합에 Ak를 더한 것이다.

또한 size가 k인 배열의 원소중 최대값은 size가 (k - 1)인 배열의 원소중 최대값과 Ak중 더 큰 값이 된다.

이를 코드로 구현하면 아래와 같이 간단하게 한 번의 반복문으로 표현할 수 있게 된다.

std::vector<int> Array;

int Sum = 0;
int Max = 0;

for(int i = 0; i < Array.size(); i++)
{    
    Max = std::max(Max, Array[i]);
    Sum += Array[i];
    
    if(Max - Sum == Sum)
    {
        //Prefix Array is Good!
    }
}

풀이 코드

int ArraySize = 0;
std::cin >> ArraySize;

std::vector<long long> Array(ArraySize);
for (int i = 0; i < ArraySize; i++)
{
    std::cin >> Array[i];
}

먼저 배열을 입력받아 준다.

int GoodCount = 0;

long long MaxNum = 0;
long long Sum = 0;

다음은 값을 저장할 변수들을 선언해주었다.

for (int i = 0; i < ArraySize; i++)
{
    Sum += Array[i];
    MaxNum = std::max(Array[i], MaxNum);

    if (MaxNum - Sum == Sum)
    {
        GoodCount++;
    }
}

앞에서 설명한 것과 같이 반복문을 돌며 모든 prefix에 대해 Good 여부를 판별한 뒤, Good이라면 GoodCount를 증가시켜주었다.

모든 케이스에 대해 GoodCount를 구한 뒤 출력해주면 된다.

코드 전문

#include <iostream>
#include <vector>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumCase = 0;
    std::cin >> NumCase;

    std::vector<int> Answers(NumCase);

    for (int Case = 0; Case < NumCase; Case++)
    {
        int ArraySize = 0;
        std::cin >> ArraySize;

        std::vector<long long> Array(ArraySize);
        for (int i = 0; i < ArraySize; i++)
        {
            std::cin >> Array[i];
        }

        int GoodCount = 0;

        long long MaxNum = 0;
        long long Sum = 0;

        for (int i = 0; i < ArraySize; i++)
        {
            Sum += Array[i];
            MaxNum = std::max(Array[i], MaxNum);

            if (MaxNum * 2 == Sum)
            {
                GoodCount++;
            }
        }

        Answers[Case] = GoodCount;
    }

    for (int i = 0; i < NumCase; i++)
    {
        std::cout << Answers[i] << "\n";
    }

    return 0;
}

 

밥은 N개의 빵을 판매할 것이다.

밥은 0 <= K <= min(n, b) 범위를 만족하는 K를 하나 고를 것이다.

K개의 빵을 판매할 때, i번째로 판매되는 빵의 가격은 (b - i + 1)원으로 판매할 것이다.

K개의 빵을 모두 판매한 뒤에 남은 빵은 모두 a원의 고정 가격으로 판매할 것이다.

이 때, K값에 따라 총 매출은 달라지는데 가능한 경우중 총 매출의 최대값을 구하여 출력하면 된다.

문제 풀이

이 문제는 특정할 알고리즘을 사용하기 보단 아이디어를 떠올려 해결하는 문제이다.

두 가지의 경우를 생각해보자.

1. b >= a 인 경우

K개의 빵에 대해, 판매되는 빵의 가격은 b원, b - 1원, b - 2원.....b - k + 1원이 된다.

이 때, 이 가격이 모두 a원보다 크거나 같은 값이 되어야 매출은 최대가 될 것이다.

(k가 너무 커서 b - k + 1이 a원보다 작게 되면, a원으로 판매할 때보다 손해를 보기 때문에)

즉, b - k + 1 = a 를 만족하는 k에 대해, 총 매출이 최대가 될 것이다.

2. b < a 인 경우

이 경우엔, K개의 빵에 대해 모두 a원보다 낮은 가격으로 판매하게 된다.

차라리 모든 빵을 a원으로 판매하는 것이 이득일 것이다.

그러므로, k가 0일 때 총 매출이 최대가 될 것이다.

위의 두 경우를 고려하여 답을 구하여 출력하면 된다.

풀이 코드

테스트케이스의 수를 입력받는 것은 제외하고 코드를 설명할 것이다.

long long N = 0;
long long A = 0;
long long B = 0;

std::cin >> N >> A >> B;

먼저 값을 입력받아 준다.

long long K = std::max((long long)0, std::min(N, B - A));

K값을 위와 같이 세팅해준다.

B가 A보다 크거나 같다면, B - A개만큼 A원보다 크거나 같은 값으로 판매할 수 있다. 반면, B가 A보다 작은 경우엔 1개도 A원보다 비싸게 판매할 수 없다. B가 A보다 작게 되면, B - A가 음수가 되므로 K값은 0이 된다.

또한 K의 범위는 0 <= K <= min(n, b) 이므로 B-A가 N보다 큰 경우 N으로 값을 조정해주었다.

long long Answer = GetProfit(K, NumOfBun, BasicPrice, FirstModifiedPrice);

GetProfit이라는 함수는 총 이익을 계산해주는 함수이다. 

long long GetProfit(long long _K, long long _N, long long _A, long long _B)
{
    long long SumProfit = 0;

    SumProfit += _B * (_B + 1) / 2;
    SumProfit -= (_B - _K) * (_B - _K + 1) / 2;
    SumProfit += _A * (_N - _K);

    return SumProfit;
}

등차수열의 합 공식을 사용하여 간단하게 총 이익을 구해주었다.

함수가 반환한 값을 출력해주면 된다.

코드 전문

#include <iostream>
#include <vector>

long long GetProfit(long long _K, long long _N, long long _A, long long _B)
{
    long long SumProfit = 0;

    SumProfit += _B * (_B + 1) / 2;
    SumProfit -= (_B - _K) * (_B - _K + 1) / 2;
    SumProfit += _A * (_N - _K);

    return SumProfit;
}

int main()
{
    int NumCase = 0;
    std::cin >> NumCase;

    std::vector<long long> Answers(NumCase);

    for (long long Case = 0; Case < NumCase; Case++)
    {
        long long N = 0;
        long long A = 0;
        long long B = 0;

        std::cin >> N >> A >> B;

        long long K = std::max((long long)0, std::min(N, B - A));
        long long Answer = GetProfit(K, N, A, B);

        Answers[Case] = Answer;
    }

    for (int i = 0; i < NumCase; i++)
    {
        std::cout << Answers[i] << "\n";
    }

    return 0;
}

 

N개의 책과 각 책이 보유한 페이지 수가 주어진다.

각 책은 입력된 순서대로 1~N의 번호가 부여되어 있다.

이 때, N개의 책을 두 그룹으로 나눌 것이다. (각 그룹에는 최소한 1개의 책이 존재한다.)

Alice는 각 그룹에서 가장 번호가 높은 책을 하나씩 읽을 것이다.

가능한 경우 중에서, Alice가 읽을 수 있는 페이지 수의 총합의 최대값은 얼마인가?

문제 풀이

특정 알고리즘을 사용하기 보단, 아이디어를 떠올려 푸는 문제이다.

먼저, 모든 책을 두 그룹으로 나눈다면, 두 그룹 중 하나에는 반드시 N번째의 책이 포함되어 있을 것이다.

해당 그룹에선, 무슨 일이 있어도 N번째의 책을 읽을 수 밖에 없다. (N보다 큰 번호를 부여받은 책은 없으므로)

즉, 어떠한 경우에든 N번째의 책은 반드시 읽힌다. 그렇다면, N번째 책을 제외한 나머지 하나의 책의 페이지 수가 최대일 때의 앨리스가 읽은 페이지 수의 총합이 최대값이 될 것이다. 

즉 N번째 책을 제외한, 나머지 책 중 페이지수가 가장 많은 책이 해당 그룹에서 가장 높은 번호를 가지도록 그룹을 나누면 된다. (만약, M번째의 책이 N번째 책을 제외한 책중 페이지 수가 가장 많다면, 1~M, M+1~N으로 두 그룹을 나누어 M번째책과 N번째 책을 읽도록 할 수 있다.)

아이디어만 떠올리면 아주 간단하게 코드로 작성할 수 있다.

풀이 코드

테스트 케이스의 개수에 대한 입력은 제외하고, 코드를 설명할 것이다.

int NumBook = 0;
std::cin >> NumBook;

std::vector<int> Pages(NumBook);
for (int i = 0; i < NumBook; i++)
{
	std::cin >> Pages[i];
}

먼저, 입력을 받아 저장해주자.

책의 수와 각 책의 페이지 수를 저장해 주었다.

int Answer = Pages[NumBook - 1];

이후, N번째 책의 페이지 수를 Answer에 더해주자. (N번째의 책은 어떠한 경우에든 반드시 읽으므로)

int MaxPage = 0;
for (int i = 0; i < NumBook - 1; i++)
{
    MaxPage = std::max(MaxPage, Pages[i]);
}

N번째 책을 제외한 나머지 책들 중 페이지 수가 가장 많은 책을 탐색해주자.

Answer += MaxPage;

위에서구한 값을 Answer에 더해주면 끝이다.

Answer을 출력해주면 된다.

코드 전문

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    int NumTestCase = 0;
    std::cin >> NumTestCase;

    std::vector<int> Answers(NumTestCase);

    for (int Case = 0; Case < NumTestCase; Case++)
    {
        int NumBook = 0;
        std::cin >> NumBook;

        std::vector<int> Pages(NumBook);
        for (int i = 0; i < NumBook; i++)
        {
            std::cin >> Pages[i];
        }

        int Answer = Pages[NumBook - 1];

        int MaxPage = 0;
        for (int i = 0; i < NumBook - 1; i++)
        {
            MaxPage = std::max(MaxPage, Pages[i]);
        }

        Answer += MaxPage;
        Answers[Case] = Answer;
    }

    for (int i = 0; i < NumTestCase; i++)
    {
        std::cout << Answers[i] << std::endl;
    }

    return 0;
}

 

로봇이 같은 곳을 한 번보다 많이 이동하지 않는다는 의미가 다소 헷갈렸는데, 방문했던 곳을 다시 방문하지 않는다는 의미였다. 즉, 로봇이 한 번 방문했던 곳을 방문하지 않고 이동하는 경우가 이동경로가 단순한 것이다.

로봇이 동, 서, 남, 북으로 이동할 수 있는 확률이 주어질 때 단순하게 이동하는 경우의 확률을 출력하는 문제이다.

문제 풀이

풀이는 간단하다. 단순하게 이동하는 모든 경우의 수에 대해 확률을 구한 뒤, 그 확률을 모두 더한 값이 정답이 된다.

모든 경우의 수를 어떻게 구할까?

DFS를 사용하면 쉽게 구할 수 있다. 먼저, 로봇이 방문한 거리를 체크하기 위한 이차원 배열을 하나 만들어줄 것이다.

이차원 배열의 크기를 설정할 때, 최소의 크기는 (N * 2 + 1) * (N * 2 + 1) 이 되어야 한다.

배열의 중앙에서 로봇이 이동을 시작한다고 했을 때, 상하좌우 중 한쪽으로만 쭉 이동한 경우 배열의 범위를 초과하지 않으려면 배열의 중앙을 기준으로 양 끝까지 최소 N의 거리가 필요하기 때문이다.

(왼쪽 N + 중앙 1칸 + 오른쪽 N) -> (2 * N + 1)

본인은 N에 따라 가변적으로 변하도록 구현하지는 않았고, 편하게 30 * 30의 배열을 선언하여 사용하였다.

(메모리를 최적화 하고 싶다면  (N * 2 + 1) * (N * 2 + 1) 의 크기로 만드는 것이 당연히 유리하다.)

로봇이 배열의 중앙에서 출발하도록 한 뒤, DFS를 사용하여 이동할 수 있는 모든 경로를 탐색하면 된다.

N번 이동을 마친 뒤, 해당 경로의 확률을 계산한 뒤 그 값을 하나의 변수에 누적해서 더해주면 된다.

풀이 코드

int MoveCount = 0;
double ProbSum = 0;

std::vector<double> Probs;
std::vector<std::vector<bool>> isVisit;

std::vector<int> DirX = { 1, -1, 0, 0 };
std::vector<int> DirY = { 0, 0, 1, -1 };

먼저, 위와 같이 전역변수를 선언하였다.

MoveCount는 N을 저장할 변수이며, ProbSum은 출력할 정답을 저장할 곳이다.

Probs는 상하좌우로 이동할 확률을 저장하고 있으며, isVisit는 위에서 설명했던 방문체크 배열이다.

DirX, DirY는 DFS에서 사용되는 상하좌우 이동에 사용될 배열이다.

Probs.resize(4);

std::cin >> MoveCount;

for (int i = 0; i < 4; i++)
{
	std::cin >> Probs[i];
	Probs[i] /= 100.0l;
}

위와 같이 입력을 받아준 뒤, Probs[i]의 모든 원소를 100.0l로 나누어준다.

(25로 입력이 들어오면, 0.25로 변환하여 확률 계산을 편하게 하기 위해서)

isVisit.resize(30, std::vector<bool>(30, 0));

위에서 설명했던 것과 같이 방문 배열을 30 * 30으로 resize해주었다.

DFS(15, 15, 0, 1.0l);

다음은 DFS 함수를 호출하였다. 첫번째와 두번째 인자는 시작 위치이며, 세번째 인자는 움직인 횟수이다.

4번째 인자는 누적확률이다.

함수 내부 코드를 보자.

void DFS(int _X, int _Y, int _CurMoveCount, double _ProbSum)
{
    if (_CurMoveCount >= MoveCount)
    {
        ProbSum += _ProbSum;
        return;
    }

    isVisit[_Y][_X] = true;

    for (int i = 0; i < 4; i++)
    {
        int NextX = _X + DirX[i];
        int NextY = _Y + DirY[i];

        if (Probs[i] == 0)
        {
            continue;
        }

        if (isVisit[NextY][NextX] == false)
        {
            DFS(NextX, NextY, _CurMoveCount + 1, _ProbSum * Probs[i]);
        }
    }

    isVisit[_Y][_X] = false;
}

가장 위의 조건문을 보면, 이동 횟수가 최대 이동 횟수보다 같거나 크게 된 경우 확률을 ProbSum에 누적해준 뒤 return해주었다.

그 다음, isVisit에 현재 위치에 대한 방문 체크를 해주었다.

다음은 4방향에 대해 아직 방문하지 않은 곳이라면 이동하도록 하도록 하였다.

이동할 때, 현재 방향에 대한 확률을 _ProbSum에 곱하여 확률을 갱신하도록 하였다.

(Probs 배열의 인덱스에 대해 0, 1, 2, 3을 동, 서, 남, 북으로 설정하였다.)

printf("%.10lf", ProbSum);

return 0;

DFS가 모두 끝난 뒤, 정답을 출력해주었다.

(문제의 조건이 최대 10^(-9)까지 오차를 인정하고 있기 때문에 소수점 10자리까지 줄력하도록 하였다.)

코드 전문

#include <iostream>
#include <vector>

void Init()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
}

int MoveCount = 0;
double ProbSum = 0;

std::vector<double> Probs;
std::vector<std::vector<bool>> isVisit;

std::vector<int> DirX = { 1, -1, 0, 0 };
std::vector<int> DirY = { 0, 0, 1, -1 };

void DFS(int _X, int _Y, int _CurMoveCount, double _ProbSum)
{
    if (_CurMoveCount >= MoveCount)
    {
        ProbSum += _ProbSum;
        return;
    }

    isVisit[_Y][_X] = true;

    for (int i = 0; i < 4; i++)
    {
        int NextX = _X + DirX[i];
        int NextY = _Y + DirY[i];

        if (Probs[i] == 0)
        {
            continue;
        }

        if (isVisit[NextY][NextX] == false)
        {
            DFS(NextX, NextY, _CurMoveCount + 1, _ProbSum * Probs[i]);
        }
    }

    isVisit[_Y][_X] = false;
}

int main()
{
    Init();
    Probs.resize(4);

    std::cin >> MoveCount;
    
    for (int i = 0; i < 4; i++)
    {
        std::cin >> Probs[i];
        Probs[i] /= 100.0l;
    }

    isVisit.resize(30, std::vector<bool>(30, 0));
    
    DFS(15, 15, 0, 1.0l);

    printf("%.10lf", ProbSum);

    return 0;
}

 

N이라는 숫자를 2의 멱수 (2의 제곱수)의 합으로 표현하는 경우의 수를 구하는 문제이다.

문제 풀이

위의 문제는 DP를 사용하여 해결할 수 있다.

DP를 사용하기 위해선, 먼저 점화식을 세워야 한다.

DP배열의 i번째 인덱스의 원소는 i를 2의 멱수의 합으로 표현할 수 있는 경우의 수라고 하자.

그렇다면, DP[i]에 대한 점화식은 어떻게 될까?

먼저, N을 2의 멱수의 합으로 표현하기 위한 한 가지 간단한 경우가 있다.

(N - 1)을 2의 멱수의 합으로 표현한 것 뒤에 + 1을 더해주는 것이다.

예를 들어, 3을 2의 멱수의 합으로 표현하는 방법은 (1 + 1 + 1) 과 (1 + 2)가 있다.

이 식에 + 1만 추가해준다면, (1 + 1 + 1 + 1), (1 + 1 + 2)로 4를 2의 멱수로 표현하는 경우가 된다.

즉, DP[i - 1]의 값은 그대로 DP[i]에 포함된다고 할 수 있다. (모든 경우에 1만 더하면 i를 만들 수 있으므로)

그렇다면, DP[i] = DP[i -1]; 일까?

한 가지 경우를 더 고려해야 한다.

멱수의 합에 1이 포함되지 않은 경우이다.

2 + 4, 2 + 8, 4 + 4 등의 경우이다.

멱수의 합에 1이 포함되지 않았다면, 식을 이루는 모든 수가 짝수라는 의미가 된다.

즉 2로 묶을 수가 있게 된다. 2 + 4 = 2 * (1 + 2) , 2 + 8 = 2 * (1 + 4) 등등..

즉 N을 1을 제외한 2의 멱수의 합으로 표현하는 것은 2 * (N / 2를 멱수의 합으로 표현한 것) 이라고 할 수 있으며 이를 통해 DP[i / 2] 또한 DP[i]에 포함된다고 할 수 있다.

그렇다면 최종적으로 DP[i] = DP[i - 1] + DP[i / 2]라고 할 수 있다.

하지만, 이 것은 틀렸다.

1이 아닌 2의 멱수로만 합을 표현하는 경우 짝수의 합으로만 N을 구성하기 때문에 반드시 N은 짝수여야 한다.

즉 N이 홀수라면 DP[N / 2]를 더해선 안된다는 것이다.

그러므로 N이 홀수일 땐 DP[N] = DP[N -1]이 되며, N이 짝수일 땐 DP[N] = DP[N - 1] + DP[N / 2]라는 점화식이 성립한다.

풀이 코드

int TargetNumber = 0;
std::cin >> TargetNumber;

std::vector<int> DP(TargetNumber + 1, 0);
DP[1] = 1;
DP[2] = 2;

먼저, 목표 숫자를 입력받은 뒤 해당 숫자 + 1만큼 DP배열을 resize해준다.

그리고, DP[1]과 DP[2]를 1과 2로 초기화해준다.

for (int i = 3; i <= TargetNumber; i++)
{
    if (i % 2 == 0)
    {
        DP[i] = DP[i - 1] + DP[i / 2];
    }
    else
    {
        DP[i] = DP[i - 1];
    }

    DP[i] %= 1000000000;
}

다음은 위에 말했던 점화식을 그대로 사용하면 된다.

std::cout << DP[TargetNumber];
return 0;

마지막으로 목표 숫자에 해당하는 인덱스의 값을 출력해주면 된다.

코드 전문

#include <iostream>
#include <vector>
#include <cmath>
#include <set>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int TargetNumber = 0;
    std::cin >> TargetNumber;

    std::vector<int> DP(TargetNumber + 1, 0);
    DP[1] = 1;
    DP[2] = 2;

    for (int i = 3; i <= TargetNumber; i++)
    {
        if (i % 2 == 0)
        {
            DP[i] = DP[i - 1] + DP[i / 2];
        }
        else
        {
            DP[i] = DP[i - 1];
        }

        DP[i] %= 1000000000;
    }

    std::cout << DP[TargetNumber];
    return 0;
}

알파 테스팅

알파 테스팅이란, 물체를 투명, 불투명으로만 처리하는 방식이다.

알파 값을 0 혹은 1로만 사용하며, 투명한 부분은 아예 클리핑하는 기법이다.

반투명 처리를 하지 않기 때문에, 처리 속도가 매우 빠른 편이라는 장점이 있지만 반투명을 처리하지 않는 만큼 그래픽 표현에 제약이 있는 방식이다.

또한, 오브젝트를 불투명으로만 렌더링하기 때문에 뒤에 가려지는 물체에 대한 렌더링을 할 필요가 없으며 깊이 테스트 또한 정확하게 실행할 수 있게 된다.

알파 블렌딩

반투명을 허용하며 겹쳐있는 물체들의 색을 보간하여 최종 색상을 결정하는 방식이다.

반투명을 처리하는 만큼, 하나의 픽셀에 대해 여러 번의 렌더링이 실행될 수 있다.

알파 테스팅에 비해 다양한 그래픽 표현을 할 수 있게 되지만, 그만큼 처리 속도가 느리다.

또한, 렌더링 순서에 따라 의도하지 않은 클리핑이 발생하는 경우도 있다.

위의 그림을 보자.

앞에 먼저 그려진 풀의 경우, 알파가 0인 부분도 클리핑하지 않고 렌더링을 실행하게 된다. 그 이후 뒤에 있는 풀을 그리게 되면 앞의 풀보다 뒤에 있는 부분이 깊이 테스트에서 걸러지기 때문에, 뒤의 풀이 그려져야 함에도 불구하고 일부분이 그려지지 않는 것을 확인할 수 있다.

알파 블렌딩은 이처럼 그려지는 순서나 위치에 따라 의도하지 않은 클리핑이 발생할 수 있다.

알파 소팅

위의 문제를 해결하기 위해선, 간단한 방법이 있다.

뒤에 있는 물체부터 그리는 것이다.

위의 경우, 붉은색 풀의 일부가 클리핑되는 이유는 초록색 풀이 그려진 부분에서 투명한 곳의 깊이보다 더 깊이가 크기 때문에, 깊이 테스트에서 걸러졌기 때문이다. 

그렇다면, 가장 뒤의 오브젝트부터 순서대로 앞의 오브젝트를 렌더링하게 되면 기존의 깊이보다 깊이가 더 작은 경우에만 렌더링되기 때문에 위의 그림처럼 일부가 가려지는 경우가 발생하지 않을 것이다.

하지만, 알파 소팅을 사용한다고 하더라도 모든 상황에서 문제가 해결되는 것은 아니다.

알파 소팅은 기본적으로 CPU에서 카메라와 물체의 거리를 기준으로 오브젝트를 정렬한 뒤, 렌더링 순서를 정하는 방식이다. 즉, 거리가 더 먼 대상을 먼저 렌더링 한다는 것이다.

그렇다면, 아래의 그림을 보자.

위의 경우에 초록색 물체가 주황색 물체보다 더 앞에 있는 것을 볼 수 있다.

하지만, 카메라와의 거리를 기준으로 판단한다면 초록색 물체가 더 멀리 있다고 볼 수 있다.

이로 인해, 실제로는 주황색 물체가 먼저 그려져야 함에도 불구하고 초록색 물체가 먼저 그려지는 상황이 발생할 수 있다.

이러한 문제를 해결할 수 있는 가장 간단한 방법은 깊이 버퍼를 사용하지 않는 것이다.

새로 그려지는 물체가 항상 앞에 그려지도록 한다면, 위와 같은 문제 없이 간단하게 알파 소팅의 문제점을 해결할 수 있다.

하지만, 깊이 버퍼를 사용하지 않으면 또 다른 문제가 발생하게 된다.

위와 같이, 물체의 내부가 비치는 상황이 발생할 수 있다. 깊이 테스트를 하지 않고 렌더링하기 때문에 반투명한 모든 오브젝트가 섞여서 렌더링되는 것이다.

위와 같이 반투명한 물체들이 겹쳐서 렌더링 되는 경우에 내부가 비치지 않도록 하고 싶다면 2Pass 렌더링을 해야한다.

먼저, 1차적으로 오브젝트를 불투명 상태로 렌더링을 하며 렌더타겟에 깊이를 기록한다.

이후, 해당 깊이값을 이용하여 반투명으로 다시 렌더링하는 것이다. 1차적으로 저장했던 깊이 값보다 더 큰 깊이 값을 가지고 있다면 렌더링하지 않도록 하는 것이다. 이를 통해, 내부가 비치지 않도록 해결할 수 있다.

이 방식은 2번의 Draw Call이 발생하므로, 필요한 상황에만 적절하게 사용하는 것이 좋다. (오버헤드가 발생할 수 있음)

 

N자리의 정수 중, 신기한 소수를 구하는 문제이다.

신기한 소수란, 정수의 가장 앞에서부터 1자리, 2자리, 3자리 .... N자리까지의 숫자가 모두 소수인 수이다.

예를 들어, 7331의 경우 앞에서부터 1자리인 7도 소수이며, 앞에서부터 2자리인 73도 소수이고, 앞에서부터 3자리인 733과 앞에서부터 4자리인 7331도 소수이다.

이러한 수를 모두 출력하면 된다.

문제 풀이

이 문제의 규칙을 한 번 생각해보자.

7331처럼, 신기한 소수가 되는 수는 7, 73, 733, 7331 이 모두 소수이다.

4개의 숫자를 생각해보면, 73은 7의 뒤에 한자리의 숫자가 더해진 형태이며 733은 73의 뒤에 한자리의 숫자가 더해진 형태이다. 7331또한, 733뒤에 한자리의 숫자가 더해진 형태이다.

즉, N자리의 신기한 소수는 (N - 1)자리의 신기한 소수의 뒤에 한 자리의 숫자가 더해진 형태가 된다.

이를 기반으로 1자리 수 부터 탐색을 해보자.

1자리의 신기한 소수는 2, 3, 5, 7이 있다.

2자리의 신기한 수는 1자리의 신기한 수의 뒤에 1자리의 숫자를 더한 형태였다.

그렇다면, 21, 22, 23, 24, 25, 26, 27,28, 29, 31, 32, 33, 34, 35, 36,37, 38, 39 .... 등의 숫자들이 신기한 수의 후보가 될 수 있다. 이 수들 중에 소수인 수가 있다면 해당 수는 신기한 소수일 것이다.

그렇다면, 해당 숫자들을 대상으로 소수 판별을 해야한다.

소수가 되기 위해선 첫 번째로, 가장 마지막 자리가 짝수여서는 안된다.

그러므로, 22, 24, 26, 28 ...등은 후보에서 제외할 수 있다.

남은 숫자 21, 23, 25, 27, 29, 31, 33 등의 숫자를 대상으로 소수 판별을 해보자.

소수를 판별하는 방법은 간단하다. N이라는 숫자가 있을 때, 2~sqrt(N)까지 반복문을 돌면서 N을 해당 수로 나누어보면 된다. 

예를 들어, 15가 소수인지 판별하고 싶다면 2~sqrt(15)까지의 정수에 대해 15를 나누었을 때, 나머지가 0이되는 경우가 있는지를 탐색하면 된다.

15 % 2 = 1

15 % 3 = 0

=> 15가 3으로 나누어지므로, 3이라는 약수가 존재함을 알 수 있다. 이로 인해, 15는 소수가 아님을 알 수 있다.

이렇게, 신기한 수의 뒤에 한자리 수 하나를 더하고 해당 수가 소수인지 아닌지를 판별하는 것을 한자리의 신기한 소수부터 시작해서 계속 반복하면 된다. 계속 반복하여 N자리의 소수를 모두 구한 뒤 출력하면 된다.

풀이 코드

int Digit = 0;
std::cin >> Digit;

먼저, 목표로 하는 자리 수를 입력받아준다.

std::priority_queue<int, std::vector<int>, std::greater<int>> Numbers;
for (int i = 2; i <= 9; i++)
{
    if (isPrimeNumber(i) == true)
    {
        Numbers.push(i);
    }
}

다음은 우선순위 큐에 한자리의 신기한 소수를 모두 삽입해준다.

isPrimeNumber는 해당 수가 소수인지 판별해주는 함수이다. 내부 구현 코드는 잠시 뒤에 보도록 하자.

if (Digit == 1)
{
    PrintAll(Numbers);
    return 0;
}

만약, 입력받은 자리수가 1이었다면, 그대로 모든 우선순위 큐의 모든 원소를 출력해주면 된다.

int Threshold = static_cast<int>(std::pow(10, Digit - 1));

이건, 미리 설정한 한계 수치이다.

예를 들어, 입력받은 자리수가 4라고 한다면 3자리 숫자에 대한 탐색이 끝나는 순간에 탐색을 멈추어야 한다.

3자리 숫자의 뒤에 한 자리 숫자를 더해 4자리 숫자를 구하고, 4자리 숫자의 뒤에 한자리 숫자를 더해 5자리 숫자를 구하는 방식이기 때문에, 현재 참조하는 숫자가 4자리 숫자라면 더이상 탐색을 진행할 필요가 없어진다.

Digit가 4인 경우에, Threshold는 1000이 되고, 현재 숫자가 1000보다 크거나 같다면 반복문을 종료하도록 할 것이다.\

while (true)
{
    int CurNum = Numbers.top();
    if (CurNum >= Threshold)
    {
        break;
    }

    Numbers.pop();

    CurNum *= 10;
    int NextNum = 0;

    for (int i = 0; i <= 9; i++)
    {
        if (i % 2 == 0)
        {
            continue;
        }

        NextNum = CurNum + i;

        if (isPrimeNumber(NextNum) == true)
        {
            Numbers.push(NextNum);
        }
    }
}

우선순위 큐의 원소중 최소값을 기준으로 Threshold 보다 큰지 작은지를 검사하였다.
최소값이 Threshold보다 더 작다면, 그대로 반복문을 종료해준다.

그렇지 않다면, 우선순위 큐의 최소값을 pop한 뒤, 해당 숫자의 뒤에 1을 더한 숫자를 모두 검사하여, 소수인 숫자는 다시 우선순위 큐에 삽입하도록 하였다.

2는 23, 29를 우선순위 큐에 삽입하며, 3은 31과 37을 우선순위 큐에 삽입한다. 5는 53과 59를 우선순위 큐에 삽입하며, 7은 71, 73, 79를 우선순위 큐에 삽입한다.

한 자리 수에 대한 탐색이 모두 끝나게 되면, 두 자리의 숫자를 대상으로 탐색을 하게 된다.

23은 233,239를 우선순위 큐에 삽입하고, 29는 293을 우선순위 큐에 삽입한다. 31은 311,313,317을 우선순위 큐에 삽입하며, 37은 37와 3789를 우선순위 큐에 삽입한다.

이 과정을 N자리 수의 신기한 소수를 모두 구할 때까지 반복하는 것이다.

PrintAll(Numbers);

return 0;

반복문이 끝난 뒤, 우선 순위 큐에 있는 모든 원소를 출력해주면 끝난다.

bool isPrimeNumber(int _Num)
{
    int NumSqrt = std::sqrt(_Num);

    for (int i = 2; i <= NumSqrt; i++)
    {
        if (_Num % i == 0)
        {
            return false;
        }
    }

    return true;
}

위의 코드는 소수를 판별하는 코드이다. 2~sqrt(N)까지 반복문을 돌며, _Num의 약수인 수가 있는지 확인하는 것이다.

void PrintAll(std::priority_queue<int, std::vector<int>, std::greater<int>>& _Numbers)
{
    while (_Numbers.size() > 0)
    {
        std::cout << _Numbers.top() << std::endl;
        _Numbers.pop();
    }
}

위 코드는 우선 순위 큐의 모든 원소를 출력하는 함수이다.

하나씩 pop해주며, top을 계속 출력하도록 하였다.

코드 전문

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

void PrintAll(std::priority_queue<int, std::vector<int>, std::greater<int>>& _Numbers)
{
    while (_Numbers.size() > 0)
    {
        std::cout << _Numbers.top() << std::endl;
        _Numbers.pop();
    }
}

bool isPrimeNumber(int _Num)
{
    int NumSqrt = std::sqrt(_Num);

    for (int i = 2; i <= NumSqrt; i++)
    {
        if (_Num % i == 0)
        {
            return false;
        }
    }

    return true;
}

int main()
{
    Init();

    int Digit = 0;
    std::cin >> Digit;

    std::priority_queue<int, std::vector<int>, std::greater<int>> Numbers;
    for (int i = 2; i <= 9; i++)
    {
        if (isPrimeNumber(i) == true)
        {
            Numbers.push(i);
        }
    }

    if (Digit == 1)
    {
        PrintAll(Numbers);
        return 0;
    }

    int Threshold = static_cast<int>(std::pow(10, Digit - 1));

    while (true)
    {
        int CurNum = Numbers.top();
        if (CurNum >= Threshold)
        {
            break;
        }

        Numbers.pop();

        CurNum *= 10;
        int NextNum = 0;

        for (int i = 0; i <= 9; i++)
        {
            if (i % 2 == 0)
            {
                continue;
            }

            NextNum = CurNum + i;

            if (isPrimeNumber(NextNum) == true)
            {
                Numbers.push(NextNum);
            }
        }
    }

    PrintAll(Numbers);

    return 0;
}

컴퓨터 그래픽스에서 가장 근본적으로 추구하는 것은 최종적으로 렌더링되는 장면의 품질이다.

어떻게 하면 우리가 의도한 것을 그대로 화면에 표현할 수 있는지 혹은 얼마나 더 자연스럽고 사실적으로 표현할 수 있는가에 대한 탐구가 컴퓨터 그래픽스의 근본적 목적이다.

하지만, 우리의 하드웨어는 한계가 있다. 가상의 공간에 현실과 유사하게 렌더링 할 수 있는 기술은 이미 수십년 전부터 마련이 되어 있었지만, 현재 까지도 하드웨어는 그 연산을 모두 감당할 수 없는 상태이다.

이러한 문제로 인해, 그래픽스 분야에선 다양한 최적화 기법이 연구되고 있지만 당연하게도 최적화 기법을 적용하게 되면 어느정도의 품질 손상을 감수해야만 한다. 

가능한 품질의 손상을 적게 하면서 높은 수준의 최적화를 이룰 수 있는 방법으로 고안된 최적화 기법 중 가장 대표적인 것이 LOD이다.

LOD (Level Of Detail)

LOD란, 이름 그대로 디테일의 정도를 조절하는 기능이다. 

그래픽스에서 최적화를 달성하는 방법은 크게 두 가지가 있다. 

하나는 드로우 콜을 줄이는 것이고, 하나는 렌더링되는 폴리곤을 줄이는 것이다.

LOD는 후자에 속한다. 렌더링이 되는 매쉬의 폴리곤을 줄이는 것이다.

그런데, 폴리곤을 무작정 줄이면 오브젝트의 모양이 상당히 부자연스럽게 보일 것이다.

아래 사진을 보자.

언리언 엔진의 기능을 사용하여, LOD를 적용한 것이다.

왼쪽은 원본 그대로이고, 오른쪽은 폴리곤의 수를 줄인 채로 렌더링한 것이다.

상당히 부자연스럽고 뾰족하게 렌더링된 것을 볼 수 있다.

이렇게 렌더링하면, 최적화 부분에서야 당연히 이점이 있겠지만 렌더링 퀄리티가 너무 처참하게 낮아진다.

그럼에도 불구하고 LOD를 쓰는 이유는 뭘까?

아래 사진도 한 번 보자.

이번엔, 조금 멀리서 오브젝트를 렌더링하였다. 가까이 봤을 때랑 비교했을 때, 차이가 느껴지지 않는다.

주변에 배경이 깔리고 여러가지 효과가 적용되면 사실상 차이를 느끼지 못할 것이다.

폴리곤의 개수를 줄이면, 가까이서 봤을 땐 매쉬의 모양이 상당히 부자연스럽게 렌더링된다.

하지만, 멀리서 본다면 제대로 렌더링 했을 때와 그렇게 큰 차이를 느낄 수가 없다.

그렇다면, 멀리서 볼 땐 폴리곤의 개수를 줄이는 것이 좋은게 아닐까?

LOD는 이런 개념에서 시작된 것이다. 오브젝트가 멀어지거나 작아질수록 디테일하게 렌더링되지 못한다.

그러므로, 폴리곤을 줄이거나 텍스쳐의 해상도를 낮춰도 거의 티가 나지 않는다.

이처럼, 거리 등을 기준으로 폴리곤의 개수를 유동적으로 줄였다 늘렸다 하는 기술이 LOD이다.

폴리곤의 개수가 10만개인 매쉬를 화면에 렌더링한다고 해보자.

그런데, 오브젝트가 아주 멀리있어서 거의 점처럼 보이는 상황이라면, 폴리곤을 무식하게 2~3개로 줄여버려도 큰 차이를 느끼지 못할 것이다. LOD를 사용하면, 10만개의 폴리곤을 2~3개로 만들어버릴 수도 있는 것이다. (실제로는 이렇게 극단적으로 줄이는 경우는 거의 없을 것이다.)

거리 기반 LOD, 면적 기반 LOD

LOD는 어떤 기준에 따라 폴리곤을 줄이고 늘리는 기법이다.

그 기준이 되는 것은 보통 거리와 면적이 있다.

거리란, 카메라의 위치를 기준으로 물체가 얼마나 멀리있느냐를 기준으로 하는 것이다.

오브젝트가 충분히 멀리있다면 폴리곤의 수를 기존보다 줄이고 충분히 가깝다면 원래의 폴리곤으로 렌더링을 하는 것이다. 

거리 기반 LOD는 면적 기반에 비해 연산이 상대적으로 가볍지만, 한 가지 문제가 있다.

거리로 봤을 때는 멀리 있지만, 실제로는 화면에 크게 렌더링되는 경우가 있다.

뒤 쪽의 황금 나무를 보자.

실제로는 카메라와 거리가 상당히 먼 곳에 위치하고 있지만, 그 크기가 매우 커서 화면에 아주 크게 렌더링되고 있다.

LOD는 어쨋든, 화면에서 잘 눈에 안띄어서 폴리곤의 수를 줄여도 시각적 경험의 차이가 적도록 하는 것이 목적이다.

그런데, 저렇게 크게 렌더링되고 있는 대상의 폴리곤을 무작정 줄여버리면 부자연스럽게 보일 수도 있을 것이다.

반면, 거리는 가까이 있지만 크기가 작아 디테일하게 표현할 필요가 없는 대상을 디테일하게 렌더링하는 경우도 있을 수 있다.

이 때문에, 거리 기반 LOD의 경우 상황에 따라 렌더링 품질이 감소하거나, LOD를 제대로 적용하지 못해 최적화를 달성하지 못하는 문제가 발생할 수 있다.

면적 기반 LOD는 물체가 화면에서 얼마나 차지하는 가를 기준으로 LOD를 적용한다. 화면에서 실제로 렌더링되고 있는 크기를 기준으로 폴리곤의 수를 조절하기 때문에, 거리 기반 LOD에 비해 렌더링 품질을 더 보존할 수 있다는 장점이 있다.

다만, 면적을 계산하는 과정을 CPU에서 진행해야 하기 때문에 CPU에 부하를 줄 수 있다는 단점이 있다.

*LOD 단계 : 폴리곤의 수를 얼마나 줄일지 단계를 나누어 LOD를 적용한다.

*LOD 효율 : 렌더링 품질을 얼마나 보존할 수 있는가

Static LOD, Dynamic LOD

LOD란, 특정 기준에 따라 렌더링 되는 폴리곤의 수를 조절하는 것이라고 하였다.

폴리곤의 수를 조절하는 방법은 크게 두 가지로 분류된다.

static LOD는 디자이너가 매쉬를 만들 때, LOD단계에 따라 여러 개의 매쉬를 만들어 놓는 것이다.

하나의 파일(Fbx, Obj 등등)에 LOD단계에 따라 달라지는 버텍스의 정보가 미리 저장되어 있기 때문에 빠르게 런타임에 LOD단계를 조절할 수 있다. 다만, 미리 만들어 놓는다는 것은 그만큼 메모리 사용량이 많아진다는 뜻이다.

static LOD는 런타임 성능에 영향을 크게 미치지 않지만, 메모리를 많이 사용하게 되며 로딩 시간이 길어질 수 있다.

dynamic LOD는 버텍스의 수를 CPU연산을 통해 런타임에 조절하는 것이다. dynamic LOD는 LOD 단계에 따른 버텍스의 수를 미리 저장해놓지 않기 때문에, 메모리 사용량이 적지만 런타임 성능에 영향을 줄 수 있다는 단점이 있다.

dynamic LOD는 한 가지 장점이 더 있는데, static LOD는 LOD단계에 따른 폴리곤의 수가 미리 정해져 있기 때문에 LOD단계가 바뀔 때, 이전 단계와의 차이에 따라 유저가 급격한 변화를 느낄 수가 있다. 반면, dynamic LOD는 유동적으로 폴리곤의 수를 조절할 수 있기 때문에 상대적으로 변화를 느끼는 정도가 적다는 장점이 있다.

Popping

Popping란, LOD 단계가 변할 때 유저가 급격한 차이를 느끼는 현상이다. 만약, LOD가 변하는 특정 거리 근처에서 계속 왔다갔다 하게 되면 오브젝트가 계속 변하는 것을 확인할 수 있을 것이다.

위의 영상은 유튜브에서 발견한 LOD Popping 영상이다. 동영상을 보면, 오브젝트가 거리에 따라 변화하는 것을 볼 수 있는데, 이러한 문제를 Popping이라고 한다.

이를 해결하기 위해 LOD단계간의 폴리곤 개수나 위치 등을 보간하면서 자연스럽게 보이도록 하는 연산을 활용하기도 한다고 한다.