급하게임개발

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

이 문제는 프로그래머스 알고리즘 고득점 Kit의 문제이다 
Programmers LV3 문제 치고는 접근 법이 매우 쉬웠다 이 문제의 경우

이렇게 생긴 벡터가 제공이 된다 

실제 자료형은 이렇게 제공이 되는데
이 문제는 똑같은 삼각형을 만들고 나의 이전 행에 있는 나를 기준으로 양대각선의 있는 값중 나와의 합이 최대가 되는 애와의 합을 내가 현재 있는 위치에 넣는 것이다

즉 이그림을 보면 3번 째줄에 와서 보면 1을 기준으로 내가 선택할 수 있는 것은 이전행의 10과 15이다 이중 두값중 1과 합했을때 큰값을 16임으로 나의 위치에 16을 넣어준다 이를 계속 반복 해주면 된다

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

int solution(vector<vector<int>> triangle) {
    vector<vector<int>> dpV;
    vector<int> rowV1;
    dpV.push_back(rowV1);
    dpV[0].push_back(triangle[0][0]);
    for(int i=1; i<triangle.size(); i++){
        vector<int> rowV;
        dpV.push_back(rowV);
        
        for(int j=0; j<triangle[i].size(); j++){
            if(j==0){
                dpV[i].push_back(dpV[i-1][j]+triangle[i][j]);
            }
            else if(j==triangle[i].size()-1){
                dpV[i].push_back(dpV[i-1][j-1]+triangle[i][j]);
            }
            else{
                dpV[i].push_back(max(triangle[i][j]+dpV[i-1][j-1],triangle[i][j]+dpV[i-1][j]));
            }
        }
    }
    int answer = 0;
    for(int i=0; i<dpV[triangle.size()-1].size(); i++){
        answer=max(answer,dpV[triangle.size()-1][i]);
    }
    return answer;
}

위에 코드를 보게 되면 똑같은 이차원 벡터를 만들어 주고 해당 벡터를 dp 로 놓고 이전 행과의 합을 계속 누적 하고 마지막행에서 최댓값을 구하는 방법으로 코드를 구현 했다

이 문제의 경우 프로그래머스 에서 dfs, bfs로 분류를 해놓았다 하지만 문제를 보았을 때 해당 방식으로 푸는것 보다는 그래프 이론중 유니온 파인드를 통해서 푸는게 더 맞는 방식으로 생각되어 해당 방식으로 풀이를 진행 하였다

#include <string>
#include <vector>
#include <set>
#include <iostream>
using namespace std;
int parent[200];

int GetParent(int x) {
    if (parent[x] == x)
        return parent[x];
    else {
        parent[x] = GetParent(parent[x]);
        return parent[x];
    }
}

bool IsSameParent(int x, int y) {
    if (GetParent(x) != GetParent(y)) {
        return false;
    }
    else
        return true;
}

void MakeSameParent(int x, int y) {
    if (!IsSameParent(x, y)) {
        parent[GetParent(y)] = GetParent(x);
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    set<int> s;
    for (int i = 0; i < n ; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(computers[i][j]==1)
                MakeSameParent(i, j);
        }
    }

    for (int i = 0; i < n ; i++) {
        s.insert(GetParent(parent[i]));
    }

    answer = s.size();
    return answer;
}

int main() {
    vector<vector<int>> computers = { {1,1,1},{1,1,0},{1,0,1} };
    int n = 3;

    cout<<solution(3, computers);
}

이 문제는 프로그래머스의 분류 실수이다 처음에는 그리디 문제로 계획을 했겠지만 후에 테스트케이스를 추가하면서 완전 탐색으로 풀게 변경되었다. 문제의 알고리즘이 변경되면 분류도 변경되어야 하지만 해당부분이 변경되지 않아 푸는데 많은시간을 소비하게 됬다

