자료구조란?

데이터를 효율적으로 저장, 관리, 처리하기 위한 구조

자료구조는 데이터 항목 간의 관계를 정의하고, 데이터에 효율적으로 접근 및 수정할 수 있게 해줍니다. 각 자료구조는 특정 작업을 최적화하기 위해 설계되었으며, 컴퓨터 성능을 효율적으로 이용하기 위해 필수적입니다.

배열 (Array)

고정된 크기의 연속적인 메모리 공간에 데이터를 저장하는 자료구조

배열은 식단표와 같습니다. 식단 계획표는 각 요일별로 어떤 음식을 먹을지 정해 놓은 표입니다. 배열은 마찬가지로 연속된 메모리 공간에 동일한 타입의 데이터를 저장하는 구조입니다. 여기서 각 요일이 배열의 인덱스, 음식이 동일한 타입의 데이터에 해당합니다.

배열의 특징

• 고정된 크기
  주간 식단 계획표를 갑자기 열흘로 늘리기 어려운 것처럼, 배열은 선언할 때 크기가 고정됩니다.

• 빠른 접근
  월요일에 어떤 음식을 먹을지 바로 알 수 있는 것처럼, 배열에서는 인덱스를 통해 데이터에 빠르게 접근할 수 있습니다.

• 메모리 연속성
  일주일 식단 계획표가 연속된 칸으로 구성되어 있는 것처럼, 배열도 연속된 메모리 공간에 저장됩니다. 이는 데이터 접근을 효율적으로 만듭니다.

• 삽입 및 삭제의 비효율성
  식단 계획표의 중간에 새로운 음식을 추가하거나 제거하려면 많은 요일의 계획을 변경해야 하듯이, 배열에서도 요소를 삽입하거나 삭제할 때 많은 데이터를 이동시켜야 합니다.

배열의 활용

• 가계부 항목 기록
  한 달 동안의 가계부 항목을 배열에 저장하고, 항목별 지출 금액을 계산합니다.

• 주간 식단 계획
  일주일 동안의 식단 계획을 배열에 저장하고, 특정 요일의 식단을 조회합니다.

연결 리스트(Linked List)

데이터와 다음 요소를 가리키는 포인터를 포함하는 노드로 연결된 자료구조

연결 리스트는 기차와 같습니다. 기차는 여러 객차가 연결된 구조로 되어 있습니다. 각 객차는 승객을 태우고, 다음 객차와 연결장치로 연결되어 있습니다. 연결 리스트도 마찬가지로, 여러 노드가 연결된 구조입니다. 각 노드는 데이터를 저장하고, 다음 노드를 가리키는 포인터를 포함합니다. 여기서 각 객차는 노드, 승객은 데이터, 연결장치는 포인터에 해당합니다.

연결 리스트의 특징

• 동적 크기 조절
  배열과 달리 연결 리스트는 고정된 크기를 가지지 않습니다. 필요에 따라 노드를 추가하거나 제거할 수 있어 크기가 동적으로 조절됩니다. 따라서, 메모리를 효율적으로 사용할 수 있습니다

• 빠른 삽입과 삭제
  배열에서 중간에 요소를 삽입하거나 삭제하려면 많은 요소를 이동시켜야 하지만, 연결 리스트에서는 포인터만 변경하면 되므로 삽입 삭제가 빠릅니다. 예를 들어, 새로운 노드를 중간에 삽입하거나 기존 노드를 제거하는 작업이 효율적입니다.

• 순차 접근
  연결 리스트는 인덱스를 사용하여 임의 접근(Random Access)이 가능한 배열과 달리, 순차 접근(Sequential Access)만 가능합니다. 즉, 특정 위치의 노드에 접근하려면 첫 번째 노드부터 순서대로 접근해야 합니다.

• 메모리 사용량
  연결 리스트는 각 노드가 데이터 외에도 포인터를 저장해야 하므로 배열보다 메모리를 더 많이 사용합니다. 따라서, 데이터의 변동이 거의 없는 정적인 상황에서는 배열이 더 효율적입니다.

연결 리스트의 활용

• 할 일 목록 관리
  할 일 목록을 연결 리스트로 저장하여, 새로운 할 일을 추가하거나 완료된 할 일을 목록에서 제거합니다.
• 음악 플레이리스트 관리
  음악 플레이리스트를 연결 리스트로 저장하여, 새로운 곡을 추가하거나, 현재 곡을 재생한 후 다음 곡으로 이동합니다.

스택 (Stack)

후입선출(LIFO) 방식으로 데이터를 관리하는 자료구조

스택은 접시 쌓기와 비슷한 구조를 가진 자료구조입니다. 접시를 쌓을 때, 새로운 접시는 가장 위에 놓고, 사용할 때도 가장 위에서부터 꺼내는 방식으로 작동합니다. 스택도 마찬가지로, 요소를 추가할 때는 가장 위에 쌓고, 요소를 제거할 때도 가장 위에서 제거합니다.

스택의 특징

• LIFO 구조
  스택은 LIFO(Last In First Out) 방식으로 작동합니다. 즉, 가장 나중에 쌓은 접시를 가장 먼저 꺼내게 됩니다.

• 제한된 접근
  접시를 쌓을 때 가장 위의 접시만 접근할 수 있는 것처럼, 스택에서도 가장 위의 요소에만 접근할 수 있습니다.

스택의 활용

• 웹 브라우저 방문 기록 관리 (뒤로 가기 기능)
  방문한 웹 페이지를 스택에 저장하여, 사용자가 "뒤로 가기" 버튼을 눌렀을 때 가장 최근에 방문한 페이지로 돌아갑니다.

