어느 게임 개발자의 기록

이 게시글에선 실제로 노말맵을 적용하는 수학적 연산은 설명하지 않을 것이다.

두 노말맵의 종류와 장단점에 대해선만 설명할 것..

우리는 3D 오브젝트의 표면 색상을 자연스럽게 결정짓기 위해 표면의 노말(법선)을 사용해 빛을 계산하여 색상을 결정짓곤 한다.

일반적으로 이 노말 벡터의 정보는 각 버텍스(정점)에 담겨져 있으며 버텍스 쉐이더의 Input으로 받아서 사용할 수 있다.

하지만, 버텍스에 저장된 노말 벡터를 사용하는 것은 다소 한계가 있다.

이러한 모델을 생각해 보자. 벽돌 사이 시멘트 부분은 움푹 파여있으므로 이 부분에 대해선 노말벡터가 벽돌의 평면과 다르게 적용되어야 한다. 이러한 노말 벡터의 값을 모든 정점이 보유하게 하려면 해당 모델의 정점 개수는 매우 많아질 것이고 이는 메모리 사용량과 쉐이더 연산량의 증가로 이어진다. 즉 최적화 측면에서 매우 손실을 보게 된다.

이러한 개념에서 시작된 것이 노말맵이다. 먼저, 위의 모델을 표현하기 위해 4각형 하나를 만들고, 그 위에 평면의 벽돌 색상의 디퓨즈(알베도) 텍스쳐를 입히는 것이다. 그리고 또 하나의 텍스쳐에는 의도에 맞게 노말 벡터를 저장하여, 버텍스에 저장된 노말 값이 아닌 해당 텍스쳐에 저장된 노말값을 사용하여 빛을 연산하는 것이다.

이렇게 되면, 정점별로 노말 벡터를 저장하기 위해 매우 많은 정점을 만들고 데이터를 보관할 필요 없이 하나의 텍스쳐만을 추가로 활용하여 음영을 디테일하게 연산할 수 있게 되는 것이다. (물체를 실제로 울퉁불퉁하게 만드는 것이 아니라, 실제로는 평면이지만 울퉁불퉁한 물체인 것처럼 노말 벡터를 저장하여 빛을 연산하여 속이는 것이다.)

그리고, 그 노말 벡터가 저장된 텍스쳐를 노말 맵(Normal Map)이라고 한다.

이러한 노말 맵에는 두 가지의 종류가 있다. 로컬 스페이스 노말 맵과 탄젠트 스페이스 노말 맵이다.

로컬 스페이스 노말 맵

로컬 스페이스 노말 맵이란, 3D 모델의 방향(회전이 적용되지 않은 상태)를 기준으로 노말을 계산하여 저장하는 것이다.

이렇게 구형의 물체가 있다고 가정해보자. 회색 네모가 칠해진 최상단의 버텍스의 UV좌표가 (0, 0)이라고 가정해보자.

하늘색 화살표는 해당 정점의 노말 벡터이다.

이 때, 물체가 회전하여 아래와 같이 된다면?

이 때, 노말 벡터는 아래 그림처럼 향하는 것이 우리가 의도한 방향일 것이다.

하지만 노말맵에서 매핑하여 사용하게 되면 아래 그림과 같이 되어있다.

노말 맵은 물체가 회전되지 않은 최초의 형태를 기준으로 값이 저장되어 있으므로, 노말맵의 값을 그대로 사용하면 이렇게 노말이 제대로 적용되지 않는다. 그러므로 물체의 회전 행렬을 노말 벡터에도 곱해주어 노말 벡터에 매번 회전을 적용해주어야 정상적으로 적용된다.

로컬 스페이스의 노말 맵은 이처럼 물체의 회전에 영향을 받지 않는 상태로 저장되어 있으므로 매번 회전을 적용하여 벡터의 방향을 갱신해야 한다.

탄젠트 스페이스 노말맵

탄젠트 스페이스 노말 맵은 버텍스의 탄젠트, 바이탄젠트, 노말 값을 축으로 사용하는 탄젠트 공간에서 저장된 노말 벡터를 사용하는 노말 맵이다. 이게 무슨말이냐면...

하나의 정점에는 노말 벡터가 존재하고, 그 노말 벡터에 수직인 탄젠트가 존재한다. 여기서 탄젠트란 해당 정점의 접선이라고 할 수 있다. 그리고 탄젠트 벡터와 노말 벡터에 대해 수직인 또 하나의 벡터(바이 탄젠트)도 존재할 것이다.

이 3개의 벡터를 X,Y,Z 축으로 활용해 T(탄젠트), B(바이 탄젠트), N(노말) 축을 만들 수 있고 이 축에 대해 노말 값을 저장하는 것이 탄젠트 스페이스 노말 맵이다.

그런데 왜 이렇게 복잡하게 노말 값을 저장하는 걸까?