그리디로 풀었을 때의 코드는

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
bool isVisited[20] = { 0, };
int nextIdx(int idx) {
    if (idx + 1 == n) {
        return 0;
    }
    else
        return idx + 1;
}
int beforeIdx(int idx) {
    if (idx - 1 == -1) {
        return n - 1;
    }
    else {
        return idx - 1;
    }
}
int solution(string name) {
    int idx = 0;
    int beforeDif = 1;
    string alphaAs = "";
    int nIdx;
    int bIdx;
    n = name.size();
    for (int i = 0; i < n; i++) {
        alphaAs += 'A';
    }
    int answer = 0;
    while (name.compare(alphaAs) != 0) {
        isVisited[idx] = true;
        answer += min(name[idx] - 'A', 'Z' - name[idx] + 1);
        name[idx] = 'A';
        int left_idx = idx;
        int right_idx = idx;
        int leftCnt = 0;
        int rightCnt = 0;
        while (name[left_idx] == 'A' && leftCnt<n) {
            if (name.compare(alphaAs) == 0) {
                return answer;
            }
            left_idx = beforeIdx(left_idx);
            leftCnt++;
        }
        while (name[right_idx] == 'A' && rightCnt<n) {
            if (name.compare(alphaAs) == 0) {
                return answer;
            }
            right_idx = nextIdx(right_idx);
            rightCnt++;
        }
        if (leftCnt < rightCnt) {
            answer += leftCnt;
            idx = left_idx;
        }
        else {
            answer += rightCnt;
            idx = right_idx;
        }

    }
    return answer;
}

이렇게 되지만 해당 부분이 정답이 아니었다.
이에 프로그래머스 커뮤니티를 찾아보니 그리디로 풀리지 않는다고 나왔다.
이 문제는 어떻게 보면 투포인터 혹은 탐색문제의 가깝다

이 문제의 알파벳 탐색 방향은 총 4가지다

1. 오른쪽으로 쭉 탐색하기
2. 왼쪽으로 쭉 탐색하기
3. 왼쪽으로 갔다가 오른쪽으로 가기
4. 오른쪽으로 갔다가 왼쪽으로 가기
즉 1번어떠한 지점까지 갔다가 다시되돌아오면서 탐색하는  거 까지가 이 문제의 진행 방향이다
여러번되면 최소인 1번과 2번의 횟수보다 많아지기에 해당 로직은 검사하지 않는다

예시로 JAZAAAP 라는 문자가 있다고 생각하자

일단 우리는 방향을 바꿀 지점이 필요하고 방향을 바꾸고 어디까지 탐색할지에 대한 지점이 필요하다

자 이 문제를 우리가 해결하기 위해서는 처음 받은 문자열에서 가장 긴 문자열을 탐색 하지 않아야 한다 이에 
우리가 이문제를 풀기 위해서는
가장 긴 AAA가 나오는 부분을 건너지 말아야하므로 해당 영역의 시작점 X와 Y를 구해야한다

해당 예시에서 구해지면 이렇게 된다.
즉 이렇게 우리가 구간을 나눴을 때 우리는 
방향을 바꿔서 원점에서 -> y -> x 와 원점에서 ->x->y 에서의 최솟값을 구해야 한다.

원점에서 왼쪽으로 y를 탐색하고 x를 탐색하는 것의 식은
(n-y)+(n-y)+x 이고
원점에서 오른쪽으로 x를 탐색하고 y를 탐색하는 것의 식은
x+x+(n-y)이다

이에 우리는 특정 x를 기준으로 가장 긴 A가 만들어지는 Y를 찾으면 되는 문제이다 그후 두영역에서 방향을 바꾼다고 가정할 때의 최솟값이 커서의 이동의 최소 횟수 임으로 해당 횟수 + 문자를 A로 바꾸는횟수를 더해주면 된다

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int solution(string name) {
    int upDownMove[26] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,12,11,10,9,8,7,6,5,4,3,2,1 };
    int ans = 0, n = name.size();
    int leftRightMove = n - 1;
    for (int x = 0; x < n; x++) {
        ans += upDownMove[name[x] - 'A'];
        int y = x + 1; 
        while (y < n && name[y] == 'A') y++;
        leftRightMove = min(leftRightMove, min(x + x + (n - y), x + (n - y) + (n - y)));
    }
    ans += leftRightMove;
    return ans;
}

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

