언리얼 엔진 빌드 툴 타깃 레퍼런스

https://dev.epicgames.com/documentation/ko-kr/unreal-engine/unreal-engine-build-tool-target-reference

msdn CS0101 에러

https://learn.microsoft.com/ko-kr/dotnet/csharp/misc/cs0101

플러그인이란?

언리얼 엔진의 플러그인이란, 개발자가 프로젝트 단위로 에디터 내에서 활성화/비활성화 할 수 있는 코드 집합이다. 기존에 C++로 개발했던 언리얼 프로젝트에 Gameplay Abilities 플러그인을 활성화하였으나, cs0101 에러가 발생했다.

문제 배경

문제가 발생한 파일

우선 해당 에러는 Target.cs 파일과 Target.Editor.cs 파일에서 발생했다. 해당 C# 파일은 언리얼 빌드 툴(UBT)이 빌드할 때 참고하는 설정 파일이다. 해당 파일 내에 사용하는 엔진 버전이나, 어떤 실행파일로 빌드할지 = 타겟(게임, 서버, 에디터)를 기재해주면 UBT가 해당 내용을 읽는다.

에러 내용

cs0101 에러는 이미 네임스페이스에 type에 정의가 포함되어있다는 에러이다. 즉, 같은 네임스페이스를 쓰는 코드 내에서 같은 이름으로 클래스를 만들어서 컴파일러에서 식별이 안된다는 뜻이다.

해결 방법

삽질 과정

지피티에게 물어보니 .NET SDK가 9.0이라서 그렇다는 둥, 임시 생성 파일을 모아두는 폴더인 Intermediate 폴더를 지우라는 둥 여러 해결책을 주었다. .NET SDK를 8.0으로도 바꿔보고, 빌드 후 생성되는 폴더 & sln 파일을 모두 지우고 빌드도 해보고, AppData에 UBT 캐시 폴더를 지우고도 빌드해봤지만 모두 도움이 되지 못했다.

(진짜) 해결한 방법

에러가 발생한 파일을 돌이켜보자. Target.cs 파일과 Target.Editor.cs 파일이다. 결론은 해당 파일들의 경로가 문제였다.

언리얼 엔진의 경우 프로젝트 생성 시 blueprint 프로젝트로 생성할 것인지, C++ 프로젝트로 생성할 것인지 옵션이 있다. 중간에 blueprint 프로젝트로 생성하고 추후 C++ 프로젝트로 확장할 수 있는데, 그럴 경우 주 게임 모듈 폴더 내에 Target.cs 파일과 Target.Editor.cs 파일이 위치한다.

하지만 C++ 프로젝트에서 UBT가 해당 파일들의 위치를 찾으려면 루트 폴더 내에 위치해야한다. 아니라면, UBT가 C++ 프로젝트가 아니라고 인식하고 Intermediate/Source 내에 임시 cs 파일들을 생성해주기 때문이다. 이것 때문에 임시 cs 파일과 기존 cs 파일이 같은 클래스 네임을 가지고 있어, 네임스페이스 오류가 발생한것이다.

한줄요약 : Target.cs 파일과 Target.Editor.cs 파일을 Source 디렉터리로 옮겨주면 해결된다.

따라오는 의문

그렇다면, 기존에도 C++을 사용하는 프로젝트였는데 왜 오류가 안나고 제대로 UBT에서 cs 파일을 인식했을까? 지피티에게 물어보았다.

플러그인 추가 시 UBT가 빌드 그래프를 다시 생성한다고 하는데, 어떤 것인지는 잘 모르겠지만 이때 source 디렉터리에 cs 파일이 없어서 C++ 프로젝트로 인식을 못한 것이라고 한다. 이전에는 이미 cs 파일의 위치를 스캔해서 기존 target 정보가 있는 상태이기 때문에 정상적으로 동작했을 것이다 .. 라고 하더이다. 추후 빌드 그래프에 대해 공부해보면 좋을 것 같다.

https://school.programmers.co.kr/learn/courses/30/lessons/258707

풀이

0. 동전을 최대한 적게 소모하면서 라운드를 진행해야 하므로, 동전 소모 개수에 따라서 분기한다. 0-1. 동전을 0개(zeroCoinPairs), 1개(oneCoinPairs), 2개(twoCoinPairs) 소모하고 다음 라운드로 넘어갈 수 있는 경우의 수를 변수로 선언한다. 0-2. 손에 들고 있는 카드 체크용 벡터(hand), 카드 뭉치에 남아있는 카드 체크용 벡터(reserve)를 선언한다.

1. n/3개의 카드를 hand에 넣어준다. 이때, hand에 있는 카드끼리 조합해 n+1이 된다면 동전을 0개 소모하고 다음 라운드로 넘어갈 수 있기에 zeroCoinPairs를 증가시킨다.

2. n/3부터 카드 뭉치를 순회하며 2개의 카드(draw1, draw2)를 꺼낸다. 2-1. reserve에 draw1, draw2 카드를 넣어주고, 해당하는 동전 소모 경우의 수를 1씩 증가시켜준다. 2-2. 동전을 가장 적게 소모하는 경우의 수부터 확인하며, 라운드 횟수를 늘리고 동전 소모 경우의 수를 1씩 감소시킨다. 2-3. 동전을 0개, 1개, 2개를 소모하는 경우의 수에 모두 포함되지 않는 경우 해당 라운드에서 게임이 종료되므로 반복문을 종료한다.