로컬 스페이스 노말맵과 탄젠트스페이스 노말맵의 장단점

일반적으로 프로그래밍에서 어떠한 기법의 장점을 말한다면 항상 3가지 중 하나로 답이 나온다.

빠르거나, 메모리를 적게 사용하거나, 편하거나.

이 3개를 기준으로 두 노말맵을 비교해보겠다.

1. 누가 더 빠른가?

로컬 스페이스 노말맵은 매번 픽셀 쉐이더에서 회전행렬을 곱해주어야 한다.

하지만, 탄젠트 스페이스 노말맵은 회전행렬을 버텍스 쉐이더에서 곱해도 된다.

왜냐하면, 탄젠트 스페이스에서 정의된 노말 벡터의 경우, 노말 벡터에 회전을 적용하는 것이 아니라 정점의 탄젠트, 바이 탄젠트, 노말에 회전을 적용해야 하기 때문이다. 이 정보는 정점 단위로 주어지므로 버텍스 쉐이더에서 해결할 수 있다.

즉 회전 연산 자체는 탄젠트 스페이스가 일반적으로 더 적게 수행되는 편이다.

하지만, 빛을 적용하기 위해선 광원과 노말벡터의 좌표계를 맞춰주어야 한다. 광원을 탄젠트 스페이스로 옮기든가, 노말 벡터를 월드 스페이스로 옮기든가. 광원을 탄젠트 스페이스로 옮기는 것은 버텍스 쉐이더에서 수행할 수 있으므로 광원을 탄젠트 스페이스로 옮겨서 빛을 계산하는 것이 일반적으로 더 효율적일 것이다.

하지만, 로컬 스페이스 노말맵의 경우엔 이런 연산을 하지 않아도 된다. (이미 광원과 좌표계가 일치하므로)

그렇기 때문에 회전하지 않는 물체에 대해서 로컬 스페이스 노말맵은 회전도 좌표변환도 수행하지 않아도 되기 때문에 연산량이 상대적으로 매우 적지만, 탄젠트 스페이스 노말맵은 항상 좌표계를 맞춰주는 연산을 해야하기 때문에 회전하지 않는 물체에 대해서는 더 많은 연산이 수행될 것이다.

그러므로 일반적으로 생각했을 때, 회전하는 동적인 물체에 대해선 탄젠트 스페이스 노말 맵이 더 성능에 유리하지만 회전하지 않는 정적인 물체에 대해선 로컬 스페이스 노말 맵이 더 성능에 유리할 것이다.

2. 누가 더 메모리를 적게 사용하는가?

노말 맵에 저장된 노말 벡터는 일반적으로 정규화되어 저장된다. 정규화되었다는 뜻은 X^2 + Y^2 + Z^2의 값이 1이라는 뜻이다. 이 때, X, Y 를 알면 Z를 얼추 구할 수 있다. Z^2 = 1 - X^2 - Y^2 이기 때문이다.

하지만, X, Y를 알더라도 z를 정확히 구할 수는 없다. 왜냐하면 양수와 음수 두 가지가 존재하기 때문이다. 어느 것이 실제 값인지 유추할 수 없으므로 우리는 x,y,z를 모두 정확히 알아야만 한다.

하지만, 탄젠트 스페이스의 경우 조금 다르다. 탄젠트 스페이스는 정점을 기준으로 정의된 공간이다. 이 탄젠트 스페이스에서 정점의 노말은 항상 양의 방향을 향한다. (당연하지만 법선은 평면의 표면이 향하는 방향이다. 이 방향은 항상 양의 방향일 수 밖에 없다.)

그러므로 탄젠트 스페이스에서 정의된 노말 벡터는 x, y만 알더라도 z를 유추할 수 있게 된다. 그러므로 노말 맵에도 R,G,B 채널 모두 사용할 필요 없이 R,G 채널만 사용하여 값을 저장할 수 있게 된다. 이로 인해 탄젠트 스페이스 노말맵은 B, A 채널을 다른 목적(러프니스, 메탈릭 등)을 위해 사용할 수 있게 되고, 이로 인해 메모리를 절약할 수 있게 된다.

3. 누가 더 사용하기 편한가?

이건 사실 둘 다 또이또이 인 듯 하다. 둘 다 사용하기 어려운 것도 아니고, 누가 더 편하고 말고 할 건 크게 없는 듯 하다. 굳이 따지자면 탄젠트 스페이스의 경우 좌표계를 고려해야 하기 때문에 조금 더 복잡할 수는 있다.

결론

회전하지 않는 물체에 대해서 로컬 스페이스 노말맵을 사용하게 되면, 메모리를 조금 더 사용하는 대신 더 빠르게 연산을 수행할 수 있다.

