자료구조 초간단 정리(Array ~ Heaps)

array

  - 인덱스가 존재하며 타입의 데이터가 연속적으로 존재하는 집합
  - 따라서 조회가 빠르나 미리 배열의 크기를 지정해야하며, 데이터 삽입·삭제가 불편하다

list

  - 수정가능하며 순서가 있는 데이터 집합

  - 각 원소의 길이가 달라도 되며 각 원소의 데이터 타입이 달라도 된다.
  - 인덱스가 존재하나 순서만 나타내는 정도이며 메모리 주소가 비연속적일 수 있다.
  - 포인터를 통해 다음 데이터를 가리키고 있어 삽입 및 삭제가 쉬우나 데이터 검색 성능이 좋지 않다

○ list.insert(idx, elm)

  - list에서 idx번째 위치에 elm을 삽입함. 
  - idx에 elm을 삽입하기 위해선 list의 길이가 1 증가해야하며 기존 idx에 있던 원소는 한칸씩 밀려나게 된다

○ del(list[idx])

  - list에서 idx번째 위치에 요소를 삭제함.
  - list의 idx번째 요소를 삭제하면서 idx + 1번째 부터 나머지 요소들이 앞으로 한칸씩 당겨지게 된다

 

정렬이란? 

  - Array 또는 List 내에 있는 원소들을 정해진 규칙에 따라 나열하는 것

 

 

탐색이란?

  - Array 또는 List 내에 있는 원소들 중에서 어떠한 조건에 맞는 원소들을 찾아내는 것

1. 선형탐색

  - list의 처음부터 순차적으로 조회해하면서 원하는 값을 찾는 방법
  - 따라서, 리스트의 길이에 따라 탐색 소요시간에 영향을 받기 때문에 O(n)의 시간 복잡도를 갖는다

2. 이진탐색

  - '정렬이 되어있는' list를 반으로 나눠 2개의 list 중 찾고자 하는 값과 가장 일치하는 쪽으로 선택하며 검색 범위를 줄여나가면서 원하는 값을 찾는 방법
  - 한 번 비교할 때 마다 리스트가 반씩 줄기 때문에 O(log n)의 시간 복잡도를 갖는다

 

 

재귀함수란?

  - 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는것
  - 시간복잡도를 줄일 수 있으나, 스택오버플로우의 위험이 있다

 

 

연결 리스트

  - 각 노드가 데이터와 포인터를 가지고 나열되어 있는 데이터 집합
  - 각 노드의 포인터는 다음 노드의 주소를 갖고있다.
  - 연결 리스트의 맨 앞을 Head, 맨 뒤를 tail이라고 한다.
  - 노드를 삽입 및 삭제 시 포인터만 조작하면 되기 때문에 데이터의 삽입 삭제가 용이하다
  - 하지만, 주소 역시 메모리가 필요하기 때문에 메모리 소요가 배열보다 크다
  - 또한, 인덱스가 있는 배열과 달리 특정 번째의 원소에 접근하기 위해선 앞에서부터 하나씩 접근해야한다

 

 

환형 큐

  - 제한된 공간과 시간 자원을 일반 큐 보다 효율적으로 활용하기 위해 개선된 큐
  - deque가 시작되는 지점을 front라 하고 deque가 실행되는 지점을 rear라고 하면
  - deque가 실행된다면 deque된 데이터 수 만큼 front를 이동
  - 만약, rear의 위치가 qeu길이가 같아진다면 rear의 위치를 que의 맨 앞으로 다시 이동시킴.

 

 

우선순위 큐

 - enque된 순서와 상관없이 우선순위가 높은 데이터가 deque가 되는 자료 구조

 

 

트리

  - 정점과 간선으로 이루어진 그래프

  - 트리는 하나의 루트 노드를 가진다
  - 루트 노드는 0개 이상의 자식노드를 가질 수 있다
  - 자식 노드 또한 0개 이상의 자식 노드를 가질 수 있으며, 이는 반복적으로 정의된다.

 

 

이진트리

  - 트리의 한 종류로 leaf node를 제외한 모든 레벨의 노드들이 가득차 있는 트리
  - 하나의 루트 노드를 가지며 루트 노드는 2개 이하의 자식 노드를 가질 수 있다
  - 자식 노드 또한 2개 이하의 자식 노드를 가질 수 있으며, 이는 반복적으로 정의된다.

 

