자료구조 기초 정리

자료구조란?

자료구조는 데이터를 효율적으로 저장하고 관리하는 방법입니다. 우리가 프로그래밍할 때 데이터가 많아지면, 데이터를 어떻게 관리하느냐에 따라 프로그램의 성능이 크게 달라집니다. 그래서 데이터를 잘 정리하고, 필요한 정보를 빠르게 찾을 수 있도록 하는 것이 자료구조의 역할입니다. 배열, 스택, 큐, 트리 같은 것들이 자료구조에 속합니다.

자료구조를 배워야하는 이유

자료구조를 배우는 이유는, 코드를 더 효율적으로 짜기 위해서입니다. 데이터를 다루는 방법을 잘 알면, 프로그램의 속도를 빠르게 만들 수 있고, 메모리도 아낄 수 있습니다. 예를 들어, 어떤 자료구조를 쓰느냐에 따라 데이터를 찾거나, 추가하거나, 삭제하는 데 걸리는 시간이 크게 달라질 수 있습니다.

자료구조의 종류

배열(Array)

배열은 데이터를 연속된 메모리 공간에 저장하는 자료구조로, 고정된 크기를 미리 설정하여 사용합니다.

• 연속적인 메모리 : 메모리 상에 연속적으로 배치됩니다. 이는 논리적 저장 위치와 물리적 저장 위치가 일치한다는 의미로, 각 원소는 인덱스를 통해 직접 접근이 가능합니다.
• 고정된 크기 : 배열 선언 시 크기를 정해야 하며, 이후에는 변경할 수 없습니다. 이로 인해 메모리 크기보다 데이터의 크기가 작을 경우 메모리 낭비가 발생할 수 있습니다.
• 시간복잡도
  • 탐색(Access) : 인덱스를 사용하여 원소에 접근할 수 있기 때문에 O(1)의 시간 복잡도를 가집니다. 인덱스를 모르는 경우, 모든 원소를 확인해야 하므로 O(n)의 시간 복잡도가 소요됩니다.
  • 삽입 및 삭제 (Insertion and Deletion): 배열의 끝에서 원소를 추가하거나 삭제하는 경우는 O(1)의 시간 복잡도를 가지지만, 배열의 중간에 원소를 삽입하거나 삭제할 때는 해당 위치 이후의 모든 원소를 이동시켜야 하므로 O(n)의 시간이 소요됩니다.

-> 메모리 크기보다 더 큰 데이터를 저장시켜야될 경우엔?

연결리스트(Linked List)

연결 리스트는 노드라는 구조체를 사용하여 비연속적인 메모리 공간에 데이터를 저장하는 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(주소)를 포함합니다.

• 비연속적인 메모리 : 노드들은 메모리 상에 연속적으로 저장되지 않습니다. 각 노드는 메모리의 다른 위치에 저장되며, 다음 노드를 가리키는 포인터를 통해 연결됩니다.
• 가변적인 크기 : 연결 리스트는 동적으로 크기를 조절할 수 있습니다. 데이터가 추가되거나 삭제될 때 메모리의 재할당이 필요 없으며, 노드가 추가될 때마다 메모리가 동적으로 할당됩니다.
• 시간복잡도
  • 탐색(Access) : 노드들이 메모리 상에 비연속적으로 저장되기 때문에, 특정 인덱스의 원소에 접근하려면 처음부터 순차적으로 탐색해야 합니다. 이로 인해 O(n)의 시간 복잡도를 가집니다.
  • 삽입 및 삭제 (Insertion and Deletion): 노드를 추가하거나 삭제할 때는 해당 노드의 포인터만 변경하면 되므로, 인접한 노드의 포인터만 수정하면 됩니다. 따라서 O(1)의 시간 복잡도를 가집니다. 단, 특정 위치에 삽입하거나 삭제하려면 해당 위치까지 탐색해야 하므로, 탐색을 포함할 경우 O(n)이 될 수 있습니다.

스택(Stack)

스택은 후입선출(LIFO) 방식으로 데이터를 관리하는 자료구조입니다.

• 연산
  • push : 데이터 삽입
  • pop : 데이터 삭제
  • peek : 맨 위의 데이터 확인(제거x)
