[자료구조] 자료 구조와 알고리즘은 무엇인가 총정리

📌  자료 구조는 왜 공부해야하나

 

1. 자료 구조가 무엇인가

자료 구조 = Data + Structure = 자료들의 집합

즉, 자료가 뭉쳐있는 생김새를 말한다.

자료 구조는 데이터들의 관계가 논리적으로 정의된 일정한 규칙에 의해 나열된다.

자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 조직적, 체계적으로 구분해서 표현한거다.

이런 식으로 딱딱 구분지어서 예쁘게 놓은 거란 말이다.

 

2. 자료 구조의 목적

자료구조의 목적은 크게 3가지이다.

1. 효율적인 데이터 저장 및 접근

2. 메모리 사용의 최적화

3. 문제 해결 및 알고리즘 설계 지원

각각 다른 책장이 존재한다고 가정하자.

1번 책장은 책이 무작위로 꽂혀 있기 때문에 나중에 원하는 책을 찾기가 어려울 수 있다.

2번 책장은 칸마다 같은 색상의 책을 진열했다. 하지만 꽂지 못하는 책과 빈 공간이 발생했다.

3번 책장은 색상 별로 섹션을 나누어 책을 분류했다. 그러나 가림막을 설치하는 과정에서 책장의 공간이 줄어들었다.

책장 = 메모리공간

책 = 데이터

라고 볼 수 있다.

위의 예시처럼 상황별로 효율적인 자료구조는 다 따로 있다.

 

3. 자료 구조의 내용, 자료 구조의 목표

우리는 현실의 문제를 컴퓨터로 해결하고자 한다. 하지만 컴퓨터와 현실 사이에는 표현하는 방법의 차이가 있다.

이처럼 자료를 다루는 방법에서도 컴퓨터와 현실에서는 차이가 있다. 이론적 측면은 현실에서 일어나는 것이고, 실제적 측면은 컴퓨터에서 작동하는 것이라고 할 수 있다.

그림에서 알 수 있듯이 자료구조의 목표는 현실에서의 데이터를 컴퓨터에서 구조화하고 그 구조 안에서 데이터를 효율적으로 처리하고, 각 구조의 효율성을 측정하는 것이다.

 

 

4. 자료의 형태에 따른 자료 구조의 분류

그리느라 너무 고생했다ㅠ 퍼갈때 참조 부탁드려요

이렇게 어마무시하게 많다.

이 중에 기본이 되는 자료구조부터 공부하는 것이 좋다.

 

 

 

1️⃣ 선형 구조

선형 자료구조는 한 개의 데이터 뒤에 한 개의 데이터가 따라오는 구조이다.

내부의 각 데이터 들은 1:1 구조를 가지고 있다.

대표적으로 배열(Array) 연결 리스트(Linked List) 스택 (Stack) 큐 (Queue) 데크 (Deque,Double-Ended Queue) 있고, 차근 차근 하나씩 포스팅 해나가야겠다.

	배열(Array)	연결 리스트(Linked List)	스택 (Stack)	큐 (Queue)	데크 (Deque, Double-Ended Queue)
정의	동일한 타입의 요소들이 연속된 메모리 공간에 저장된 자료구조	각 요소가 데이터와 다음 요소를 가리키는 포인터로 구성된 자료구조	후입선출(LIFO, Last In First Out) 원칙을 따르는 자료구조	선입선출(FIFO, First In First Out) 원칙을 따르는 자료구조	양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조
종류	1차원 배열: 단일 행으로 구성된 배열. 다차원 배열: 여러 행과 열로 구성된 배열 (예: 2차원 배열, 3차원 배열).	단일 연결 리스트 (Singly Linked List): 각 노드가 다음 노드를 가리킵니다. 이중 연결 리스트 (Doubly Linked List): 각 노드가 이전 노드와 다음 노드를 가리킵니다. 원형 연결 리스트 (Circular Linked List): 마지막 노드가 첫 번째 노드를 가리킵니다.	배열 기반 스택: 배열을 사용하여 스택을 구현. 연결 리스트 기반 스택: 연결 리스트를 사용하여 스택을 구현.	일반 큐 (Regular Queue): 기본적인 큐 구조. 우선순위 큐 (Priority Queue): 각 요소에 우선순위를 부여하고, 우선순위가 높은 요소가 먼저 처리됨. 원형 큐 (Circular Queue): 배열을 사용하여 큐를 구현하고, 끝과 시작이 연결된 구조.	배열 기반 데크: 배열을 사용하여 데크를 구현. 연결 리스트 기반 데크: 연결 리스트를 사용하여 데크를 구현.
특징	- 인덱스를 통해 요소에 직접 접근 가능. - 고정된 크기, 크기 변경 불가. - 메모리 사용 효율적, 접근 속도 빠름.	- 동적 크기 조절 가능. - 삽입, 삭제가 배열보다 효율적. - 요소 접근 속도가 느림.	- push: 요소를 스택의 맨 위에 추가. - pop: 스택의 맨 위 요소를 제거. - peek: 스택의 맨 위 요소를 확인. - 메모리 관리가 간단함.	- enqueue: 요소를 큐의 뒤에 추가. - dequeue: 큐의 앞 요소를 제거. - 요소 추가와 제거가 효율적.	- 양쪽 끝에서 삽입과 삭제가 가능. - 유연한 요소 추가와 제거. - 일반 큐와 스택의 기능을 모두 포함.

 

 

