99코딩

#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;
}

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

#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;
}

• 해시 문제라 unordered_map으로 접근
• 해당 unorded_map을 벡터에 할당해주고 벡터를 장르별 총합 재생수 기준으로 정렬해준 뒤 각 장르마다 장르 내의 곡들을 재생수 기준으로 정렬(뭐부터 정렬할지 순서는 상관없음)
• 이후 총합 재생수가 높은 장르부터 재생수가 높은 곡 2개를 수록. 단, 장르에 곡이 하나면 한 곡만 수록

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

// 장르 내의 곡들의 재생수 합이 가장 큰 장르부터 장르 내의 곡들을 재생수 순서대로 출력
// 가장 많이 재생된 노래를 두 개씩 모아서 재생
// 해시 문제 unordered_map 사용(key, value 삽입 시 정렬이 필요 없음)

using namespace std;

// 장르별 총합 재생 수 비교자
bool cmpGenre(const pair<string, pair<int, vector<pair<int, int>>>> &a, const pair<string, pair<int, vector<pair<int, int>>>> &b) {
    return a.second.first > b.second.first;
}

// 곡 재생 수 비교자
bool cmpPlay(const pair<int, int> &a, const pair<int, int> &b) {
    return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string, pair<int, vector<pair<int, int>>>> m;
    vector<pair<string, pair<int, vector<pair<int, int>>>>> v;
    
    for(int i = 0; i < genres.size(); i++) {
        m[genres[i]].first += plays[i];
        m[genres[i]].second.push_back({i, plays[i]}); 
    }
    
    v.assign(m.begin(), m.end());
    
    // 장르별 총합 재생수 기준으로 정렬
    sort(v.begin(), v.end(), cmpGenre);
    
    // 각 장르마다 장르 내의 곡들을 재생수 기준으로 정렬
    for(int i = 0; i < v.size(); i++)
        sort(v[i].second.second.begin(), v[i].second.second.end(), cmpPlay);
    
    // 총합 재생수가 높은 장르마다 재생수가 높은 곡 2개씩 수록
    for(int i = 0; i < v.size(); i++) {
        for(int j = 0; j < 2; j++) {
            answer.push_back(v[i].second.second[j].first);
            
            // 장르에 곡이 하나만 있다면 하나만 수록
            if(v[i].second.second.size() == 1) break;
        }
    }
    
    return answer;
}