<aside> 🧑‍💻 자료구조 : 데이터의 구조

</aside>

• 자료구조와 자료형이 동일 하지는 않음
• 자료 구조의 종류

  • 선형 자료 구조

    • 배열 : 연속된 메모리 공간에 저장되어 있는 자료 구조
      • 리스트와 마찬가지로 인덱스로 접근이 가능
      • 크기가 고정되며 연속된 메모리 공간을 할당받는 자료 구조
    • 연결 리스트 : 데이터가 담긴 여러 노드들이 순차적으로 연결된 형태의 자료 구조
      • 순차적

    <aside> 🧑‍💻 리스트 : 배열과 연결 리스트의 장점을 모두 가지고 있는 자료 구조

    </aside>

    • 해시 테이블 : KEY-VALUE 형태로 자료를 저장하는 자료 구조
      • 딕셔너리와 같은 자료 구조
      • 값이 1 대 1 매핑을 이룸
      • 해시 함수를 사용하여 변환한 값을 색인(INDEX)으로 삼아 키(KEY)와 데이터(VALUE)를 저장
        • 시간 복잡도는 줄여주나 공간 복잡도가 올라감
        • 시간 복잡도가 공간 복잡도보다 유의미한 차이를 보이기는 함
    • 스택 : 후입선출, LIFO
    • 큐 : 선입선출, FIFO

    <aside> 🧑‍💻 deque : 스택과 큐의 장점을 모아 놓은 큐 자료 구조

    </aside>

  • 비 선형 자료 구조

    • 그래프 : 정점과 정점 사이를 연결하는 간선으로 연결된 자료 구조
      • 인접 : 간선으로 연결된 상태
    • 트리 : 그래프의 일종, 사이클이 없는 하나의 연결 그래프
      • 계층 관계를 가지고 있는 자료 구조
      • 더 이상 연결되지 않는 노드 → ‘리프’라고 함
• 본 강의에서는 파이썬으로 리스트나 딕셔너리로 구현

재귀

<aside> 🧑‍💻 자기 자신을 계속 호출하며 문제를 해결하는 방식

</aside>

• 종료 조건 + 점화식 (자기 자신을 호출하는 곳)
• 재귀 함수는 종료 조건을 설정하지 않으면 무한하게 자기 자신을 호

탐색 알고리즘

<aside> 🧑‍💻 원하는 어떤 값을 찾아내는 알고리즘

</aside>

• 선형 탐색 (= 완전 탐색)
  • 시간 복잡도 ⇒ O(n)
• 이진 탐색
  • 정렬이 되어 있는 1차원 리스트 안에서 중앙값과 찾고 싶은 값을 비교하여 중앙 값보다 작으면 왼쪽 부분만 탐색하고 크면 오른쪽 부분만 탐색함

<aside> 🧑‍💻 그래프

</aside>

1. 인접 행렬로 표현하는 방식

   

   갈 수 있는 경우를 1로 설정

   • 두 노드의 연결은 matrix[i][j]로 확인 가능
   • 시간 복잡도 기준으로는 인접 행렬이 효율성이 떨어지지만 접근하기는 쉬움
   • 코딩테스트 출제 유형에 빈출적으로 나

2. 인접 리스트로 표현하는 방식