2-4. round를 반환한다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int coin, vector<int> cards)
{
    vector<bool> hand(1000, false);
    vector<bool> reserve(1000, false);

    int cardCount = cards.size();
    int zeroCoinPairs = 0, oneCoinPairs =0, twoCoinPairs =0;

    for(int i=0; i<cards.size() / 3; i++)
    {
        hand[cards[i]] = true;
        if(hand[cards[i]] && hand[cardCount + 1 - cards[i]])
        {
            zeroCoinPairs++;
            hand[cardCount + 1 - cards[i]] = false;
        }
    }

    int round = 1;
    for(int i=cards.size() / 3; i<cardCount; i+=2)
    {
        int draw1 = cards[i];
        int draw2 = cards[i+1];

        reserve[draw1] = true;
        reserve[draw2] = true;

        if(reserve[draw1] && hand[cardCount + 1 - draw1])
        {
            oneCoinPairs++;
            reserve[draw1] = false;
            hand[cardCount + 1 - draw1] = false;
        }
        if(reserve[draw2] && hand[cardCount + 1 - draw2])
        {
            oneCoinPairs++;
            reserve[draw2] = false;
            hand[cardCount + 1 - draw2] = false;
        }
        if(reserve[draw1] && reserve[cardCount + 1 - draw1])
        {
            twoCoinPairs++;
            reserve[draw1] = false;
            reserve[cardCount + 1 - draw1] = false;
        }
        if(reserve[draw2] && reserve[cardCount + 1 - draw2])
        {
            twoCoinPairs++;
            reserve[draw2] = false;
            reserve[cardCount + 1 - draw2] = false;
        }

        if(zeroCoinPairs > 0)
        {
            zeroCoinPairs--;
            round++;
        }
        else if(oneCoinPairs > 0 && coin >= 1)
        {
            oneCoinPairs--;
            coin--;
            round++;
        }
        else if(twoCoinPairs > 0 && coin >= 2)
        {
            twoCoinPairs--;
            coin -= 2;
            round++;
        }
        else
            break;
    }

    return round;
}

https://school.programmers.co.kr/learn/courses/30/lessons/258709

풀이

1. n개의 주사위 중, A와 B가 n/2개씩 주사위를 나누어 갖는 조합을 구한다. 1-1. 주사위 조합을 구하기 위해 n개의 크기를 가진 comb 벡터를 선언한다. 1-2. comb 벡터의 begin부터 절반까지 1로 채운다. comb 벡터에서 1인 index가 teamA에 포함될 주사위의 index이다. 1-3. comb 벡터를 순회하며 comb[i]가 1일때 teamA에 push_back, 반대일 때 teamB에 push_back 해준다. 1-4. prev_permutation 함수로 더 작은 순열이 없을 때까지 반복한다.

2. dfs를 활용하여 각 조합별 주사위끼리 눈의 합을 sumsA 벡터, sumsB 벡터에 저장한다. ex) 주사위 = [[1, 2], [2, 3], [3, 4], [4, 5]] / teamA = [0, 1], teamB = [2, 3] 라고 가정하자. A는 0, 1번째 주사위의 합 [1+2, 1+3, 2+2, 2+3]을 반환하고, B는 2, 3번째 주사위의 합 [3+4, 3+5, 4+4, 4+5]를 반환한다.

3. sumsB 벡터를 sort 함수로 정렬한다. 3-1. sumsA 벡터를 순회하며 현재 값이 sumsB 벡터에서 몇번째 인덱스에 있는 요소보다 크거나 같은지 계산하고, winCount에 저장한다. 즉, sumsB 요소가 현재 sumsA 요소보다 큰 횟수가 몇번인지 확인할 수 있다. ex) sumsA = [3, 4, 4, 5], sumsB = [7, 8, 8, 9] 일 때, sumsB에서 3보다 같거나 큰 첫번째 인덱스는 0이다. sumsB 요소가 3보다 모두 크다는 것을 알 수 있다.

4. winCount와 최다 우승 횟수(bestWin)를 비교하여 갱신하고, 최적의 조합을 answer 벡터에 저장한다.

5. 주사위 번호는 1번부터 시작하기 때문에 answer 벡터를 순회하며 값을 1씩 증가시킨다.

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> dice;

void dfs(int index, int sum, int size, vector<int>& sums, vector<int>& team)
{
    if(index == size)
    {
        sums.push_back(sum);
        return;
    }

    for(int face : dice[team[index]])
        dfs(index+1, sum+face, size, sums, team);
}

vector<int> getSums(vector<int>& team)
{
    vector<int> sums;
    dfs(0, 0, team.size(), sums, team);
    return sums;
}

