자료구조

• 데이터를 조작하는 방법
• 자료구조는 컨셉, 개념이기 때문에 어떠한 언어든 구현이 가능하다.
• 구현력 상승에 도움이 된다.

재귀

• 자기 자신을 호출하는 함수

• 기저조건 : 재귀를 중단 시키는 조건

• 재귀조건 : 기저조건으로 수렴하게 되는 조건

• 재귀에는 단점이 존재
  - 함수 호출에 따른 오버헤드가 있다. 이로인해 오버플로가 발생할 수 있다.
  - 오버헤드 : 어떤 처리를 하기 위해 들어가는 간접적인 처리시간, 메모리등을 말함
  - 오버플로 : 스택이 가용할 수 있는 공간을 벗어나는 것을 말한다.
  

자료구조

종류

• 선형구조
  - 리스트
  - 스택
  - 큐
  

• 비선형구조
  - 그래프
  - 트리

• 연산
  - 읽기 : 자료구조 내 특정 위치를 찾아보는 것이다.

  • 검색 : 자료구조 내 특정 값을 찾는 것이다.
  • 삽입 : 자료구조에 새로운 값을 추가하는 것이다.
  • 삭제 : 자료구조 내 특정 값을 삭제하는 것이다.

구현

• 순차 자료구조
  - 모든 데이터가 메모리에 연속적으로 저장된다.
  • 임의 원소에 즉각적으로 접근할 수 있다.
  • 캐시 지역성 효과로 인해 모든 데이터를 순회하는 것이 매우 빠르다.
  • 데이터 저장을 위해 정확하게 데이터 크기만큼 메모리를 사용한다.
• 연결 자료구조
  - 데이터는 노드에 저장되고, 노드는 메모리 곳곳에 흩어져 있을 수 있다.
  • 임의 원소에 접근하는 것은 선형 시간 복잡도를 가지며 느린 편이다.
  • 캐시 지역성 효과가 없어 모든 데이터를 순회하는 것이 느리다.
  • 각 노드에서 포인터 저장을 위해 여분의 메모리를 사용한다.

지역성 : CPU가 기억장치의 측정 부분에 위치한 
데이터나 프로그램 코드를 집중적으로 액세스하는 현상이다

시간복잡도

• 알고리즘을 수행하는 데 필요한 연산이 몇 번 실행되는지 숫자로 표기한 것