CS study - 자료구조 - 1

 

자료구조

효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합

1. 복잡도

1-1 시간 복잡도

시간 복잡도란 ‘문제를 해결하는 데 걸리는 시간과 입력의 함수 관계’를 가리킵니다. 어떠한 알고리즘의 로직이 ‘얼마나 오랜 시간’이 걸리는지를 나타내는 데 쓰입니다.

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.next();
        System.out.println(a + "In");
    }
}

시간복잡도에는 평균과 최악의 시간복잡도를 고려하면서 씁니다.

• 자료 구조의 평균 시간 복잡도자료구조 접근 탐색 삽입 삭제

  배열	O(1)	O(n)	O(n)	O(n)
  스택(stack)	O(n)	O(n)	O(1)	O(1)
  큐(queue)	O(n)	O(n)	O(1)	O(1)
  이중 연결 리스트(doubly linked list)	O(n)	O(n)	O(1)	O(1)
  해시테이블(hash table)	O(1)	O(1)	O(1)	O(1)
  이진 탐색 트리(BST)	O(logn)	O(logn)	O(logn)	O(logn)
  AVL 트리	O(logn)	O(logn)	O(logn)	O(logn)
  레드 블랙 트리	O(logn)	O(logn)	O(logn)	O(logn)

• 자료구조의 최악의 시간 복잡도자료구조 접근 탐색 삽입 삭제

  배열	O(1)	O(n)	O(1)	O(1)
  스택(stack)	O(n)	O(n)	O(1)	O(1)
  큐(queue)	O(n)	O(n)	O(1)	O(1)
  이중 연결 리스트(doubly linked list)	O(n)	O(n)	O(1)	O(1)
  해시테이블(hash table)	O(n)	O(n)	O(n)	O(n)
  이진 탐색 트리(BST)	O(n)	O(n)	O(n)	O(n)
  AVL 트리	O(logn)	O(logn)	O(logn)	O(logn)
  레드 블랙 트리	O(logn)	O(logn)	O(logn)	O(logn)

이 시간 복잡도를 수치화하듯 나타낼 때 흔히 쓰이는 게 바로 ‘빅오표기법’입니다.

빅오표기법 (big O)

O(1), O(n), O(n2)등 알고리즘의 속도를 측정할 때 쓰입니다.

