99코딩

• 해당 요청시점에서 들어온 작업 중 소요 시간이 짧은 작업들부터 처리하는 것이 관건
• 작업 배열을 요청 시점 기준으로 오름차순 정렬하고 이후 우선순위 큐에 소요 시간 기준으로 오름차순 정렬
• 이후 모든 작업을 완료할 때까지 작업 수행

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

using namespace std;

// 소요 시간이 짧은 것부터 처리하는 것이 평균을 줄이는 방법
// 일단 jobs 배열을 오름차순으로 정렬하고 우선순위 큐에 소요 시간을 기준으로 오름차순 정렬하면 될듯

struct cmp {
    bool operator()(vector<int> a, vector<int> b) {
        return a[1] > b[1];
    }
};

int solution(vector<vector<int>> jobs) {
    // 각각 총 소요시간, 현재까지의 소요시간, 작업 카운트
    int totalCost = 0, curCost = 0, cnt = 0;
    
    priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
    
    // 정렬
    sort(jobs.begin(), jobs.end()); 
    
    // 작업이 끝나지 않은 동안
    while(cnt < jobs.size() || !pq.empty()) {
        
        // 요청 시간이 현재까지의 소요 시간보다 작으면
        if(cnt < jobs.size() && jobs[cnt][0] <= curCost) {
            pq.push(jobs[cnt]); 
            cnt++;
            continue;
        }
        
        // 우선순위 큐에 수행할 작업이 들어있다면
        if(!pq.empty()) {
            curCost += pq.top()[1];
            totalCost += curCost - pq.top()[0];
            pq.pop();
        }
        // 작업은 남았는데 현재 시간에 우선순위 큐에 들어있는 작업이 없다면
        else {
            curCost = jobs[cnt][0];
        }
    }
    
    return totalCost / jobs.size();
}

​

• 최단거리 문제
• 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;
}

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