경우없는 개발 블로그

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18TrIqIwUCFAZN&categoryId=AV18TrIqIwUCFAZN&categoryType=CODE&problemTitle=%EC%9E%91%EC%97%85&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&&

#문제 간단 정리

위상정렬

#문제 해결 방법

정석적인 위상정렬이기 때문에

위상정렬 코드를 구현하도록 하자

#전체 코드

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
int main()
{
     
    for (int T = 1; T <= 10; T++) {
        int V, E;
        cin >> V >> E;
 
        vector<vector<int>> graph(V + 1);
        vector<int> indegree(V + 1, 0);
 
        for (int i = 1; i <= E; i++) {
 
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            indegree[v]++;
 
        }
 
        queue<int> q;
 
        cout << '#' << T << ' ';
 
        for (int i = 1; i <= V; i++) {
            if (indegree[i] == 0) {
                cout << i << ' ';
                q.push(i);
            }
        }
 
 
  
       
        while (!q.empty()) {
            int front = q.front();
            q.pop();
 
            for (auto nextNode : graph[front]) {
 
                indegree[nextNode] --;
 
                if (indegree[nextNode] == 0) {
                    cout << nextNode << ' ';
                    q.push(nextNode);
                }
            }
 
        }
 
 
        cout << '\n';
   }
 
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14tDX6AFgCFAYD

#문제 간단 정리

기존의 후위 표기법 변환과 같다

괄호 사용함에 주의하자

#문제 해결 방법

#전체 코드

#include <iostream>
#include <stack>
#include <cctype> 

using namespace std;

int precedence(char op) {
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    for (int tc = 1; tc <= 10; tc++) {
        int t; cin >> t;

        string s;
        cin >> s;

        stack<char> st;
        string output;

        for (int i = 0; i < s.length(); i++) {
            char now = s[i];

            if (isdigit(now)) {
                output += now;
            }
            else if (now == '(') {
                st.push(now);
            }
            else if (now == ')') {
                while (!st.empty() && st.top() != '(') {
                    output += st.top();
                    st.pop();
                }
                st.pop();
            }
            else {
                while (!st.empty() && precedence(st.top()) >= precedence(now)) {
                    output += st.top();
                    st.pop();
                }
                st.push(now);
            }
        }

        while (!st.empty()) {
            output += st.top();
            st.pop();
        }

        //cout << output << '\n';


        //계산
        stack<int> st2;
        for (int i = 0; i < output.length(); i++) {

            char now = output[i];
            if (isdigit(now)) {
                st2.push(now - '0');
            }
            else {
                char temp = output[i];
                int second = st2.top();
                st2.pop();
                int first = st2.top();
                st2.pop();
                if (temp == '+') {
                    st2.push(first + second);
                }
                else if (temp == '-') {
                    st2.push(first - second);
                }
                else if (temp == '*') {
                    st2.push(first * second);
                }
                else if (temp == '/') {
                    st2.push(first / second);
                }
            }

        }

        cout << '#' << tc << ' ' << st2.top() << '\n';
    }

    return 0;
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14geLqABQCFAYD&

#문제 간단 정리

간단한 dfs 문제

#문제 해결 방법

#전체 코드

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

bool flag;

void dfs(vector<vector<int>> &vec, bool visited[],int idx) {
    if (idx == 99) {
        flag = true;
        return;
    }
    for (int i = 0; i < vec[idx].size(); i++) {
        int nextIdx = vec[idx][i];
        if (!visited[nextIdx]) {
            visited[nextIdx] = true;
            dfs(vec, visited, nextIdx);
            visited[nextIdx] = false;
        }
    }
    return;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for (int tc = 1; tc <= 10; tc++) {

        int n, length;
        cin >> n >> length;
        vector<vector<int>> nodes(100,vector<int>(0));
        bool visited[100] = { false };

        for (int i = 0; i < length; i++) {

            int a, b;
            cin >> a >> b;
            nodes[a].push_back(b);
        }

        flag = false;

        dfs(nodes, visited, 0);

        cout << '#' << tc << ' ' << (flag ? 1 : 0) << '\n';
    }

    return 0;
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14eWb6AAkCFAYD

#문제 간단 정리

스택을 활용한 괄호 문제

#문제 해결 방법

map으로 좀 더 깔끔하게 짜고자 했다.

기존유형문제와 풀이 방법은 같다

#전체 코드

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



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    map<char, char> cache;
    cache[')'] = '(';
    cache[']'] = '[';
    cache['}'] = '{';
    cache['>'] = '<';

    for (int tc = 1; tc <= 10; tc++) {

        int n;
        cin >> n;

        string s;
        cin >> s;

        bool flag = true;

        vector<char> brackets;
        for (int i = 0; i < s.size(); i++) {

            if (s[i] == '(' || s[i] == '[' || s[i] == '{' || s[i] == '<') {
                brackets.push_back(s[i]);
            }
            else {
                if (brackets.empty()) {
                    flag = false;
                    break;
                }
                else if(cache[s[i]] == brackets.back())  {
                    brackets.pop_back();
                }
                else {
                    flag = false;
                    break;
                }
            }
        }


        if (!brackets.empty()) {
            flag = false;
        }

        if (flag) {
            cout << '#' << tc << ' ' << 1 << '\n';
        }
        else {
            cout << '#' << tc << ' ' << 0 << '\n';
        }

    }


    return 0;
}

#문제 간단 정리

dfs 를 이용한 완전탐색

#문제 해결 방법

 우선 거리를 측정하는 방법을 알려 준 것이 힌트라고 생각한다.

처음에는 순간 map 을 이용하는 방법이 떠올랏지만

거리를 단순히 두 좌표의 차이를 더해서 구해주기 때문에

두 거리의 좌표 차들만 순회해서 (완전탐색) 으로

조회해서 최대 거리만 구해주면 답을 구할 수 있다 (10!)

#전체 코드

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <iomanip>
#include <tuple>
#include <sstream>
#include <map>
#include <algorithm>
#include <climits>
#include <cstring>
using namespace std;

bool visited[10];
int result;
vector<pair<int, int>> clients;
pair<int, int> company;
pair<int, int> house;

void dfs(int idx, int dist , pair<int,int> now ) {
    if (idx == clients.size()) {
        dist += abs(now.first - house.first) + abs(now.second - house.second);
        if (dist < result) {
            result = dist;
        }
    }


    for (int i = 0; i < clients.size(); i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(idx +1, dist + (abs(now.first - clients[i].first) + abs(now.second - clients[i].second)), clients[i]);
            visited[i] = false;
        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int tc;
    cin >> tc;

    for (int i = 0; i < tc; i++) {
        int n;
        cin >> n;

        cin >> company.first >> company.second;
        cin >> house.first >> house.second;

        clients.resize(n);
        for (int j = 0; j < n; j++) {
            cin >> clients[j].first >> clients[j].second;
        }

        memset(visited, false, sizeof(visited));
        result = INT_MAX;
        dfs(0, 0, company);

        cout << '#' << i+1 << ' ' << result << '\n';
        
    }
        
    return 0;
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh&

#문제 해결 방법

앞 뒤로  두칸은 0으로 채워지기 때문에 

전체 순회를 하면서 현재칸과 앞뒤 +- 2칸과의 차이가 0 이상이라면 이 차이만큼

결과값에 더해주면 된다.

#전체 코드

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

int main() {
    for (int i = 1; i <= 10; i++) { 
        int N;
        cin >> N;
        vector<int> buildings(N);
        for (int j = 0; j < N; j++) {
            cin >> buildings[j];
        }

        int count = 0;
        for (int k = 2; k < N - 2; k++) {
            int left1 = buildings[k] - buildings[k - 1];
            int left2 = buildings[k] - buildings[k - 2];
            int right1 = buildings[k] - buildings[k + 1];
            int right2 = buildings[k] - buildings[k + 2];

            if (left1 > 0 && left2 > 0 && right1 > 0 && right2 > 0) {
                int minView = min(min(left1, left2), min(right1, right2));
                count += minView;
            }
        }
    
        cout << count << '\n'; 
    }

    return 0;
}