○ 넓이 우선 탐색(Breadth First Traversal)

  - 수준(level)이 낮은 노드를 우선으로 방문하는 트리
  - 가장 왼쪽부터 방문하여 오른쪽으로 순차적으로 방문함
  - 한 노드를 방문하였을 때 나중에 방문해야할 자식 노드들을 왼쪽부터 순서대로 기록해 두어야 하며 그러기 위해선 자료구조 큐를 사용해야한다
  - 하나의 노드를 방문할 시 같은 level의 다른 노드를 방문해야하기 때문에 재귀적인 성질을 갖지 않는다.

 

○ 깊이 우선 탐색(Depth First Treversal)

  - 어떤 노드부터 시작하여 인접한 노드들을 왼쪽부터 재귀적으로 방문하며, 방문한 노드는 재방문하지 않으며
    가 분기마다 마다 가장 멀리 있는 노드까지 탐색하는 알고리즘
 - 한 노드를 방문하였을 때 나중에 방문해야할 자식 노드들을 기록하고 나중에 기록한 순서 부터 방문하며
    방문 시 기록을 지워야 하며 그러기 위해선 자료구조 스택을 사용해야 한다

 

 

이진탐색트리

  - 이진트리와 연결리스트를 결합한 자료구조의 일종
  - 효율적인 탐색 능력을 가능하면서도 빈번한 자료 입력과 삭제를 가능하게 끔 고안됨
  - 이진탐색트리는 다음과 같은 특징을 갖는다

    1. 각 노드엔 중복되지 않느 키(Key)가 있다.
    2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드 들로 이루어져 있다
    3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드 들로 이루어져 있다
    4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.

 

○ 삽입

  1. 삽입할 값이 루트 노드와 같다면 오류를 발생한다(중복값 허용X)
  2. 삽입할 값이 루트 노드보다 작다면 왼쪽 서브트리를 탐색하며 만약 비었다면 값을 추가하고,
    비어있지 않다면 서브 트리의 루트 노드와 다시 값을 비교한다.
  3.삽입할 값이 루트 노드보다 작다면 오른쪽 서브트리를 탐색하며 만약 비었다면 값을 추가하고,
    비어있지 않다면 서브 트리의 루트 노드와 다시 값을 비교한다.

○ 삭제

  1. 삭제할 노드의 서브트리가 없는 경우
    - 삭제할 노드를 NULL로 하고 해당 노드를 삭제하면 된다
  2. 삭제할 노드의 서브트리가 1개인 경우
    - 삭제할 노드의 부모트리가 가리키는 자식노드를 삭제할 노드의 자식 노드로 가리키고 삭제하면 된다
  3. 삭제할 노드의 서브트리가 2개인 경우
    3 - 1. 삭제할 노드의 왼쪽 서브 트리에서 가장 큰 노드를 해당 노드 자리에 올린다
    3 - 2. 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 노드를 해당 노드 자리에 올린다
    → 이렇게 해야 이진탐색트리의 특징을 만족함

 

 

힙(Heaps)

  - '무엇인가를 차곡차곡 쌓아올린 더미'란 뜻으로서 대표적인 우선순위(값의 크기 기준) 큐의 구현 방법 중 하나인 자료구조이며  Max Heap과 Min Heap이 있다
  - Max Heap과 Min Heap에서 부모 노드는 자식 노드보다 무조건 크거나 작아야 한다 -> 루트 노드는 서브트리의 루트노드보다 크거나 작아야하며 따라서 루트 노드는 모든 자식 노드보다 크거나 작다
  - 여기서 우선순위는 키 값의 크기가 된다.
    →  삽입 ☞ 키 값이 가장 큰(작은)노드가 루트 노드에 위치하도록 함
    →  삭제 ☞ 루트 노드를 삭제한 뒤 나머지 노드들 중 가장 큰(작은)노드가 루트 노드에 위치하도록 함-

 

○ 삽입(Max Heap 기준)

  1. 추가할 노드를 완전 이진트리의 형태를 깨지 않는 선에서 leaf node에 추가한다
  2. 추가된 노드와 부모 노드의 값을 비교하여 자식 노드가 클 시 부모 노드와 위치를 교환한다
  3. 추가된 노드의 값보다 큰 부모 노드를 만날 때 까지 2번을 반복한다

 

○ 삭제(Max Heap 기준)

  1. 루트노드를 삭제한다
  2. leaf node 중 가장 맨 우측에 있는 노드를 root node에 위치시킨다
  3. 위치가 바뀐 노드와 그 자식 노드의 값을 비교하여 자식 노드가 클 시 자식 노드와 위치를 교환한다
  3 - 1. 자식 노드가 두개이고 두 자식 모두 위치가 바뀐 노드보다 클 시 가장 큰 값을 가진 자식과 위치를 교환한다
  4. 위치가 바뀐 노드의 값보다 작은 자식 노드를 만날 때 까지 3번을 반복한다