C++에서는 스마트 포인터라는 아주 편리한 기능을 지원해준다.

스마트 포인터는 일반적인 포인터 변수를 사용해 동적으로 할당받은 메모리 주소를 참조할 경우 발생할 수 있는 문제점들을 보완하기 위해 추가된 기능이다. 스마트 포인터에 대해 알아보기 전에, 일반적인 포인터 사용의 문제점을 알아보자.

 

일반적인 포인터의 문제점

동적으로 할당받은 메모리 주소를 참조할 때, 일반적인 포인터를 사용하면 발생할 수 있는 문제점은 댕글링 포인터와 메모리 누수가 있다.

 

1. 댕글링 포인터

두 포인터 변수 APtr과 BPtr이 같은 주소를 가리키고 있다고 해보자.

이 때, APtr이 참조하고 있는 메모리 영역을 할당 해제해버린다면?

 

두 포인터 변수가 가리키는 주소는 더 이상 유효하지 않은 주소가 된다. APtr의 경우, 본인이 해제를 하였으니 nullptr을 변수에 대입하여 오류를 방지할 수 있지만, BPtr은 주소가 유효하지 않음을 알지 못한다.

 

이로 인해, BPtr이 메모리 영역에 참조를 시도하면 세그멘테이션 오류가 발생하게 된다.

 

2. 메모리 누수

 

malloc, new 를 이용해 동적으로 메모리를 할당받게 되면, 사용이 끝난 뒤 반드시 메모리 할당을 해제해주어야 한다.

하지만, 메모리를 해제하지 않고 포인터 변수가 지역을 벗어나 소멸하거나 다른 주소를 가리키게 될 경우 할당 받은 메모리는 절대 해제할 수 없게 된다. 즉, 동적으로 할당받은 메모리에 대한 철저한 감시, 추적이 요구되며, 이를 소홀히 할 경우 메모리 누수가 발생할 수 있다. 아주 중요한 일이지만 동시에 프로그래머 입장에선 상당히 불편한 일이라고 할 수 있다.

 

스마트 포인터

스마트 포인터는 위의 두 문제를 해결하기 위해 만들어진 기능이다.

 

메모리의 해제를 프로그래머가 직접하지 않아도 되기 때문에, 높은 안정성과 편의성을 보장하고 있으며 사용법을 잘 숙지하였다면 메모리의 누수 또한 발생하지 않는다.

 

스마트 포인터는 std::shared_ptr, std::weak_ptr, std::unique_ptr의 총 3가지 종류가 있다.

먼저, 각 특징을 알아보기 전에 전체적인 구조와 동작 원리를 알아보자.

 

스마트 포인터의 동작 원리

스마트 포인터를 사용할 경우 std::make_shared, std::make_unique를 통해 메모리를 동적으로 할당할 수 있다.

std::shared_ptr<int> SharedPtr1 = std::make_shared<int>();
std::shared_ptr<int> SharedPtr2(std::make_shared<int>());

std::unique_ptr<double> UniquePtr = std::make_unique<double>();
std::unique_ptr<double> UniquePtr(std::make_unique<double>());

make_shared로 메모리를 동적으로 할당하게 되면, 참조 테이블이라는 것이 생성된다.

참조 테이블은 해당 메모리 영역과 관련된 여러 정보를 담고 있다.

 

대표적으로는 strong reference count, weak reference count를 담고 있다. 참조 테이블은 메모리 영역당 1개가 생성되며, 같은 메모리 영역을 가리키는 스마트 포인터는 모두 하나의 참조 테이블을 공유하게 된다.

 

어떠한 스마트 포인터가 새롭게 메모리 영역을 가리키게 되면, strong refence count가 1이 증가하며, 메모리 영역을 가리키지 않게 되면 strong reference count가 1이 감소하게 된다.

 

strong refence count가 0이 되는 순간, 해당 메모리는 할당이 해제된다.

//SRC = Strong Reference Count

std::shared_ptr<int> A = std::make_shared<int>(); //SRC = 1
std::shared_ptr<int> B = A; //SRC = 2
B = nullptr; //SRC = 1;
A = nullptr; //A = 0; -> 메모리 할당 해제

해당 메모리를 가리키고 있는 변수가 모두 사라져야만 메모리 할당이 해제되기 때문에 댕글링 포인터의 문제가 발생하지 않는다. 또한, 프로그래머의 실수로 메모리 누수가 발생할 확률도 매우 줄어든다고 할 수 있다.

 

의도적으로 참조를 끊고 싶다면, 위의 코드처럼 nullptr을 삽입해도 되고, 다른 대상을 가리켜도 된다. 지역을 벗어나면서 변수가 소멸할 때에도 알아서 참조가 끊어지기 때문에 상황에 맞게 사용하면 된다.

 

그렇다면, weak reference count는 뭘까? 이걸 알기 전에, std::shared_ptr과 std::weak_ptr에 대해 먼저 알아보자.

 

std::shared_ptr

std::shared_ptr은 말 그대로 하나의 메모리 주소를 공유하여 사용하는 포인터이다.

하나의 메모리 영역을 둘 이상의 개체가 참조하는 것이 허용되는 스마트 포인터이다.

 

std::shared_ptr은 위에서 말한 것처럼 참조 테이블을 통해, 메모리 주소를 가리키는 개체의 존재 여부를 파악하며 모든 개체가 참조를 끊게 되면 메모리 영역을 해제하게 된다. 

 

일반적인 상황에서 이는 매우 안전하고 편리한 방법이지만, 한 가지 상황에서 문제가 발생한다.

바로, 두 개의 shared_ptr이 서로를 가리키는 경우이다.

 

이렇게, 두 스마트 포인터가 서로를 가리키고 있다고 해보자.

이 때, 프로그램이 종료된다고 한다면 두 객체를 소멸하려고 할 것이다.

 

객체 A가 소멸되기 위해선, 객체 B의 shared_ptr이 A를 가리키지 않도록 해야 한다. 즉, 객체 B가 소멸해야 한다.

객체 B를 소멸하려고 보니, 객체 B는 반대로 객체 A가 소멸되어야만 소멸할 수 있다.

 

즉, 서로가 서로를 참조하는 상황으로 인해, 두 객체가 모두 소멸할 수 없는 상황이 된 것이다.

이러한 상황을 순환참조라고 한다. std::shared_ptr을 일반적으로 사용할 경우 순환 참조가 발생하여 두 객체 모두 소멸하지 못해 메모리 누수로 이어지게 된다.

 

std::shared_ptr에서 발생할 수 있는 순환참조 문제를 해결하기 위해 사용되는 것이 std::weak_ptr이다.

 

std::weak_ptr

std::weak_ptr은 std::shared_ptr과 거의 동일하지만, 한 가지 크게 다른 점이 있다.

std::shared_ptr은 strong reference count를 증가/감소시키는 반면, std::weak_ptr은 weak reference count를 증가/감소시키며 동작한다.

 

 위에서 말했듯이, 참조 테이블에는 strong reference count와 weak reference count 두 개의 참조 카운트 변수가 있다.

strong refenrece count는 메모리의 해제를 위해 사용되는 반면, weak reference count는 메모리 해제에 관여되지 않는다.

weak reference count가 0이든 10이든 100이든 strong reference count가 0이면 메모리가 해제되고, 1 이상이면 메모리가 해제되지 않는다.

 

즉, 위의 순환참조 상황에서, std::weak_ptr을 사용하면 순환참조 문제에서 벗어날 수 있다.

 

그렇다면, strong reference count가 0이 되면, 스마트 포인터 관련 모든 메모리가 해제될까?

아니다. 동적으로 할당한 메모리는 해제하지만, 참조 테이블은 사라지지 않는다.

왜냐하면, weak_ptr로 주소를 참조하고 있는 객체의 동작이 안전하게 완료되는 것을 보장하기 위해, weak reference count가 1 이상이면, 참조 테이블은 사라지지 않는다. weak reference count가 0이 되는 순간 참조 테이블이 소멸하며, 사용하던 스마트 포인터 관련 메모리가 모두 해제된다.

 

 weak_ptr을 사용하기 위해선, 2개의 기능을 알아야 한다.

lock과 expired이다.

 

 위에서 말했듯이, weak reference count는 할당된 메모리 해제에 관여하지 않는다. 즉, 현재 weak_ptr로 참조하고 있는 메모리 영역이 이미 해제된 곳일 가능성도 있다는 말이다.

 

이를 확인하기 위한 함수가 expired이다. 가리키는 메모리 주소가 유효하다면 false를 반환하고, 유효하지 않다면 true를 반환한다. 이를 이용해, weak_ptr을 안전하게 사용할 수 있다.

 

lock은 weak_ptr에서 참조중인 주소의 데이터를 직접적으로 사용하기 위해 호출하는 함수이다.

 

weak_ptr은 그 자체로는 원시 포인터에 접근할 수 없다. 왜냐하면, weak_ptr은 스마트 포인터의 생명 주기에 관여하지 않는다. 그럼에도 불구하고 shared_ptr처럼 마음껏 주소를 사용하고 변경할 수 있다면, 스마트 포인터를 사용하는 이유가 사라지게 된다. 그렇기 때문에, weak_ptr은 그 자체로 주소에 접근할 수 없고, lock을 이용해서 접근해야 한다.

lock은 해당 주소에 접근할 수 있는 shared_ptr을 반환해주는 함수이다. 이를 사용하여, weak_ptr이 참조중인 메모리 영역의 데이터를 사용할 수 있게 된다.

class A
{
public:
    int a = 0;
};

int main()
{
    std::shared_ptr<A> SharedPtr = std::make_shared<A>();
    std::weak_ptr<A> WeakPtr = SharedPtr;

    if (WeakPtr.expired() == false)
    {
        WeakPtr.lock()->a = 5;
    }
}

위와 같이 사용할 수 있다. expired를 이용해 주소의 유효성을 판별한 뒤, lock을 통해 메모리 주소에 접근한다.

 

std::unique_ptr

std::unique_ptr은 메모리 영역을 단 하나의 포인터 변수만 가리킬 수 있도록 하고 싶을 때 사용하는 스마트 포인터이다.

shared_ptr이나 weak_ptr은 하나의 메모리 영역을 여러개의 포인터로 가리킬 수 있었다.

하지만, unique_ptr은 메모리 영역을 단 하나의 포인터만 가리킬 수 있다.

 

스마트 포인터의 장단점