회전하는 물체에 대해선 탄젠트 스페이스 노말맵이 성능, 메모리 두 측면에서 모두 유리하다.

C++ 에선 컴파일러에게 함수의 성질을 알려주어 최적화를 수행하거나 경고를 제거하는 등의 작업을 도울 수 있다.

이 기능이 Attribute이다.

Attribute는 종류가 여러가지가 있으므로 하나씩 알아보자.

[[noreturn]]

[[noreturn]] 은 이름 그대로, 반환하지 않는다는 의미이다. 함수가 반환된다는 것은 return 을 만나 함수가 종료되고, 다음 동작이 수행되는 것을 의미한다. [[noreturn]] 이란, 해당 함수가 절대 반환되지 않고 다음 동작이 수행되지 않음을 의미한다.

예를 들어, 아래의 코드를 보자.

int main()
{
    std::exit(0);
    int A = 0;
    
    return 0;
}

std::exit 함수가 실행되면 프로그램은 그대로 종료된다. 다른 일반적인 함수가 호출되었다면 int A = 0; 과 return 0; 의 구문까지 모두 수행되어야 하지만, std::exit() 함수는 그 즉시 프로그램을 종료하는 역할이기 때문에 다음 코드가 수행되지 않는다. 이러한 경우를 함수가 반환하지 않는 경우라고 할 수 있다.

이 때, [[noreturn]] 키워드를 통해, 컴파일러에게 해당 함수는 반환하지 않는다는 것을 알려줄 수 있다. 컴파일러가 이를 알게 되면, 절대 수행될 수 없는 코드(noreturn 함수 이후에 수행되는 코드)를 판별할 수 있게 되고, 이를 제거하여 컴파일하게 된다. 코드 용량이 조금이나마 절약되는 효과가 있을 것이다.

또한, 컴파일러는 noreturn 이후에 수행되는 구문에 컴파일러 경고를 띄워주는데, 프로그래머는 이를 확인하여 의도에 맞게 코드를 수정할 수 있게 된다. (noreturn 이전에 실행되어야 하는 구문이 noreturn 이후에 실행되고 있는 등의 설계 오류를 수정 가능) 

[[noreturn]] void Exit()
{
    throw std::exception();
}

이렇게 함수 앞에 붙여 속성을 명시할 수 있게 된다. throw 키워드를 통해 예외를 던지는 경우에도 예외를 catch한 후에 프로세스가 종료되므로 [[noreturn]] 키워드를 사용하여 의미를 명시할 수 있다.

이렇게 [[noreturn]] 키워드가 사용된 함수 이후에 작성된 구문은 도달할 수 없다는 경고를 보여주게 된다.

[[deprecated]]

이 attribute는 더이상 함수가 사용되지 않음을 프로그래머에게 알려주기 위해 사용한다.

예를 들어, 내가 만든 라이브러리를 배포한다고 해보자. 이전 버전에선 특정 함수를 사용했었으나, 라이브러리의 버전이

높아지면서 해당 함수를 더이상 사용하지 않는 경우에는 이를 라이브러리 사용자에게 알려줄 필요가 있게 된다. 이 때, [[deprecated]] 를 사용하여 알려줄 수 있다.

사용되지 않는다는 에러가 발생하는 것을 확인할 수 있다.

아래와 같이 사용하면 그 사유를 함께 알려줄 수도 있다.

사유도 함께 명시되는 것을 확인할 수 있다.

[[fallthrough]]

switch 문을 사용할 때, 우리는 아래와 같이 사용한다.

int main()
{
    int A = 0;
    
    switch(A)
    {
    case 0:
        A += 0;
        break;
    case 1:
        A += 1;
        break;
    default:
        A += 2;
        break;
    }

    return 0;
}

A의 값에 따라 서로 다른 분기로 들어가고, break를 만나면 switch문을 탈출하여 다음 코드를 수행하게 된다.

하지만 break가 없는 상황이라면?

int main()
{
    int A = 0;
    
    switch(A)
    {
    case 0:
        A += 0;
    case 1:
        A += 1;
    default:
        A += 2;
        break;
    }

    return 0;
}

이런 경우엔, A의 값에 따라 처음 들어간 분기를 시작으로 break를 만날 때까지 모든 코드를 수행하게 된다.

일반적으로는 이런 경우 컴파일 경고가 발생하게 된다. 하지만, 의도적으로 코드를 이렇게 작성하였다면 해당 경고가 필요 없게 된다. 그런 경우 [[fallthrough]]를 사용하여 경고를 제거할 수 있다.

int main()
{
    int A = 0;
    
    switch(A)
    {
    case 0:
        A += 0;
        [[fallthrough]];
    case 1:
        A += 1;
        [[fallthrough]];
    default:
        A += 2;
        break;
    }

    return 0;
}

이렇게 의도된 코드임을 명시하여 경고를 제거할 수 있다.