이 문제는 간단한 문제인줄 알고 건드렸다가 2시간을 날릴 정도로 고생한 문제이다 
일단 이 문제의경우 딱 봤을 때 BFS를 사용하는거는 확실 해 보이지만 매번 시추할 때 마다 BFS를 돌리면 효율성 검사에서 점수가 떨어지게 된다 이에 이문제는 BFS를 이용해서 뽑아낸 데이터를 어떤 자료 구조에 넣어 사용하는 지가 매우 중요한 문제이다

#include <string>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
int directionX[4] = { 1, 0, -1, 0 };
int directionY[4] = { 0, 1, 0, -1 };
int isVisited[501][501] = { 0, };
map<int, int> sizeOfOil;
int sizeOfLandX;
int sizeOfLandY;
int areaNum = 1;
vector<vector<int>> oilMap;
void BFS(int startX, int startY ) {
    int tmp = 0;
    queue<pair<int, int>> q;
    q.push({ startX, startY });
    oilMap[startX][startY] = areaNum;
    isVisited[startX][startY] = 1;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        tmp++;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nextX = x + directionX[i];
            int nextY = y + directionY[i];
            if (nextX >= 0 && nextX < sizeOfLandX && nextY >= 0 && nextY < sizeOfLandY && isVisited[nextX][nextY] == false && oilMap[nextX][nextY]>0) {
                oilMap[nextX][nextY] = areaNum;
                isVisited[nextX][nextY] = 1;
                q.push({ nextX,nextY });
            }
        }
    }
    sizeOfOil[areaNum] = tmp;
    areaNum++;
   
}
int solution(vector<vector<int>> land) {
    int answer = 0;
    oilMap = land;
    sizeOfLandX = land.size(); //열의 길이
    sizeOfLandY = land[0].size(); //행의 길이

    for (int i = 0; i < sizeOfLandX; i++) {
        for (int j = 0; j < sizeOfLandY; j++) {
            if (isVisited[i][j] == false && land[i][j] == 1) {
                BFS(i, j);
            }
        }
    }

    for (int j = 0; j < sizeOfLandY; j++) {
        set<int> oilSet;
        int sumOfOil=0;
        for (int i = 0; i < sizeOfLandX; i++) {
            oilSet.insert(oilMap[i][j]);
        }
        set<int>::iterator iter;
        for (auto it : oilSet) {
            sumOfOil += sizeOfOil[it];
        }
        answer = max(answer, sumOfOil);
    }

    return answer;
}

일단 이 문제의 경우 내가 블로그에 기존에 올렸던 BFS보다 간단 하다 원래는 Direction을 일일히 내가 정해줬었는데 이를 배열에 넣어 간단하게 보이게 했다. 코드 가독성이 올라가니 확실히 디버깅 효율이 올라갔다

자 일단 이문제의 핵심로직은 BFS로 구해놓은 영역의 유전의 크기를 영역별로 들고 있어야 한다 이를 위해 위 코드에

void BFS(int startX, int startY ) {
    int tmp = 0;
    queue<pair<int, int>> q;
    q.push({ startX, startY });
    oilMap[startX][startY] = areaNum;
    isVisited[startX][startY] = 1;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        tmp++;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nextX = x + directionX[i];
            int nextY = y + directionY[i];
            if (nextX >= 0 && nextX < sizeOfLandX && nextY >= 0 && nextY < sizeOfLandY && isVisited[nextX][nextY] == false && oilMap[nextX][nextY]>0) {
                oilMap[nextX][nextY] = areaNum;
                isVisited[nextX][nextY] = 1;
                q.push({ nextX,nextY });
            }
        }
    }
    sizeOfOil[areaNum] = tmp;
    areaNum++;
   
}

BFS 부분에서sizeOfOil에 저장해 주었다 여기서 sizeOfOil은 맵 자료형이다 맵자료형은 map<int,int>이렇게 사용했을 때 맨앞에 오는 값은 Key로서 두번쨰 오는 값은 value로 써 작용합니다.
즉 map<key, value> 의 형태로 각각의 해당하는 자료형을 넣어주면 됩니다 .

이 문제에서는 Map의 저장해놓은 데이터를 순환하여 찾아와야 하기 때문에

for (auto iter = m.begin() ; iter !=  m.end(); iter++)
{
	cout << iter->first << " " << iter->second << endl;
}
cout << endl;