for (int i = 0; i < 10; i++) {
    for (int j = 0; j < n; j += t) {
        for (int k = 0; k < n; k++) {
            if (true) {
                System.out.println(k + "In");
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (true) {
            System.out.println(i + "In");
        }
    }
}

1-2 공간 복잡도

공간 복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말합니다. 정적 변수로 선언된 것 말고도 재귀함수로 인해 생긴 공간을 계속해서 필요로 할 경우등도 포함됩니다.

---

2. 선형 자료 구조

선형 자료구조 란 요소가 일렬로 나열되어 있는 자료 구조를 말합니다.

2-1 연결 리스트

데이터를 감싼 노드를 포인터로 연결해서 공간적은 효율성을 극대화시킨 자료구조 입니다. 삽입과 삭제가 O(1)이 걸리며, 탐색에는 O(n)만큼 걸립니다.

• 싱글 연결 리스트 : next 포인터만 가집니다.
• 이중 연결 리스트 : next 포인터와 prev 포인터를 가집니다.
• 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것을 의미합니다.

2-2 배열

배열은 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합입니다. 또한 중복을 허용하며 순서가 있습니다.

‘정적 배열’을 기반으로 설명하며, 탐색에 O(1) 이 되어 랜덤 접근이 가능합니다. 삽입과 삭제는 O(n)이 걸립니다. 따라서 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열로 하는 것이 좋습니다.

랜덤 접근과 순차적 접근

랜덤 접근(직접 접근)은 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능입니다. 이는 데이터를 저장된 순서대로 검색해야 하는 순차적 접근과는 반대입니다.

 

 

 

배열과 연결 리스트 비교

배열은 상자를 순서대로 나열한 데이터 구조이며 인덱스만 알면 바로 데이터를 꺼낼 수 있습니다.

연결 리스트는 상자를 선으로 연결한 형태의 데이터 구조이며, 상자 안의 요소를 알기 위해서는 하나씩 상자 내부를 확인해봐야 한다는 점이 다릅니다.

 

 

 

위 구조로 보이듯 배열은 빠르고 연결 리스트는 보다 느립니다. 배열의 경우 그저 상자의 요소를 탐색하면 되는 반면에 연결 리스트는 요소안을 열어봐야하고 주어진 선을 기반으로 순차 탐색해야 합니다.

하지만 데이터 추가 및 삭제의 경우 연결 리스트가 더 빠르고 배열은 느립니다. 배열은 모든 상자를 앞으로 옮겨야가능하지만 연결 리스트는 선을 바꿔서 연결해주기만 하면 되기 때문입니다.

public class Main {
    public static void main(String[] args) {
        int[] a = new int[10];
        for (int i = 0; i < 10; i++) {
            a[i] = i;
        }
        for (int it : a) {
            System.out.print(it + " ");
        }
        System.out.println("In");
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> a = new LinkedList<>();
        for (int i = 0; i < 10; i++) {
            a.add(i);
        }
        for (int i = 0; i < 10; i++) {
            a.add(0, i);
        }
        ListIterator<Integer> it = a.listIterator();
        it.next();
        it.add(1000);
        for (int it : a) {
            System.out.print(it + " ");
        }
        System.out.println();

        a.remove(0);
        a.remove(a.size() - 1);
        for (int it : a) {
            System.out.print(it + " ");
        }
        System.out.println();
    }
}

2-3 벡터

동적으로 요소를 할당할 수 있는 동적 배열입니다. 컴파일 시점에 개수를 모른다면 벡터를 써야 합니다. 중복을 허용하며 순서가 있고 랜덤 접근이 가능합니다. 탐색과 맨 뒤의 요소를 삭제하거나 삽입하는데 **O(1)**이 걸리며, 맨 뒤나 앞이 아닌 요소를 삭제하고 삽입할 때는 **O(n)**의 시간이 걸립니다.

• 뒤에서부터 삽입하는 push_back()의 경우는 O(1)이 걸립니다.
• 벡터의 크기가 증가되는 시간 복잡도가 amortized(상수 시간) 복잡도 와 유사한 시간복잡도입니다.

import java.util.*;
public class Main {
    public static void main(String[] args) {
        List<Integer> v = new ArrayList<>();
        for (int i = 1; i <= 10; i++) v.add(i);
        for (int a : v) System.out.print(a + " ");
        System.out.println("In");
        v.remove(v.size()-1);
        for (int a : v) System.out.print(a + " ");
        System.out.println("In");
        v.subList(0, 1).clear();
        for (int a : v) System.out.print(a + " ");
        System.out.println("In");
        int idx = v.indexOf(100);
        if (idx == -1) System.out.println("not found");
        Collections.fill(v, 10);
        for (int a : v) System.out.print(a + " ");
        System.out.println("In");
        v.clear();
        for (int a : v) System.out.print(a + " ");
        System.out.println("In");
    }
}

• c++ 함수 → java 함수
  • push_back() → java List 의 add() : 뒤부터 요소를 더함
  • pop_back() → java List 의 remove() : 뒤부터 삭제
  • erase() → java List의 subList() 리스트의 지정 범위의 요소를 반환**, clear()** 리스트를 비움 : 삭제
  • find() → java List의 indexOf() : 찾기
  • clear() → java List의 clear() 동일하다 : 초기화

2-4 스택 stack

스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질 (LIFO, Last In First Out)을 가진 자료구조 입니다. 스택은 보통 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방순 기록등에 쓰입니다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸립니다.

 

 

 

 

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

				for (int i = 0; i < 10; i++) {
            stack.push(i);
        }

        System.out.println("Stack: " + stack);

        while (!stack.empty()) {
            System.out.print(stack.peek() + " ");
            stack.pop();
        }
        int top = stack.pop();
        System.out.println("Popped element: " + top)

        int peeked = stack.peek();
        System.out.println("Peeked element: " + peeked);
    }
}

2-5 큐 queue

큐는 먼저 집어넣은 데이터가 먼저 나오는 성질 (FIFO, First In First Out)을 지닌 자료구조이며 먼저 삽입한 데이터가 먼저 나오는 구조로 스택과는 반대되는 개념을 가졌습니다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸립니다.

큐가 자주 쓰이는 곳은 CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 대기하는 행렬, 너비 우선 탐색, 캐시등에 사용됩니다.

 

 

 

 

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < 10; i++) {
            queue.add(i);
        }

        while (!queue.isEmpty()) {
            System.out.print(queue.peek() + " ");
            queue.remove();
        }
    }
}