[PS] 자료구조와 알고리즘 개념 정리 (Data Structure) Part 1

본 포스팅은 필자가 Problem Solving(PS)를 공부하면서 정리한 포스팅이다.

Data structure

Linked list

연결 리스트(Linked List)는 노드들이 포인터로 연결되어 있는 선형 자료구조이다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있으며, 데이터의 동적 추가 및 삭제가 용이하다.  연결하는 방법 및 개수에 따라 단일 연결 리스트(single linked list), 이중 연결 리스트(double linked list), 원형 연결 리스트(circular linked list)로 구분할 수 있다. 

• 배열과 달리 임의의 원소로 가기 위해서는 첫번째 원소부터 순서대로 방문해야 한다.
• 배열과 달리 메모리 상의 배치가 불연속적이다.
• Overhead : 다음 원소의 주소값을 가지고 있어야 하므로 64비트(=8바이트) 컴퓨터 기준 $8N$ 바이트만큼 추가적인 메모리가 필요하다.
• 손코딩 문제 (출처: BaaarkingDog님 블로그)
  1. 원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 리스트의 길이를 효율적으로 구하는 방법은?
     • 동일한 노드가 나올 떄 까지 계속 다음 노드로 가면 된다. 공간복잡도 $O(1)$, 시간복잡도 $O(N)$
  2. 중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때 만나는 지점을 구하는 방법은?
     • 두 시작점에 대해 각각 끝까지 탐색하여 길이를 구한다. 그 후 두 시작점으로 돌아와서 더 긴쪽을 둘의 차이만큼 앞으로 먼저 이동시켜놓고 두 시작점이 만날 때까지 동시에 한 칸 씩 전진시킨다. 공간복잡도 $O(1)$ 시간복잡도 $O(A+B)$
  3. 주어진 연결 리스트 안에 사이클이 있는지 판단하라.
     • Floyd's circle-finding 알고리즘을 사용한다. 한 칸씩 가는 커서와 두 칸씩 가는 커서를 시작점에서 동시에 출발시키면 사이클이 있을 경우 두 커서는 반드시 만나게 된다. 반대로 사이클이 없으면 두 커서는 연결 리스트의 끝에 도달한다. 공간복잡도 $O(1)$ 시간복잡도 $O(N)$

List 

STL의 list 컨테이너는 이중 연결 리스트(double linked list)이다.

 

Time Complexity

• $k$번째 원소를 확인/변경  $O(k)$
• 임의의 위치에 원소를 추가/제거 $O(1)$

C++ Skeleton Code (Pure)

#include <cstdio>
const int LM=100005;

int dat[LM], pre[LM], nxt[LM];
int unused=1;

void insert(int addr, int num) {
    dat[unused] = num;
    pre[unused] = addr;
    nxt[unused] = nxt[addr];
    if(nxt[addr] != -1) pre[nxt[addr]] = unused;
    nxt[addr] = unused;
    unused++;
}

void erase(int addr) {
    nxt[pre[addr]] = nxt[addr];
    if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}

void traverse() {
    int cur=nxt[0];
    while(cur != -1) {
        printf("%d ", dat[cur]);
        cur = nxt[cur];
    }
    puts("");
}

int main() {
    for(int i=0; i<LM; i++) {  // Initalize to -1
        pre[i] = -1; 
        nxt[i] = -1;
    }
    
    insert(0, 10); traverse();   // 10(addr=1)
    insert(0, 30); traverse();   // 30(addr=2) 10
    insert(2, 40); traverse();   // 30 40(addr=3) 10
    insert(1, 20); traverse();   // 30 40 10 20(addr=4)
    insert(4, 70); traverse();   // 30 40 10 20 70(addr=5)
    
    erase(1); traverse();  // 30 40 20 70
    erase(2); traverse();  // 40 20 70
    erase(4); traverse();  // 40 70
    erase(5); traverse();  // 40
}

C++ Skeleton Code (w/ STL)

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

list<int> L;

void traverse() {
    for(auto l : L) printf("%d ", l);
    puts("");
}

int main() {    
    L = {1, 2};          // 1 2
    auto t = L.begin();  // t는 1을 가리킴
    
    L.push_front(10); traverse(); // 10 1 2
    L.push_back(5); traverse();   // 10 1 2 5
    L.insert(t, 6); traverse();   // 10 6 1 2 5
    t = L.erase(t);               // 1 제거, t가 가리키는 값은 2
    printf("%d", *t);             // 2
}

 

Array

배열(Array)는 메모리 상에 원소를 연속하게 배치한 자료구조를 말한다. C++에서는 배열의 원소가 한 번 정해지면 ( int A[10] ) 이후 크기를 변경하는 것이 일반적으로 불가능하다. 

Vector

STL의 벡터(Vector) 컨테이너를 사용하면 배열과 유사하지만 크기를 가변적으로 사용할 수 있다. 벡터는 가변적인 배열의 역할을 수행하기 때문에 배열을 사용하는 거의 모든 C++ 코드에서 광범위하게 사용된다.