[[nodiscard]]

해당 함수의 반환값이 낭비되는 경우 경고를 방출해주는 attribute이다.

아래의 코드를 보자.

int Function()
{
    int A = 0;
    return A;
}

int main()
{
    Function();
    return 0;
}

위의 코드에서 Function은 A를 반환하고 있지만, 반환값을 전혀 사용하고 있지 않다. 의도된 경우엔 상관이 없지만, getter처럼 애초부터 반환 값을 사용하는 것이 호출 목적인 경우 반환값을 반드시 사용하라고 경고하는 것이 좋다.

이 때, 아래와 같이 사용할 수 있다.

함수 앞에 nodiscard 속성을 명시하였고, 컴파일 경고가 발생함을 확인할 수 있다.

이 4가지 말고도 추가적인 attribute가 있지만, 이는 추후 추가적으로 작성해보도록 하겠다!

C++ 에서는 shared_ptr 이라는 스마트 포인터를 제공해준다.

shared_ptr을 활용하면 동적 메모리의 해제를 직접 신경쓸 필요가 없어져 편리하고 안전하게 메모리를 관리하는 것이 가능해진다. 하지만, shared_ptr에는 치명적인 단점이 하나 있다. 바로 순환참조 문제이다.

두 객체를 shared_ptr로 만들고, 각 객체의 멤버변수에 상대 객체를 가리키는 상황이 발생한다면? 두 shared_ptr은 상대 객체가 소멸하기만을 기다리다가 둘 다 소멸하지 못하는 상황이 발생하고 만다.이를 해결하기 위해 탄생한 것이 weak_ptr이다.

std::make_shared 함수를 통해 동적 메모리를 할당하고 그 메모리를 관리하는 스마트 포인터 객체를 만들었다면, 동적 메모리와 함께 참조 테이블이 생성된다.

참조 테이블엔 강한 참조 카운트와 약한 참조 카운트가 존재하며, 메모리 영역을 가리키는 shared_ptr 객체의 수에 따라 강한 참조 카운트가 증가하거나 감소하게 된다. 그리고 강한 참조 카운트가 0이 되면 메모리 영역을 해제하게 된다.

weak_ptr은 강한 참조 카운트에는 영향을 주지 않고 약한 참조 카운트에만 영향을 준다. 즉, 메모리 영역을 가리키고 있는 shared_ptr이 없다면 해당 메모리 영역을 관리하는 weak_ptr이 있더라도 메모리 영역은 해제된다는 것이다.

이를 통해 멤버함수에서 shared_ptr이 아닌 weak_ptr로 상대 객체를 가리키게 되면 순환참조에서 벗어날 수 있게 되는 것이다. 하지만, 이 상황엔 아무런 문제가 발생하지 않을까?

아래의 그림을 보자.

이렇게 3개의 shared_ptr과 1개의 weak_ptr이 메모리 영역을 가리키고 있다고 해보자.

현재 강한 참조 카운트는 3이고, 약한 참조 카운트는 1이다.

이 때, 아래의 그림과 같이 참조 상태가 변경된다면?

3개의 shared_ptr 객체가 nullptr을 가리키고 있거나 객체가 소멸한 상황이라면 이처럼 동적 메모리를 가리키는 것은 weak_ptr 뿐이고 이 때, 강한 참조 카운트는 0이되어 메모리 영역을 해제하게 된다.

그런데, 잘 생각해보자. 위 그림을 보면 무언가 떠올라야 한다. 바로 댕글링 포인터이다. 메모리 영역은 해제되었지만 weak_ptr은 여전히 메모리 영역을 가리키고 있고, 객체가 소멸되지 않은 상황이다. 이 때, weak_ptr을 통해 메모리 영역에 접근한다면 어떻게 될까? 당연히 유효하지 않은 메모리 영역에 접근하게 되어 오류가 발생할 것이다.

이를 해결하기 위해 우리는 weak_ptr의 멤버함수를 통해 메모리 영역의 유효성을 판단해야 한다. weak_ptr의 멤버함수에는 expired라는 함수가 있다. 이 함수가 true를 반환하면 메모리 영역은 유효하지 않다는 의미이며, false를 반환하면 메모리 영역이 유효하다는 의미이다.

if(WeakPtr.expired() == false)
{
    //메모리 영역에 접근하는 코드
}

즉 위 코드와 같이 로직을 작성할 수 있다. 하지만, 여기서도 문제가 발생할 여지는 있다. 바로 멀티 스레드 환경에서 발생할 수 있는 문제이다.

WeakPtr의 유효성을 검사한 시기엔 expired가 false였지만, 메모리에 접근하기 직전 다른 스레드에서 shared_ptr객체의 참조를 끊어 해당 메모리 영역을 해제하였다면? 위의 코드에서 메모리 영역에 실제 접근하는 순간엔 오류가 발생하게 될 것이다.

