[실전 알고리즘] 0x04강

[실전 알고리즘] 0x04강 - 연결 리스트

2022. 1. 21. 17:34ㆍAlgorithm/1강

1. 정의와 성질

연결 리스트 - 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조

연결 리스트의 성질

1. k번째 원소를 찾기 위해 O(k)의 시간이 필요

2. 임의의 위치에 원소 추가/제거 O(1)

3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

연결 리스트의 종류

1. 단일 연결 리스트(Singly Linked List)

2. 이중 연결 리스트(Doubly Linked List)

3. 원형 연결 리스트(Circular Linked List)

배열 vs 연결 리스트

	배열	연결 리스트
k번째 원소의 접근	O(1)	O(k)
임의 위치에 원소 추가/제거	O(N)	O(1)
메모리 상의 배치	연속	불연속
추가적으로 필요한 공간(Overhead)	-	O(N)

overhead를 생각해보면 배열은 데이터만 저장하면 될 뿐 딱히 추가적으로 필요한 공간이 없다. 굳이 따지면 길이 정보를 저장할 int 1개가 필요할 수 있지만 이건 너무 미미하니 신경을 쓸 필요가 없을 정도. 그런데 연결 리스트에서는 각 원소가 다음 원소, 혹은 이전과 다음 원소의 주소값을 가지고 있어야 한다. 그래서 32비트 컴퓨터면 주소값이 32비트(=4바이트) 단위이니 4N 바이트가 추가로 필요하고, 64비트 컴퓨터라면 주소값이 64비트(=8바이트) 단위이니 8N 바이트가 추가로 필요하다. 즉 N에 비례하는 만큼의 메모리를 추가로 쓰게 된다.

2. 기능과 구현

기능

1. 임의의 위치에 있는 원소를 확인/변경 = O(N)

2. 임의의 위치에 있는 원소 추가/제거 = O(1)

구현

struct NODE {
  struct NODE *prev, *next;
  int data;
};

연결 리스트의 정석적인 구현은 위의 코드처럼 NODE 구조체나 클래스를 만들어서 원소가 생성될 때 동적할당을 하는 방식이다. 코딩테스트에서는 그냥 STL list를 활용하면 된다. 그런데 코딩테스트에서 STL을 허용하지 않는다면 직접 연결 리스트를 구현해야 한다. 아래는 바킹독님이 구현한 정석이 아닌 야매로 구현한 방식의 연결 리스트다.

const int MX = 1000005;
int dat[MX], pre[MX], nxt[PX];
int unused = 1;

fill(pre, pre+MX, -1);
fill(nxt, nxt+MX, -1);

구현에 필요한 변수들을 보면 dat[i]는 i번지 원소의 값, pre[i]는 i번지 원소에 대해 이전 원소의 인덱스, nxt[i]는 다음 원소의 인덱스입니다. pre나 nxt의 값이 -1이면 해당 원소의 이전/다음 원소가 존재하지 않는다는 의미입니다. unused는 현재 사용되지 않는 인덱스, 즉 새로운 원소가 들어갈 수 있는 인덱스이고 원소가 추가된 이후에는 1씩 증가될 것입니다. 그리고 특별히 0번지는 연결 리스트의 시작 원소로 고정되어 있습니다. 달리 말하면 0번지는 값이 들어가지 않고 단지 시작점을 나타내기 위한 dummy node입니다.

지금 코드 상에는 별도로 길이 정보를 두지 않았지만 길이가 필요하다면 따로 len 변수를 두고 원소가 추가될 때 1 증가시키고 제거될 때 1 감소시키면 됩니다.

traverse 함수

void traverse(){
  int cur = nxt[0];
  while(cur != -1){
    cout << dat[cur] << ' ';
    cur = nxt[cur];
  }
  cout << "\n\n";
}

insert 함수 구현 알고리즘

1. 새로운 원소를 생성

2. 새 원소의 pre 값에 삽입할 위치의 주소를 대입

3. 새 원소의 nxt 값에 삽입할 위치의 nxt 값을 대입

4. 삽입할 위치의 nxt 값과 삽입할 위치의 다음 원소의 pre 값을 새 원소로 변경

5. unused 1 증가

erase 함수 구현 알고리즘

1. 이전 위치의 nxt를 삭제할 위치의 nxt로 변경

2. 다음 위치의 pre를 삭제할 위치의 pre로 변경

전체 코드

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

const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
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)
    {
        cout << dat[cur] << ' ';
        cur = nxt[cur];
    }
    cout << "\n\n";
}

