자료구조

기술노트
Admin (토론 | 기여)님의 2025년 4월 17일 (목) 14:23 판 (CS 용어 정리 - 자료구조 추가)
(차이) ← 이전 판 | 최신판 (차이) | 다음 판 → (차이)

자료구조

> data structure는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 말한다.

![image](https://user-images.githubusercontent.com/65716445/220313454-3f6e765e-2a91-4ee4-bb9f-bda0f41e7f7a.png)

💡 빅오 표기법

  • 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용
  • 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것
  • Big-O로 측정되는 복잡성에는 시간과 공간복잡도가 있다.
 - 시간복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다.
 - 공간복잡도는 알고리즘이 실행될때 사용하는 메모리의 양을 나타낸다.요즘에는 데이터를 저장할 수 있는 메모리의 발전으로 중요도가 낮아졌다.
  • Big-O의 복잡도를 나타내는 표

![image](https://user-images.githubusercontent.com/65716445/220313526-fafe3a30-ba3e-445e-aa07-d820d056a186.png)

💡 시간 복잡도

  • 알고리즘의 성능을 설명하는 것
  • 알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화 한것

시간복잡도에서 가장 큰 영향을 미치는 n의 단위

1             O(1)   --> 상수
2n + 20       O(n)   --> n이 가장 큰영향을 미친다.
3n^2          O(n^2) --> n^2이 가장 큰영향을 미친다.

시간복잡도의 문제해결 단계

O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.

💡 공간 복잡도

  • 공간 복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
  • `총 공간 요구 = 고정 공간 요구 + 가변 공간 요구`
  • 고정 공간은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)
  • 가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간, 그러니까 동적으로 필요한 공간
bash
int a[1004];// a 배열은 1004 x 4 바이트의 크기를 가지게 된다.

💡 자료구조의 시간 복잡도

![image](https://user-images.githubusercontent.com/65716445/220313575-48a8649f-e62f-407a-a43d-c6b11a904728.png)

선형 자료 구조

> 요소가 일렬로 나열되어 있는 자료 구조

💡 Array vs Linked List

💡 Array

  • 가장 기본적인 자료구조
  • 논리적 저장 순서와 물리적 저장 순서가 일치
  • 인덱스(index)로 해당 원소(element)에 접근할 수 있다.
 → 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다.
 → 즉 random access 가 가능하다는 장점

BUT

  • 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤 (O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에 시간이 더 걸린다.
  • 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉 빈 공간이 생긴다.
  • 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 O(n)가 된다.
  • 그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 time complexity 의 worst case 는 O(n)이 된다.
  • 삽입의 경우도 마찬가지이다. 만약 첫번째 자리에 새로운 원소를 추가하고자 한다면 모든 원소들의 인덱스를 1 씩 shift 해줘야 하므로 이 경우도 O(n)의 시간을 요구하게 된다.

💡 Linked List

  • 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조

![image](https://user-images.githubusercontent.com/65716445/220313664-42c7fbe5-8fd8-4b27-8d40-e480e9d08562.png)

  • prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것
  • 단순 연결 리스트 : next 포인터만 가진다.
  • 원형 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것을 말한다.
  • 이중 연결 리스트 : next 포인터와 prev 포인터를 가진다.

---

  • 배열의 문제점을 해결하기 위한 자료구조가 linked list
  • 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다.
  • 따라서 이 부분만 다른 값으로 바꿔주면 삭제와 삽입O(1) 만에 해결할 수 있는 것이다.

BUT

  • 하지만 Linked List 역시 한 가지 문제가 있다.
  • 원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search 과정에 있어서 첫번째 원소부터 다 확인해봐야 한다는 것이다. Array 와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문이다. 이것은 일단 삽입하고 정렬하는 것과 마찬가지이다.
  • 이 과정 때문에, 어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해서(탐색) O(n)의 시간이 추가적으로 발생하게 된다.
  • 결국 linked list 자료구조는 search 에도 O(n)의 time complexity 를 갖고, 삽입, 삭제에 대해서도 O(n)의 time complexity 를 갖는다.

→ 그렇다고 해서 아주 쓸모없는 자료구조는 아니기에, 우리가 학습하는 것이다. 이 Linked List 는 Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다. ![image](https://user-images.githubusercontent.com/65716445/220313718-6e97f38d-8a78-402e-ac7b-5d4107c42d72.png)

<배열과 연결 리스트 비교>

<aside>

배열 탐색 O(1) | 삽입, 삭제 O(n) 연결 리스트 → 탐색 O(n) | 삽입, 삭제 O(1)

</aside>

_배열은 상자를 순서대로 나열한 데이터 구조이며 몇 번째 상자인지만 알면 해당 상자의 요소를 끄집어낼 수 있다._

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

_탐색은 배열이 빠르고 연결 리스트는 느리다. 배열의 경우 그저 상자 위에 있는 요소를 탐색하면 되는 반면에, 연결 리스트는 상자를 열어야 하고 주어진 선을 기반으로 순차적으로 열어야 한다._

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

_따라서 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열로 하는 것이 좋다._

💡Vector

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

💡 Stack and Queue

![image](https://user-images.githubusercontent.com/65716445/220313771-ab8237c5-34a1-4e49-b48b-22ae167c90eb.png)

💡 Stack

  • 선형 자료구조의 일종으로 `Last In First Out (LIFO)` . 즉, 나중에 들어간 원소가 먼저 나온다.
  • 차곡차곡 쌓이는 구조로 먼저 Stack 에 들어가게 된 원소는 맨 바닥에 깔리게 된다.
  • 그렇기 때문에 늦게 들어간 녀석들은 그 위에 쌓이게 되고 호출 시 가장 위에 있는 녀석이 호출되는 구조이다.
  • 스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out)을 가진 자료 구조이다. 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다.

💡 Queue

  • 선형 자료구조의 일종으로 `First In First Out (FIFO)`. 즉, 먼저 들어간 놈이 먼저 나온다.
  • Stack 과는 반대로 먼저 들어간 놈이 맨 앞에서 대기하고 있다가 먼저 나오게 되는 구조이다.
  • 참고로 Java Collection 에서 Queue 는 인터페이스이다. 이를 구현하고 있는 `Priority queue`등을 사용할 수 있다.
  • 큐(queue)는 먼저 집어 넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 지닌 자료 구조이며, 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념을 가졌다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다.

> [참고자료](https://blog.chulgil.me/algorithm/) > [참고자료](https://madplay.github.io/post/time-complexity-space-complexity) > [참고자료](https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#array-vs-linked-list) > [참고자료](https://osy0907.tistory.com/82?category=911997)