의 형태와

for (auto iter : m) {
	cout << iter.first << " " << iter.second << endl;
}

의 형태의 두가지 형태로 map을 순환 할 수 있습니다.
이에 필자는 두번째 형태로 사용하였습니다. 

이렇게 Map형태로 저장해놓은 데이터에서 우리는 land 배열에 새로줄에서 만나는 areaNum들을 set에 넣어줍니다.
Set은 마찬가지로 중복되는 자료를 넣으면 넣지 않기 때문에 areaNum을 최대 1번씩만 넣을 수 있습니다
이에 set.insert를 이용해서 각 세로줄에 있는 유전의 areaNum을 넣습니다.

그후 이를 순회하면서 areaNum을 통해 세로줄에 있는 해당 유전에 크기를 더하여 최대값을 출력합니다

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

이 문제의 경우 백준의 dp문제에 항상 시달리던내가 풀기에도 쉬운 문제였다 처음 이문제를 풀때는 dfs로 접근해볼까라는 생각을 하고 풀어보았다 하지만 dfs의 특징상 하나한 다해보기때문에 경우의 수가 기하급수적으로 늘어나 시간복잡도가 무지막지하게 늘어나는 현상을 보여주었기 떄문에 결국에 이전값을 사용하는 dp로 이문제를 풀었다 이문제의 경우 어떠한 발판에 도착하는  경우의 수는 총 2가지이다 내 2번째  전 발판에서 오거나 내 저에 발판에서 오거나 이다. 2번째 발판 전도 마찬가지고 전 발판들도 똑같다 즉 나까지 도착하는 경우의수는 내 2번째전 발판까지 오는 경우의수와 나의 전 발판 까지 오는 경우의 수의 합이다. 이에 점화식은 

 dp[i] = (dp[i - 1] + dp[i - 2]) 이것이다

long long dp[2001];
long long solution(int n) {
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2])%1234567;
    }
    long long answer = dp[n];
    return answer;
}

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

백준만 풀다가 프로그래머스 문제가 빡세다고 해서 풀어보았다 개어렵다 kakao의 문제는 문자열 위주로 코딩테스트?가 진행 되는건가 싶었는데 오늘 풀고 나서 kakao의 문제는 대부분 문자열 처리인 거 같다는 생각을 했다 오늘 진행한건 일단 lv2  였는데 저녁을 안먹어서 그런지 오지게 안풀렸다 일단 이문제를 푸는데 약 1시간 반정도 걸렸으니 실제로 이문제가 나왔으면 코테에서 널어졌을 거 같다. 나는 일단 이문제를 이렇게 생각했다 사전에서 일단 1개의 문자가 맞는지 탐색한다 맞으면 자신과 자신의 다음문자를 합쳐서 나 이후로 검사한다 만약 또나온다면 합친 문자열에 또 그 다음문자를 합쳐서 검색한다. 그 후 반복이 끝나면 합치기 전에 나의 index를 저장 한다. 이 index는 즉 문자들을 합쳤을때 최종적으로 벡터에 존재하는 문자열을 의미한다.

#include<iostream>
#include<vector>
#include<string>
using namespace std;
vector<int> solution(string msg) {
    vector<int> answer;
    char start = 'A';
    int k = 0;
    vector<string> dictionary;
    for (int i = 1; i <= 26; i++) {
        dictionary.push_back(string(1, start));
        start++;
    }


    for (int i = 0; i < msg.length(); i++) {
        string temp = string(1,msg[i]);
        int endnumber=0;
        for (int j = 0; j < dictionary.size(); j++) {
            if (temp == dictionary[j]) {
                temp = temp + msg[i += 1];
                endnumber = j+1;
            }
        }
        answer.push_back(endnumber);
        if ((i) == msg.length()) {
            continue;
        }
        dictionary.push_back(temp);
        if (i >= 1) {
            i = i - 1;
        }
    }
    return answer;
}
int main() {
    vector<int> answe1r;
    answe1r=solution("TOBEORNOTTOBEORTOBEORNOT");
    for (int i = 0; i < answe1r.size(); i++) {
        cout << answe1r[i] << '\n';
    }
    
}