vector<int> solution(vector<vector<int>> inDice) 
{
    dice = inDice;
    int diceCount = dice.size();

    long long bestWin = -1;
    vector<int> answer;

    vector<int> comb(diceCount, 0);
    fill(comb.begin(), comb.begin() + diceCount/2, 1);

    do
    {
        vector<int> teamA, teamB;
        for(int i=0; i<diceCount; i++)
        {
            if(comb[i] > 0)
                teamA.push_back(i);
            else
                teamB.push_back(i);
        }

        vector<int> sumsA = getSums(teamA);
        vector<int> sumsB = getSums(teamB);
        sort(sumsB.begin(), sumsB.end());

        long long winCount =0;
        for(int x : sumsA)
        {
            winCount += lower_bound(sumsB.begin(), sumsB.end(), x) - sumsB.begin();
        }

        if(winCount > bestWin)
        {
            bestWin = winCount;
            answer = teamA;
        }

    } while (prev_permutation(comb.begin(), comb.end()));

    for(int& i : answer)
        i++;

    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/150370

풀이와 주의점

풀이

1. '.' 기준으로 오늘 날짜 문자열을 나눠 벡터에 저장해준다. 1-1. 띄어쓰기 기준으로 문자열을 나눠 약관 종류를 key, 유효기간을 value로 map에 저장해준다. 1-2. 띄어쓰기 기준으로 문자열을 나눠 수집 일자 / 약관 종류를 나누고, 다시 수집 일자를 '.' 기준으로 나눠 벡터에 저장해준다.

2. 오늘 날짜, 약관 종류에 따른 유효기간, 수집 일자를 순차적으로 isDestroy에 넣어서 계산한다.

주의점

1. 모든 달은 28일이라고 가정한다.

코드

#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <algorithm>

using namespace std;

bool isDestroy(vector<int>& day, int term, vector<int>& today)
{
    day[0] += term/12;
    day[1] += term%12;

    if(day[1] > 12)
    {
        day[0] += day[1]/12;
        day[1] = day[1]%12;
    }

    if(day[2] > 1)
    {
        day[2] -=1;
    }
    else if(day[2] == 1)
    {
        day[1] -=1;
        day[2] = 28;
    }

    if(day[0] == today[0])
    {
        if(day[1] == today[1])
        {
            return day[2] >= today[2] ? false : true;
        }
        else
        {
            return day[1] > today[1] ? false : true;
        }
    }

    return day[0] > today[0] ? false : true;
}

vector<int> solution(string today, vector<string> terms, vector<string> privacies) 
{
    stringstream ss(today);
    string temp;
    vector<int> todayInt;
    while(getline(ss, temp, '.'))
    {
        todayInt.push_back(stoi(temp));
    }

    map<string, int> termsMap;
    for(int i=0; i<terms.size(); i++)
    {
        ss.str(terms[i]);
        ss.clear();
        string key;
        int value;
        ss >> key >> value;
        termsMap.insert({key, value});
    }

    vector<int> answer;
    for(int i=0; i<privacies.size(); i++)
    {
        ss.str(privacies[i]);
        ss.clear();
        string day;
        string key;
        ss >> day >> key;

        ss.str(day);
        ss.clear();
        vector<int> dayInt;
        while(getline(ss, temp, '.'))
        {
            dayInt.push_back(stoi(temp));
        }

        if(isDestroy(dayInt, termsMap[key], todayInt))
            answer.push_back(i+1);
    }

    return answer;
}

다른 풀이와 코드

1. 모든 날짜를 일자 기준으로 변환해서 손쉽게 계산한 코드

#include <algorithm>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

using namespace std;
vector<int> solution(string today, vector<string> terms, vector<string> privacies) 
{
    vector<int> answer;
    int year = stoi(today.substr(0, 4));
    int month = stoi(today.substr(5, 2));
    int days = stoi(today.substr(8));
    int todayD = (year)*12 * 28 + (month - 1) * 28 + days;

    vector<int> ar(privacies.size());
    map<char, int> mp;
    for (int i = 0; i < terms.size(); i++) 
    {
        stringstream ss(terms[i]);
        char c;
        int month;
        ss >> c >> month;
        mp[c] = month;
    }
    for (int i = 0; i < privacies.size(); i++) 
    {
        int y = stoi(privacies[i].substr(0, 4));
        int m = stoi(privacies[i].substr(5, 2));
        int d = stoi(privacies[i].substr(8, 2));
        char c = privacies[i].back();
        ar[i] = (y)*12 * 28 + (m - 1) * 28 + d + mp[c] * 28 - 1;
    }
    for (int i = 0; i < ar.size(); i++) 
    {
        if (ar[i] < todayD) 
        {
            answer.push_back(i + 1);
        }
    }
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/258711

풀이

1. 단방향 그래프는 이중벡터, 각 노드별로 나가는 간선 수 / 들어오는 간선 수는 벡터로 저장한다.

2. 나가는 간선 수가 2개(최소 그래프 개수) 이상이고, 들어오는 간선 수가 하나도 없다면 새로 생성된 노드이다.

3. 새로 생성된 노드에 연결된 노드는, 각 그래프에 포함된 노드이다. 3-1. 각 그래프에 포함된 노드와 간선 개수를 dfs로 구한다.

4. 노드와 간선 개수를 비교하여 각 그래프 카운트를 증가시킨다.

코드

#include <vector>
#include <algorithm>
using namespace std;

void dfs(int current, vector<vector<int>>& adj, vector<int>& visited, int& vertex, int& edge)
{
    visited[current] = true;

    vertex++;
    for(int next : adj[current])
    {
        edge++;
        if(!visited[next])
        {
            dfs(next, adj, visited, vertex, edge);
        }
    }
}

vector<int> solution(vector<vector<int>> edges) 
{   
    vector<int> answer(4, 0);

    int nodeCount = 0;
    for (auto& info : edges) 
        nodeCount = max(nodeCount, max(info[0], info[1]));

    vector<int> inDegree(nodeCount+1);
    vector<int> outDegree(nodeCount+1); 
    vector<vector<int>> adj(nodeCount+1);

    for (auto& info : edges) 
    {
        int from = info[0];
        int to   = info[1];

        adj[from].push_back(to);

        outDegree[from]++;
        inDegree[to]++;
    }

    int totalGraphs = 0;

    for (int i = 1; i <= nodeCount; i++) 
    {
        if (inDegree[i] == 0 && outDegree[i] >= 2) 
        {
            answer[0] = i;
            totalGraphs = outDegree[i];
            break;
        }
    }

    vector<int> visited(nodeCount+1, false);
    for (int current : adj[answer[0]]) 
    {
        int vertex =0;
        int edge =0;

        dfs(current, adj, visited, vertex, edge);

        if (vertex == edge) 
            answer[1]++; 
        else if (vertex - 1 == edge) 
            answer[2]++; 
        else
            answer[3]++;
    }

    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/258712

풀이

1. map<string, int>로 사람 이름별 인덱스를 저장한다.

2. 이중벡터 giftCount를 만들어 giftCount[i][j] = i가 j에게 준 선물 갯수 를 저장한다.

3. 벡터 giftDiff를 만들어 선물 지수를 저장한다.

4. giftCount를 순회하며 i가 j에게 준 선물 개수와 j가 i에게 준 선물 개수를 비교하고, 더 큰 쪽의 다음달 선물 개수를 증가시킨다. 4-1. 만약 주고받은 선물이 없거나, 개수가 같을 경우 선물 지수를 비교하여 더 큰 쪽의 다음달 선물 개수를 증가시킨다.

5. 다음달 선물 개수 벡터를 순회하며 가장 큰 값을 반환한다.

코드

#include <string>
#include <vector> 
#include <map> 
#include <sstream>

using namespace std;

int solution(vector<string> friends, vector<string> gifts) 
{
    map<string, int> stringToIndex;
    for(int i=0; i<friends.size(); i++)
    {
        stringToIndex.insert({friends[i], i});
    }

    vector<vector<int>> giftCount(friends.size(), vector<int>(friends.size(), 0)); 
    vector<int> giftDiff(friends.size(), 0);
    for (string s : gifts)
    {
        stringstream ss(s);
        string giver, receiver;
        ss >> giver >> receiver;

        giftCount[stringToIndex[giver]][stringToIndex[receiver]]++;

        giftDiff[stringToIndex[giver]]++;
        giftDiff[stringToIndex[receiver]]--;
    }

    vector<int> nextMonth(friends.size(), 0);
    for (int i=0; i<giftCount.size() - 1; i++)
    {
        for(int j=i+1; j<giftCount[0].size(); j++)
        {
            if (giftCount[i][j] > giftCount[j][i])
            {
                nextMonth[i]++;
            }
            else if(giftCount[i][j] < giftCount[j][i])
            {
                nextMonth[j]++;
            }
            else
            {
                if(giftDiff[i] > giftDiff[j])
                    nextMonth[i]++;
                else if(giftDiff[i] < giftDiff[j])
                    nextMonth[j]++;
            }
        }
    }

    int result =0;
    for(int i : nextMonth)
    {
        result = max(result, i);
    }

    return result;
}

다른 풀이와 코드

0. 서로에게 준 선물 개수 벡터 순회를 깔끔하게 한 것 같아서 참고

#include <string>
#include <vector>
#include <map>
#include <sstream>

using namespace std;

int solution(vector<string> friends, vector<string> gifts) {

    vector<int> point(friends.size(), 0);
    vector<vector<int>> count(friends.size(), vector<int>(friends.size(), 0));
    map<string, int> m;

    for(int i=0;i< friends.size(); i++) 
        m.insert({friends[i], i});

    for(int i = 0; i < gifts.size(); i++) {
        string from, to;
        stringstream parse(gifts[i]);
        parse >> from >> to;

        int fromIdx = m[from], toIdx = m[to];
        count[fromIdx][toIdx]++;

        point[fromIdx]++;
        point[toIdx]--;
    }

    int ans = 0;

    for(int i = 0; i < friends.size(); i++) {
        int res = 0;

        for(int j = 0; j < friends.size(); j++) {
            if(i == j || count[i][j] < count[j][i]) continue;

            if(count[i][j] > count[j][i]) res++;
            else {
                if(point[i] > point[j]) res++;
            }
        }

        ans = max(res, ans);
    }

    return ans;
}

https://school.programmers.co.kr/learn/courses/30/lessons/49189?language=cpp

풀이

1. 간선 정보를 포함한 무방향 그래프를 이중 벡터로 구현한다. 이때, 노드 번호가 1부터 시작이므로 1씩 빼준다. 1-1. 오름차순으로 노드를 탐색할 수 있도록 정렬해준다.

2. 시작점(0번 노드)를 큐에 넣고, bfs를 수행한다. 2-1. 거리를 저장할 벡터(distance)를 만들어서, -1로 초기화를 해준다. 2-2. 만약 다음 노드의 거리가 -1이라면 아직 방문하지 않은 것이기에, 현재 거리 + 1로 설정해준다. 2-3. 큐가 빌 때까지 반복

3. algorithm 헤더의 max_element로 distance 요소 중 가장 큰 값을 구한다. 3-1. distance 벡터를 순회하며, 최대 거리와 같은 요소가 있다면 반환할 노드 수를 증가시킨다.

코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int>> edge) 
{
    vector<vector<int>> adj(n);
    for(int i=0; i<edge.size(); i++)
    {
        int from = edge[i][0];
        int to = edge[i][1];

        --from;
        --to;

        adj[from].push_back(to);
        adj[to].push_back(from);
    }

    for(int i=0; i<adj.size(); i++)
    {
        sort(adj[i].begin(), adj[i].end());
    }

    vector<int> distance(n, -1);

    queue<int> bfs;
    bfs.push(0);
    distance[0] = 0;

    while(!bfs.empty())
    {
        int current = bfs.front();
        bfs.pop();

        for(int next : adj[current])
        {
            if(distance[next] != -1)
                continue;

            distance[next] = distance[current] + 1;
            bfs.push(next);
        }
    }

    int answer = 0;
    int maxDistance = *max_element(distance.begin(), distance.end());

    for(int i =0; i<distance.size(); i++)
    {
        if(distance[i] == maxDistance)
            answer++;
    }

    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/42840

풀이

풀이

1. 찍는 패턴 순서대로 벡터 만들어두고, index % 각 벡터 size를 인덱스로 하여 answers 값과 비교한다. 1-1. answers 값과 비교하여 scores 벡터 업데이트

2. scores 중 최댓값 도출

3. 최대 score과 동일하다면, 현재 index + 1 수포자가 가장 높은 점수를 획득했다는 뜻이기에 answer 벡터에 index + 1 넣어준다.

주의점

1. 찍는 패턴 벡터 초기화를 잘못 해서 정확성 검사 통과를 못했다.. 문제 확인을 꼼꼼히 하도록 하자...

코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> answers) 
{
    vector<int> first = { 1, 2, 3, 4, 5 };
    vector<int> second = { 2, 1, 2, 3, 2, 4, 2, 5 };
    vector<int> third = { 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 };

    vector<int> scores(3, 0);
    for (int i=0; i<answers.size(); i++)
    {
        if(answers[i] == first[i % first.size()])
            scores[0]++;

        if(answers[i] == second[i % second.size()])
            scores[1]++;

        if(answers[i] == third[i % third.size()])
            scores[2]++;
    }

    int maxScore =0;
    for(int i=0; i<scores.size(); i++)
    {
        if(maxScore < scores[i])
            maxScore = scores[i];
    }

    vector<int> answer;
    for(int i=0; i<scores.size(); i++)
    {
        if(maxScore == scores[i])
            answer.push_back(i + 1);
    }

    return answer;
}

다른 풀이와 코드

0. max score를 구할 때, std::max_element를 활용하였다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> one = {1,2,3,4,5};
vector<int> two = {2,1,2,3,2,4,2,5};
vector<int> thr = {3,3,1,1,2,2,4,4,5,5};

vector<int> solution(vector<int> answers) 
{
    vector<int> answer;
    vector<int> they(3);
    for(int i=0; i<answers.size(); i++) 
    {
        if(answers[i] == one[i%one.size()]) they[0]++;
        if(answers[i] == two[i%two.size()]) they[1]++;
        if(answers[i] == thr[i%thr.size()]) they[2]++;
    }
    int they_max = *max_element(they.begin(),they.end());
    for(int i = 0; i< 3; i++) 
    {
        if(they[i] == they_max) answer.push_back(i+1);
    }
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/86491

풀이

1. 가로와 세로 길이를 비교하며 더 큰 수를 가로로 swap

2. 가로 길이 중 제일 큰 수, 세로 길이 중 제일 큰 수 도출 후 곱하여 return

코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> sizes) 
{
    int maxWidth = 0, maxHeight = 0;

    for (int i=0; i<sizes.size(); i++)
    {
        auto info = sizes[i];

        if (info[0] < info[1])
            swap(info[0], info[1]);

        if (maxWidth < info[0])
            maxWidth = info[0];

        if (maxHeight < info[1])
            maxHeight = info[1];
    }

    return maxWidth * maxHeight;
}

다른 풀이와 코드

0. swap을 사용하지 않고 푼 코드

1. 가로 길이 : 짧은 길이 중에 가장 긴 길이 / 세로 길이 : 긴 길이 중에 가장 긴 길이

2. 1에서 구한 가로 * 세로 곱하여 return

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<vector<int>> sizes)
{
    int answer=0;

    int w=0, h=0;
    for(int i=0; i<sizes.size(); i++)
    {
        w=max(w,min(sizes[i][0],sizes[i][1]));
        h=max(h,max(sizes[i][0],sizes[i][1]));
    }
    answer=w*h;

    return answer;
}

https://www.hackerrank.com/challenges/torque-and-development/problem?isFullScreen=true

1. 도시 개수(n), 도서관 건설비용(c_lib), 도로 건설비용(c_road), 건설 가능 도로 정보(cities)가 매개변수로 주어진다.

2. 최소 건설비용을 들여 모든 도시에서 도서관에 접근할 수 있어야 한다. 이때, 최소 건설 비용을 반환하는 함수를 작성하라.

풀이와 주의점

풀이

1. 도로 건설비용이 도서관 건설비용과 같거나, 더 클 경우 각 도시에 도서관을 짓는게 더 적은 비용이 들기 때문에 도시 수 * 도서관 건설비용을 반환한다.

2. 이중벡터로 무방향 그래프를 만들고, 간선 정보를 포함시켜 준다.

3. bfs로 그래프를 순회하며 이어져있는 노드 수를 구한다.

4. bfs가 끝났다면, 해당 노드로부터 이어진 모든 노드를 탐색했다는 뜻이기에 이어진 한 덩어리 개수가 구해진다. => 해당 덩어리에 도서관을 1개 짓고, node - 1 개수만큼 도로를 짓는 비용을 totalCount에 더해준다.

5. 만약 방문하지 않은 노드라면, 3, 4번을 반복한다.

주의점

1. 잘못된 index 접근 => 1부터 n까지 노드 번호가 입력되는데, 이를 간과해서 에러가 발생했다. 따라서 from과 to를 인접 리스트에 포함시키기 전, 전위 증감 연산자로 1씩 감소시켜서 해결하였다.

2. 명확한 자료형 => 히든 케이스에서 자꾸 틀려서 코드를 다시 확인하다가, 도시 수 * 도서관 건설비용을 반환할 때 long으로 형변환을 해주지 않았다는 걸 발견했다. totalCost 계산할 때도 마찬가지로 형변환을 해주어야 한다.

코드

long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) 
{ 
    if (c_lib <= c_road)
    {
        return (long)n * c_lib;
    }

    vector<vector<int>> adj(n);
    for(int i=0; i<cities.size(); i++)
    {
        int from = cities[i][0];
        int to = cities[i][1];

        --from;
        --to;

        adj[from].push_back(to);
        adj[to].push_back(from);
    }

    long totalCost = 0;

    vector<bool> visited(n, false);

    for (int i = 0; i<n; i++)
    {
        if (visited[i])
            continue;

        queue<int> bfs;
        bfs.push(i);
        visited[i] = true;

        long nodeCount = 1;

        while(!bfs.empty())
        {
            int current = bfs.front();
            bfs.pop();

            for(int next : adj[current])
            {
                if(visited[next])
                    continue;

                visited[next] = true;
                nodeCount++;
                bfs.push(next);
            }
        }

        totalCost += (long)c_lib + (long)c_road * (nodeCount - 1);
    }

    return totalCost;
}

