모각코 Part 2

1. 재귀탐색: 연산자 끼워넣기 (백준 14888, 실버 1)

#include<bits/stdc++.h>
using namespace std;
 
int N, temp_ans, f;
vector<int>ans, A, ma;
 
// 연산자를 배열에 저장하고 순열 사용하여 모든 경우의 수를 계산
void check() {
    temp_ans = 0;
    sort(ma.begin(), ma.end());
    do {
        temp_ans = A[0];
        for (int i = 0; i < ma.size()+1; i++) {
                if (ma[i] == 1) 
                    temp_ans += A[i + 1];
                if (ma[i] == 2) 
                    temp_ans -= A[i + 1];
                if (ma[i] == 3) 
                    temp_ans *= A[i + 1];
                if (ma[i] == 4) 
                    temp_ans /= A[i + 1];
        }
        ans.push_back(temp_ans);
    } while (next_permutation(ma.begin(), ma.end()));
}
 
int main() {
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;
    int ss;
    int num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        A.push_back(num);
    }
    for (int i = 0; i < 4; i++) {
        cin >> ss;
        for (int j = 0; j < ss; j++) {
            if (i == 0)
                ma.push_back(1);
            if (i == 1)
                ma.push_back(2);
            if (i == 2)
                ma.push_back(3);
            if (i == 3)
                ma.push_back(4);
        }
    }
    check();
    sort(ans.begin(), ans.end());
    cout << ans.back() << endl << ans[0];
}

2. 스택의 응용: 괄호의 값 (백준 2504, 실버 1)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s;
    cin >> s;
    stack<char>st;
    int res = 0, tmp = 1;
    for (int i = 0; i < s.size(); i++) {
    	// (일때 2곱하고 push
        if (s[i] == '(') {
            st.push('(');
            tmp *= 2;
        }
        else if (s[i] == '[') {
            st.push('[');
            tmp *= 3;
        }
        // 스택이 비거나 top이 (가 아닌경우
        else if (s[i] == ')') {
            if (st.empty() || st.top() != '(') {
                cout << 0 << "\n";
                return 0;
            }
            // 이전 문자열이 (인 경우
            st.pop();
            if (s[i - 1] == '(') {
                res += tmp;
                tmp /= 2;
            }
            // 이전 문자열이 (이 아닌경우 경우
            else
                tmp /= 2;
        }
        else {
         	// 스택이 비거나 top이 [가 아닌 경우
            if (st.empty() || st.top() != '[') {
                cout << 0 << "\n";
                return 0;
            }
            // 이전 문자열이 [인 경우
            st.pop();
            if (s[i - 1] == '[') {
                res += tmp;
                tmp /= 3;
            }
            // 이전 문자열이 [이 아닌 경우
            else
                tmp /= 3;
        }
    }
    // 남아있다면 올바르지 못함
    if (!st.empty()) {
        cout << 0 << "\n";
        return 0;
    }
    cout << res << "\n";
    return 0;
}

3. 시뮬레이션 기본: 빗물 (백준 14719, 골드 5)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    int N, M, K;
    int X, Y;
    int answer = 0;

    cin >> N >> M;
    vector<int> v(M);

    for (int i = 0; i < M; i++)
        cin >> v[i];

    for (int i = 1; i < M - 1; i++) {
        int left = 0; int right = 0;
        //왼쪽 최대 값
        for (int j = 0; j < i; j++) left = max(left, v[j]);
        //오른쪽 최대 값
        for (int j = M - 1; j > i; j--) right = max(right, v[j]);
        //빗물 계산
        answer += max(0, min(left, right) - v[i]);
    }

    cout << answer << endl;
    return 0;
}

 

4. 투 포인터의 기본: 부분합 (백준 1806, 골드 4)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, s;
    cin >> n >> s;
    int arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    int start = 0, end = 0;
    int sum = arr[0];
    int len = INT_MAX;
    int cnt = 0;

    while (end < n)
    {
    	// 현재 포인터의 합이 더 큰 경우
        if (sum < s)
        	// end 포인터 증가 합 증가
            sum += arr[++end];
		// 합이 더 작은 경우
        else if (sum > s) {
            cnt++;
            // 짧은 길이만 저장
            len = min(len, end - start + 1);
            // 같으면 끝 포인터 증가하고 합 증가
            if (start == end)
                sum += arr[++end];
            // 다르면 시작 포인터 증가 합 감소
            else
                sum -= arr[start++];
        }
        // 합과 같은 경우 끝 포인터 증가하고 합 증가
        else {
            cnt++;
            len = min(len, end - start + 1);
            sum += arr[++end];
        }
    }
    // 불가능한 경우
    if (cnt == 0)
        cout << 0 << "\n";
    else
        cout << len << "\n";
    return 0;
}

5. 벨만포드 뼈대문제: 최소비용 구하기 (백준 1916, 골드 5)

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> vec[1001];
vector<int> dist(1001, INT_MAX);

void dijkstra(int dept){
    dist[dept] = 0;
    // 시작 weight, vertex
    priority_queue<pair<int, int>> pq;
    pq.push({dist[dept], dept}); 
    
    while(!pq.empty()){
        int cur = pq.top().second;
        // 현재까지 dept에서 cur 정점까지 가는 dist
        int distance = pq.top().first * -1; 
        pq.pop();
        
        //이미 distance가 최소로 변경됨 
        if(dist[cur] < distance) 
        	continue; 
        
        for(int i = 0; i < vec[cur].size(); i++){
        	// cur 정점과 연결된 정점들
            int nxt = vec[cur][i].first; 
            int nxtdist = vec[cur][i].second + distance;
            // 현재까지 dept에서 cur정점까지의 최소 거리와 
            // cur을 지나 nxt까지의 거리를 더한것 cur정점에서 nxt까지의 distance      
            // cur을 지나가는 것이 더 가까운 경우
            if(nxtdist < dist[nxt]){
                dist[nxt] = nxtdist;
                // 새롭게 갱신된 weight와 vertex
                pq.push({nxtdist * -1, nxt});
            }
        }
    }
}
int main(){
    int N, M;
    cin >> N >> M;
    
    while(M--){
        int s, e, w; 
        cin >> s >> e >>w;
        vec[s].push_back({e, w});
    }
    
    int dept, dest;
    cin >> dept >> dest;
    
    dijkstra(dept);
    cout << dist[dest];
    
    return 0;
}