2️⃣ 비선형 구조

비선형 자료구조는 한개의 데이터 뒤에 여러개의 데이터가 따라오는것을 말하며 각 데이터가 1:n 또는 n:n의 관계를 가지게 된다.

계층 구조를 표현하기에 적절한 자료구조이다.

대표적으로 트리 (Tree) 그래프 (Graph) 힙 (Heap) 트라이 (Trie) 해시 테이블 (Hash Table) 이 있다.

	트리 (Tree)	그래프 (Graph)	힙 (Heap)	트라이 (Trie)	해시 테이블 (Hash Table)
정의	계층적 구조를 가진 비선형 자료구조로, 루트 노드에서 시작하여 자식 노드로 뻗어나가는 구조	정점(노드)과 이들을 연결하는 간선(엣지)으로 구성된 자료구조	완전 이진 트리의 일종으로, 특정 속성을 만족하는 자료구조	문자열을 저장하고 효율적으로 검색하기 위한 트리 기반 자료구조	키-값 쌍을 저장하고 빠르게 검색하기 위한 자료구조
종류	이진 트리 (Binary Tree): 각 노드가 최대 두 개의 자식 노드를 가짐. 이진 탐색 트리 (Binary Search Tree): 이진 트리의 일종으로, 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼. AVL 트리: 자가 균형 이진 탐색 트리. B-트리: 데이터베이스 및 파일 시스템에 사용되는 균형 트리.	무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프. 방향 그래프 (Directed Graph, Digraph): 간선에 방향이 있는 그래프. 가중 그래프 (Weighted Graph): 간선에 가중치가 있는 그래프. 비가중 그래프 (Unweighted Graph): 간선에 가중치가 없는 그래프.	최대 힙 (Max Heap): 부모 노드가 자식 노드보다 크거나 같은 트리. 최소 힙 (Min Heap): 부모 노드가 자식 노드보다 작거나 같은 트리.	표준 트라이: 각 노드가 알파벳 문자 또는 다른 문자를 자식으로 가짐. 압축 트라이: 단일 자식 노드를 병합하여 메모리 사용을 줄인 트라이. 테르나리 검색 트리 (Ternary Search Trie): 각 노드가 세 개의 자식을 가짐(작은 값, 동일 값, 큰 값).	체이닝 (Chaining): 충돌이 발생하면 연결 리스트로 해결 오픈 어드레싱 (Open Addressing): 충돌이 발생하면 다른 해시 버킷을 찾음 더블 해싱 (Double Hashing): 두 번째 해시 함수를 사용하여 충돌 해결
특징	- 노드 간 계층 관계. - 다양한 형태로 확장 가능. - 효율적인 탐색, 삽입, 삭제 연산.	- 복잡한 관계를 표현 가능. - 네트워크, 경로 찾기 등에 사용. - 다양한 알고리즘 적용 가능 (DFS, BFS, 다익스트라 등).	- 최댓값 또는 최솟값을 빠르게 추출 가능. - 우선순위 큐 구현에 사용. - 효율적인 삽입, 삭제 연산.	- 문자열 검색과 자동 완성 기능에서 뛰어남. - 중복을 피하고 공간 효율적. - 문자열 기반 애플리케이션에 유용.	- 평균적으로 O(1)의 시간 복잡도로 빠른 검색. - 키 기반 데이터 접근에 효율적. - 충돌 해결 전략 필요.

 

