99코딩

• 최단거리 문제
• bfs로 해결
• 현재 길의 정보에만 방향성을 추가하면 될 줄 알았으나 25번 케이스가 오답이 나와서 찾아보니cost 배열 자체에도 방향성을 저장할 필요가 있다고 해서 적용하니 해결됨

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

using namespace std;

// bfs를 수행하면서 전달하는 정보에 방향을 추가하면 될 것 같음

struct INFO {
    int x;
    int y;
    int cost;
    int dir;
};

int dirX[4] = {0, 1, 0, -1};
int dirY[4] = {1, 0, -1, 0};

int solution(vector<vector<int>> board) {
    int answer = INT32_MAX;
    
    int cost[4][26][26];
    
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 26; j++)
            for(int k = 0; k < 26; k++)
                cost[i][j][k] = INT32_MAX;
    
    queue<INFO> q;
    q.push({0, 0, 0, 0});
    cost[0][0][0] = 0;
    
    q.push({0, 0, 0, 1});
    cost[1][0][0] = 0;
    
    // bfs 수행
    while(!q.empty()) {
        INFO curINFO = q.front();
        q.pop();
        
        if(curINFO.x == board.size() - 1 && curINFO.y == board.size() - 1) {
            answer = min(answer, curINFO.cost);
            continue;
        }
        
        for(int i = 0; i < 4; i++) {
            int nx = curINFO.x + dirX[i];
            int ny = curINFO.y + dirY[i];
            
            if(nx >= 0 && nx < board.size() && ny >= 0 && ny < board.size()) {
                if(board[nx][ny] == 1) continue;
                
                int nCost;
                if(curINFO.dir == i) nCost = curINFO.cost + 100;
                else nCost = curINFO.cost + 600;

                if(nCost <= cost[i][nx][ny]) {
                    cost[i][nx][ny] = nCost;
                    INFO nextINFO = {nx, ny, nCost, i};
                    q.push(nextINFO);
                }
            }
        }
    }
    
    return answer;
}

• 간단한 bfs/dfs 문제
• roads를 각 노드에 대한 인접 리스트로 만들어서 bfs를 수행하면 됨

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

// 그래프 문제
// 각 노드별 인접 리스트를 만들어서 bfs 돌리면 될듯

using namespace std;

int bfs(int startNode, int destination, vector<vector<int>> &list) {
    queue<pair<int, int>> q;
    bool isVisited[100001] = {false};
    int dist = INT32_MAX;
    
    q.push({startNode, 0});
    isVisited[startNode] = true;
    
    while(!q.empty()) {
        int curNode = q.front().first;
        int movedDist = q.front().second;
        q.pop();
        
        if(curNode == destination) {
            dist = min(dist, movedDist);
        } 
        
        for(int i = 0; i < list[curNode].size(); i++) {
            if(!isVisited[list[curNode][i]]) {
                isVisited[list[curNode][i]] = true;
                q.push({list[curNode][i], movedDist + 1});
            }
        }
    }
    
    return dist;
}

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    vector<vector<int>> list(n + 1);
    
    // 리스트 생성
    for(int i = 0; i < roads.size(); i++) {
        list[roads[i][0]].push_back(roads[i][1]);
        list[roads[i][1]].push_back(roads[i][0]);
    }
    
    // 각 부대원 별로 bfs 수행
    for(int i = 0; i < sources.size(); i++) {
        // 이미 목적지에 위치해 있으면
        if(sources[i] == destination) {
            answer.push_back(0);
            continue;
        }
        
        int result = bfs(sources[i], destination, list);
        
        if(result == INT32_MAX) answer.push_back(-1);
        else answer.push_back(result);
    }
    
    return answer;
}

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

using namespace std;

// dp 문제
// 합이 최대가 되려면 결국에 최대한 많은 스티커를 떼어내야함
// dp[i]에서 스티커를 뜯을건지 뜯지 않을건지 결정하며 각 구간마다 최댓값을 선택해야함
// 점화식은 dp[i] = max(dp[i-1], dp[i-2] + sticker[i])
// 배열에서 첫 번째 스티커를 선택했을 때와 두 번째 스티커를 선택했을 때를 나누어서 수행해야함
// 첫 번째 스티커를 선택했을 때는 마지막 스티커를 선택하지 못함 > 원형으로 이어져있기 때문
// 두 번째 스티커를 선택했을 때는 첫 번째 스티커를 선택하지 못하므로 제외해야함
// dp 배열 2개 만들고 따로 수행해주면 될듯

int dp1[100001];
int dp2[100001];
int solution(vector<int> sticker)
{
    int answer = 0;
    int length = sticker.size();
    
    if(length == 1) return sticker[0];
    
    // 첫 번째 스티커를 선택할 때
    dp1[0] = sticker[0];
    dp1[1] = sticker[0];
    
    // dp 수행
    for(int i = 2; i < length - 1; i++)
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + sticker[i]);
    
    answer = max(answer, dp1[length - 2]);
    
    // 두 번째 스티커를 선택할 때
    dp2[0] = 0;
    dp2[1] = sticker[1];
    
    // dp 수행
    for(int i = 2; i < length; i++)
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + sticker[i]);
    
    answer = max(answer, dp2[length - 1]);
    
    return answer;
}