위에서 말했듯이, 스마트 포인터의 장점은 안정성에 있다. 프로그래머가 직접적으로 delete를 호출해주지 않아도 되기 때문에 실수로 인한 메모리 누수를 방지할 수 있으며 이로 인해 안정성과 편의성이 매우 높아진다.

 

반면, delete를 직접 호출하지 않기 떄문에 메모리 해제 시기를 프로그래머가 정확히 파악하기 힘들다는 단점이 있다. 이로 인해, 만약 메모리 누수가 발생한다면, 정확히 어디에서 어떻게 발생하고 있는지 파악하기가 매우 힘들어진다. 또한, 상속 관계에서 스마트 포인터를 사용하는 것이 여러가지 불편한 점이 있는데, 이 부분은 추후 별도의 게시물을 작성할 예정이다.

 

 

'C++ > C++' 카테고리의 다른 글

C++ - if constexpr  (1) 2024.10.05
C++ - Concept, Requires 키워드  (3) 2024.09.11
C++ - Callable 과 std::function (함수 객체, 람다 함수)  (1) 2024.06.11
C++ - Move Semantic (std::move, std::forward)  (1) 2024.06.09
C++ - L-Value vs R-Value  (1) 2024.06.09

 

여러 개의 집이 순서대로 놓여 있고, 이 집의 외벽에 색을 칠하고자 한다.

하나의 집에 인접한 두 집과 같은 색이 아니도록 칠하고자 한다.

 

각 집마다 색을 칠할 때의 비용이 상이하게 책정되어 있다.

인접한 집과 다른 색상이라는 조건을 유지하며 색을 칠할 때 그 비용의 최소를 구하자.

 

문제 풀이

이 문제는 모든 경우를 탐색하며 그 비용을 구해야 한다.

하지만, 일반적인 완전탐색 방식으로 모든 경우를 탐색하면 말도 안되는 경우의 수가 나온다.

그러므로 다이나믹 프로그래밍을 사용하여 효율적으로 비용의 최소 값을 구해야 한다.

 

먼저, 첫 번째 집의 색상을 하나로 고정하여 시작하는 DP를 3번 반복하는 것이다. 

 

왜 3번을 할까? 첫 번째 집과 마지막 집의 색이 같으면 안된다는 조건 때문이다.

그렇기 때문에 첫 번째 집을 Red로 칠하는 경우, Green으로 칠하는 경우, Blue로 칠하는 경우를 하나씩 확인해야 한다.

 

그럼, 이제 DP를 해보자.

먼저, DP는 2차원 배열로 만들 것이다.

DP[i][j] 가 있다면, i는 집의 순번이고 j는 색상이다. (0은 R, 1은 G, 2는 B)

저장될 값은 최소 비용이다.

 

DP[3][2] 라고 한다면, 3번째 집을 Blue로 칠할 때의 최소 비용이다.

DP[10][1]은 10번째 집을 Green으로 칠할 때의 최소 비용이다.

이렇게 집의 위치와 색상을 함께 고려할 것이다.

 

이 때, DP[i][0] 은 어떻게 구해야 할까?

i번째 집을 빨간색으로 칠한다고 하면, 일단 i-1번째 집은 빨간색이어선 안된다.

또한, i - 1 개의 집을 칠하는데 들어간 총 비용 + i번째 집을 빨간색으로 칠하는 비용이다.

i - 1 개의 집을 칠하는데 들어가는 총 비용은 i - 1 번째 집이 파란색이냐, 초록색이냐에 따라 다를 수 있다.

 

그러므로, DP[i][0] 은 std::min(DP[i - 1][1] + Cost[i][j], DP[i - 1][2] + Cost[i][j]) 가 될 것이다.

DP[i][0]에 저장할 값은 최소비용이므로, 이전의 집이 파란색일 때의 총 비용과 초록색일 때의 총 비용중 최소 값을 기준으로 현재 집을 칠하는 비용을 더해서 총 비용의 최소값을 갱신하는 것이다.

 

이렇게 마지막 집까지 모두 갱신했다고 해보자.

그러면, 마지막 집이 R인 경우의 총 비용, G인 경우의 총 비용, B인 경우의 총 비용 이렇게 3개의 값을 구할 수 있다.

이 3개의 비용 중 가장 작은 비용이 첫 번째 집을 R로 칠하는 경우 중 최소 비용인 것이다.

 

하지만, 마지막 집은 첫 번째 집과 같은 색일 수 없다는 조건이 있으므로, 마지막 집이 R인 경우의 총 비용은 제외하고, 마지막 집이 G인 경우의 총 비용과 B인 경우의 총 비용만 고려하여 최소를 구하면 된다.

 

첫 번째 집을 R로 칠할 때의 최소 비용, G로 칠할 때의 최소 비용, B로 칠할 때의 최소비용 총 3개를 구한 뒤 셋 중 최소비용을 구하면 그 값이 답이 된다.

 

풀이 코드

#define BIGNUMBER 999999999

먼저, 최소값을 갱신하기 전 초기값을 잡기 위해 충분히 큰 값을 하나 정의해주었다.

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

std::vector<std::vector<int>> Cost(NumOfHouse, std::vector<int>(3, 0));
for (int i = 0; i < NumOfHouse; i++)
{
    for (int j = 0; j < 3; j++)
    {
        std::cin >> Cost[i][j];
    }
}

이후 입력을 받아주었다. 모든 비용을 Cost에 저장해주었다. 

Cost[i][j]는 i번째 집을 j색(0 = R, 1 = G, 2 = B)으로 칠하는 비용이다.

int Answer = BIGNUMBER;

std::vector<std::vector<int>> DP(NumOfHouse, std::vector<int>(3, BIGNUMBER));
for (int i = 0; i < 3; i++)
{
    for (int j = 0; j < DP.size(); j++)
    {
        std::fill(DP[j].begin(), DP[j].end(), BIGNUMBER);
    }

    DP[0][0] = Cost[0][0];
    DP[0][1] = Cost[0][1];
    DP[0][2] = Cost[0][2];

    for (int j = 0; j < 3; j++)
    {
        if (i == j)
        {
            continue;
        }

        DP[1][j] = DP[0][i] + Cost[1][j];
    }

    for (int j = 2; j < NumOfHouse; j++)
    {
        DP[j][0] = std::min(DP[j - 1][1] + Cost[j][0], DP[j - 1][2] + Cost[j][0]);
        DP[j][1] = std::min(DP[j - 1][0] + Cost[j][1], DP[j - 1][2] + Cost[j][1]);
        DP[j][2] = std::min(DP[j - 1][0] + Cost[j][2], DP[j - 1][1] + Cost[j][2]);
    }

    for (int j = 0; j < 3; j++)
    {
        if (j == i)
        {
            continue;
        }

        Answer = std::min(Answer, DP[NumOfHouse - 1][j]);
    }
}

먼저,std::fill을 사용하여 DP배열을 초기화해주었다.

하나의 배열을 재활용 할 것이기 때문에 초기화 코드를 넣어주었다.

 

DP는 위에서 말했듯이, 첫번째 집이 R인 경우, G인 경우, B인 경우 총 3개의 경우를 진행할 것이다.

 

DP[0][0], DP[0][1], DP[0][2] 는 Cost[0][0], Cost[0][1], Cost[0][2] 로 초기화 해 주었다.

 

이후 반복문으로 DP[1]도 갱신해주었다. 

그리고 이후, DP[2]부터 DP[NumOfHouse]까지 모두 갱신해주었다.

 

DP[1]만 따로 갱신한 이유는 첫번째 집을 칠하는 색을 하나로 정해두었기 때문에, DP[1]은 첫번째 집이 어떤 색인지 고려하여 값을 계산할 필요가 없기 때문이다. 첫번째 집이 빨간색이라면 그에 맞게 DP[1]을 갱신하였고, 파란색이라면 그에 맞게 갱신한 것이다.

 

DP배열을 모두 갱신한 뒤에, DP배열의 마지막에 저장된 총 비용 중 최소값을 Answer에 저장해주었다.

 

이를, 총 3번(첫 번째 집이 R인경우, G인 경우, B인 경우) 실행하였고, 최종적으로 Answer에 저장된 값이 정답이 된다.

 

std::cout << Answer;

return 0;

마지막으로 답을 출력해주면 된다.

 

 

코드 전문

더보기
#include <iostream>
#include <vector>
#include <algorithm>

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

#define BIGNUMBER 999999999

int main()
{
    Init();

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

    std::vector<std::vector<int>> Cost(NumOfHouse, std::vector<int>(3, 0));
    for (int i = 0; i < NumOfHouse; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            std::cin >> Cost[i][j];
        }
    }

    int Answer = BIGNUMBER;

    std::vector<std::vector<int>> DP(NumOfHouse, std::vector<int>(3, BIGNUMBER));
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < DP.size(); j++)
        {
            std::fill(DP[j].begin(), DP[j].end(), BIGNUMBER);
        }

        DP[0][0] = Cost[0][0];
        DP[0][1] = Cost[0][1];
        DP[0][2] = Cost[0][2];

        for (int j = 0; j < 3; j++)
        {
            if (i == j)
            {
                continue;
            }

            DP[1][j] = DP[0][i] + Cost[1][j];
        }

        for (int j = 2; j < NumOfHouse; j++)
        {
            DP[j][0] = std::min(DP[j - 1][1] + Cost[j][0], DP[j - 1][2] + Cost[j][0]);
            DP[j][1] = std::min(DP[j - 1][0] + Cost[j][1], DP[j - 1][2] + Cost[j][1]);
            DP[j][2] = std::min(DP[j - 1][0] + Cost[j][2], DP[j - 1][1] + Cost[j][2]);
        }

        for (int j = 0; j < 3; j++)
        {
            if (j == i)
            {
                continue;
            }

            Answer = std::min(Answer, DP[NumOfHouse - 1][j]);
        }
    }

    std::cout << Answer;

    return 0;
}

 

 

3개의 돌 그룹이 있다. 각 그룹에는 돌이 A개, B개, C개씩 포함되어있다.

이 때, 두 개의 돌 그룹을 선택하여 돌의 개수를 바꾸는 연산을 진행한다.

개수를 바꾸는 진행은 두 그룹의 돌 개수가 X, Y 이고, X < Y라고 했을 때, X = 2 * X , Y = Y - X 의 형식으로 진행한다.

이 연산을 반복하여 A,B,C의 개수를 모두 동일하게 만들 수 있다면 1을 출력하고, 아니라면 0을 출력하면 된다.

 

문제 풀이