https://school.programmers.co.kr/learn/courses/30/lessons/43163

풀이

1. source 문자열과 target 문자열을 비교한다고 가정하자. 1개의 문자 빼고 모두 같으며 한번도 확인하지 않은 문자열이라면 source 문자열은 target 문자열로 변환될 수 있다. 1-1. 문자열을 비교할 수 있는 canChange 함수를 만든다.

2. 해당 과정을 words 벡터를 순회하며 반복하고, 만약 현재 문자열이 최종 문자열과 같다면 변환 횟수를 반환한다. 2-1. 이때, bfs용 큐에는 현재 문자열과 변환 횟수를 담을 수 있도록 pair<string, int>를 자료형으로 사용한다.

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

bool canChange(const string& source, const string& target)
{
    int diff = 0;
    for(int i=0; i<source.size(); i++)
    {
        if(source[i] != target[i])
            diff++;
        if(diff > 1)
            return false;
    }

    return diff == 1;
}

int solution(string begin, string target, vector<string> words) 
{    
    vector<bool> visited(words.size(), false);

    queue<pair<string, int>> bfs;
    bfs.push({begin, 0});

    while(!bfs.empty())
    {
        string currentString = bfs.front().first;
        int currentLength = bfs.front().second;
        bfs.pop();

        if (currentString == target)
            return currentLength;

        for (int i=0; i<words.size(); i++)
        {
            if (!canChange(currentString, words[i]) || visited[i])
                continue;

            visited[i] = true;
            bfs.push({words[i], currentLength + 1});
        }
    }

    return 0;
}

