c++ 자료구조의 적절한 활용방안

이미리·2023년 6월 25일

boj_Algorithm

목록 보기

17/25

백준을 풀던 도중 같은 로직을 사용하였는데도 불구하고, list를 썼을 땐 통과가 되는데 vector를 이용해 구현을 하면 시간 초과가 나는 걸 발견했다. 이런 문제는 꽤나 많이 겪어왔는데, 머리 속에서는 정리가 안 되었다는 생각이 들었다. 그럼 정확히 언제 무엇을 써야 효율적인지 정리해보겠다. ~~2학년 자료구조 시간에 배운 것 같은데 제대로 기억이 안난다.^^~~

(아래의 내용은 챗 지피티와 함께 합니다..)

1. 스택(Stack):

후입선출(LIFO) 구조의 자료구조입니다.
요소들이 순서대로 쌓이고, 가장 위의 요소에만 접근할 수 있습니다.
주로 임시 데이터 저장, 함수 호출 시 로컬 변수 저장, 괄호 짝 맞추기 등에 사용됩니다.
C++에서는 std::stack 컨테이너 어댑터를 사용하여 구현할 수 있습니다.

2. 큐(Queue):

선입선출(FIFO) 구조의 자료구조입니다.
요소들이 순서대로 삽입되고, 가장 앞의 요소에만 접근할 수 있습니다.
주로 작업 대기열, 이벤트 처리, 너비 우선 탐색(BFS) 등에 사용됩니다.
C++에서는 std::queue 컨테이너 어댑터를 사용하여 구현할 수 있습니다.

3. 덱(Deque):

양쪽 끝에서의 삽입과 삭제가 모두 가능한 자료구조입니다.
요소들이 양쪽 끝에 추가되거나 삭제될 수 있습니다.
주로 큐와 스택의 특징을 모두 사용해야 할 때, 덱을 사용합니다.
C++에서는 std::deque 컨테이너를 사용하여 구현할 수 있습니다.

4. 리스트(List):

순서가 있는 요소들의 집합을 저장하는 자료구조입니다.
요소들이 링크로 연결되어 있으며, 임의 위치에서의 삽입과 삭제가 가능합니다.
주로 중간 삽입/삭제가 빈번하거나 반복자의 유효성이 유지되어야 할 때 사용합니다.
C++에서는 std::list 컨테이너를 사용하여 구현할 수 있습니다.

5. 벡터(Vector):

동적 배열로 구현된 자료구조입니다.
배열과 유사한 구조이며, 요소들이 연속적으로 저장됩니다.
임의 위치에서의 삽입과 삭제는 비효율적이지만, 인덱스를 통한 빠른 접근이 가능합니다.
주로 데이터의 순차적인 접근과 빠른 임의 접근이 필요한
경우 사용합니다.
C++에서는 std::vector 컨테이너를 사용하여 구현할 수 있습니다.

6. 맵(Map):

키-값 쌍으로 이루어진 자료구조입니다.
각 요소는 고유한 키(Key)를 가지며, 키를 통해 값을 검색하고 저장합니다.
주로 검색 기능이 필요한 경우 사용하며, 키의 정렬 또는 중복을 허용하지 않는 경우에 사용됩니다.
C++에서는 std::map 컨테이너를 사용하여 구현할 수 있습니다.

7. 세트(Set):

중복을 허용하지 않는 요소들의 집합을 저장하는 자료구조입니다.
요소들이 정렬된 상태로 저장되며, 검색과 삽입이 빠르게 이루어집니다.
주로 중복을 제거하고 유일한 값만을 유지해야 할 때 사용됩니다.
C++에서는 std::set 컨테이너를 사용하여 구현할 수 있습니다.

이러한 자료구조들은 각각의 특징과 사용 목적에 따라 적합한 상황이 다릅니다. 예를 들어, 스택은 함수 호출과 관련된 임시 데이터 저장에 사용되고, 큐는 작업 대기열 등 순차적인 처리가 필요한 상황에 사용될 수 있습니다. 덱은 양쪽 끝에서의 삽입과 삭제가 필요한 경우에 유용하며, 리스트는 중간 삽입과 삭제가 빈번한 경우에 유용합니다. 벡터는 순차적인 접근과 빠른 임의 접근이 필요한 경우에 사용되며, 맵은 키-값 쌍을 검색하기 위해 사용됩니다. 세트는 중복을 제거하고 유일한 값만을 유지해야 할 때 사용됩니다.

자료구조의 선택은 주어진 문제의 특성과 요구사항에 따라 달라지므로, 문제를 분석하고 필요한 기능과 성능을 고려하여 적절한 자료구조를 선택하는 것이 중요합니다.

위의 내용을 통해서 왜 vector를 사용했을 때 timeover가 발생했는지 알 수 있었다. vector의 경우 임의 위치에서의 삽입과 삭제가 느리기 때문에 임의 위치 삽입, 삭제를 사용할 땐 list가 적절한 자료구조라는 것이다. vector를 애용하는 나로써는 잘 알아두어야 할 특성인 것 같다. 참고로 접근 자체는 빠르다고 하니 헷갈리지 말자!

관련문제: 키로거(boj5397)

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

int main() {
    vector<char> v;
    auto v_idx = v.begin();  // v가 비어있을 경우에도 v_idx를 초기화할 수 있도록 수정
    int n;
    string s;
    cin >> n;
    while (n--) {
        v.clear();
        v_idx = v.begin();
        cin >> s;

        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '<') {
                if (v.begin() != v_idx) {
                    v_idx--;
                }
            } else if (s[i] == '>') {
                if (v.end() != v_idx) {
                    v_idx++;
                }
            } else if (s[i] == '-') {
                if (v_idx != v.begin()) {
                    v_idx = v.erase(--v_idx);
                }
            } else {
                v_idx = v.insert(v_idx, s[i]) + 1;
            }
        }
        for (v_idx = v.begin(); v_idx != v.end(); v_idx++) cout << *v_idx;
        cout << '\n';
    }
}

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

int main() {
    list<char> v;
    auto v_idx = v.begin();  // v가 비어있을 경우에도 v_idx를 초기화할 수 있도록 수정
    int n;
    string s;
    cin >> n;
    while (n--) {
        v.clear();
        v_idx = v.begin();
        cin >> s;

        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '<') {
                if (v.begin() != v_idx) {
                    v_idx--;
                }
            } else if (s[i] == '>') {
                if (v.end() != v_idx) {
                    v_idx++;
                }
            } else if (s[i] == '-') {
                if (v_idx != v.begin()) {
                    v_idx = v.erase(--v_idx);
                }
            } else {
                v.insert(v_idx, s[i]);
            }
        }
        for (v_idx = v.begin(); v_idx != v.end(); v_idx++) cout << *v_idx;
        cout << '\n';
    }
}