자료구조 예상 문제 1

1. 괄호 깊이 추적

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

using namespace std;

class MyStack {
public:
    void push(int value) {
        stack.push_back(value);
    }

    int pop() {
        if (!stack.empty()) {
            int value = stack.back();
            stack.pop_back();
            return value;
        }
        return -1;  // stack is empty
    }

private:
    vector<int> stack;
};

vector<int> track_parentheses_depth(const string& expression) {
    MyStack stack;
    int depth = 0;
    vector<int> result;

    for (char ch : expression) {
        if (ch == '(') {
            depth++;
            stack.push(depth);
            result.push_back(depth);
        } else if (ch == ')') {
            result.push_back(stack.pop());
            depth--;
        }
    }
    return result;
}

int main() {
    string expression = "(a+(b*c))+(d/e)";
    vector<int> result = track_parentheses_depth(expression);
    
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;  // 출력: 1 2 2 1 3 3
    return 0;
}

 

2. 가장 큰 수를 위한 스택 필터링

 

#include <iostream>
#include <vector>

using namespace std;

class MyStack {
public:
    void push(int value) {
        while (!stack.empty() && stack.back() <= value) {
            stack.pop_back();
        }
        stack.push_back(value);
    }

    int size() {
        return stack.size();
    }

private:
    vector<int> stack;
};

vector<int> largest_stack_filter(const vector<int>& sequence) {
    MyStack stack;
    vector<int> result;

    for (int num : sequence) {
        stack.push(num);
        result.push_back(stack.size());
    }
    return result;
}

int main() {
    vector<int> sequence = {3, 0, 3, 4, 1};
    vector<int> result = largest_stack_filter(sequence);
    
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;  // 출력: 1 2 1 1 2
    return 0;
}

 

3. 가장 큰 수를 위한 숫자 제거

 

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

using namespace std;

string largest_number_after_removal(string number, int k) {
    vector<char> stack;
    
    for (char digit : number) {
        while (k > 0 && !stack.empty() && stack.back() < digit) {
            stack.pop_back();
            k--;
        }
        stack.push_back(digit);
    }

    // 남은 자릿수에서 k만큼 제거
    stack.resize(stack.size() - k);

    return string(stack.begin(), stack.end());
}

int main() {
    string number = "442311";
    int k = 2;
    string result = largest_number_after_removal(number, k);
    cout << result << endl;  // 출력: 4431
    return 0;
}

 

4. 이진 이미지에서 연결된 컴포넌트 크기 계산

 

#include <iostream>
#include <vector>

using namespace std;

class MyStack {
public:
    void push(pair<int, int> value) {
        stack.push_back(value);
    }

    pair<int, int> pop() {
        if (!stack.empty()) {
            pair<int, int> value = stack.back();
            stack.pop_back();
            return value;
        }
        return {-1, -1};  // stack is empty
    }

private:
    vector<pair<int, int>> stack;
};

vector<pair<int, int>> get_neighbors(int x, int y, int rows, int cols) {
    vector<pair<int, int>> neighbors;
    int directions[8][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
    for (auto& dir : directions) {
        int nx = x + dir[0], ny = y + dir[1];
        if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
            neighbors.push_back({nx, ny});
        }
    }
    return neighbors;
}

int dfs(int x, int y, vector<vector<int>>& image, vector<vector<bool>>& visited) {
    MyStack stack;
    stack.push({x, y});
    visited[x][y] = true;
    int component_size = 0;

    while (true) {
        auto [cx, cy] = stack.pop();
        if (cx == -1) break;
        component_size++;
        for (auto& [nx, ny] : get_neighbors(cx, cy, image.size(), image[0].size())) {
            if (image[nx][ny] == 1 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                stack.push({nx, ny});
            }
        }
    }
    return component_size;
}

vector<int> count_components(vector<vector<int>>& image) {
    int rows = image.size();
    int cols = image[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    vector<int> components;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (image[i][j] == 1 && !visited[i][j]) {
                int component_size = dfs(i, j, image, visited);
                components.push_back(component_size);
            }
        }
    }
    return components;
}

int main() {
    vector<vector<int>> image = {
        {0, 1, 0, 0},
        {1, 1, 1, 0},
        {0, 0, 1, 1},
        {0, 1, 0, 0}
    };

    vector<int> components = count_components(image);
    for (int comp : components) {
        cout << comp << " ";
    }
    cout << endl;  // 출력: 3 5 2
    return 0;
}

 

 

5. 후위 표기식 계산기

#include <iostream>
#include <string>
#include <stack>
#include <cctype>
#include <cmath>

using namespace std;

double evaluate_postfix(const string& expression) {
    stack<double> stk;
    
    for (char ch : expression) {
        if (isdigit(ch)) {
            stk.push(ch - '0');
        } else if (ch == '+') {
            double b = stk.top(); stk.pop();
            double a = stk.top(); stk.pop();
            stk.push(a + b);
        } else if (ch == '-') {
            double b = stk.top(); stk.pop();
            double a = stk.top(); stk.pop();
            stk.push(a - b);
        } else if (ch == '*') {
            double b = stk.top(); stk.pop();
            double a = stk.top(); stk.pop();
            stk.push(a * b);
        } else if (ch == '/') {
            double b = stk.top(); stk.pop();
            double a = stk.top(); stk.pop();
            stk.push(a / b);
        }
    }

    return stk.top();
}