void insert_test()
{
    cout << "****** insert_test *****\n";
    insert(0, 10); // 10(address=1)
    traverse();
    insert(0, 30); // 30(address=2) 10
    traverse();
    insert(2, 40); // 30 40(address=3) 10
    traverse();
    insert(1, 20); // 30 40 10 20(address=4)
    traverse();
    insert(4, 70); // 30 40 10 20 70(address=5)
    traverse();
}

void erase_test()
{
    cout << "****** erase_test *****\n";
    erase(1); // 30 40 20 70
    traverse();
    erase(2); // 40 20 70
    traverse();
    erase(4); // 40 70
    traverse();
    erase(5); // 40
    traverse();
}

int main(void)
{
    fill(pre, pre + MX, -1);
    fill(nxt, nxt + MX, -1);
    insert_test();
    erase_test();
}

3. STL list

list 사용법

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

int main(void) {
  list<int> L = {1,2}; // 1 2
  list<int>::iterator t = L.begin(); // t는 1을 가리키는 중
  L.push_front(10); // 10 1 2
  cout << *t << '\n'; // t가 가리키는 값 = 1을 출력
  L.push_back(5); // 10 1 2 5
  L.insert(t, 6); // t가 가리키는 곳 앞에 6을 삽입, 10 6 1 2 5
  t++; // t를 1칸 앞으로 전진, 현재 t가 가리키는 값은 2
  t = L.erase(t); // t가 가리키는 값을 제거, 그 다음 원소인 5의 위치를 반환
                  // 10 6 1 5, t가 가리키는 값은 5
  cout << *t << '\n'; // 5
  for(auto i : L) cout << i << ' ';
  cout << '\n';
  for(list<int>::iterator it = L.begin(); it != L.end(); it++)
    cout << *it << ' ';
}

push_back, pop_back, push_front, pop_front - O(1)

list::iterator 타입을 치기가 너무 귀찮으면 auto t = L.begin()도 가능하다.

erase는 제거한 다음 원소의 위치를 반환한다.

순회를 할 때는 C++11 이상이면 range-based for loop를 사용하면 되지만 그게 되지 않을 때는 맨 아래의 for 문이나 auto 타입을 사용하면 된다.

4. 연습 문제

BOJ 1406번 : 에디터

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s;
    int n;
    cin >> s >> n;
    list<char> L;

    for (auto c : s)
    {
        L.push_back(c);
    }

    auto cursor = L.end();

    for (int i = 0; i < n; i++)
    {
        char opt, c;
        cin >> opt;
        switch (opt)
        {
        case 'L':
            if (cursor != L.begin())
            {
                cursor--;
            }
            break;
        case 'D':
            if (cursor != L.end())
            {
                cursor++;
            }
            break;
        case 'B':
            if (cursor != L.begin())
            {
                cursor--;
                cursor = L.erase(cursor);
            }
            break;
        case 'P':
            cin >> c;
            L.insert(cursor, c);
            break;
        default:
            break;
        }
    }
    for (auto c : L)
    {
        cout << c;
    }
    return 0;
}

위의 코드를 더 정리하면 아래 코드와 같다. 아스키코드를 이용해서 switch 문의 긴 코드를 freq[c-'a']++; 한 줄로 바꿀 수 있다.

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


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int freq[26] = {0,};
    string s;
    cin >> s;
    for (auto c:s){
        freq[c-'a']++;
    }
    for (int i = 0; i < 26; i++){
        cout << freq[i] << " ";
    }

    return 0;
}

Q1. 원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법?

A1. 동일한 노드가 나올 때까지 계속 다음 노드로 가면 된다. 공간복잡도 O(1), 시간복잡도 O(N)

Q2. 중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때 만나는 지점을 구하는 방법은?

A2. 일단 두 시작점 각각에 대해 끝까지 진행시켜서 각각의 길이를 구한다. 그 후에 다시 두 시작점으로 돌아아서 더 긴 쪽을 둘의 차이만큼 앞으로 먼저 이동시켜놓고 두 시작점이 만날 때까지 두 시작점을 동시에 한 칸씩 전진시키면 된다. 공간복잡도 O(1), 시간복잡도 O(A+B)

Q3. 주어진 연결 리스트 안에 사이클이 있는지 판단하라

A3. Floyd's cycle-finding algorithm, 공간복잡도 O(1), 시간복잡도 O(N)

Floyd's cycle-finding algorithm이라는 이름이 붙어있는 알고리즘으로 해결이 가능한데, 한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발시키면 사이클이 있을 경우 두 커서는 반드시 만나게 됩니다. 반대로 만약 사이클이 없으면 두 커서가 만나지 못하고 연결 리스트의 끝에 도달합니다.

참고자료