• 텍스트 편집기 (Undo 기능)
  텍스트 편집기의 "실행 취소(Undo)" 기능을 구현하기 위해 사용자 작업을 스택에 저장합니다.

큐 (Queue)

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

큐는 대기줄과 비슷한 구조를 가진 자료구조입니다. 대기줄에서는 먼저 줄을 선 사람이 먼저 서비스를 받게 됩니다. 큐도 마찬가지로, 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 방식으로 작동합니다. 즉, 큐는 선착순이라고 할 수 있습니다

큐의 특징

• FIFO 구조
  큐는 FIFO(First In First Out) 방식으로 작동합니다. 즉, 대기줄에서 먼저 줄을 선 사람이 먼저 서비스를 받는 것처럼, 큐에서는 먼저 들어온 데이터가 먼저 나갑니다.
• 제한된 접근: 대기줄에서 중간에 끼어드는 것이 허용되지 않는 것처럼, 큐에서도 중간에 데이터를 삽입하거나 제거하는 것이 허용되지 않습니다. 항상 앞에서 제거하고, 뒤에 삽입합니다.

큐의 활용

• 프로세스 관리: 운영 체제에서 실행 대기 중인 프로세스들은 대기줄과 같으며, 먼저 도착한 프로세스가 먼저 CPU를 할당받습니다.
• 콜센터 고객 대기줄: 콜센터에서 전화를 건 고객들이 대기줄에 들어가며, 먼저 전화를 건 고객이 먼저 상담원과 연결됩니다.

덱 (Deque)

양쪽 끝에서 데이터의 삽입과 삭제가 가능한 자료구조

덱(Deque, Double-Ended Queue)을 양쪽에서 접근 가능한 도로에 비유할 수 있습니다. 도로는 양쪽 끝에서 차량이 들어오고 나갈 수 있습니다. 마찬가지로, 덱은 양쪽 끝에서 데이터의 삽입과 삭제가 가능한 자료구조입니다.

덱의 특징

• 양방향 접근: 도로의 양쪽 끝에서 차량이 들어오고 나갈 수 있는 것처럼, 덱에서는 앞과 뒤 양쪽에서 데이터를 삽입하고 삭제할 수 있습니다.
• 유연성: 도로에서 차량이 양쪽 끝으로 자유롭게 이동할 수 있는 것처럼, 덱은 스택과 큐의 기능을 모두 수행할 수 있습니다. 스택처럼 사용할 때는 한쪽 끝에서만 삽입과 삭제를 하고, 큐처럼 사용할 때는 한쪽에서 삽입하고 반대쪽에서 삭제할 수 있습니다.

덱의 활용

• 캐시: 웹 브라우저의 뒤로 가기와 앞으로 가기 기능은 덱을 사용하여 구현할 수 있습니다. 사용자가 방문한 페이지를 덱에 저장하여 앞으로 가기와 뒤로 가기를 할 수 있습니다.
• 일정 관리: 양쪽 끝에서 일정을 추가하거나 삭제하는 방식으로 덱을 사용하여 일정 관리를 할 수 있습니다.

트리 (Tree)

계층적인 구조로 데이터를 저장하는 자료구조

트리는 족보와 같습니다. 족보는 부모가 자식들을 가지고 있으며, 자식들도 자신의 자식들을 가질 수 있습니다. 트리도 마찬가지로 루트 노드에서 시작하여 계층적으로 자식 노드가 연결된 구조입니다. 여기서 부모는 부모 노드, 자식은 자식 노드에 해당합니다.

트리의 특징

• 깊이
  가족 트리의 세대와 같습니다. 예를 들어, 루트 노드가 1세대라면 그 자식 노드는 2세대, 그 자식의 자식 노드는 3세대입니다.

• 계층적 구조
  트리는 루트 노드에서 시작하여 여러 레벨로 구성됩니다.

• 부모-자식 관계
  각 노드는 자신을 포함하는 부모 노드와 연결되어 있으며, 가족 트리에서 부모와 자식 간의 관계와 같습니다.

트리의 활용

• 파일 시스템 관리
  운영체제의 파일 시스템을 트리 구조로 관리하여, 디렉토리와 파일 간의 계층 구조를 표현합니다.

• 회사 조직도
  회사의 조직 구조를 트리로 표현하여, 상위 관리자부터 하위 직원까지의 계층을 나타냅니다.

그래프 (Graph)

노드와 노드 간의 관계를 간선으로 표현한 자료구조

그래프는 도시의 도로망과 같습니다. 각 도시는 노드에 해당하고, 도시간을 연결하는 도로는 간선에 해당합니다. 그래프는 노드와 간선으로 이루어져 있으며, 복잡한 관계를 표현하는 데 적합합니다.

그래프의 특징

• 노드와 간선
  그래프는 노드(정점)와 이들을 연결하는 간선(엣지)으로 구성됩니다. 이는 데이터 간의 관계를 명확히 나타내는 데 유용합니다.

• 다양한 형태
  그래프에는 방향 그래프와 무방향 그래프, 가중치 그래프와 비가중치 그래프 등 다양한 형태가 있습니다. 각각의 형태는 특정한 문제를 해결하는 데 적합합니다.

• 복잡한 관계 표현
  그래프는 복잡한 네트워크 구조를 표현하는 데 적합합니다. 이는 소셜 네트워크나 통신 네트워크에서 자주 사용됩니다.

그래프의 활용

• 소셜 네트워크 분석
  사람들 간의 관계를 그래프로 표현하여, 친구 추천 알고리즘을 구현합니다.

• 네트워크 라우팅
  인터넷의 라우팅 프로토콜에서 최적의 경로를 찾기 위해 그래프를 사용합니다.