• operator= : 깊은 복사(deep copy)가 발생한다.

Time Complexity

• push_back : 원소를 끝에 추가 $O(1)$
• pop_back : 마지막 원소 제거 $O(1)$
• [], at : 임의의 위치에 원소 확인/변경: $O(1)$
• insert, erase : 임의의 위치에 원소 추가/제거 $O(N)$

C++ Skeleton Code (Pure)

#include <cstdio>

int A[10] = {10, 20, 30};
int len = 3;
  
void insert(int idx, int num) {
    for(int i=len; i>idx; i--) A[i] = A[i-1];
    A[idx] = num;
    len++;
}

void erase(int idx) {
    len--;
    for(int i=idx; i<len; i++) A[i] = A[i+1];
}

void Print() { 
    for(int i=0; i<len; i++) printf("%d ", A[i]); 
    puts(""); 
}


int main() {
  printf("insert test\n");
  insert(3, 40); Print(); // 10 20 30 40
  insert(1, 50); Print(); // 10 50 20 30 40
  insert(0, 15); Print(); // 15 10 50 20 30 40
  
  printf("erase test\n");
  erase(4); Print(); // 15 10 50 20 40 
  erase(1); Print(); // 15 50 20 40 
  erase(3); Print(); // 15 50 20 
}

C++ Skeleton Code (w/ STL)

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

vector<int> A;
  
void Print() { 
    for(int i=0; i<A.size(); i++) printf("%d ", A[i]); 
    puts(""); 
}


int main() {
  A.push_back(10), A.push_back(20), A.push_back(30);
  
  printf("insert test\n");
  A.insert(A.begin()+3, 40); Print(); // 10 20 30 40
  A.insert(A.begin()+1, 50); Print(); // 10 50 20 30 40
  A.insert(A.begin()+0, 15); Print(); // 15 10 50 20 30 40
  
  printf("erase test\n");
  A.erase(A.begin()+4); Print(); // 15 10 50 20 40 
  A.erase(A.begin()+1); Print(); // 15 50 20 40 
  A.erase(A.begin()+3); Print(); // 15 50 20 
}

 

Stack

스택(Stack)은 마지막에 삽입된 요소가 가장 먼저 삭제되는 LIFO(Last In, First Out) 방식의 선형 자료구조이다. 이는 함수의 호출 스택 처리, 수식의 괄호 검사 등에 활용된다. 스택은 제일 상단이 아닌 나머지 원소들의 확인과 변경이 원칙적으로 불가능한 특징이 있다.

Time Complexity

• 원소 추가/제거: $O(1)$
• 제일 상단의 원소 확인: $O(1)$

C++ Skeleton Code (Pure)

#include <cstdio>
constexpr int LM = 1000005;

struct Stack{ 
    int stack[LM];
    int pos=0;
    
    void push(int x) { stack[pos++] = x; }
    void pop() { pos--; }
    int top() { return stack[pos-1]; }

} S;

int main() {
    S.push(5); S.push(4); S.push(3);
    printf("%d\n", S.top());  // 3
    S.pop(); S.pop();
    printf("%d\n", S.top());  // 5
    S.push(10); S.push(12); 
    printf("%d\n", S.top());  // 12
    S.pop();
    printf("%d\n", S.top());  // 10
}

C++ Skeleton Code (w/ STL)

#include <cstdio>
#include <stack>
using namespace std;

stack<int> S;

int main() {
    S.push(5); S.push(4); S.push(3);
    printf("%d\n", S.top());  // 3
    S.pop(); S.pop();
    printf("%d\n", S.top());  // 5
    S.push(10); S.push(12); 
    printf("%d\n", S.top());  // 12
    S.pop();
    printf("%d\n", S.top());  // 10
}

 

Queue

큐(Queue)는 처음 삽입된 요소가 가장 먼저 삭제되는 FIFO(First In, First Out) 방식의 선형 자료구조이다. 운영체제의 작업 스케줄링, 네트워크 요청 처리 등에 사용된다. 큐는 제일 앞/뒤가 아닌 나머지 원소들의 확인과 변경이 원칙적으로 불가능한 특징이 있다.

Time Complexity

• 원소 추가/제거: $O(1)$
• 제일 앞/뒤의 원소 확인: $O(1)$

 

C++ Skeleton Code (Pure)

#include <cstdio>
constexpr int LM = 1000005;

struct Queue{
    int fr=0, re=0;
    int que[LM];

    void push(int x) { que[re++] = x; }
    void pop() { fr++; }
    int front() { return que[fr]; }
    int back() { return que[re-1]; }
} Q;

int main() {
    Q.push(10); Q.push(20); Q.push(30);
    printf("%d %d\n", Q.front(), Q.back());  // 10 30
    Q.pop(); Q.pop();
    Q.push(15); Q.push(25);
    printf("%d %d\n", Q.front(), Q.back());  // 30 25
}

 