이 문제는 모든 경우를 탐색하는 방법 말고는 더 좋은 방법은 딱히 없는 듯 하다.

방문 체크를 하며, 이미 탐색한 경우는 제외하고 모든 경우에 대해 탐색하도록 하였다.

 

최초에 A, B, C가 주어진다.

 

연산은 두 그룹을 선택했을 때, 더 작은 쪽의 값을 작은 쪽에 더하고, 큰 쪽에서 빼는 연산을 하게 된다.

같은 양을 양쪽에 빼고 더하기 때문에, 전체 총량 (A + B + C)는 변하지 않는다.

 

즉, A와 B만 알면 사실 C는 구할 수 있다.

이 아이디어를 기준으로, 방문 체크는 3차원 배열이 아닌 2차원 배열을 사용하여 2개의 돌을 기준으로만 하게 된다.

 

또한, 1, 2, 3 과 3, 2, 1은 사실 같은 경우라고 할 수 있다.

문제에서 구하는 것은 연산을 반복했을 때, 모든 돌 그룹의 돌 개수가 같아질 수 있는지 여부를 반환하는 것이기 때문에 1,2,3 에서 true가 나온다면 3, 2,1에서도 당연히 true가 나올 수 밖에 없다.

 

그렇기 때문에, 돌 개수를 정렬하여 탐색을 할 것이다.

(1, 2, 3 과 3, 2, 1을 같은 경우라고 가정하기 위해)

 

처음 A, B, C가 있다면, 이 중 2개의 돌 A, B만 선택하여 Queue에 삽입한다.

이후, Queue에서는 front를 pop한 뒤, A,B,C를 기준으로 BFS를 진행할 것이다.

 

1. A, B를 선택하는 경우

2. A, C를 선택하는 경우

3. B, C를 선택하는 경우

 

세 경우를 탐색하며 계속 BFS를 진행하며, A,B,C가 같아지는 타이밍이 온다면 1을 출력하고 종료하도록 하였다.

만약, BFS가 모두 끝날 때 까지 A,B,C가 같아지는 타이밍을 발견하지 못한다면 0을 출력하도록 하였다.

 

또한, A, B, C 가 절대 같아질 수 없는 경우가 한 가지 있는데, A + B + C의 값이 3의 배수가 아닌 경우이다.

A, B, C가 모두 X라는 값으로 같은 값을 가진다면 A + B + C 는 3X 가 된다.

즉, A, B, C 가 같다면, A + B + C 는 반드시 3의 배수여야 한다.

 

그러므로, A + B + C가 3의 배수가 아니라면 바로 0을 출력하고 종료하도록 예외처리를 해주었다.

 

풀이 코드

int A = 0;
int B = 0;
int C = 0;

std::cin >> A >> B >> C;

int SumStone = A + B + C;

if (SumStone % 3 != 0)
{
    std::cout << 0;
    return 0;
}

먼저, 입력을 받아준 뒤 세 수의 합이 3의 배수가 아니라면 0을 출력한 뒤 종료하도록 하였다.

std::queue<std::pair<int, int>> BFS;

if (A > B)
{
    std::swap(A, B);
}

BFS.push({A, B});

다음은 queue에 첫 원소인 {A, B}를 삽입해 주었다.

이 때, A와 B를 오름차순으로 정렬하여 넣어주어야 한다.

while (BFS.size() > 0)
{
    std::pair<int, int> CurStone = BFS.front();
    BFS.pop();

    int A = CurStone.first;
    int B = CurStone.second;
    int C = SumStone - A - B;

    if (A == B && B == C)
    {
        std::cout << 1;
        return 0;
    }

    if (A != B)
    {
        InsertQueue(A, B, BFS);
    }

    if (B != C)
    {
        InsertQueue(B, C, BFS);
    }

    if (A != C)
    {
        InsertQueue(A, C, BFS);
    }
}

BFS내부 코드이다.

 

먼저, C를 구해준다. 그리고, A와 B와 C가 모두 같은지 검사해준다. 만약 같다면 1을 출력하고 그대로 종료한다.

같지 않다면, 그대로 너비 우선 탐색을 진행한다.

 

두 그룹을 선택했을 때, 돌의 개수가 같다면 선택할 수 없으므로 두 그룹의 돌 개수가 다른 경우에만 탐색을 진행하도록 하였다.

void InsertQueue(int _Left, int _Right, std::queue<std::pair<int, int>>& _Queue)
{
    if (_Left > _Right)
    {
        std::swap(_Left, _Right);
    }

    _Right -= _Left;
    _Left *= 2;

    if (isVisit[_Left][_Right] == false)
    {
        isVisit[_Left][_Right] = true;
        _Queue.push({ _Left, _Right });
    }
}

이는 queue에 원소를 삽입하는 함수이다.

동일한 코드를 여러 번 작성하는 것이 불편하니, 함수로 만들어주었다.

 

먼저, 선택된 두 숫자를 오름차순으로 정렬하였다.

그리고, 연산을 진행하였다. 큰 수에서는 작은 수를 빼주고, 작은 수에는 작은 수를 더해주었다.

 

그렇게 나온 경우를 이미 탐색한 경험이 없다면, 방문 체크를 한 뒤 queue에 삽입해주었다.

std::cout << 0;

return 0;

만약, 반복문이 끝날 때 까지 프로그램이 종료되지 않았다면 세 그룹의 돌 개수가 같은 경우를 발견하지 못한 것이므로 0을 출력하고 끝내주었다.

 

 

코드 전문

더보기
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>

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

std::vector<std::vector<bool>> isVisit(1501, std::vector<bool>(1501, false));

void InsertQueue(int _Left, int _Right, std::queue<std::pair<int, int>>& _Queue)
{
    if (_Left > _Right)
    {
        std::swap(_Left, _Right);
    }

    _Right -= _Left;
    _Left *= 2;

    if (isVisit[_Left][_Right] == false)
    {
        isVisit[_Left][_Right] = true;
        _Queue.push({ _Left, _Right });
    }
}

int main()
{
    Init();

    int A = 0;
    int B = 0;
    int C = 0;

    std::cin >> A >> B >> C;

    int SumStone = A + B + C;

    if (SumStone % 3 != 0)
    {
        std::cout << 0;
        return 0;
    }

    std::queue<std::pair<int, int>> BFS;

    if (A > B)
    {
        std::swap(A, B);
    }

    BFS.push({A, B});

    while (BFS.size() > 0)
    {
        std::pair<int, int> CurStone = BFS.front();
        BFS.pop();

        int A = CurStone.first;
        int B = CurStone.second;
        int C = SumStone - A - B;

        if (A == B && B == C)
        {
            std::cout << 1;
            return 0;
        }

        if (A != B)
        {
            InsertQueue(A, B, BFS);
        }

        if (B != C)
        {
            InsertQueue(B, C, BFS);
        }

        if (A != C)
        {
            InsertQueue(A, C, BFS);
        }
    }

    std::cout << 0;

    return 0;
}

Callable

Callable이란, 말 그대로 호출이 가능한 모든 것을 가리킨다. 호출이 가능한게, 함수 말고 또 뭐가 있겠나 싶을 수도 있지만, 함수 객체, 람다 함수 등이 대표적인 Callable이다.

 

함수 객체

함수 객체란, 객체를 함수처럼 사용하는 것이다.

코드를 보면 단 번에 이해가 될 것이다.

class FuncObject
{
public:
    int operator()(int _A, int _B)
    {
        return (_A + _B);
    }
};

위의 클래스를 보자. 클래스 내에 ()연산자를 오버로딩하여 두 수의 합을 반환하도록 하였다.

해당 객체는 아래와 같이 사용될 수 있다.

int main()
{
    FuncObject NewFuncObject;
    int Sum = NewFuncObject(5, 6);
    
    return 0;
}

 NewFuncObject는 함수가 아니라, 객체의 인스턴스이다. 그럼에도, () 연산자를 오버로딩 했기 때문에 함수와 동일하게 사용될 수 있다. 이러한 것을 함수 객체라고 한다. 실제로 함수는 아니고 객체이지만, 함수처럼 사용되는 것이다.

 

그냥 함수를 쓰면 되는데 왜 이런 걸 쓰냐? 라는 생각이 들 수도 있다. 

함수 객체의 장점은 속성을 저장하는 등, 함수에선 사용할 수 없는 기능을 추가로 사용할 수 있다는 장점이 있다.

 

아래의 코드를 보자.

class Plus
{
    int Count = 0;
    
public:
    void operator=()(int& _A)
    {
        Count++;
        _A += Count;
    }
};

특정 변수에 대한 참조형을 인수로 넘기면, 값을 증가시키는 함수를 만들었다고 해보자.

이 함수가 여러 번 실행될 때마다 더해지는 값이 1씩 증가하도록 만들고 싶다.

 

예를 들면, 처음엔 1을 더하고 두 번째 호출되었을 때는 2를 더하고 세 번째 호출되었을 때는 3을 더하는 것이다.

게임에서 이런 경우를 자주 볼 수 있을 것이다. 실행 횟수가 늘어날수록 그 비용이 증가하는 것이다.

 

일반적인 함수를 사용해서 이를 구현하기 위해선, 별도로 함수가 호출된 횟수를 저장하고 기록해야 한다. 하지만, 함수 객체를 사용하는 경우 객체 내부에 횟수를 멤버변수로 저장하여 사용할 수 있기 때문에 더욱 간단하게 구현 및 사용이 가능한 것이다.

 

위의 코드를 보면, 객체 내부에 Count라는 변수를 두고, ()연산자가 호출될 때마다 이 변수의 값을 증가시키고 있다.

이처럼, 함수 객체는 객체 내부에 별도의 속성을 정의하여 다양하게 활용할 수 있다는 장점이 있다.

 

또한, 속도가 일반 함수보다 빠르다고 한다. 얼마나 차이나는지는 정확히 모르겠지만, 함수를 사용할 땐 inline 처리가 되지 않지만 함수 객체를 사용하면 inline으로 처리가 가능한 부분이 있다고 한다.

 

람다 함수

람다 함수란, 이름이 없는 함수를 말한다. 조금 더 실전적으로 말하자면, 미리 정의해놓은 함수를 사용하는 것이 아니라 필요할 때마다 즉석에서 정의하는 것이다.

 

아래 코드를 보자.

int main()
{
    []()->int{return 10;};
}

 뭔가 요상한 식이 적혀있는 것을 볼 수 있다.