https://school.programmers.co.kr/learn/courses/30/lessons/1844

풀이

1. bfs로 상하좌우 위치 탐색하며 방문 체크 및 distance 증가하는 방식으로 코드 짬 => 도착지로부터 멀어지는 경우의 수에도 distance가 증가하여 최단 거리 도출 실패

2. tuple로 현재 칸까지의 최단 거리를 저장해서 해결

코드

#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int solution(vector<vector<int>> maps)
{
    int col = maps.size();
    int row = maps[0].size();

    queue<tuple<int, int, int>> bfs;
    vector<vector<bool>> visited(col, vector<bool>(row, false));

    bfs.push({ 0, 0, 1 });
    visited[0][0] = true;

    vector<int> dirX = { 1, 0, -1, 0 };
    vector<int> dirY = { 0, 1, 0, -1 };

    while (!bfs.empty())
    {
        tuple<int, int, int> current = bfs.front();
        int currentX = get<0>(current);
        int currentY = get<1>(current);
        int currentDistance = get<2>(current);

        bfs.pop();

        if (currentX == (row - 1) && currentY == (col - 1))
            return currentDistance;

        for (int i = 0; i < dirX.size(); i++)
        {
            int nextX = currentX + dirX[i];
            int nextY = currentY + dirY[i];

            if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col)
                continue;

            if (maps[nextY][nextX] == 0 || visited[nextY][nextX])
                continue;

            visited[nextY][nextX] = true;
            bfs.push({ nextX, nextY, currentDistance + 1 });
        }
    }

    return -1;
}