int main() {
    string expression = "23*5+";
    double result = evaluate_postfix(expression);
    cout << "Result: " << result << endl;  // 출력: Result: 11
    return 0;
}

6. 최대 힙을 이용한 숫자 처리

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class MaxHeap {
public:
    void push(int value) {
        heap.push_back(value);
        push_heap(heap.begin(), heap.end());
    }

    int pop() {
        if (heap.empty()) return -1;
        pop_heap(heap.begin(), heap.end());
        int value = heap.back();
        heap.pop_back();
        return value;
    }

private:
    vector<int> heap;
};

int main() {
    MaxHeap maxHeap;
    maxHeap.push(5);
    maxHeap.push(10);
    maxHeap.push(3);
    
    cout << maxHeap.pop() << endl;  // 출력: 10
    cout << maxHeap.pop() << endl;  // 출력: 5
    cout << maxHeap.pop() << endl;  // 출력: 3

    return 0;
}

 

 

 

문제 1: 수식의 계산 (전위/후위 표기식)

1. 중위 표기식을 전위 또는 후위 표기식으로 변환.
2. 변환된 전위/후위 표기식을 계산.

구현 계획:

• 중위 표기식 → 후위 표기식 (Postfix notation) 변환
• 중위 표기식 → 전위 표기식 (Prefix notation) 변환
• 후위 표기식 계산
• 전위 표기식 계산

#include <iostream>
#include <stack>
#include <string>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

// 연산자 우선순위
int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

// 중위 표기식을 후위 표기식으로 변환
string infixToPostfix(const string& infix) {
    stack<char> operators;
    string postfix;
    
    for (char ch : infix) {
        if (isdigit(ch)) {
            postfix += ch;
        } else if (ch == '(') {
            operators.push(ch);
        } else if (ch == ')') {
            while (!operators.empty() && operators.top() != '(') {
                postfix += operators.top();
                operators.pop();
            }
            operators.pop(); // '(' 제거
        } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            while (!operators.empty() && precedence(operators.top()) >= precedence(ch)) {
                postfix += operators.top();
                operators.pop();
            }
            operators.push(ch);
        }
    }
    
    while (!operators.empty()) {
        postfix += operators.top();
        operators.pop();
    }
    
    return postfix;
}

// 중위 표기식을 전위 표기식으로 변환
string infixToPrefix(const string& infix) {
    string reversedInfix = infix;
    reverse(reversedInfix.begin(), reversedInfix.end());
    
    for (char &ch : reversedInfix) {
        if (ch == '(') {
            ch = ')';
        } else if (ch == ')') {
            ch = '(';
        }
    }
    
    string reversedPostfix = infixToPostfix(reversedInfix);
    reverse(reversedPostfix.begin(), reversedPostfix.end());
    return reversedPostfix;
}

// 후위 표기식 계산
int evaluatePostfix(const string& postfix) {
    stack<int> values;
    
    for (char ch : postfix) {
        if (isdigit(ch)) {
            values.push(ch - '0'); // 문자 -> 정수 변환
        } else {
            int b = values.top(); values.pop();
            int a = values.top(); values.pop();
            
            switch (ch) {
                case '+': values.push(a + b); break;
                case '-': values.push(a - b); break;
                case '*': values.push(a * b); break;
                case '/': values.push(a / b); break;
            }
        }
    }
    
    return values.top();
}

// 전위 표기식 계산
int evaluatePrefix(const string& prefix) {
    stack<int> values;
    
    for (int i = prefix.length() - 1; i >= 0; i--) {
        char ch = prefix[i];
        
        if (isdigit(ch)) {
            values.push(ch - '0');
        } else {
            int a = values.top(); values.pop();
            int b = values.top(); values.pop();
            
            switch (ch) {
                case '+': values.push(a + b); break;
                case '-': values.push(a - b); break;
                case '*': values.push(a * b); break;
                case '/': values.push(a / b); break;
            }
        }
    }
    
    return values.top();
}

int main() {
    string infix;
    
    cout << "중위 표기식 입력 (예: (3+4)*5): ";
    cin >> infix;
    
    // 중위 표기식을 후위 표기식으로 변환
    string postfix = infixToPostfix(infix);
    cout << "후위 표기식: " << postfix << endl;
    
    // 중위 표기식을 전위 표기식으로 변환
    string prefix = infixToPrefix(infix);
    cout << "전위 표기식: " << prefix << endl;
    
    // 후위 표기식 계산
    int postfixResult = evaluatePostfix(postfix);
    cout << "후위 표기식 계산 결과: " << postfixResult << endl;
    
    // 전위 표기식 계산
    int prefixResult = evaluatePrefix(prefix);
    cout << "전위 표기식 계산 결과: " << prefixResult << endl;
    
    return 0;
}