이 것은 람다 함수로, 상수처럼 일회성으로 사용되는 함수이다. (물론 지속적으로 사용하는 방법도 있다. 이는 std::function과 함께 설명하도록 하겠다.)

 

먼저, 구문을 분석해보자. 

 

앞의 []는 람다 캡쳐라는 것이다. 람다 캡쳐는 조금 뒤에 설명하도록 하겠다.

()는 함수에 사용할 파라미터이다.

->int 는 함수의 반환형을 의미한다. ->char을 사용하면 반환형이 char이 되고, ->std::string 을 사용하면 반환형이 std::string이 된다.

 

여기서 ->int 부분은 생략해도 함수는 정상 작동한다. 이는 반환형을 명시하기 위한 것이고, 실제로는 컴파일러가 알아서 처리해준다.

 

뒤의 중괄호가 함수의 구현부이다. 그 안에 함수를 구현하는 대로 람다함수가 작동하는 것이다.

//람다 표현식
[](int _A, int _B)->int{return _A + _B;};

//일반 함수
int Sum(int _A, int _B)
{
    return _A + _B;
}

위의 코드에서 람다 표현식으로 작성한 것과 일반 함수로 작성한 것은 동일하게 기능한다.

람다 함수를 저렇게 구현했다면, 사용은 어떻게 할까?

[](int _A, int _B)->int{return _A + _B;}(3, 5);

일반 함수들과 동일하게 뒤에, ()을 붙이고 인자를 넣으면 된다.

그런데, 우리는 람다 함수 구현부에서 외부의 변수를 사용하고 싶을 수도 있다.

 

외부의 변수란, 말 그대로 람다 함수 구현부 내부에서 선언된 변수가 아니라 외부에서 선언된 변수를 의미한다.

아래의 코드를 보자.

int main()
{
    int A = 0;
    int B = 0;
    
    []()->int
    {
    	return A + B;
    };
    
    return 0;
}

이렇게 람다함수를 구현했다고 해보자.

 

함수 내부에서는 A와 B를 사용하고 있지만, 실제로 함수 내부에서 선언된 것은 아니다.

함수 외부에 있는 변수를 저렇게 그냥 사용하게 되면 컴파일 오류가 발생한다.

 

이러한 문제를 해결하기 위해 사용하는 것이 앞서 말한 람다 캡쳐이다.

람다 캡쳐는 람다 함수 선언 코드의 가장 앞에 존재하는 [] 이다.

[] 괄호 사이에는 몇 가지 기호를 삽입할 수 있다.

 

[=], [&], [변수 이름] 등으로 사용할 수 있다.

 

[=] : 외부에 있는 변수를 Call By Value로 사용하겠다는 의미이다.

당연히, 람다 함수가 선언된 지역에서 참조할 수 있는 값만 사용이 가능하다.

 

[&] : 외부에 있는 변수를 Call By Reference로 사용하겠다는 의미이다.

역시나, 람다 함수가 선언된 지역 내에서 참조 가능한 변수만 사용이 가능하다.

 

[A] : A는 위의 코드에서 선언된 변수의 이름이다. [=]은 외부의 모든 값에 대해 사용을 허락하지만, 이렇게 변수 이름을 직접 삽입하게 되면 해당 변수만 사용이 가능하다.

 

[&A] : 이렇게 참조형으로도 사용이 가능하다.  

 

[A, &B] : 이렇게 특정 변수는 Value로 특정 변수는 Reference로 사용하는 것도 가능하다.

 

[] : 만약 이렇게 아무 것도 삽입하지 않으면, 람다 함수 내부에서 선언된 값이나 전역으로 선언된 값만 사용이 가능하다.

 

int main()
{
    int A = 0;
    int B = 0;
    
    [=]()->int
    {
    	return A + B;
    };
    
    return 0;
}

그러므로, 위의 코드는 이렇게 람다 캡쳐에 = 을 넣어 주어야 컴파일 오류가 발생하지 않는다.

 

int main()
{
    int A = 0;
    int B = 0;
    
    int Sum = [=]()->int
    {
    	return A + B;
    }();
    
    return 0;
}

이렇게 반환 값을 변수에 저장할 수도 있다.

 

std::function

그런데, 람다 함수는 사실 저렇게만 사용하면 매우 불편한 함수이다.

가독성도 떨어질 뿐더러, 함수의 재사용성도 개나 줘버린 상태인 것이다. 

 

std::function과 함께 사용하면, 람다 함수의 효율성을 더욱 높일 수 있다.

허나, 그건 부가적으로 따라오는 효과일 뿐 std::function의 목적은 아니다.

 

std::function은 C스타일의 함수 포인터가 가지고 있던 단점들을 보완하기 위해, C++에서 지원하는 컨테이너이다.

std::function은 std::function<반환형(파라미터)> 변수 이름 의 형태로 선언하여 사용할 수 있다.

class FuncObject
{
public:
    int operator()(int _A, int _B)
    {
        return (_A + _B);
    }
};

int main()
{
    FuncObject NewFuncObject;

    std::function<int(int, int)> Functor = NewFuncObject;
    int Sum = Functor(3, 5);
}

이렇게, std::function을 사용하면 함수 객체를 저장하여 사용할 수 있다.

int main()
{
    std::function<int()> Lamda = []()->int{return 10;};
    int LamdaReturn = Lamda();
}

이렇게 람다 함수를 저장하여, 간편하게 사용하는 것도 가능하다.

람다함수를 이렇게 std::function 과 함께 사용하면 여러모로 편리한 점이 많다.

 

멤버함수 또한, std::function에 저장할 수 있다.

class Object
{
public:
    void Test()
    {
        //
    }
};

int main()
{
    std::function<void(Object*)> MemberFunc = &Object::Test;
    //std::function<void(Object&)> MemberFunc = &Object::Test;
}

이렇게, 멤버 함수를 저장할 수도 있다. 중요한 점은 인자로 클래스의 참조형을 받고 있다는 것이다. (포인터가 아닌 참조자도 가능하다.) 멤버 함수는 반드시 그 함수를 실행할 객체의 주소가 필요하기 때문에, 첫 번째 인자로 반드시 객체의 주소를 넘겨주어야 한다.

 

사용할 떄 역시, 객체의 주소를 인자로 넘겨주어야 한다.

class Object
{
public:
    void Test()
    {
        //
    }
};

int main()
{
    std::function<void(Object&)> MemberFunc = &Object::Test;
    //std::function<void(Object*)> MemberFunc = &Object::Test;
    
    Object NewObject;
    MemberFunc(&NewObject);
}

위처럼 &NewObejct를 인자로 넘겨주어야 한다.

 

std::bind

하지만, 매 번 객체의 주소를 넘겨주는 것이 상당히 불편한 일이다.

다행히도 C++에선, 멤버 함수 포인터와 객체의 주소를  하나로 묶어버리는 std::bind라는 기능을 지원해준다.

 

std::bind는 std::function에 멤버 함수 포인터를 저장할 때 객체의 주소와 함수를 묶은 상태로 std::function에 저장해준다.

std::function에 저장된 함수를 사용할 때, 객체의 주소값을 대입하는 것 없이 그냥 호출할 수 있게 된다.

int main()
{
    Object NewObject;
    
    std::function<void()> BindedMemberFunc = std::bind(&Object::Test, &NewObject);
    BindedMemberFunc();
}

이렇게, std::bind의 첫 번째 인자에 함수의 주소값을 넣고, 두 번째 인자로 객체를 넣어주면 된다.

위 코드와 같이 함수를 실행할 때, 객체의 주소를 인자로 사용하지 않아도 정상작동하게 된다.

 

std::bind를 엄밀히 설명하자면, 객체를 함수에 묶어준다기보다는 인자를 묶어주는 개념이다. 위의 코드에선, 멤버함수의 첫 번째 인자가 반드시 객체의 포인터임을 이용해서 객체의 주소를 함수와 묶어준 것이다.

 

그렇기 때문에, 객체의 주소가 아니라도 그냥 인자를 고정하여 묶어줄 수 있게 된다. 예를 들어, 플레이어 객체가 소유하고 있는 장비 아이템의 개수와 소비 아이템의 개수를 반환하는 함수를 만든다고 해보자.

class Player
{
public:
    int NumEquip = 0;
    int NumConsumption = 0;
};

int SumFunc(const int* _A, const int* _B)
{
    return *_A + *_B;
}

int main()
{
    Player NewPlayer;
    std::function<int()> SumFuncPtr = std::bind(&SumFunc, &NewPlayer.NumEquip, &NewPlayer.NumConsumption);
    std::cout << SumFuncPtr() << std::endl;
}

std::bind의 두 번째 인자와 세 번째 인자로 멤버함수의 변수 NumEquip과 NumConsumption 대입하였다.

이후, SumFuncPtr을 호출할 때특별한 인자를 삽입하지 않아도 두 변수의 합을 반환해주게 된다.

 

이처럼, 인자를 함수에 묶어주는 역할을 하는 것이 std::bind이다. 객체의 주소가 아니더라도 파라미터와 일치하는 값은 다 넣어줄 수 있다. 하지만, 두 개의 인자 중 하나만 묶어놓고 나머지 인자는 상황에 맞게 사용하고 싶을 수도 있다.

 

예를 들어, 플레이어가 가지고 있는 소비 아이템에서 일정 개수를 삭제하는 코드를 구성한다고 해보자.

class Player
{
public:
    int NumEquip = 0;
    int NumConsumption = 0;
};

void RemoveFunc(int* _Target, int _RemoveValue)
{
    *_Target -= _RemoveValue;
}

int main()
{
    Player NewPlayer;
    std::function<void(int)> RemoveFuncPtr = std::bind(&RemoveFunc, &NewPlayer.NumConsumption, std::placeholders::_1);
    RemoveFuncPtr(5);
}

위의 코드를 보면, 두 개의 인자중 하나는 NewPlayer.NumCumption을 넣어주었지만, 두 번째 인자는 std::placeholders::_1 이라는 인자를 대입하였다. 그리고 함수를 실제로 호출할 때엔, int형 정수값 하나만 인자에 대입해주었다.

 

std::placeholders는 임시로 인자를 묶어주는 역할이다. 함수는 인자를 두 개를 받지만, 하나만 묶고 싶을 때 남은 자리를 채워주는 역할이다.

 

std::placeholder뒤의 숫자 _1은 인자의 순서이다. _1, _2, _3 등등 여러 숫자를 사용할 수 있다.