다른 풀이와 코드

0. tuple을 사용하지 않은 코드

1. map에 현재까지 최단거리를 기록하면 됨

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

using namespace std;

int check[101][101];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int solution(vector<vector<int> > maps)
{
    int n, m;
    n = maps.size();
    m = maps[0].size();
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    check[0][0] = true;

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0<=nx && nx<n && 0<=ny && ny<m)
            {
                if(check[nx][ny] == false && maps[nx][ny] > 0)
                {
                    check[nx][ny] = true;
                    maps[nx][ny] = maps[x][y] + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }

    int answer = 0;
    if(maps[n-1][m-1] == 1)
    {
        answer = -1;
    }
    else
    {
        answer = maps[n-1][m-1];
    }
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/43162

풀이

1. 노드의 개수 n, 간선 정보 computers 벡터가 주어졌을 때 간선으로 이어진 덩어리의 개수를 세는 문제이다. => bfs로 풀이

2. 이중벡터로 간선 정보를 포함한 인접 리스트를 만든다.

3. 인접 리스트를 순회하며 방문하지 않은 노드를 bfs 큐에 넣어주고, 방문 표시를 해준다. 3-1. bfs 큐가 빌 때(간선으로 이어진 모든 노드를 탐색할 때)까지 간선으로 이어진 다음 노드를 탐색하고, 3을 수행한다. 3-2. bfs 큐가 비었다면, 한 덩어리를 모두 탐색했다는 뜻이기에 개수를 증가시킨다.

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> computers) 
{
    vector<vector<int>> adj(n);
    for (int i=0; i<computers.size(); i++)
    {
        for(int j =0; j<computers[i].size(); j++)
        {
            if(i == j || computers[i][j] == 0)
                continue;

            adj[i].push_back(j);
        }
    }

    queue<int> bfs;
    vector<bool> visited(n, false);

    int answer = 0;

    for(int i=0; i<adj.size(); i++)
    {
        if (visited[i])
            continue;

        bfs.push(i);
        visited[i] = true;

        while (!bfs.empty())
        {
            int current = bfs.front();
            bfs.pop();

            for (int next : adj[current])
            {
                if (visited[next])
                    continue;

                visited[next] = true;
                bfs.push(next);
            }
        }

        answer++;
    }

    return answer;
}

다른 풀이와 코드

0. dfs를 사용한 코드

1. bfs보다 코드가 짧아서 가독성이 좋다. 다만 개인적으로 재귀함수 사용이 미숙해서 dfs는 꺼리게 되는듯..

#include <string>
#include <vector>

using namespace std;

void DFS(int from, int n, vector<int> &visited, vector<vector<int>> &computers) 
{
    for (int i = 0; i < n; i++) 
    {
        if (from != i && computers[from][i] == 1 && visited[i] == 0) 
        {
            visited[i] = 1;
            DFS(i, n, visited, computers);
        }
    }
}

int solution(int n, vector<vector<int>> computers) 
{
    int network = 0;
    vector<int> visited(n, 0);

    for (int i = 0; i <n; i++) 
    {
        if (visited[i] == 1) 
        {
            continue;
        }

        // visit node and start DFS
        network++;
        visited[i] = 1;

        DFS(i, n, visited, computers);
    }

    return network;
}

https://school.programmers.co.kr/learn/courses/30/lessons/43165

풀이

1. 깊이 우선 탐색을 통해 각 원소에 + 또는 -를 붙였을 때의 합을 구한다. => 합이 target과 같다면, 1을 반환한다.

2. 재귀함수를 사용해서 현재 index, 현재까지의 합 sum을 인자로 전달해준다. 2-1. 종료 조건 : 만약 index가 numbers의 크기와 같다면 dfs로 하나의 경우를 모두 탐색했다는 뜻이기에 sum과 target을 비교한다. 2-2. 다음 단계 : sum에서 numbers[index] 값을 더하거나 빼는 dfs를 각각 수행해 반환 값을 더해준다.

코드