시간복잡도 정리표 -> 더보기

 

5. 자료 구조 선택 기준

그럼 자료 구조 선택 기준이 뭔가?

✅ 데이터 접근 패턴

• 배열(Array)은 인덱스를 통한 빠른 접근이 가능하지만, 삽입과 삭제가 어렵다. 반면에, 링크드 리스트(Linked List)는 삽입과 삭제가 용이하지만 데이터 접근 속도가 느릴 수 있다.

✅ 시간 복잡도 & 공간 복잡도

• 해시 테이블(Hash Table)은 평균적으로 O(1)의 시간 복잡도를 가지지만, 최악의 경우 O(n)이 될 수 있다. 이진 검색 트리(Binary Search Tree)는 평균적으로 O(log n)의 검색, 삽입, 삭제 시간이 소요된다.
• 배열은 고정된 크기를 가지기 때문에 메모리 낭비가 발생할 수 있으며, 링크드 리스트는 각 노드가 추가적인 포인터를 필요로 하여 메모리 사용이 증가할 수 있다.

✅ 데이터의 크기와 형태

• 대용량 데이터를 처리해야 하는 경우, 배열과 같은 연속된 메모리 공간을 요구하는 자료 구조는 부적합할 수 있다. 트리(Tree)나 그래프(Graph)는 복잡한 데이터 구조를 나타내는 데 유리하다.

✅ 특정 연산의 빈도

• 특정 연산(삽입, 삭제, 검색 등)의 빈도를 고려하여 최적의 자료 구조를 선택한다. 예를 들어, 큐(Queue)나 스택(Stack)은 삽입과 삭제가 빈번한 경우에 적합하다.

✅ 동시성 제어

• 멀티스레드 환경에서 스레드 안전성을 제공하는 자료 구조를 선택한다.예를 들어, ConcurrentHashMap은 동시성을 고려한 해시 테이블이다.

✅ 사용 용이성 및 유지보수

• 복잡한 자료 구조는 구현 및 디버깅이 어려울 수 있으므로, 간단한 자료 구조를 선호하는 것이 유지 보수 측면에서 유리할 수 있다.

✅ 응용 프로그램의 요구 사항

• 각 응용 프로그램은 고유한 요구 사항과 제약 조건을 가지므로, 이에 맞는 최적의 자료 구조를 선택하는 것이 중요하다.

 

 

📌  알고리즘은 무엇인가

알고리즘은 레시피다.

알고리즘은 문제를 해결하기 위한 계산 절차이자 처리 과정에 대한 순서이다.

자료구조의 특성에 따라 문제를 빠르고, 효율적인 문제 풀이 방법을 선택하게 된다.

만약에 초록색 책(5)을 찾고자 한다고 가정한다면

2번 책장의 경우, 2번째 칸 👉🏻 5번째 책을 찾게 된다.

3번 책장의 경우, 초록색 👉🏻 가장 마지막에 위치한 책을 찾게 된다.

이렇듯 자료구조에 따라 알고리즘(방식)이 다르게 된다.

 

따라서, 자료구조와 알고리즘 학습은 하나의 세트라고 할 수 있다.

프로그램 = 자료구조 + 알고리즘

=> 최대값 탐색 프로그램 = 배열 + 순차탐색

 

알고리즘 분류

• 구현: 재귀적 알고리즘, 연역적 알고리즘, 결정론적 알고리즘, 근사 알고리즘, 양자 알고리즘 등.
• 설계: 무차별 대입 공격, 분할 정복 알고리즘, 그래프 순회, 분기 한정법, 확률적 알고리즘, 리덕션, 백트래킹 등.
• 최적화 문제: 선형 계획법, 동적 계획법, 탐욕 알고리즘, 휴리스틱 함수 등.
• 이론적 분야: 검색 알고리즘, 정렬 알고리즘, 수치 알고리즘, 그래프 알고리즘, 문자열 알고리즘, 암호학적 알고리즘, 기계 학습, 데이터 압축 등.

 

 

 

📌 Ref

https://iosdevlime.tistory.com/entry/CSData-Structure-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80%EC%9A%94

https://prgms.tistory.com/134

https://limecoding.tistory.com/46

https://velog.io/@sisofiy626/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-1.-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%A0%95%EC%9D%98%EC%99%80-%EC%A2%85%EB%A5%98-%EC%84%A0%ED%98%95-%EB%B9%84%EC%84%A0%ED%98%95