이 때, 만약 두 인자를 std::placeholder::_1, std::placeholder::_2 가 아니라, std::placeholder::_1, std::placeholder::_1 과 같이 숫자를 중복해서 넣게 되면, 인자로 (3, 6) 이렇게 2개를 넣어도 실제로는 함수에 (3, 3) 의 인자가 전달된다.

두 번째 인자의 값에도 첫 번째 인자의 값이 강제로 들어가버리는 것이다. 그러므로, 순서에 주의하여 사용하여야 한다.

프로그래밍에 있어서 최적화는 정말 중요한 문제이다.

프로그래밍에서 최적화를 해치는 요소는 여러가지가 있지만, 잦은 복사는 최적화를 해치는 것에 있어서 널리 알려진 것이다. 크기가 큰 데이터에 대한 깊은 복사를 계속 하게 되면 프로그램에 상당한 부하가 발생할 것이다.

하지만, 복사가 반드시 필요한 상황도 분명 존재할 수 있다. 그렇다면, 성능과 기능 중 한가지를 포기해야만 할까?

 

이러한 딜레마를 해결해주고자 하는 것이 Move Semantic이다.

C++ 11 부터는 깊은 복사로 인한 성능 저하를 해결하기 위해 이동 문법을 제공해주고 있다.

이동 문법을 Move Semantic이라고 하며, 이번 게시글에선 이에 대해 알아볼 것이다.

 

얕은 복사와 깊은 복사의 문제점

얉은 복사는 값을 그대로 복사하기 때문에, 포인터 변수를 복사할 경우 동일한 주소값을 가리키게 된다.

한쪽에서 값을 변경하거나 메모리를 해제할 경우 다른 쪽에서는 예측할 수 없는 문제가 발생할 수 있으므로 얕은 복사는 안정성이 매우 떨어진다고 할 수 있다.

 

이러한 문제를 해결하기 위해 복사 생성자, 복사 대입자를 오버로딩하여 깊은 복사를 하게 된다.

깊은 복사는 별도의 메모리 공간을 할당받은 뒤, 값만 동일하게 저장하는 것이다.

그렇기 때문에 어느 한 쪽에서 메모리를 해제하는 등의 작업을 하더라도 다른 쪽에는 전혀 영향을 주지 않게 된다.

 

하지만, 깊은 복사는 안정성을 얻는 대신 성능적인 부분에서 손해를 많이 보게 된다.

배열의 경우를 예로 든다면, 10만개의 원소를 보유한 배열을 복사한다면 10만번의 반복문을 돌며 모든 원소를 복사해야 한다.

 

Move Semantic

우리가 깊은 복사를 하는 근본적인 이유를 생각해보자.

서로 다른 포인터 변수가 같은 메모리를 가리킬 때, 어느 한 쪽에서 수행한 작업이 다른 쪽에 영향을 미칠 수 있기 때문이다. 거기서 발생하는 위험을 막기 위해 깊은 복사를 하는 것이고, 그로 인한 성능 저하가 발생하는 것이다.

 

그렇다면, 다른 쪽에서 해당 메모리 영역을 절대 건드리지 않는다는 확신이 있다면 얕은 복사를 해도 되지 않을까?

예를 들어, A와 B가 있다고 해보자. B가 가지고 있는 데이터를 모두 A로 복사하고자 할 때, 만약 B가 더이상 사용되지 않을 것이라고 확신할 수 있다면 얕은 복사를 해서 성능상 이점을 챙기는 것이 더 좋지 않을까? 어차피 위험이 발생할 가능성이 없으니까 말이다.

 

이러한 아이디어를 실현하는 것이 무브 시맨틱이다. 복사되는 쪽이 더 이상 사용되지 않을 것이라고 확신할 수 있다면, 그냥 얕은 복사를 해버리자는 것이다.

 

무브 시맨틱은 엄밀히 말하면 복사라는 개념과는 살짝 거리가 있다. 왜냐하면, 복사한다는 것은 동일한 테이터를 다른 곳에 또 만든다는 개념이지만, 무브 시맨틱은 어느 한쪽은 더이상 사용할 수 없게 만들어 버리기 때문이다. 얕은 복사를 하면서 발생할 수 있는 위험성을 차단하기 위해 복사되는 쪽의 데이터를 지워버리게 된다.

 

이러한 특징 때문에, 복사가 아니라 이동이라는 용어를 사용하게 된다. 

 

그림으로 한 번 이해해보자.

 

얕은 복사는 위처럼, 두 변수가 모두 같은 주소를 가리키게 하는 것이다.

 

반면, 이동의 경우 위의 그림처럼 한 쪽은 소유권을 포기하고, 다른 쪽이 새로 소유권을 가지도록 하는 것이다.

데이터를 다른 쪽으로 이동한 것이다.

 

우측값 참조

Move Semantic은 위에서도 말했듯이, 더이상 사용되지 않을 것이라고 확신하는 대상의 정보를 다른 곳으로 옮기는 것이라고 하였다. 

 

그런데 더 이상 사용되지 않을 것이라고 확신되는 것이 뭐가 있을까?

가장 쉽게 생각할 수 있는 것이 바로 임시 객체들, 즉 R-Value 이다. R-Value는 식이 끝난 뒤에 사라지는 친구들이다.

그러므로 우리가 R-Value인 객체의 값을 이후에 사용하고 싶어도 사용할 수가 없다. R-Value의 값을 복사하는 경우에는 깊은 복사를 하는 것의 이점이 전혀 없으므로, 이동을 통해 해결하는 것이다.

class A
{
public:
    //기본 생성자
    A() 
    {
        Arr = new int[50];
        
        for(int i = 0; i < 50; i++)
        {
            Arr[i] = i;
        }
    }
    
    ~A()
    {
    	if(Arr != nullptr)
        {
        	delete[] Arr;
            Arr = nullptr;
		}
	}
    
    int* Arr = nullptr;
};

A CreateA()
{
    A ReturnA;
    return ReturnA;
}

int main()
{
    A NewA = CreateA();
    return 0;
}

위의 코드를 보자. CreateA로 반환되는 값은 R-Value이다. 값을 NewA로 복사한 뒤에, 더 이상은 사용할 수 없는 값이다.

그렇다면, CreateA()에 의해 반환되는 값은 NewA로 얕은 복사를 해도 상관이 없을 것 같다.

하지만, 아니다. 왜냐하면, 소멸자에서 Arr의 메모리를 해제하고 있기 때문이다.

 

CreateA()에 의해 반환되는 값은 우리가 직접 그 값을 조작할 수는 없지만, 객체가 파괴되기 전에 소멸자를 호출하게 된다.

즉, Arr의 값을 NewA에 복사한 뒤에 메모리를 해제하여 NewA의 Arr이 댕글링 포인터가 되어버린다.

 

그러므로, 얕은 복사의 문제점이 여전히 발생하는 셈이다.

 

그렇다고 깊은 복사를 하게 된다면? 성능의 저하가 발생하게 된다. 그렇다면, 한 가지 방법이 있다.

 

Arr이 가지고 있는 주소값을 NewA의 Arr에 복사한 뒤에, 임시 객체의 Arr을 nullptr로 만들어버리는 것이다.

임시 객체의 Arr을 nullptr로 만들면, Arr이 소멸될 때, 예외 처리에 의해 delete가 호출되지 않는다.

 

그렇다면, 복사 생성자와 복사 대입자를 아래와 같이 정의할 수 있을 것이다.

A(A& _Other)
{
    Arr = _Other.Arr;
    _Other.Arr = nullptr;
}

A& operator=(A& _Other)
{
    if (Arr != nullptr)
    {
        delete[] Arr;
    }

    Arr = _Other.Arr;
    _Other.Arr = nullptr;
}

이렇게 복사 생성자와 복사 대입자를 오버로딩하면, 문제가 해결될 것만 같다.

하지만, 문제가 한 가지 추가로 발생하게 된다.

 

이렇게 하면 깊은 복사를 사용할 수가 없다는 것이다.

위에서 말했듯이, 이동 연산은 더 이상 사용되지 않을 것이라고 확신하는 대상에 대해 사용하는 것이다.

반대로 말하자면, 이후에도 사용될 것으로 예상되는 대상에 대해서는 깊은 복사를 여전히 해야한다는 것이다.

 

그런데, 위처럼 함부로 복사 생성자를 이동 연산으로 정의해버리면, 깊은 복사를 사용할 수가 없게 된다.

 

그러므로, 이동 연산은 복사 생성자, 복사 대입자를 오버로딩하는 것이 아니라, 우측값을 참조하는 이동 생성자, 이동 대입자를 오버로딩 해야 한다.

//복사 생성자
A(const A& _Other)
{
    Arr = new int[50];
    
    for(int i = 0; i < 50; i++)
    {
        Arr[i] = _Other.Arr[i];
    }
}

//복사 대입자
A& operator=(const A& _Other)
{    
    for(int i = 0; i < 50; i++)
    {
        Arr[i] = _Other.Arr[i];
    }
}

//이동 생성자
A(A&& _Other) noexcept
{
    Arr = _Other.Arr;
    _Other.Arr = nullptr;
}

//이동 대입자
A& operator=(A&& _Other) noexcept
{
    if (Arr != nullptr)
    {
        delete[] Arr;
    }

    Arr = _Other.Arr;
    _Other.Arr = nullptr;
    
    return *this;
}

복사의 경우 A& 타입으로 인자를 받고 있지만, 이동은 A&& 타입을 인자로 받고 있다.

&&타입으로 인자를 받는 생성자와 대입자를 정의하게 되면 이동 연산이 가능하게 된다.

(이동은 default가 없으므로 반드시 정의해주어야 한다.)

 

여기서 중요한 점은 이동 생성자와 이동 대입자는 반드시 noexcept 키워드를 붙여야 한다는 것이다.

예외가 발생할 수 있는 상황이라면, 이동이 아닌 복사가 발생하도록 컴파일러가 구성되어 있기 때문에, 예외가 없음을 보장해주어야 한다.

 

시간 테스트를 한 번 해보자.

for (int i = 0; i < 1000000; i++)
{
    NewA = CreateA();
}

위의 코드를 총 5번 실행할 것이다.

 

위의 결과는 복사 생성자, 복사 대입자만 정의했을 때의 시간이다.

 

위의 결과는 이동 생성자와 이동 대입자도 정의했을 때의 시간이다.

훨씬 빨라진 것을 볼 수 있다.

 

만약, 테스트를 위해 만든 클래스 내부의 배열이 50개의 원소만 가지고 있었지만 500개나 5000개 등 크기를 더 늘리게 되 차이는 더욱 커질 것이다.

 