#include <iostream>
#include <vector>
using namespace std;

int dfs(vector<int>& numbers, int target, int index, int sum)
{
    if (index == numbers.size())
    {
        if (sum == target)
        {
            return 1;
        }

        return 0;
    }

    return dfs(numbers, target, index + 1, sum+numbers[index]) + dfs(numbers, target, index+1, sum-numbers[index]);
}

int solution(vector<int> numbers, int target)
{
    return dfs(numbers, target, 0, 0);
}

https://school.programmers.co.kr/learn/courses/30/lessons/42586

풀이

1. 선입선출 구조의 큐를 사용해서 각 기능마다 완성까지 남은 날짜를 push한다.

2. 큐의 front를 최소 날짜로 잡고, 반환할 벡터(answer)에 1을 넣어준 뒤 pop한다. 2-1. 큐의 top이 최소 날짜보다 크다면, 최소 날짜를 top으로 변경하고, 반환할 벡터에 1을 넣어준 뒤 pop한다. 2-2. 아니라면, 우선순위가 후순위기 때문에 현재 최소 날짜에 배포된다. 따라서 answer의 마지막 원소에 1을 증가시키고, pop한다.

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds)
{
    queue<int> days;

    for (int i=0; i<progresses.size(); i++)
    {
        int day = 0;
        int diff = 100 - progresses[i];
        while (diff > speeds[i] * day)
        {
            day++;
        }

        days.push(day);
    }

    vector<int> answer;

    int minDay = days.front();
    answer.push_back(1);
    days.pop();

    while(!days.empty())
    {
        if (minDay < days.front())
        {
            minDay = days.front();
            answer.push_back(1);
            days.pop();
        }
        else
        {
            answer[answer.size() - 1]++;
            days.pop();
        }
    }

    return answer;
}

다른 풀이와 코드

0. 나눗셈 올림(나머지가 있다면, 무조건 올린다)을 사용해서 최적화한 코드이다.

1. $\lceil \frac{A}{B} \rceil = \frac{A + B - 1}{B}$ (나눗셈 올림) 을 사용하여 각 기능마다 필요한 날짜 수를 구한다.

2. 반환할 벡터(answer)가 비어있거나, 필요한 날짜 수가 이전 기능 개발에 필요한 날짜 수보다 크다면 => 이전 기능 배포 후에 배포할 수 있다는 뜻이기에 answer에 1을 넣어준다.

3. 아니라면, 이전 기능에 필요한 날짜 수보다 작거나 같다는 뜻이기에 answer의 back을 증가시킨다.

4. 최대 날짜보다 현재 날짜가 더 클 경우, 최대 날짜를 갱신한다.

#include <string>
#include <vector>
using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) 
{
    vector<int> answer;

    int day;
    int max_day = 0;
    for (int i = 0; i < progresses.size(); ++i)
    {
        day = (99 - progresses[i]) / speeds[i] + 1;

        if (answer.empty() || max_day < day)
            answer.push_back(1);
        else
            ++answer.back();

        if (max_day < day)
            max_day = day;
    }

    return answer;
}

+) cmath 헤더를 추가하여 ceil 함수로 나눗셈 올림을 할 수 있다.