이를 위해, 우리는 lock()을 사용해 일시적으로 강한 참조 카운트를 증가시키는 것이 좋다. weak_ptr을 사용하면 직접적으로 메모리 영역에 접근할 수 없고, lock()함수를 사용해야만 접근할 수 있다.이 lock()이라는 함수는 weak_ptr의 형태로 메모리에 접근하게 해주는 것이 아니라 shared_ptr 객체를 하나 만들어주는 역할을 한다. 

즉, weak_ptr의 lock을 호출하면 강한 참조 카운트가 1이 증가하게 되므로 다른 스레드에 의해 해당 메모리 영역이 해제되는 것을 방지할 수 있게 된다. (최소한의 1은 현재 스레드에서 보장하고 있으므로)

weak_ptr의 lock()함수는 참조할 메모리 영역이 없다면 nullptr을 반환하기 때문에, weak_ptr 의 lock()가 반환하는 값이 nullptr인지를 판단하여 유효성을 검사하는 것이 expired보다 더 안전할 수 있다.

std::shared_ptr<int> LockPtr = WeakPtr.lock();

if(LockPtr != nullptr)
{
    //메모리 접근
}

weak_ptr은 순환참조를 방지하는 역할을 해주지만, 잘못 사용하면 안정성을 크게 해칠 수 있으므로 반드시 위와 같은 안전검사를 해주도록 하자!

Rider가 Visual Studio 보다 가볍다는 말이 있어서 관심은 갔었는데, 유료라서 선뜻 구매할 생각은 못했었다.

그런데 최근 비영리용으로는 무료 제공을 하는 것으로 정책이 바뀌어서 사용해보기로 하였다!

(언리얼 엔진에서 컴파일 드럽게 오래걸리고 인텔리센스 먹통이던게 조금 괴로웠어서 기대감을 품으며!)

그런데 라이더를 깔자마자 뭔 코드에 경고가 엄청 많이 떴다. 보니까 작명규칙을 강제하는 거였는데, 분명 이걸 설정하는 옵션이 있을 것 같아서 찾아보니 당연히 있었다.