std::move

위에서는 이동 연산을 임시 객체를 기준으로 설명하였다.

하지만, 임시 객체가 아닌 대상에도 이동 연산을 적용할 수 있다.

바로, std::move 함수의 도움을 받는 것이다.

 

std::move는 L-Value를 R-Value로 캐스팅하여, 복사 생성자, 복사 대입자가 아니라 이동 생성자, 이동 대입자가 호출될 수 있도록 도와주는 역할을 한다.

void Func(A& _A)
{
    A NewA;
    _A = NewA;
}

위와 같은 함수를 보자.

위의 함수에서 NewA 는 임시 객체가 아니라 지역 변수이다.

즉 L-Value인 것이다. 하지만, 함수가 끝나면 사라져서 더 이상 사용되지 않을 객체이기도 하다.

이런 경우에도 깊은 복사가 불필요하지만, NewA가 L-Value이기 때문에 이동 연산이 실행되지 않는다.

void Func(A& _A)
{
    A NewA;
    _A = std::move(NewA);
}

위의 코드처럼 std::move를 사용하여 대입 연산을 실행하게 되면 std::move는 NewA를 R-Value로 캐스팅한 값을 반환하므로 이동 대입자가 호출된다. 이처럼, L-Value이지만 더 이상 사용이 되지 않을 대상이나 소유권을 완전히 이전하고 싶은 대상에 대해서는 std::move 함수를 사용하면 이동 연산을 통해 효율적으로 데이터를 옮길 수 있게 된다.

 

std::forward

std::Move는 복사할 대상을 확실하게 알고 있을 때 사용 가능하다. 하지만, 특정 상황에선 변수의 상태를 정확히 예측할 수 없다.

 

예를 들어, 템플릿 함수를 사용한다고 해보자. 템플릿에는 다양한 자료형이 들어올 수 있고, 어떤 변수가 들어올 지 예상할 수가 없다. 인자로 L-Value가 들어올 수도 있고 R-Value가 들어올 수도 있다. 일반적인 상황에선 안정성을 위해, 인자로 들어오는 모든 값이 L-Value라고 가정하고 깊은 복사를 실행하는 것이 좋다.

 

하지만, std::forward를 사용하면, L-Value는 깊은 복사, R-Value는 이동 연산을 실행하도록 별도로 처리하여 추가적인 최적화를 노려볼 수 있다.

class A
{

};

void Func(A& _A)
{
    std::cout << "L-Value 참조 " << std::endl;
}

void Func(A&& _A)
{
    std::cout << "R-Value 참조 " << std::endl;
}

template <typename T>
void FuncTemplate(T _T)
{
    Func(_T);
}

int main()
{
    A NewA;

    FuncTemplate(NewA);
    FuncTemplate(A());
}

위의 코드는 std::forward를 사용하지 않은 상황이다.

L-Value와 R-Value를 인자로 받는 함수를 오버로딩하였다.

 

기대하는 결과는, FuncTemplate(NewA);  에선 L-Value를 인자로 받는 Func가 호출되고
FuncTemplate(A()); 에서는 R-Value를 인자로 받는 Func가 호출되는 것이다.

하지만 실행해보면 위처럼, 둘 다 L-Value를 인자로 받는 함수를 호출하게 된다.

템플릿 때문에 컴파일러가 인자를 정확하게 추론하지 못하고 있는 상황인 것이다.

template <typename T>
void FuncTemplate(T&& _T)
{
    Func(std::forward<T>(_T));
}

하지만, FuincTemplate를 위처럼 코드를 바꿔본다면?

 

이렇게, L-Value와 R-Value를 컴파일러가 정확히 구분할 수 있게 된다.

사용하기 위해선, 위처럼 템플릿 함수의 인자를 &&타입으로 바꾼 뒤, std::forward<T>(_T)의 형식을 사용하면 된다.

C++에선, 값을 2개로 분류하고 있다.
바로, L-Value와 R-Value이다.
 
L-Value와 R-Value가 무엇인지 알아보자.
 

L-Value

L-Value와 R-Value를 보면, 이름에서 가장 쉽게 연상하는 것은 left와 Right이다. 실제로, L-Value, R-Value의 개념과도 연관이 있기 때문에 L-Value는 식에서 좌측에 있는 값, R-Value는 식에서 우측에 있는 값이라고 설명하는 경우가 많다.
 
하지만 이는 틀린 설명이다.
왜냐하면, R-Value는 우측에만 있는 것이 맞지만 L-Value는 우측에도 있을 수 있고 좌측에도 있을 수 있기 때문이다.
 
L-Value란, 메인 메모리에 할당된 공간에 저장되어 있는 값이다.
메모리에 실제로 할당이 되어 있기 때문에, 주소값을 참조하여 사용할 수 있다.
 
또한, L-Value는 읽는 연산과 쓰는 연산이 모두 가능하다. (값을 변경하는 것이 가능하다.)
 

R-Value

R-Value는 식에서 우측에만 존재할 수 있다.
 
R-Value는 잠깐 생겼다가 사라지는 임시 값이다. 그렇기 때문에, 별도의 주소값이 존재하지 않고 이를 참조할 수가 없다.
(임시 레지스터에 저장된 경우 레지스터의 주소값은 존재하겠지만, 이를 사용자가 참조에 사용할 수는 없다.)
 

예제

글로만 보면, 이해가 힘들 수 있으므로 예제를 한 번 보자.

int A = 3; // A는 L-Value, 3는 R-Value

 
위의 코드를 보자. int A = 3; 이라는 구문이 있다.
 
이 때, A라는 것은 특정 메모리 영역에 붙인 이름이다. int A 를 통해, 4바이트의 정수형 값을 저장하기 위한 메모리를 할당하였다. 그리고, 그 안에 최초에 저장되어 있는 쓰레기 값을 밀어내고 초기값을 설정하기 위해, A = 3; 이라는 코드로 저장된 값을 변경하였다
 
즉, int A = 3; 에서 A는 메모리 공간을 할당받고 있으며, 주소값이 존재하고 그 안에 저장된 값을 바꿀 수 있다는 것이다.
그러므로 A는 L-Value라고 할 수 있다.
 

int X = 0;
int Y = 1;
int Z = 2;

X = Y + Z;

 
위의 식에서, X,Y,Z는 모두 L-Value이다. 하지만, 마지막 식에서 (Y + Z)는 R-Value 이다.
두 변수의 값을 합한 값은 메인 메모리에 저장되어 있지 않고, 이를 참조할 수도 없기 때문이다. 

3 = 4; //3은 변경될 수 없는 임시의 값이다.
int* A = &3; // 3은 저장된 메모리 공간이 없으므로, 주소값을 참조할 수 없다.

 
3이라는 값은 잠시 사용될 임시 값이다. 모든 리터럴 숫자가 그렇다. 메인 메모리에 할당된 영역이 없기 때문에 그 값을 바꿀 수가 없다.  또한, 메인 메모리에 할당되지 않았으므로 주소값을 참조할 수 없다.
 

int Func()
{
    int Value = 0;
    return Value;
}

int main()
{
    int A = 0;
    
    A = Func(); // 가능
    Func() = 3; // 불가능
}

 
Func()는 0이라는 정수 값을 반환하고 있다.
내부에선 L-Value인 Value라는 변수를 반환하고 있지만, 이 변수는 함수가 종료되면 사라진다.
즉, Func()에서 Value를 그 자체로 반환하여도 외부에선 사용할 수가 없는 것이다. (파괴되었으므로)
 
그렇기 때문에, Func()는 Value를 자체로 반환하지 않고 저장되어 있는 값만 반환한다.
즉, 위의 코드에서 Func()가 반환하는 것은 Value가 아니라 0이라는 R-Value 라고 할 수 있는 것이다.
(임시 값이며, 참조할 수 없는 값)
 
main함수 내부를 보자.
 
A = Func(); 라는 코드는 A = 0; 으로 해석할 수 있고, 이는 올바른 문장이다.
반면, Func() = 3; 을 보면, 0 = 3; 이 되므로, 올바른 문장이 아니다.
 

int Value = 0;

int& Func()
{
    return Value;
}

int main()
{
    int A = 0;
    
    A = Func(); // 가능
    Func() = 3; // 가능
}

 
위의 함수에선 조금 다르다.
 
Value는 전역변수이다.
그리고, Func()는 전역변수 Value에 대한 참조를 반환하고 있다.
그러므로, Func()는 Value 자체를 반환한다고 보아도 된다.
 
그래서 main() 함수 내부의 코드의 의미가 조금 달라진다.
A = Func(); 는 A = Value; 가 되므로, 올바른 문장이다.
 
여기서 좌측과 우측이 모두 L-Value 이다. 위에서 L-Value는 좌측과 우측에 모두 올 수 있다고 했던 것이 이런 경우이다.
 
Func() = 3; 이라는 문장은 Value = 3; 이라는 문장으로 해석할 수 있다. 문제가 없는 문장이 된다.

 

N의 길이를 가지는 좋은 수열 중, 하나의 수로 표현했을 때 가장 작은 수가 되는 좋은 수열을 구하자.

 

좋은 수열이란, 나쁜 수열이 아닌 수열이다.

나쁜 수열이란, 특정 부분 수열이 반복되는 부분 수열이 존재하는 수열이다.

 

예를 들어, 123123 은 123이라는 부분 수열이 반복되는 123123이라는 부분 수열이 존재한다.

312123 은, 12라는 부분 수열이 반복되는 1212라는 부분 수열이 존재한다.

11은, 1이라는 부분 수열이 반복되는 11이라는 부분 수열이 존재한다.

 

문제 풀이

이 문제는 특별한 규칙을 찾을 수는 없었다. 하나하나 경우의 수를 탐색하는 방법말고는 다른 방법은 딱히 없는 듯 하다.

본인은 백트래킹을 활용하여 문제를 해결하였다.

 

문자열의 맨 뒤에 1, 2, 3을 더한 뒤, 해당 수열이 좋은 수열인지 탐색하는 것이다.

 

그렇다면, 해당 수열이 나쁜 수열인지 좋은 수열인지 판단하는 방법이 필요하다.

본인은 맨 뒤에서부터 수열의 절반만큼 탐색하며 판단하였다.

 

예를 들어 "12323" 을 판별한다고 해보자.

 

맨 뒤에서 1글자를 기준으로 비교하게 되면, "12323이렇게 파란색 문자열과 빨간색 문자열을 비교하게 된다.