#include <string>
#include <vector>
#include <cmath>
using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) 
{
    vector<int> answer;

    int day;
    int max_day = 0;
    for (int i = 0; i < progresses.size(); ++i)
    {
        int remain = 100 - progresses[i];
        day = static_cast<int>(ceil(remain / (double)speeds[i]));

        if (answer.empty() || max_day < day)
            answer.push_back(1);
        else
            ++answer.back();

        if (max_day < day)
            max_day = day;
    }

    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/12909

풀이

1. 여는 괄호 '('를 스택에 넣는다.

2. 닫는 괄호 ')'가 나온다면, 스택의 top에 여는 괄호가 있는지 검사한다. 2-1. top이 여는 괄호라면, 쌍이므로 pop 2-2. 여는 괄호가 아니라면, 닫는 괄호가 중복되었으므로 false를 반환

2-3. 스택이 비었다면 모두 쌍이 있다는 의미이기에 true 반환, 반대의 경우 false 반환

코드

#include <string>
#include <iostream>
#include <stack>

using namespace std;

bool solution(string question)
{
    stack<char> st;
    for (char c : question)
    {
        if (c == '(')
        {
            st.push(c);
        }
        else if (c == ')')
        {
            if (st.empty())
            {
                return false;
            }
            else if (st.top() == '(')
            {
                st.pop();
            }
        }
    }

    if(st.empty())
    {
        return true;
    }
    else
    {
        return false;
    }
}

다른 풀이와 코드

0. 스택을 사용하지 않고, 여는 괄호와 닫는 괄호의 개수만으로 풀이한 코드이다.

1. 변수가 음수라면, 현재까지 문자열에 여는 괄호 없이 닫는 괄호만 있다는 뜻이기에 false를 반환한다. 1-1. 아니라면, 문자열에 여는 괄호가 포함되어 있을 때 변수를 증가시키고, 닫는 괄호가 포함되어 있을 때 변수를 감소시킨다.

2. n이 0과 같은지 판단하는 조건식을 반환한다.

#include<string>
#include <iostream>

using namespace std;

bool solution(string s)
{
    int n = 0;
    for (int i = 0; i < s.length(); i++) 
    {
        if (n < 0)
            return false;

        if (s[i] == '(')
            n++;

        else if (s[i] == ')')
            n--;
    }
    return n == 0;
}

struct compareString 
{ 
    bool operator()(string a, string b) const {return a+b > b+a;} 
}; 

string solution(vector<int> numbers) 
{ 
    ...

    sort(numbers_string.begin(), numbers_string.end(), compareString); 

    ...
}

코테 풀이 중 algorithm 헤더의 sort 함수에 커스텀한 compare 인자를 넣으려고 했는데, 아래와 같은 오류가 발생했다.

/solution0.cpp:22:56: error: 'compareString' does not refer to a value
    sort(numbers_string.begin(), numbers_string.end(), compareString);
                                                       ^
/solution0.cpp:7:8: note: declared here
struct compareString 
       ^
1 error generated.

오류를 직역하자면, 'compareString'은 값을 참조하지 않는다는 뜻이다.

위 코드에서 compareString은 구조체의 이름이지, 객체가 아니다.

하지만 compare 인자는 class이기 때문에 객체를 넣어주어야 한다. => 즉, 구조체든 함수든 객체를 생성하여 넣어주어야 한다.

문제 해결

[1] functor 임시 객체 생성

struct compareString 
{ 
    bool operator()(string a, string b) const {return a+b > b+a;} 
}; 

string solution(vector<int> numbers) 
{ 
    ...

    sort(numbers_string.begin(), numbers_string.end(), compareString()); 

    ...
}

기본 생성자로 임시 객체를 생성하여 인자로 넣어준다. 이때, compareString 구조체는 함수처럼 동작하는 객체이기에 functor이다.

[2] 익명 구조체 생성

struct  
{ 
    bool operator()(string a, string b) const {return a+b > b+a;} 
}compareString; 

string solution(vector<int> numbers) 
{ 
    ...

    sort(numbers_string.begin(), numbers_string.end(), compareString); 

    ...
}

익명 구조체 정의와 객체 생성을 동시에 한 뒤, 이를 인자로 전달한다.

[3] 람다 사용

string solution(vector<int> numbers) 
{ 
    ...

    sort(numbers_string.begin(), numbers_string.end(), 
    [](const string& a, const string& b){ return a+b > b+a; }; 

    ...
}

익명 함수 객체인 람다를 사용하여 바로 compare 인자로 전달한다.

functor vs 람다

람다가 훨씬 가독성이 좋은데, 왜 굳이 functor을 써야할까? 의문이 들었다. 게다가 std::function도 있는데, 왜 functor 라는게 있는가 싶어서 짱피티한테 물었더니 아래와 같이 대답해주더이다.

functor

• 재사용 가능 : 동일한 비교 로직을 여러 곳에서 쓰거나, 여러 알고리즘에 적용할 때 유용함
• 상태 저장 가능 : 람다도 캡처로 가능하지만, 구조체처럼 멤버 변수로 관리하면 명시적이라 편리함
• 템플릿 인자로 전달 가능 : functor는 타입 자체를 전달할 수 있음

람다

• 가독성 좋음
• 일회성임
• C++11 이후부터 사용 가능 (std::function도 마찬가지)

https://school.programmers.co.kr/learn/courses/30/lessons/42746

풀이

1. algorithm 헤더의 sort 함수에 compare 인자를 커스텀해서 넣어준다. 1-1. 문자열끼리 더해서 더 큰 문자열이 앞에 오도록 정렬해준다. 이때, compare 인자는 객체를 생성해서 전달해주어야 한다. 1-2. 아래 코드의 경우, 익명 구조체를 생성한 뒤 () 연산자로 함수 객체를 생성하여 compare 인자에 넣는 방식을 사용하였다.

2. 1에서 정렬한 뒤, 더 큰 문자열이 앞에 있기 때문에 순서대로 string에 이어붙인다.

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct 
{
    bool operator()(string a, string b) const {return a+b > b+a;}
} 
compareString;


string solution(vector<int> numbers) 
{
    vector<string> numbers_string;
    for(int i : numbers)
    {
        string newNumber = to_string(i);
        numbers_string.push_back(newNumber);
    }

    sort(numbers_string.begin(), numbers_string.end(), compareString);

    if(numbers_string[0] == "0")
    {
        return "0";
    }

    string answer;
    for(string s : numbers_string)
    {
        answer += s;
    }

    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/42748

풀이

1. 일정 범위 내의 부분 배열을 저장하기 위해 새 벡터를 만들어 push_back 하고, 이를 algorithm 헤더의 sort 함수를 사용해서 정렬하니까 시간 초과 문제가 발생하였음

2. 루트가 최대인 우선순위 큐 사용하여 O(logN)의 시간에 정렬되도록 하여서 해결함

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) 
{
    vector<int> answer;

    for (int i=0; i<commands.size(); i++)
    {
        int start = commands[i][0];
        int end = commands[i][1];
        int size = commands[i][2];

        --start;
        --end;

        priority_queue<int, vector<int>, greater<int>> sub;
        for(int j=start; j<=end; j++)
        {
            sub.push(array[j]);
        }

        while(size > 1)
        {
            sub.pop();
            --size;
        }

        answer.push_back(sub.top());
    }

    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/42577

풀이

1. 원소 탐색 시 O(1)의 시간이 걸리는 unordered_set을 사용한다. phone_number의 값을 모두 set에 넣어준다.

2. phone_number vector를 순회하며 substr 함수로 부분문자열을 추출한다. 2-1. 부분 문자열을 set에서 찾았다면 접두어 문자열이 존재한다는 뜻이기에 false를 반환한다.

코드

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

bool solution(vector<string> phone_book) 
{  
    unordered_set<string> numbers(phone_book.begin(), phone_book.end());

    for (string number : phone_book)
    {
        for (int i = 1; i < number.size(); i++)
        {
            string subNumber = number.substr(0, i);

            if (numbers.find(subNumber) != numbers.end())
            {
                return false;
            }
        }
    }

    return true;
}

다른 풀이와 코드

0. 해시를 사용하지 않고, 정렬만으로 풀이한 다른 사람의 풀이이다.

1. algorithm 헤더의 sort 함수로 phone_book 벡터를 정렬한다.

2. phone_book 벡터를 순회하며 다음 원소의 부분 문자열과 현재 원소가 같다면 false를 반환한다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool solution(vector<string> phoneBook) 
{
    bool answer = true;

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

    for ( int i = 0 ; i < phoneBook.size() - 1 ; i++ )
    {
        if ( phoneBook[i] == phoneBook[i+1].substr(0, phoneBook[i].size()) )
        {
            answer = false;
            break;
        }
    }

    return answer;
}