-1은 빈 리스트를 의미 head는 머리 노드의 인덱스 e[]는 특정 위치의 값, 인덱스는 노드의 위치 ne[]는 다음 포인터 idx는 현재까지 사용된 노드의 인덱스 단일 연결 리스트

단일 연결 리스트에서 idx는 삽입된 순서가 아니라, 현재까지 할당된 노드 번호를 나타냄

#include <iostream>

using namespace std;

const int N = 100010;

int head, e[N], ne[N], idx;

void init() {
    head = -1;
    idx = 0;
}

void add_to_head(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

void add(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

void remove(int k) {
    ne[k] = ne[ne[k]];
}

int main() {
    int m;
    cin >> m;
    init();

    while (m--) {
        char op;
        cin >> op;
        if (op == 'H') {
            int x;
            cin >> x;
            add_to_head(x);
        } else if (op == 'D') {
            int k;
            cin >> k;
            if (k == 0) head = ne[head];
            else remove(k - 1);
        } else {
            int k, x;
            cin >> k >> x;
            add(k - 1, x);
        }
    }

    for (int i = head; i != -1; i = ne[i]) 
        cout << e[i] << ' ';
    cout << endl;

    return 0;
}

이중 연결 리스트

#include <iostream>

using namespace std;

const int N = 100010;

int m, e[N], l[N], r[N], idx;

void insert(int k, int x) {
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx++;
}

void remove(int k) {
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

int main() {
    cin >> m;
    r[0] = 1;
    l[1] = 0;
    idx = 2;

    while (m--) {
        string op;
        cin >> op;
        int k, x;
        if (op == "L") {
            cin >> x;
            insert(0, x);
        } else if (op == "R") {
            cin >> x;
            insert(l[1], x);
        } else if (op == "D") {
            cin >> k;
            remove(k + 1);
        } else if (op == "IL") {
            cin >> k >> x;
            insert(l[k + 1], x);
        } else {
            cin >> k >> x;
            insert(k + 1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i])
        cout << e[i] << ' ';
    cout << endl;

    return 0;
}

스택을 이용한 수식 계산

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

using namespace std;

stack<int> nums;
stack<char> ops;
unordered_map<char, int> priority{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

void evaluate() {
    int b = nums.top(); nums.pop();
    int a = nums.top(); nums.pop();
    char op = ops.top(); ops.pop();
    int result;
    switch (op) {
        case '+': result = a + b; break;
        case '-': result = a - b; break;
        case '*': result = a * b; break;
        case '/': result = a / b; break;
    }
    nums.push(result);
}

int main() {
    string expression;
    cin >> expression;

    for (int i = 0; i < expression.size(); ++i) {
        char c = expression[i];
        if (isdigit(c)) {
            int num = 0;
            int j = i;
            while (j < expression.size() && isdigit(expression[j]))
                num = num * 10 + expression[j++] - '0';
            i = j - 1;
            nums.push(num);
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (ops.top() != '(')
                evaluate();
            ops.pop();
        } else {
            while (!ops.empty() && ops.top() != '(' && 
                   priority[ops.top()] >= priority[c])
                evaluate();
            ops.push(c);
        }
    }

    while (!ops.empty())
        evaluate();

    cout << nums.top() << endl;
    return 0;
}

단조 스택 문제 해결

#include <iostream>
using namespace std;

const int N = 100005;
int n, q[N], top;

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

    cin >> n;
    int x;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        while (top > 0 && q[top] >= x)
            --top;
        if (top > 0)
            cout << q[top] << ' ';
        else
            cout << "-1 ";
        q[++top] = x;
    }
    return 0;
}

단조 큐를 활용한 최소값 찾기

#include <iostream>
using namespace std;

const int N = 1000010;

int a[N], q[N];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);

    int hh = 0, tt = -1;
    for (int i = 0; i < n; ++i) {
        if (hh <= tt && i - k + 1 > q[hh])
            ++hh;
        while (hh <= tt && a[q[tt]] >= a[i])
            --tt;
        q[++tt] = i;
        if (i >= k - 1)
            printf("%d ", a[q[hh]]);
    }
    puts("");

    hh = 0, tt = -1;
    for (int i = 0; i < n; ++i) {
        if (hh <= tt && i - k + 1 > q[hh])
            ++hh;
        while (hh <= tt && a[q[tt]] <= a[i])
            --tt;
        q[++tt] = i;
        if (i >= k - 1)
            printf("%d ", a[q[hh]]);
    }
    puts("");
    return 0;
}

해시 테이블 시뮬레이션

#include <cstring>
#include <iostream>
using namespace std;

const int N = 100003;

int h[N], e[N], ne[N], idx;

void insert(int x) {
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool find(int x) {
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x)
            return true;
    return false;
}

int main() {
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);

    while (n--) {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I')
            insert(x);
        else
            puts(find(x) ? "Yes" : "No");
    }
    return 0;
}

또 다른 해시 테이블 구현 (오픈 어드레싱)

#include <cstring>
#include <iostream>
using namespace std;

const int N = 200003, INF = 0x3f3f3f3f;

int h[N];

int find(int x) {
    int t = (x % N + N) % N;
    while (h[t] != INF && h[t] != x) {
        t++;
        if (t == N) t = 0;
    }
    return t;
}

int main() {
    memset(h, 0x3f, sizeof h);
    int n;
    scanf("%d", &n);

    while (n--) {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I')
            h[find(x)] = x;
        else
            puts(h[find(x)] == INF ? "No" : "Yes");
    }
    return 0;
}

최장 증가 부분수열 구하기 (이진 탐색 기법)

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

const int N = 100010;
int n, a[N], q[N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);

    int len = 0;
    for (int i = 0; i < n; ++i) {
        int left = 0, right = len;
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (q[mid] < a[i])
                left = mid;
            else
                right = mid - 1;
        }
        len = max(len, right + 1);
        q[right + 1] = a[i];
    }
    printf("%d\n", len);
    return 0;
}

그리디 기법을 활용한 최장 증가 부분수열

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

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i)
        cin >> arr[i];

    vector<int> stk;
    stk.push_back(arr[0]);

    for (int i = 1; i < n; ++i) {
        if (arr[i] > stk.back())
            stk.push_back(arr[i]);
        else
            *lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i];
    }

    cout << stk.size() << endl;
    return 0;
}