두 문자열이 같다면, 나쁜 수열인 것이다.

 

한 글자를 비교했을 때, 좋은 수열이었다면 이번엔 두 글자를 비교해보는 것이다. "12323" 이렇게 말이다.

이번엔, 파란색 문자열과 빨간색 문자열이 동일하므로, 나쁜 수열임을 판단할 수 있다.

 

하지만 끝을 기준으로 비교하게 되면 "132321" 이렇게 중간에 수열이 반복되는 경우는 탐지할 수가 없을 것 처럼 보인다. 하지만, 아니다. 왜냐하면, 재귀함수를 통해 1글자씩 더해가며 판별을 반복할 것이기 때문이다. 

 

맨 처음엔, 빈 문자열에 1을 더한다.

문자열 : "1"

 

위의 문자열을 판별한다.

좋은 수열인 경우, 문자열의 뒤에 "1"을 더한다

문자열 : "11"

 

또 위의 문자열을 판별한다.

좋은 수열인 경우, 문자열의 뒤에 "1"을 더한다.

하지만, 현재 문자열은 나쁜 수열이다.그러므로, 뒤의 1을 뺀 뒤, 2를 더한다. (만약 맨 뒤가 2인 상태에서 나쁜 수열로 판단된다면, 2를 빼고 3을 더한다. )

문자열 : "12"

 

위의 문자열을 판별한다.좋은 수열인 경우, 문자열의 뒤에 "1"을 더한다.

문자열 : "121"

 

이 과정을 의사 코드로 작성하면, 아래와 같다.

void Recursive(std::string _Str, int _MaxLength)
{
	if (_Str이 나쁜 수열이면?)
	{
            return;
	}

	if (길이가 MaxLength까지 왔는데, 나쁜 수열이 아니다?)
	{
            정답 발견!
            return;
	}
    
	Recursive(_Str + "1", _MaxLength);
	Recursive(_Str + "2", _MaxLength);
	Recursive(_Str + "3", _MaxLength);
}

 

이렇게 재귀함수를 활용하여, 문자열의 길이를 1씩 증가시키며 좋은 수열을 찾는 것이다.

그러므로, 중간에 반복되는 수열이 있는 경우는 있을 수가 없다.

 

(중간에 있는 반복되는 수열은 현재 문자열보다 길이가 짧은 문자열에서는 가장 뒤에 있는 반복되는 수열일 수 있다. 거기서 반복되는 수열이 발견되면서 return 해버리기 때문에, 중간에서 발견되는 반복되는 수열은 있을 수 없다.)

 

또한, 재귀함수를 보면, 1을 우선적으로 더하고 그 이후 2를 더하고 마지막에 3을 더하고 있다.즉, 가장 먼저 발견되는 좋은 수열이 정답이 될 수 밖에 없다.

 

1-> 11 -> 12 -> 121->  1211 -> 1212 -> 1213 ... 이런 식으로 숫자 크기대로 탐색하기 때문이다.

 

풀이 코드

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

먼저, 수열의 길이를 입력받는다.

 

Recursive("", Length);

std::cout << Answer;

return 0;

이후, 재귀함수를 실행한 뒤에 답을 출력할 것이다.

 

void Recursive(std::string _Str, int _MaxLength)
{
    if (Answer != "")
    {
        return;
    }

    if (Check(_Str) == false)
    {
        return;
    }

    if (_Str.size() >= _MaxLength)
    {
        Answer = _Str;
        return;
    }
    
    Recursive(_Str + "1", _MaxLength);
    Recursive(_Str + "2", _MaxLength);
    Recursive(_Str + "3", _MaxLength);
}

Answer이 ""이 아니라면, 이미 답을 구했다는 의미이므로 모든 재귀함수를 종료시킨다.

 

Check는 해당 수열이 좋은 수열인지 판단하는 함수이다. 나쁜 수열이라면 return해주었다.

 

길이가 MaxLength될 때 까지 나쁜 수열로 판별되지 않은 수열이 있다면 정답으로 저장해주었다.

 

문자열의 맨 뒤에 1을 붙이는 경우를 우선적으로 재귀적 탐색한 뒤, 정답을 발견하지 못하면 2를 붙이며 탐색하고, 그 때도 발견하지 못하면 3을 붙여 순차적으로 탐색하도록 하였다.

 

bool Check(const std::string& _Str)
{
    int Size = _Str.size();

    for (int i = 1; i <= Size / 2; i++)
    {
        int Start = Size - i * 2;
        
        if (_Str.substr(Start, i) == _Str.substr(Start + i, i))
        {
            return false;
        }
    }

    return true;
}

Check함수의 내부 코드이다.

문자열의 끌을 기준으로, 1자리, 2자리 3자리.... (문자열의 길이 / 2)자리의 수열이 앞에서 반복되고 있는 지를 판별하였다.

 

12131213

12131213

12131213

12131213

 

위와 같은 순서로, 파란색 문자열과 빨간색 문자열을 비교한 것이다.

위에서도 말했지만, 중간에서 반복되는 부분 수열은, 해당 수열이 끝에 있을 때 이미 걸러지기 때문에 중간에서는 반복되는 수열이 발견될 수 없다.

 

(123231 에서, 23과 23이 반복되고 있지만,이는 12323 에서 이미 걸러지고 return 되므로 123231이라는 문자열은 탐색되지 않는다.)

 

 

코드 전문

더보기
#include <iostream>
#include <vector>
#include <set>

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

std::string Answer = "";

bool Check(const std::string& _Str)
{
    int Size = _Str.size();

    for (int i = 1; i <= Size / 2; i++)
    {
        int Start = Size - i * 2;
        
        if (_Str.substr(Start, i) == _Str.substr(Start + i, i))
        {
            return false;
        }
    }

    return true;
}

void Recursive(std::string _Str, int _MaxLength)
{
    if (Answer != "")
    {
        return;
    }

    if (Check(_Str) == false)
    {
        return;
    }

    if (_Str.size() >= _MaxLength)
    {
        Answer = _Str;
        return;
    }
    
    Recursive(_Str + "1", _MaxLength);
    Recursive(_Str + "2", _MaxLength);
    Recursive(_Str + "3", _MaxLength);
}

int main()
{
    Init();

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

    Recursive("", Length);

    std::cout << Answer;

    return 0;
}

 

트리의 특정 간선에 연결된 두 노드 중, 한 쪽의 가중치에는 -1을 하고 다른 쪽의 가중치에는 +1을 하는 작업을 반복했을 때, 모든 노드의 가중치를 0으로 만들 수 있을까?

 

만약, 만들 수 없다면 -1을 출력하면 되고 만들 수 있다면 몇 번을 반복해야 모든 노드의 가중치가 0이 되는지 구하면 된다.

 

문제 풀이

언뜻 보기엔, 매우 복잡해보이지만 생각보다는 간단한 문제이다.

핵심은 트리의 가장 말단 노드부터 0으로 만드는 것이다.

 

DFS든 BFS든 트리의 말단을 찾아가서, 말단을 0으로 만들면서 루트 노드까지 올라왔을 때 모든 노드의 가중치를 확인하면 된다.

 

그림을 보면서 이해해보자.

 

문제의 첫 번째 입력을 그림으로 그려보면 아래와 같다.

노드 안의 숫자는 (번호 / 가중치) 이다.

이제, 말단에서부터 가중치를 0으로 만들어보자.

 

2번 노드에 대해 갱신하면, 위와 같아진다.

다음은 4번 노드에 대해서도 갱신해보자.

위와 같이 값이 갱신될 것이다.

이제, 말단 노드가 모두 0으로 되었으니, 0이 아닌 노드 중 가장 말단에 있는 노드를 0으로 만들어보자.

 

3번 노드를 갱신하고 나니, 루트 노드까지 갱신되었다.

노드의 모든 가중치를 보면 0으로 갱신되어 있는 것을 볼 수 있다.

 

이처럼, 말단노드부터 위로 올라오며 0으로 갱신하다 보면, 모든 노드를 갱신하게 된다.

모든 노드를 갱신한 뒤에, 모든 노드의 가중치가 0인지 아닌지를 확인하면 된다.

 

가중치가 0이 아니라면, -1과 +1을 하는 작업을 몇 번 반복했는지를 출력하면 되는데, 이건 노드를 0으로 만들 때, 해당 노드의 가중치의 절대값에 대한 누적합을 구하면 된다.

 

참고로 위의 과정은 루트 노드에서부터 시작해야 한다.

하지만, 입력으로 주어지는 트리는 양방향 트리이므로, 어떤 노드든 사실 루트 노드가 될 수 있다.

그러므로 아무 노드에서나 시작해도 문제는 없다.

 

하지만, 4번 노드에서부터 시작하도록 했는데 입력으로 4번 노드가 주어지지 않는다면?

이런 문제를 방지하기 위해, 0번 노드에서부터 시작하는 것이 가장 무난하다. 

 

풀이 코드

std::vector<long long> CastA(a.size());
for(int i = 0; i < a.size(); i++)
{
    CastA[i] = a[i];
}

std::vector<std::vector<int>> Link(a.size());

for(int i = 0; i < edges.size(); i++)
{
    int Node_1 = edges[i][0];
    int Node_2 = edges[i][1];

    Link[Node_1].push_back(Node_2);
    Link[Node_2].push_back(Node_1);
}
    
std::vector<bool> isVisit(a.size(), false);

CastA는 주어진 노드의 가중치를 long long 자료형으로 변환하여 새로 저장한 것이다.

왜냐하면, 기존 배열에 값을 더하고 빼며 계산할 것인데 이 과정에서 int 자료형의 범위를 초과하는 경우가 발생할 수 있기 때문이다.

 

Link는 각 노드에서 연결된 노드들을 저장한 배열이다.

 

isVisit는 DFS를 위해 만든 방문체크배열이다.

 

DFS(CastA, Link, isVisit, 0, -1);

for(int i = 0; i < CastA.size(); i++)
{
    if(CastA[i] != 0)
    {
        Count = -1;
        break;
    }
}

return Count;

다음은 DFS를 돌린 다음, 모든 노드의 가중치가 0인지를 확인하는 과정이다.

(참고로 Count는 전역변수이다.)

 