설정 -> 에디터 -> 코드스타일 -> 사용 언어(C#, C++ 등) -> 이름 지정

위에 언급한 대로 이동하면 사진처럼 규칙 설정란이 나온다.

본인은 대부분 파스칼케이스를 사용했어서 그렇게 설정하였다.

(파스칼케이스란 단어의 앞글자를 모두 대문자로 표기하는 것이고, 어퍼 카멜 케이스와 동일하다.)

또한 본인은 파라미터의 앞에는 _를 붙이는 것이 습관이라 파라미터에는 접두사로 _도 지정해주었다.

그런데, 내가 파라미터 앞에 _를 붙여온 이유가 C++이 내부적으로 그렇게 코드를 작성하고 있었기 때문에 따라한 것 이었다. 근데 C++ 에서 내부적으로 쓰고있으니까 쓰지 말라는 경고가 뜨는거 아니겠는가?!

그래서 해당 옵션도 제거해주었다.

코드에 경고가 발생했을 때 마우스를 올려서 경고 내용을 확인해보면 경고 내용 가장 뒤에 어떤 항목에 의해 경고가 발생되고 있는지 []에 담아서 알려준다.

그걸 여기서 찾아서 꺼주면 된다. 본인은 가장 위에 보이는 bugprone-reserved-identifier clang-tidy check 를 꺼주었다.

그런데 이걸 끔으로써 다른 오류를 발견하지 못하는 상황이 발생할 수도 있어서, 좀 사용해보면서 테스트좀 해봐야할듯 하다.

최소신장트리 문제이다. 모든 컴퓨터를 연결하여 최소신장트리를 구성하면 된다. 다만, 일반적인 최소신장트리와는 입력이 다르기 때문에 비용으로 주어진 2차원 배열의 모든 값을 간선으로 사용해야 한다.

또한, 최초에 연결되어 있는 간선이 있기 때문에 해당 간선은 미리 연결해준 뒤에 크루스칼이나 프림 알고리즘을 사용하면 된다. 본인은 크루스칼 알고리즘을 사용하였다.

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

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

int GetParent(std::vector<int>& _Parents, int _Index)
{
    if (_Parents[_Index] != _Index)
    {
        _Parents[_Index] = GetParent(_Parents, _Parents[_Index]);
    }

    return _Parents[_Index];
}

void Union(std::vector<int>& _Parents, int _Left, int _Right)
{
    int LeftParent = GetParent(_Parents, _Left);
    int RightParent = GetParent(_Parents, _Right);

    if (LeftParent < RightParent)
    {
        _Parents[RightParent] = LeftParent;
    }
    else
    {
        _Parents[LeftParent] = RightParent;
    }
}

bool IsCycle(std::vector<int>& _Parents, int _Left, int _Right)
{
    return GetParent(_Parents, _Left) == GetParent(_Parents, _Right);
}

int main()
{
    Init();

    int NumComputer = 0, NumLink = 0;
    std::cin >> NumComputer >> NumLink;

    std::vector<int> Parent(NumComputer);
    for (int i = 0; i < NumComputer; i++)
    {
        Parent[i] = i;
    }

    for (int i = 0; i < NumLink; i++)
    {
        int Start = 0, End = 0;
        std::cin >> Start >> End;
        Start--, End--;

        Union(Parent, Start, End);
    }

    std::vector<std::tuple<int, int, int>> Edge;
    Edge.reserve(NumLink);

    for (int i = 0; i < NumComputer; i++)
    {
        for (int j = 0; j < NumComputer; j++)
        {
            int Cost = 0;
            std::cin >> Cost;

            if (i > 0 && j > 0 && i < j)
            {
                Edge.push_back({ Cost, i, j });
            }
        }
    }
    
    int AnswerCost = 0;
    std::vector<std::pair<int, int>> AnswerPairs;

    std::sort(Edge.begin(), Edge.end());
    
    for (int i = 0; i < Edge.size(); i++)
    {
        auto& [Cost, Start, End] = Edge[i];

        if (IsCycle(Parent, Start, End) == false)
        {
            Union(Parent, Start, End);
            
            AnswerCost += Cost;
            AnswerPairs.push_back({ Start + 1 , End + 1 });
        }
    }

    std::cout << AnswerCost << " " << AnswerPairs.size() << "\n";

    for (const auto& Pair : AnswerPairs)
    {
        std::cout << Pair.first << " " << Pair.second << "\n";
    }

    return 0;
}

처음엔 BFS나 DFS로 최단거리를 찾는 문제인가 했지만, 이 문제의 경우 BFS나 DFS로 하면 왔던 경로를 다시 돌아가야 하는 상황이 생기면서 문제가 발생한다.

아무든 최소비용으로 모든 정점을 연결하는 것이 문제의 핵심이고, 다시 생각해보니 크루스칼 알고리즘이 있었다. 크루스칼 알고리즘은 최소신장트리를 찾는 알고리즘으로 위에서 말한 대로 최소비용으로 모든 정점을 연결하는 알고리즘이다.

크루스칼 알고리즘을 통해 최소비용을 구하는 것은 그냥 알고리즘을 그대로 적용하면 되니까 어렵지 않다. 다만, 문제에는 간선을 하나 연결할 때마다 증가하는 비용 t가 존재한다. 이 t는 크루스칼 알고리즘을 통해 간선을 하나 처리할 때마다 1씩 더해지는 값을 누적하여 t가 더해질 개수를 구하고 최종적으로 비용에 더해주면 된다.

무슨 말이냐면, 간선을 1개 연결할 때엔 간선의 비용이 발생하고, 2개를 연결할 때엔 t가 추가적으로 발생한다. 3개를 연결할 때엔 앞에서 더해진 t와 함께 t가 한 번 더 더해진다.

즉, n개의 간선을 연결하면 0 + 1 + 2 + 3 + 4 ..... n - 1만큼의 t가 더해지는 셈인 것이다. 이 개수와 t를 곱해서 크루스칼 알고리즘으로 구한 최소비용에 더해주면 된다.

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

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

int GetParent(std::vector<int>& _Parent, int _Index)
{
    if (_Parent[_Index] != _Index)
    {
        _Parent[_Index] = GetParent(_Parent, _Parent[_Index]);
    }

    return _Parent[_Index];
}

void Union(std::vector<int>& _Parent, int _Left, int _Right)
{
    int LeftParent = GetParent(_Parent, _Left);
    int RightParent = GetParent(_Parent, _Right);

    if (LeftParent < RightParent)
    {
        _Parent[RightParent] = LeftParent;
    }
    else
    {
        _Parent[LeftParent] = RightParent;
    }
}

bool IsCycle(std::vector<int>& _Parent, int _Point1, int _Point2)
{
    return GetParent(_Parent, _Point1) == GetParent(_Parent, _Point2);
}

int main()
{
    Init();

    int NumCity = 0, NumEdge = 0, AddCost = 0;
    std::cin >> NumCity >> NumEdge >> AddCost;

    //비용, X, Y
    std::vector<std::tuple<int, int, int>> Edge(NumEdge);
    for (int i = 0; i < NumEdge; i++)
    {
        std::cin >> std::get<1>(Edge[i]) >> std::get<2>(Edge[i]) >> std::get<0>(Edge[i]);
        
        std::get<1>(Edge[i])--;
        std::get<2>(Edge[i])--;
    }

    std::sort(Edge.begin(), Edge.end());

    int SumCost = 0;
    int EdgeCount = 0;
    int AddCount = 0;

    std::vector<int> Parent(NumCity);
    for (int i = 0; i < NumCity; i++)
    {
        Parent[i] = i;
    }
    
    for (int i = 0; i < NumEdge; i++)
    {
        if (IsCycle(Parent, std::get<1>(Edge[i]), std::get<2>(Edge[i])) == false)
        {
            Union(Parent, std::get<1>(Edge[i]), std::get<2>(Edge[i]));
            SumCost += std::get<0>(Edge[i]);
            
            EdgeCount += AddCount;
            AddCount++;
        }
    }

    SumCost += AddCost * EdgeCount;

    std::cout << SumCost;

    return 0;
}

플래티넘을 찍긴 했는데, 뻥티어가 아닌가 하는 생각이 강하게 든다.. 아직도 골드 문제를 제대로 못푸는 것도 많고, 실력이 그저 그런 것 같은데 그냥 많이 풀었다고 어쩌다 보니 티어가 플래티넘이 됐네.. 엄청 높은 티어도 아니긴 하지만, 그래도 티어에 맞는 실력을 갖출 수 있도록 계속 열심히 해야겠다

다익스트라 문제이다. 다만, 최단거리 중에서도 특정 간선을 지나는지 아닌지를 판별해야 하기 때문에 다소 까다로울 수 있는 문제이다.

그냥 다익스트라를 통해 하나의 경로만 구해버리면 최단거리가 동일한 다른 경로를 무시할 수 있기 때문에 다익스트라를 여러번 돌려서 간선을 반드시 지나는 최단거리를 구해주어야 한다. 

먼저, 본인은 시작노드를 기준으로 다익스트라 최단거리를 구하고, 냄새를 맡은 간선의 양 끝점을 기준으로도 다익스트라 최단거리를 구했다. 이렇게 하면 다익스트라를 이용해 구한 최단거리 배열은 총 3개가 있다.

이 3개의 최단거리를 이용해 시작점 -> 간선의 왼쪽점 -> 간선의 오른쪽점 경로의 최단 거리를 구할 수 있다.

간선의 양 끝점중 어느 쪽을 먼저 가느냐에 따라 최단거리가 달라질 수 있으므로 시작점 -> 간선의 오른쪽점 -> 간선의왼쪽점도 확인해준다.

이 둘중 더 작은 최단거리의 값이 시작지점을 기준으로 구한 다익스트라 최단거리 배열에서 도착 노드를 향한 최단거리와 같다면 냄새를 맡은 경로를 포함한 최단거리 경로가 존재한다는 의미이므로 정답 배열에 넣어주면 된다.

마지막으로 오름차순으로 출력해야 하므로 정답배열을 정렬해주면 된다.

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

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

std::vector<int> Dijk(int _StartNode, const std::vector<std::vector<std::pair<int, int>>>& _Link)
{
    std::vector<int> MinCost(_Link.size(), 100000000);

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> PQ;
    PQ.push({ 0, _StartNode });
    MinCost[_StartNode] = 0;

    while (PQ.size() > 0)
    {
        auto [CurCost, CurNode] = PQ.top();
        PQ.pop();

        for (int i = 0; i < _Link[CurNode].size(); i++)
        {
            int NextNode = _Link[CurNode][i].first;
            int NextCost = _Link[CurNode][i].second + CurCost;

            if (NextCost < MinCost[NextNode])
            {
                MinCost[NextNode] = NextCost;
                PQ.push({ NextCost, NextNode });
            }
        }
    }

    return MinCost;
}

int main()
{
    Init();

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

    for (int Case = 0; Case < NumCase; Case++)
    {
        int NumNode = 0, NumEdge = 0, NumEndNode = 0;
        std::cin >> NumNode >> NumEdge >> NumEndNode;

        int StartNode = 0;
        std::pair<int, int> FindedEdge;

        std::cin >> StartNode >> FindedEdge.first >> FindedEdge.second;
        StartNode--, FindedEdge.first--, FindedEdge.second--;

        std::vector<std::vector<std::pair<int, int>>> Link(NumNode);
        for (int i = 0; i < NumEdge; i++)
        {
            int Start = 0, End = 0, Cost = 0;
            std::cin >> Start >> End >> Cost;

            Link[Start - 1].push_back({ End - 1, Cost });
            Link[End - 1].push_back({ Start - 1, Cost });
        }

        std::vector<int> EndNodes(NumEndNode);
        for (int i = 0; i < NumEndNode; i++)
        {
            std::cin >> EndNodes[i];
            EndNodes[i]--;
        }

        std::vector<int> MinCostFromStart = Dijk(StartNode, Link);
        std::vector<int> MinCostFromEdgeF = Dijk(FindedEdge.first, Link);
        std::vector<int> MinCostFromEdgeS = Dijk(FindedEdge.second, Link);
    
        std::vector<int> Answer;
        Answer.reserve(EndNodes.size());

        for (int i = 0; i < EndNodes.size(); i++)
        {
            int CurNode = EndNodes[i];

            int MinCost_1 = MinCostFromStart[CurNode];
            
            int MinCost_2 = MinCostFromStart[FindedEdge.first] + MinCostFromEdgeF[FindedEdge.second] + MinCostFromEdgeS[CurNode];
            int MinCost_3 = MinCostFromStart[FindedEdge.second] + MinCostFromEdgeS[FindedEdge.first] + MinCostFromEdgeF[CurNode];

            if (MinCost_1 == std::min(MinCost_2, MinCost_3))
            {
                Answer.push_back(CurNode);
            }
        }

        std::sort(Answer.begin(), Answer.end());
        for (int AnswerNode : Answer)
        {
            std::cout << AnswerNode + 1 << " ";
        }

        std::cout << "\n";
    }


    return 0;
}

일종의 DP문제이다. 이준 반복문을 통해 약수의 합을 미리 구할 수 있다.

숫자 하나를 골라서 해당 숫자의 배수가 되는 숫자에 모두 해당 숫자를 더해준다.

예를 들어, 현재 숫자가 2라면 2, 4, 6, 8, 10 .... 등 2의 배수에 모두 2를 더해주는 것이다. 현재 숫자가 3이라면 3, 6, 9, 12...등 3의 배수에 모두 3을 더해주면 된다.

1~1000000까지 모든 숫자를 기준으로 배수가 되는 숫자에 자신을 더해주면 된다. 이중 반복문이 수행횟수가 엄청 많을 줄 알았는데 계산해보니 1400만번 정도로 시간초과가 날 정도는 아니었다.

#include <iostream>
#include <map>
#include <cmath>
#include <vector>

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

int main()
{
    Init();

    std::vector<long long> DevisorSum(1000001);
    DevisorSum[1] = 0;

    for (int i = 1; i <= 1000000; i++)
    {
        for (int j = i; j <= 1000000; j += i)
        {
            DevisorSum[j] += i;
        }
    }

    for (int i = 2; i <= 1000000; i++)
    {
        DevisorSum[i] += DevisorSum[i - 1];
    }

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

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

        std::cout << DevisorSum[TargetNum] << "\n";
    }

    return 0;
}