C++ Skeleton Code (w/ STL)

#include <cstdio>
#include <queue>
using namespace std;

queue<int> Q;

int main() {
    Q.push(10); Q.push(20); Q.push(30);
    printf("%d %d\n", Q.front(), Q.back());  // 10 30
    Q.pop(); Q.pop();
    Q.push(15); Q.push(25);
    printf("%d %d\n", Q.front(), Q.back());  // 30 25
}

 

Deque

덱(Deque)은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조로, 스택과 큐의 특성을 모두 갖는다. 더 유연한 데이터 처리가 가능해 다양한 알고리즘 구현에 유용하다. 

Time Complexity

• 원소 추가/제거: $O(1)$
• 제일 앞/뒤의 원소 확인: $O(1)$
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능 (하지만 STL deque는 가능)

C++ Skeleton Code (Pure)

#include <cstdio>
constexpr int LM = 1000005;

int deque[2*LM+1];
int fr=LM, re=LM;

void push_front(int x){ deque[--fr] = x; }

void push_back(int x){ deque[re++] = x; }

void pop_front(){ fr++; }

void pop_back(){ re--; }

int front(){ return deque[fr]; }

int back(){ return deque[re-1]; }

int main() {    
     push_back(30);  // [30]
     printf("%d ", front()); printf("%d\n", back());  // 30 30
     push_front(25); // [25 30]
     push_back(12); printf("%d\n", back());  // 12
     push_back(62); // [25 30 12 62]
     pop_front();   // [30 12 62]
     printf("%d\n", front());  // 30
     pop_front();   // [12 62]
     printf("%d\n", back());   // 62
}

C++ Skeleton Code (w/ STL)

#include <cstdio>
#include <deque>
using namespace std;

deque<int> DQ;

int main() {    
     DQ.push_back(30);  // [30]
     printf("%d ", DQ.front()); printf("%d\n", DQ.back());  // 30 30
     DQ.push_front(25); // [25 30]
     DQ.push_back(12); printf("%d\n", DQ.back());  // 12
     DQ.push_back(62); // [25 30 12 62]
     DQ.pop_front();   // [30 12 62]
     printf("%d\n", DQ.front());  // 30
     DQ.pop_front();   // [12 62]
     printf("%d\n", DQ.back());   // 62
}

 

Heap

힙(Heap)은 완전 이진 트리를 기반으로 하는 자료구조로, 각 노드의 값이 자식 노드보다 크거나 같은(최대 힙) 또는 작거나 같은(최소 힙)을 만족한다. 우선순위 큐의 구현에 주로 사용된다.

 

Priority queue

우선순위 큐(Priority Queue)는 원소들이 우선순위에 따라 정렬되며, 우선순위가 가장 높은 원소가 가장 먼저 삭제된다. 힙(Heap)을 사용하여 구현될 수 있으며, 다익스트라 알고리즘 같은 그래프 알고리즘에서 중요하게 사용된다.

 

Hash

해시(Hash)는 키-값 쌍을 저장하는데 사용되며, 해시 함수를 통해 키를 해시 테이블의 주소로 변환하여 데이터를 효율적으로 조회, 삽입, 삭제할 수 있다. 빠른 데이터 검색에 유리하다.

 

Tree

트리(Tree)는 계층적 관계를 표현하는 비선형 자료구조로, 노드와 노드를 연결하는 엣지로 구성된다. 이진 트리, AVL 트리, 레드-블랙 트리 등 다양한 형태가 있으며, 계층적 데이터를 관리하는데 적합하다.

 

Graph

그래프(Graph)는 노드(정점)들과 이를 연결하는 엣지(간선)들로 구성된 자료구조이다. 방향성, 가중치 유무에 따라 다양한 종류가 있으며, 네트워크 구조, 경로 찾기 등에 사용된다.

 

 

Set

Set은 중복되지 않는 유일한 요소들의 집합을 말한다. 이는 자료의 중복을 허용하지 않는 모든 경우에 유용하게 사용된다.

 

Map

Map은 키-값 쌍으로 데이터를 저장하는 자료구조로, 각 키는 유일하며 이를 통해 값을 조회할 수 있다. 데이터의 효율적인 저장과 검색에 쓰인다.

 

References

[1] (Blog) 알고리즘 문제풀이(PS) 시작하기 - plzrun

[2] (Blog) 내가 문제풀이를 연습하는 방법 - koosaga

[3] (Blog) 코드포스 블루, 퍼플 달성 후기 및 일지 & 공부법 - Rebro

[4] (Blog) PS를 공부하는 방법 (How to study Problem Solving?) - subinium

[5] (Site) Baejoon Online Judge

[6] (Site) JungOl

[7] (Site) SW Expert Academy

[8] (Blog) BaaaaaaaarkingDog의 강좌/실전 알고리즘

[9] (Youtube) BaaaaaaaarkingDog의 강좌/실전 알고리즘

[10] (Site) C++ 유용한 기능들