​

[2. Foot IK]

 

요즘 사용되지 않는 게임이 적은 기능이라 생각하여 이것저것 찾아서 구현해보았습니다.

 

처음엔 강의를 통해 Foot IK의 원리를 이해하려 하였고 이후엔 c++로 해당 기능을 구현해보았고 추가로 밟고 있는 땅의 각도에 따라 발이 회전하는 기능도 찾게 되어 공부하고 구현해보았습니다.

 

 

• 완전 탐색 문제
• 해당 단어의 사용 여부와 변환 가능 여부를 체크해야함

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

using namespace std;

// 완전 탐색 문제
// 단어의 사용 여부와 변환 가능 여부를 체크해서 dfs 돌리면 될듯
// target이 words 안에 없을 수도 있음 < 지나칠 뻔

// 방문 여부
bool Used[51] = {false};

// 변환 가능 여부 체크
bool canChange(string str1, string str2) {
    int diff = 0;
    
    // 두 단어 간 다른 알파벳의 개수 구하기
    for(int i = 0; i < str1.size(); i++)
        if(str1[i] != str2[i]) diff++;
    
    // 다른 알파벳의 개수가 1이면 가능 아니면 불가능
    if(diff == 1) return true;
    else return false;
}

// dfs
void dfs(int cnt, string cur, string target, vector<string> words, int &answer) {
    
    // answer보다 cnt가 커지면 더 볼 필요 없음
    if(cnt >= answer) return;
    
    // cur에서 target으로 변환이 가능하면
    if(canChange(cur, target)) {
        answer = min(answer, ++cnt);
        return;
    }
    
    // words 배열 내의 단어들 중
    for(int i = 0; i < words.size(); i++) {
        // 사용한적 없고 변환 가능하면
        if(!Used[i] && canChange(cur, words[i])) {
            
            Used[i] = true;
            // dfs 수행
            dfs(cnt + 1, words[i], target, words, answer);
            
            Used[i] = false;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    int answer = INT32_MAX;
    
    // target이 words 안에 있는지 체크
    if(find(words.begin(), words.end(), target) == words.end()) return 0;
    
    // dfs 수행
    dfs(0, begin, target, words, answer);
    
    return answer;
}

• 투 포인터 알고리즘을 통해 팰린드롬의 길이를 찾아나가면 되는 문제
• 주의해야할 건 길이가 짝수일 때와 홀수일 때 왼쪽 포인터의 시작 지점이 다르다는 것

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// 팰린드롬 찾기
// 투포인터를 활용해서 특정 인덱스 기준으로 좌우로 늘리면서 체크하면 될듯
// 문제 설명에는 팰린드롬의 길이가 홀수인 경우만 나와있지만 짝수인 경우도 고려해야함
// 이 경우엔 좌 -1, 우를 기준으로 늘려나가면 될듯

// 팰린드롬 찾고 길이 구하기
int FindPalindrome(string s, int left, int right) {
    while(s[left] == s[right] && left >= 0 && right < s.size()) {
        // 조건이 맞으면 좌우로 하나씩 늘리기
        left--;
        right++;
    }
    
    return right - left - 1;
}

int solution(string s)
{
    int answer = 0;
    
    for(int i = 0; i < s.size(); i++) {
        // 홀수 팰린드롬 길이
        int oddLength = FindPalindrome(s, i, i);
        // 짝수 팰린드롬 길이
        int evenLength = FindPalindrome(s, i - 1, i);
        
        // 더 긴거
        int longerLength = max(oddLength, evenLength);
        answer = max(answer, longerLength);
    }

    return answer;
}

백준에서 비슷한거 푼 적 있는거 같은데...

• 3 단계에서 처음 본 최소 신장 트리 문제
• 크루스칼 알고리즘을 통해 해결

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

using namespace std;

// 최소의 비용으로 모든 노드를 연결해야함 > 크루스칼 알고리즘
// 일단 비용 기준으로 정렬 필요
// 이후 부모 노드를 저장한 뒤 노드들을 순회하며 부모 노드가 같은 경우 = 싸이클이 발생하는 경우를 제외하고 다리를 건설

vector<int> parent(101);

// 부모 노드를 찾는 함수
int FindParent(int x) {
    if(parent[x] == x) return x;
    else return parent[x] = FindParent(parent[x]);
}

// 비교자
int cmp(vector<int> a, vector<int> b) {
    return a[2] < b[2];
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    // 비용 기준으로 정렬
    sort(costs.begin(), costs.end(), cmp);
    
    // 부모 노드 저장
    for(int i = 0; i < n; i++)
        parent[i] = i;
    
    for(int i = 0; i < costs.size(); i++) {
        int startNode = FindParent(costs[i][0]);
        int endNode = FindParent(costs[i][1]);
        int cost = costs[i][2];
        
        // 부모 노드가 같지 않다면 싸이클이 생기지 않으므로 다리를 건설 및 부모 노드 갱신
        if(startNode != endNode) {
            answer += cost;
            parent[endNode] = startNode;
        }
    }
    
    return answer;
}

• 완전 탐색 문제
• 단, 경로가 2개 이상일 때 알파벳 순서가 앞서는 경로를 리턴하라 했으므로 정렬하여 알파벳 순서대로 탐색할 수 있도록 하였음

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

using namespace std;

// 무조건 ICN 공항에서 출발
// 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 리턴
// 일단 정렬하면 알파벳 순서로 탐색할 수 있을듯
// 완전 탐색 문제. DFS로 접근

bool dfs(string cur, vector<vector<string>> tickets, vector<string> &answer, vector<bool> &Used, int cnt) {
    // 방문한 공항 저장
    answer.push_back(cur);
    
    // 모든 티켓 사용 완료
    if(tickets.size() == cnt) return true;
    
    // 티켓 배열을 순회하며
    for(int i = 0; i < tickets.size(); i++) {
        // 출발지가 현재 공항이고 사용한적 없는 티켓이라면
        if(tickets[i][0] == cur && !Used[i]) {
            // 사용으로 바꾸고
            Used[i] = true;
            
            // 더 안쪽으로 탐색
            if(dfs(tickets[i][1], tickets, answer, Used, cnt + 1)) return true;
            
            // 위 if 문이 거짓이 되면 모든 항공권 사용 실패이므로 백트래킹
            Used[i] = false;
        }
    }
    
    // 마찬가지로 백트래킹
    answer.pop_back();
    
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<bool> Used(tickets.size(), false);
    
    // 정렬
    sort(tickets.begin(), tickets.end());
    
    // dfs
    dfs("ICN", tickets, answer, Used, 0);
    
    return answer;
}

• 그래프에서 bfs/dfs 돌리면 되는 문제

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

using namespace std;

// 1번에서 가장 멀리 떨어진 노드가 몇 개인지 찾기. 가중치 X
// bfs/dfs 수행해서 가장 멀리 떨어진 노드까지의 거리를 저장하고 해당 거리랑 동일한 값을 갖는 노드를 카운트
// 우선 제공되는 간선 정보를 인접 리스트로 변환
// 이후 1번 노드부터 bfs 시작하며 각 노드에 최단 거리 저장

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<vector<int>> list(n + 1);
    
    // 인접 리스트로 변환
    for(int i = 0; i < edge.size(); i++) {
        list[edge[i][0]].push_back(edge[i][1]);
        list[edge[i][1]].push_back(edge[i][0]);
    }
    
    vector<int> dist(n + 1, -1);
    queue<int> q;
    
    // bfs 수행
    dist[1] = 0;
    q.push(1);
    
    while(!q.empty()) {
        int curNode = q.front();
        q.pop();
        
        for(int nextNode : list[curNode]) {
            if(dist[nextNode] == -1) {
                dist[nextNode] = dist[curNode] + 1;
                q.push(nextNode);
            }
        }
    }
    
    // 가장 큰 거리값 찾기
    int max = *max_element(dist.begin(), dist.end());
    
    // 가장 멀리 떨어진 노드들 찾기
    for(int i = 0; i < dist.size(); i++)
        // 거리가 가장 큰 거리값과 같으면
        if(dist[i] == max) answer++;
    
    return answer;
}

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

using namespace std;

// 진열된 모든 종류의 보석을 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매
// 투 포인터 알고리즘

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    unordered_map<string, int> um;
    
    for(int i = 0; i < gems.size(); i++)
        um[gems[i]] = 0;
    
    int start = 0, curGem = 0;
    answer.push_back(0);
    answer.push_back(100001);
    
    for(int end = 0; (end < gems.size()) && start <= end;) {
        // start와 같은 보석이 나오거나 start 지점의 보석과 같은 보석을 여러번 집었다면
        if((end != start && gems[start] == gems[end]) || um[gems[start]] > 1) {
            if(!(--um[gems[start++]])) curGem--;
            continue;
        }
        // end 지점의 보석을 처음 주워본다면
        else if(um[gems[end]]++ == 0) {
            curGem++;
        } 
        
        // 모든 종류의 보석을 집었을 때
        if(curGem == um.size()) {
            // 구간의 길이가 더 짧다면
            if(answer[1] - answer[0] > end - start) {
                answer[0] = start + 1;
                answer[1] = end + 1;
            }
            
            // 해당 구간에서 시작 지점 빼주기
            if(!(--um[gems[start++]])) curGem--;
        }
        
        end++;
    }
    
    return answer;
}