전형적인 이분탐색 문제이다. 다만, 공정의 개수를 K라고 했을 때 소요되는 시간을 구하는 함수를 만드는 것이 중요한데 우선순위 큐를 사용하면 쉽게 만들 수 있다.

공정에서 현재 사용시간이 가장 적은 공정에 물픔을 넣어야 하므로 우선순위 큐가 낮은 숫자가 top으로 오도록 한 뒤에 top의 숫자에 현재 맞춤형 선물의 제작시간을 더해가며 우선순위 큐를 갱신해주면 된다.

이 때, 모든 공정에서 걸리는 시간중 최대 시간이 K개의 공정을 사용할 때 걸리는 시간이므로 최대값도 함께 갱신해야 한다.

이분탐색으로 1~100000 사이에서 최적의 공정 개수를 구하면 된다. (다만, left를 0으로 하면 안된다. 본인은 이거때문에 시간을 좀 날렸다... 공정은 반드시 1개 이상 사용해야 하므로...)

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

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

int GetCostSum(std::vector<int>& _TimeCost, int _Mid)
{
    std::priority_queue<int, std::vector<int>, std::greater<>> TimeCostPerProcess;

    int MaxTime = 0;

    for (int i = 0; i < _TimeCost.size(); i++)
    {
        if (TimeCostPerProcess.size() < _Mid)
        {
            TimeCostPerProcess.push(_TimeCost[i]);

            MaxTime = std::max(MaxTime, _TimeCost[i]);
        }
        else
        {
            int MinTime = TimeCostPerProcess.top();
            
            TimeCostPerProcess.pop();
            TimeCostPerProcess.push(MinTime + _TimeCost[i]);
            
            MaxTime = std::max(MaxTime, MinTime + _TimeCost[i]);
        }
    }

    return MaxTime;
}


int main()
{
    Init();

    int NumGift = 0, RemainingTime = 0;
    std::cin >> NumGift >> RemainingTime;

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

    int Left = 1;
    int Right = 100000;
    
    int Answer = Right;

    while (Left <= Right)
    {
        int Mid = (Left + Right) / 2;
        int CurTime = GetCostSum(TimeCost, Mid);
        
        if (CurTime > RemainingTime)
        {
            Left = Mid + 1;
        }
        else
        {
            Right = Mid - 1;
            Answer = std::min(Answer, Mid);
        }
    }

    std::cout << Answer;

    return 0;
}