본 캠프 23일차 TIL

자료 구조

 1. Array (배열)

• 동일한 타입의 데이터들을 저장하며 고정된 크기를 가지고 있다.
• 인덱싱 되어 있어 인덱스 번호로 데이터에 접근 할 수 있다.

평가: 가장 기본적인 자료 구조형으로, 고정된 크기의 연속된 메모리 블록에 데이터를 저장합니다. 인덱스를 통해 빠르게 접근할 수 있습니다.

 

비유: 박스 안에 물건을 하나씩 차례로 넣고, 인덱스라는 번호를 통해 원하는 물건을 빠르게 꺼내 사용할 수 있는 서랍장과 같

 

  배열명 > A  → 1, 2, 3  < 원소 값

                           0 1 2  < 인덱스

  배열의 크기 > 3  ┘

 

 2. Linked List (연결 리스트)

• 각 데이터의 시퀀스가 순서로 연결되어 있는 구조
• 동적인 데이터 추가 및 삭제에 유리하다.

평가: 동적으로 크기를 조절할 수 있는 자료 구조형으로, 각 노드가 다음 노드를 가리키는 포인터를 포함합니다. 삽입과 삭제가 용이합니다.

 

비유: 철사로 이어진 구슬 목걸이. 구슬 하나를 빼거나 추가할 때 다른 구슬들을 모두 옮길 필요 없이 연결된 철사만 수정하면 됩니다.

 

     head   →   key , next    →    key , next   →    key , next  →  NULL

head┘           └  node ┘     └ 다음 노드 포인터 └   Tail   ┘

 

 3. 스택 (Stack)

• 후입선출(LIFO, Last In First Out) 구조로, 마지막에 삽입된 요소가 가장 먼저 제거됩니다.
• 한쪽 끝에서만 삽입과 삭제가 가능합니다.

평가: 데이터의 순서를 역으로 저장하거나, 임시 저장 공간이 필요한 경우에 유용합니다.

 

비유: 접시를 쌓아두는 것과 같아서, 가장 위에 있는 접시를 먼저 꺼내야 합니다.

┏━┓
┃ 3 ┃ <- Top "가장 최근에 삽입된 요소이자 가장 먼저 처리되는 요소"
┣━┫
┃ 2 ┃ <- 원소값
┣━┫
┃ 1 ┃ <- Bottom Bottom "가장 먼저 삽입된 요소"
┗━┛

 4. Queue(큐)

• 선입선출(FIFO, First In First Out) 구조로, 먼저 삽입된 요소가 가장 먼저 제거됩니다.
• 한쪽 끝에서 삽입, 다른 쪽 끝에서 삭제가 이루어집니다.

평가: 데이터가 입력된 순서대로 처리되어야 하는 경우에 적합합니다.

 

비유: 줄 서서 기다리는 상황. 먼저 줄을 선 사람이 먼저 서비스를 받습니다.

 

┌──┐
│  1  │  <- Front "가장 먼저 삽입된 요소이자 가장 먼저 처리되는 요소"
├──┤
│  2  │
├──┤
│  3  │  <- Rear "가장 최근에 삽입된 요소"
└──┘

 

5. Hash Table(해시 테이블)

• 키-값 쌍을 저장하는 자료 구조형으로, 해시 함수를 통해 키를 인덱스로 변환하여 저장합니다.
• 평균적으로 빠른 검색, 삽입, 삭제가 가능합니다.

평가:

• 빠른 검색과 삽입, 삭제가 필요할 때 유용하지만, 충돌 관리가 필요합니다. 간단하게 해시 테이블을 이해를 해보자면 딕셔너리의 형태를 생각하며 접근해보면 이해하기 쉽습니다.

비유:

• 책의 색인(index)처럼 특정 단어를 빠르게 찾을 수 있게 해줍니다. 책의 색인 페이지에서 단어를 찾고, 해당 페이지로 바로 이동할 수 있습니다. 다만 난수와 같아서 데이터의 크기가 커질수록 충돌이 발생할 가능성이 증가하며, 이를 관리하기 위한 추가적인 기법이 필요합니다.

┏━-━━┓
┃키1:값1┃  <- 해시 함수(키의 값)으로 인덱스 결정
┃키2:값2┃
┃키3:값3┃
┃키4:값4┃
┗━━-━┛

 

 6. Tree(트리)

•  계층적 자료 구조로, 루트 노드에서 시작하여 자식 노드로 확장됩니다. 각 노드는 여러 자식 노드를 가질 수 있습니다.

평가:

• 계층적 데이터를 저장하고 검색하는 데 적합합니다.

비유:

• 가계도와 같아서, 루트에 해당하는 조상으로부터 각 자손 노드까지 연결된 구조입니다. 그리고 카테고리 안의 상세 카테고리와도 같은 구조입니다.

             A          <- Root  "최상위 노드"
           / │ \
        B  C   D     <- parent "부모 노드"

       /     │     \
     E      F      G  <- child "자식 노드"

 

7. Binary Tree(이진 트리)

• 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조입니다.

평가:

• 검색, 삽입, 삭제가 효율적이며, 이진 탐색 트리(BST)는 정렬된 형태로 데이터 저장에 유리합니다.

비유:

• 예/아니오 같은 질문(양자택일)을 통해 원하는 답에 도달하는 구조입니다.

             A         <- Root  "최상위 노드"
           /    \
         B      C    <- parent "부모 노드"

        /  \        \
     D    E       F   <- child "자식 노드"

 

8. Heap(힙)

• 완전 이진 트리로, 부모 노드가 자식 노드보다 항상 크거나(최대 힙) 작습니다(최소 힙).

평가:

• 우선순위 큐 구현에 유용하며, 최댓값 또는 최솟값을 빠르게 찾을 수 있습니다.

비유:

• 최댓값 또는 최솟값을 빠르게 찾을 수 있는 일종의 정렬된 스택. 데의터의 가장 중요한 항목이 항상 맨 위에 있습니다.

           9              <- Root  "최상위 노드"

         /    \

      5        8         <- parent "부모 노드"

    /   \      /   \

  1     3   2    4     <- child "자식 노드"

그래프의 자료 구조형도 있지만 지금의 내가 정리하기엔 너무 어려운 자료 구조형인 것 같다.