void DFS(std::vector<long long>& _Weight, const std::vector<std::vector<int>>& _Link,  std::vector<bool>& _isVisit, int _CurIndex, int _PrevIndex)
{
    _isVisit[_CurIndex] = true;
    
    for(int i = 0; i < _Link[_CurIndex].size(); i++)
    {
        int NextIndex = _Link[_CurIndex][i];
        
        if(_isVisit[NextIndex] == false)
        {
            DFS(_Weight, _Link, _isVisit, NextIndex, _CurIndex);
        }
    }
    
    if(_PrevIndex != -1)
    {
        Count += abs(_Weight[_CurIndex]);

        _Weight[_PrevIndex] += _Weight[_CurIndex];
        _Weight[_CurIndex] = 0;
    }
}

DFS내부 코드는 이와 같다.

 

먼저, 방문체크를 해준 다음 연결된 노드 중 이동할 수 있는 노드에 대해 이동해주었다.

이후, 말단 노드에서는 더이상 이동할 곳이 없기 때문에 반복문을 탈출하게 되는데, 이 때, 해당 노드의 가중치를 0으로 만드는 과정을 거치게 된다. 말단 노드에서부터 위로 올라오며 재귀적으로 노드의 가중치를 0으로 만드는 것이다.

 

 이렇게 하면, 올바른 답을 출력할 수 있게 된다.

 

 

코드 전문

더보기
#include <string>
#include <vector>

using namespace std;

long long Count = 0;

void DFS(std::vector<long long>& _Weight, const std::vector<std::vector<int>>& _Link,  std::vector<bool>& _isVisit, int _CurIndex, int _PrevIndex)
{
    _isVisit[_CurIndex] = true;
    
    for(int i = 0; i < _Link[_CurIndex].size(); i++)
    {
        int NextIndex = _Link[_CurIndex][i];
        
        if(_isVisit[NextIndex] == false)
        {
            DFS(_Weight, _Link, _isVisit, NextIndex, _CurIndex);
        }
    }
    
    if(_PrevIndex != -1)
    {
        Count += abs(_Weight[_CurIndex]);

        _Weight[_PrevIndex] += _Weight[_CurIndex];
        _Weight[_CurIndex] = 0;
    }
}

long long solution(vector<int> a, vector<vector<int>> edges) 
{
    std::vector<long long> CastA(a.size());
    for(int i = 0; i < a.size(); i++)
    {
        CastA[i] = a[i];
    }
    
    std::vector<std::vector<int>> Link(a.size());
    
    for(int i = 0; i < edges.size(); i++)
    {
        int Node_1 = edges[i][0];
        int Node_2 = edges[i][1];
        
        Link[Node_1].push_back(Node_2);
        Link[Node_2].push_back(Node_1);
    }
    
    std::vector<bool> isVisit(a.size(), false);
    
    DFS(CastA, Link, isVisit, 0, -1);
    
    for(int i = 0; i < CastA.size(); i++)
    {
        if(CastA[i] != 0)
        {
            Count = -1;
            break;
        }
    }
    
    return Count;
}

 

n개의 자연수를 더해서, s가 될 수 있는 자연수 집합 중에서 원소들의 곱이 가장 큰 집합을 구하면 된다.

 

문제 풀이

이 문제는 어렵게 생각하면 매우 어렵지만 쉽게 생각하면 매우 쉽다.

결론부터 말하면, 최고의 집합은 원소들간의 편차가 가장 작은 집합이다.

 

예를 들어, n이 3이고 s가 10이라고 한다면 최고의 집합은 {3, 3, 4}가 된다.

n이 5이고 s가 40이라고 한다면, {8, 8, 8, 8, 8} 이 된다.

n이 4이고, s가 35라고 한다면 {8, 9, 9, 9}가 된다.

 

왜 그렇게 되는지는 사실 수학적인 증명까지는 잘 모르지만, 직접 몇 가지 경우에 대해 계산해본 결과 위처럼 편차가 가장 고른 숫자 집합이 최고의 집합이 된다는 것을 확인해볼 수 있었다.

 

그렇다면, n과 s를 사용해서 편차가 가장 고른 숫자 집합을 만들면 된다는 것이다.

어떻게 만들면 될까?

 

1. n개 만큼의 원소를 저장할 수 있는 배열을 만든다.

2. 배열의 각 원소를 s / n 으로 저장한다.

3. 배열의 가장 마지막 원소부터 (s % n) 개만큼 앞에 있는 원소까지 1씩 더해준다.

 

위의 과정을 거치면 최고의 집합을 구할 수 있다.

가장 값이 고른 숫자 집합을 만들려면, 당연히 n으로 s를 나누면 된다.

하지만 모든 숫자의 합이 s가 되기 위해선, 나머지가 0이어야만 한다. 하지만, 항상 나머지가 0이되는 것은 아니다.

나머지가 1보다 큰 상황에선 나머지의 수와 동일한 갯수만큼 각 숫자에 1씩 더해주면, 가장 편차가 적은 집합을 구성할 수 있게 된다.

 

풀이 코드

if(s < n)
{
    return {-1};
}

 

먼저, 예외처리이다. 만약, s가 n보다 작다면?
s 를 n으로 나눈 몫이 0이 된다. 최고의 집합은 모든 원소가 자연수가 되어야 하는데, s < n 인 상황에선 원소에 0이 포함되므로 s < n 인 경우에는 최고의 집합이 존재하지 않는다.

 

vector<int> Answer(n, 0);
    
int Share = s / n;
int Remain = s % n;

for(int i =  Answer.size() - 1; i  >= 0; i--)
{
    Answer[i] = Share;

    if(Remain > 0)
    {
        Answer[i] += 1;
        Remain--;
    }
}

이후, 위에서 말했던 것처럼 배열에 몫을 저장해주었고, 배열의 가장 뒤에서부터 나머지의 개수만큼 원소에 1을 더해주었다.

 

return Answer;

반복문이 끝난 후 배열을 반환해주면 된다.

 

 

코드 전문

더보기
#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) 
{
    if(s < n)
    {
        return {-1};
    }
   
    vector<int> Answer(n, 0);
    
    int Share = s / n;
    int Remain = s % n;
    
    for(int i =  Answer.size() - 1; i  >= 0; i--)
    {
        Answer[i] = Share;
        
        if(Remain > 0)
        {
            Answer[i] += 1;
            Remain--;
        }
    }
        
    return Answer;
}

데이터베이스에선, 정확한 데이터 처리를 위해 데이터의 무결성을 최대한으로 보장하도록 하고 있다.

데이터베이스를 이해하기 위해 아주 중요한 개념인 데이터 무결성에 대해 알아보자.

 

데이터 무결성

데이터 무결성이란, 데이터에 어떠한 허점이나 결점이 없는 상태를 의미한다.

조금 더 이론적으로 말하자면 정확성, 일관성, 유효성이 유지되는 상태라고 한다.

 

정확성이란?

특정 데이터에 대해 중복이나 누락이 존재하지 않아 원하는 데이터를 정확하게 찾을 수 있는 상태를 의미한다.

 

Ex) 동일한 튜플이 2~3개씩 저장되어 있다면, 어떠한 튜플을 참조해야 할 지 식별할 수가 없어진다.

 

일관성이란?

모든 데이터에 대해, 그 의미나 형식 등이 일관되어 있는 상태를 의미한다.

 

Ex 1) 사람의 나이를 만나이로 저장하기로 했다면, 모든 나이 데이터가 만 나이로 저장되어 있어야 한다.

Ex 2) 모든 학번을 NULL이 아닌 값을 저장하기로 했다면, 임시 학번을 부여해서라도 NULL이 저장되지 않도록 해야 한다.

 

유효성이란?

모든 데이터가 유효한 형식으로 저장되어 있는 상태를 의미한다.

 

Ex) 주민번호는 xxxxxxx - xxxxxxx 의 앞의 6자리와 뒤의 7자리 형식으로 저장되어야 한다. 사용자로부터 입력받을 경우, 유효하지 않은 데이터의 저장을 방지하기 위해 형식을 강제해야 한다.

 

무결성 제약조건

무결성을 보장하기 위해, 데이터베이스에 여러가지 제약조건을 설정할 수 있다.

대표적인 제약조건 3가지를 알아보자.

 

도메인 무결성 제약조건

 

도메인이란, 속성의 저장 범위를 강제하는 조건이다.

 

에를 들어, 성별이라는 속성값이 있다면 혹은 로만 저장되어야 한다.

혹은, 초등학교 학년이라는 속성값이 있다면, 1~6 사이의 정수값만 저장될 수 있을 것이다.

 

모든 데이터는 해당 도메인의 범위 내에서만 저장되어야 한다는 제약조건이 도메인 무결성 제약조건이다.

 

성별을 입력하는 입력칸에 사용자가 남이 아닌, 담, 납, 낭 등의 오탈자를 입력할 가능성이 있으므로, 체크박스를 두어 성별을 둘 중 하나로 선택하도록 강제하는 것이 도메인 무결성 제약조건을 지키는 사례라고 생각하면 된다.

 

개체 무결성 제약조건

 

개체 무결성 제약 조건이란, 테이블의 기본키에 포함되는 모든 속성값은 NULL이어서는 안된다는 조건이다.

 

기본키란, 튜플을 식별하기 위해 기본으로 사용하는 키이다. 해당 키로 데이터를 탐색하는데 NULL값이 포함되어 있다면 원하는 데이터를 정확하게 탐색하고 식별할 수 없을 것이다.

 

즉, 기본키에 해당하는 속성만큼은 절대 NULL을 포함하지 말자는 제약 조건이 개체 무결성 제약 조건이다.

 

참조 무결성 제약조건

 

참조 무결성 제약 조건이란, 외래키는 NULL이거나 참조 릴레이션의 기본키와 일치해야 한다는 것이다.

 

예를 들어, 학생 정보 튜플에 학과 번호라는 속성이 포함되어 있다고 해보자.

학과 번호를 외래키로 사용하여, 외부의 학과 정보 테이블에서 {학과 번호, 학과 이름, 학과장 }의 튜플을 식별하고자 한다고 해보자.

 

그렇다면, 해당 외래키 값에 대한 학과 번호는 반드시 학과 정보 테이블에 저장되어 있어야 한다.

학과 번호는 1~9번까지 존재하는데, 만약 외래키 학과 번호에 10이 저장되어 있다면, 학과 정보 테이블에서 올바른 학과 정보를 참조를 할 수 없을 것이다.

 

그러므로 안전한 참조를 위해, 반드시 외래키 값은 참조 테이블의 기본키 값에 존재해야 한다.

만약, 참조할 대상이 아직 없다면 NULL을 입력하여 명확히 표현해주어야 한다.

+ Recent posts