• 사용사례 : 스택은 최근에 추가된 데이터를 먼저 처리해야 하는 상황에서 유용합니다. 데이터의 순서가 중요하거나, 최신 상태를 빠르게 확인하고 싶을 때 사용됩니다. ex) 함수 호출 시의 호출 스택 관리, 웹 브라우저의 뒤로 가기 기능, 수식 계산기 등

큐(Queue)

큐는 선입선출(FIFO) 방식으로 데이터를 관리하는 자료구조입니다.

• 연산
  • enqueue : 데이터 삽입
  • dequeue : 데이터 삭제
  • peek : 맨 위의 데이터 확인(제거x)
• 사용사례 : 큐는 먼저 들어온 데이터를 먼저 처리해야 하는 상황에서 유용합니다. 데이터의 순서가 중요하거나, 순서대로 처리가 필요할 때 사용됩니다. ex) 프린터 작업 예약, 운영 체제의 작업 스케줄링, 너비 우선 탐색(BFS) 알고리즘 등

트리(Tree)

트리는 부모와 자식 노드로 이루어진 계층적 자료구조입니다. 루트 노드에서 시작해 여러 자식 노드로 확장되며, 노드 간에 순환이 없는 특징이 있습니다.

• 계층 구조 : 상위 노드에서 하위 노드로 연결되는 구조로, 부모-자식 관계를 가집니다.
• 비순환 구조 : 트리는 노드들이 한 방향으로만 연결되며, 순환이 발생하지 않습니다.
• 사용사례 : 트리는 데이터 간의 계층적 관계를 표현하는 데 유용하게 사용됩니다. 예를 들어, 파일 시스템에서는 폴더와 파일의 계층 구조를 나타내는 데 사용됩니다. 또한, 이진 탐색 트리는 데이터의 효율적인 검색과 정렬을 가능하게 하며, AVL 트리와 레드-블랙 트리는 균형을 유지하여 삽입과 삭제 시 성능을 보장합니다.

그래프(Graph)

그래프는 여러 개의 노드와 그 노드들 간의 연결로 구성된 자료구조입니다. 각 노드는 여러 방향으로 노드와 연결할 수 있습니다.

• 여러 개의 연결어떻게 수정하지 : 각 노드는 다른 여러 노드와 연결될 수 있습니다. 방향성이 있을 수도, 없을 수도 있습니다.
• 순환 구조 : 같은 노드를 다시 방문하는 경로가 존재할 수 있습니다.
• 사용사례 : 그래프는 다양한 시스템에서 노드 간의 관계를 모델링하는 데 사용됩니다. 예를 들어, 소셜 네트워크에서는 사용자 간의 관계를 표현하고, 지도에서는 도시나 장소 간의 최단 경로를 계산하는 데 활용됩니다. 또한, 컴퓨터 네트워크나 통신 네트워크의 연결 상태를 분석하는 데에도 사용됩니다.

해시그래프(Hash Table)

해시 테이블은 데이터를 Key와 Value 쌍으로 저장하는 자료구조입니다. 각 Key는 해시 함수를 통해 고유한 해시 값으로 변환되어, 이 값을 기반으로 테이블의 인덱스에 데이터를 저장합니다.

• 빠른 접근 속도 : 해시 테이블은 해시 함수를 사용해 Key를 특정 인덱스에 매핑하기 때문에, 데이터를 직접적으로 접근할 수 있어 평균적으로 O(1)의 시간 복잡도를 가집니다. 해시 함수 덕분에 대규모 데이터에서 특정 값을 검색할 때도 효율적입니다.
• 충돌 해결 : 서로 다른 키가 동일한 해시 값을 가질 때는 충돌이 발생할 수 있으며, 이를 해결하기 위한 방법으로 체이닝이나 개방 주소법이 사용됩니다.
• 사용사례 : 해시 테이블은 데이터베이스에서 키-값 쌍을 빠르게 조회할 때, 캐시 시스템에서 자주 사용하는 데이터를 저장할 때, 또는 중복 확인과 같은 검색 작업에서 널리 사용됩니다.