자료구조

Stack (스택)

FILO 구조. 자동메모리, 네트워크 프로토콜, 되돌리기 등에 사용.

Queue (큐)

FIFO 구조. 작업을 처리하는 요소에 많은 데이터가 한번에 몰렸을경우, 큐 자료구조를 사용하여 대기하는 줄을 만들어 작업에 무리가지 않게 '완충장치'로 도 사용.

Tree (트리)

• Binary Tree (이진 트리)

  하나의 노드가 자식노드를 2개까지만 가질 수 있는 트리.
  수식을 트리처럼 표현하여 계산하게 하는 Expression Binary Tree(수식 이진 트리) 와 빠른 데이터 검색을 가능하게 하는 Binary Search Tree(이진 탐색 트리) ,Red Black Tree(레드 블랙 트리) 등의 토대가 된 자료구조.
  
  
  

알고리즘

정렬

• 버블정렬

  이웃요소끼리 비교하며 제일 앞 부터 정렬된 곳 까지 반복하여 정렬 순대로 맞춰가는 방식.
  성능은 매우 나쁘나 구현이 간단하여 버그를 만들 가능성이 적다.

• 삽입정렬

  앞에서 부터 정렬 범위를 넓혀가며 새로운 요소의 위치를 옮겨 정렬을 맞추는 방식.
  최악의 경우 버블정렬의 성능과 같으나 평균적으로는 조금 더 낫다.

• 퀵 정렬

  기준 요소 선정 하여 기준보다 작은 것은 왼쪽 큰것은 오른쪽으로 이동. 이동완료 후 왼쪽과 오른쪽 부분으로 나눈다.
  분할된 요소에 대해 반복적으로 기준요소 선정 > 요소 이동 > 분할 을 하여 정렬을 맞추는 방식.
  매우 빠른 속도로 정렬 할 수 있다.

탐색

• 순차탐색

  처음부터 끝까지 모든 요소를 검사하는 전략. 성능은 나쁘나 구현이 간단하여 버그를 만들 가능성이 적다.

  • 전진 이동법

  • 전위법

  • 계수법

• 이진탐색

  정렬된 배열 에 사용 할 수 있는 '고속' 탐색 알고리즘.
  중앙 요소를 선택 후 작은 요소는 왼편 큰 요소는 오른편에 위치 하므로, 중앙값이 원하는 값이 아니라면 원하는 값을 찾을 때까지 왼쪽 또는 오른쪽 부분을 탐색 대상으로 선정하여 탐색하는 방법.
  

• 이진 트리 탐색

  • Binary Search Tree (이진 탐색 트리)

    링크드 리스트처럼 동적으로 노드를 추가,제거 할 수 있으면서 이진 탐색 알고리즘을 사용 할 수 있는 자료구조.
    빠른 탐색이 가능하다.

  • Red Black Tree (레드 블랙 트리)

    불균형하게 성장된 이진 탐색 트리는 검색 효율이 매우 낮으므로 균일하게 성장하는 이진탐색 트리를 위한 자료구조.
    평균적으로 이진탐색트리에 비해 더 빠른 탐색이 가능하다.

우선순위 큐와 힙

• Heap (힙)

  효율적인 우선순위 큐를 구현할때 사용되는 이진트리 기반 자료구조.
  트리내 모든 노드는 부모 노드보다 우선순위가 낮아야 한다. 힙에서 가장 우선순위가 높은 노드는 뿌리 노드이다.
  이진 탐색은 할 수 없다.

해시 테이블

• Hash Table (해시 테이블)

  데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력 받은 데이터를 해싱하여 테이블 내 주소를 계산하고 이 주소에 데이터를 담는 방법.

  • 충돌 해결기법

    • Open Hashing (개방 해싱)

      해시 테이블의 주소 바깥에 새로운 공간을 할당하여 문제를 수습하는 방법

    • Closed Hashing (폐쇄 해싱)

      처음에 주어진 해시 테이블 공간 안에서 문제를 해결하는 방법

  Open Addressing (개방 주소법)

  충돌이 일어나면 해시 테이블 내의 새로운 주소를 탐사하여 충돌된 데이터를 입력하는 방식으로 동작.
  선형 탐사, 제곱 탐사, 이중 해싱, 재해싱 등이 있다.

  • 이중해싱

    해시 함수 2개를 준비하여 하나는 최초의 주소를 얻을때, 또 다른 하나는 충돌이 일어날 때 탐사 이동폭을 얻기 위해 사용하는 방법.
    탐사 이동폭의 규칙성은 없애면서도 같은 키에 대해서는 항상 똑같은 결과를 얻을 수 있다.

  • 재해싱

    해시 테이블의 여유공간 거의 찼을경우 성능저하를 막아낼 방법이 없기에 해시 테이블 크기를 늘리고 늘어난 해시 테이블 크기에 맞춰 테이블 내의 모든 데이터를 다시 해싱하는 방법.
    통계적으로 해시 테이블 공간 사용률이 70%~80%에 이르면 성능 저하가 나타나므로 임계치를 75% 수준으로 설정하는것이 일반적이다.

  Chaining (체이닝)

  체이닝 기반 해시 테이블은 데이터 대신 링크드 리스트 또는 이진트리에 대한 포인터를 관리 하도록 하여, 충돌이 일어날 경우 해당 주소의 링크드 리스트 또는 이진트리에 데이터를 저장하는 방식.