자료구조 (Data Structure)

• 자료 값의 모임, 자료 간의 관계, 그리고 자료에 적용할 수 있는 함수나 명령
• 만능 자료구조 → X, 상황에 맞게 사용해야 함
• 자료(Data) - 현실 세계로부터 수집한 사실 or 개념의 값 or 이들의 집합

  • cf) 정보(Information) - 자료를 특정 용도로 사용하기 위해 처리/가공한 것

추상자료형 (Abstract data type as ADT)

• 자료구조와 유사하지만, 구체적인 구현 방법 X
• 자료구조를 구현할 때에는 자료구조 자체를 자세히 알아야 하지만, 활용하기 위해서는 추상자료형만 알아도 됨
• OOP 관점에서 추상 클래스(Abstract class) 역할 -> 추상자료형 + 구현 => 자료구조

자료구조의 분류 (1)

선형 자료구조 (Linear data Structure)

• 배열(Array)
• 리스트 (List)
• 스택 (Stack) ← 후입선출(LIFO)
• 큐 (Queue) ← 선입선출(FIPO)
• 해시 셋 (Hash set) → content-based(그림, 문자열, ...)
• 해시 테이블 (Hash table) → 〃

자료구조의 분류 (2)

비선형 자료구조 (Nonlinear data structure)

• 트리 (Tree)
• 그래프 (Graph)
• 힙 (Heap, Priority queue)
• 트라이 (Trie; Retrieval tree) -> 검색트리

자료구조의 필요성

• 필요한 자료에 효율적으로 빠르게 접근할 수 있게 함
• 저장장치를 효율적으로 사용할 수 있게 함
• 자료구조 별로 적절한 알고리즘을 기계적으로 적용할 수 있음
• 협업에 큰 도움

알고리즘 (Algorithm)

어떤 문제 해결을 위한 절차(Procedure)나 방법(Method)

알고리즘의 조건

• 입력 (Input)
• 출력 (Output) (다른 입력에 대해 출력이 최소 2가지 이상 (한 가지면 그저 메모리))
• 명확성 (Definiteness)
• 유한성 (Finiteness)
• 효과성 (Effectiveness)

알고리즘의 준류

기초 알고리즘

선형 자료구조에 적용 (직관적)
 	⋅ 정렬 (Sorthin)
 	⋅ 이진 탐색 (Binary search)
 	⋅ 투 포인터 (Two pointers)

• 탐욕법 (Greedy)

고급 알고리즘

• 분할 정복 (Divide & conquer)
• 동적계획법 (Dynamic programming)
• 백트래킹 (Backtracking) - N-Queen
• 최단 경로 (Minimum distance path)
• 최소 신장 트리 (Minimum spanning tree)

복잡도 (Complexity)

• 알고리즘의 성능을 나타내는 척도

• 시간 복잡도 (Time complexity) → 알고리즘을 동작하는 데에 필요한 연산의 횟수(시간)

• 공간 복잡도 (Space complexity) → 알고리즘의 동작에 필요한 메모리의 크기 (kilobyte, gigabyte)

• 일반적으로 시간 복잡도와 공간 복잡도는 trade-off 관계가 있다.

  시간 복잡도 (Time complexity)

  • 계산 복잡도 (Computational complexity) 라고도 부르며, 알고리즘의 동작에 필요한 연산의 횟수 → 여기서 연산은 기초 연산(elementary operation)을 의미
  • 시간 복잡도(계산 복잡도)가 낮을수록 더 알고리즘의 성능 (performance → 빠르고 적은 메모리)가 좋다고 한다.

  공간 복잡도 (Space complexity)

  • 알고리즘의 동작에 필요한 메모리(RAM(주기억장치):Random Access Memory)의 크기
  • 일반적으로 알고리즘이 동작하기 위해 필요한 메모리의 최대치 (Peak memory)를 공간 복잡도라고 한다.

복잡도의 비교

• 절대적으로 성능이 더 좋은 알고리즘이 있는가?

• 복잡도를 비교할 때 단위는 어떻게 정할 것인가?

• 알고리즘 복잡도 비교의 어려운 점

  • 시간 복잡도 vs 공간 복잡도 trade-off
  • 자료의 크기에 따른 복잡도의 차이
  • 자료의 내용에 따른 복잡도의 차이

복잡도의 분류

• 알고리즘 동작 상황에 따른 구분

  • 최악의 경우 ← 거꾸로 정렬된 리스트
  • 최선의 경우 ← 이미 정렬된 리스트
  • 평균적인 경우 → 모든 경우의 평균

• 일반적으로 최악의 경우에 대해 알고리즘 복잡도 정의

점진적 표기법

• 알고리즘에 입력되는 자료의 개수가 충분히 많다고 가정
• 성능 평가에 공평한 비교를 하기 위해 사용
  

빅오 표기법(Big-O Notation)

• 충분히 큰 N에서 가장 큰 영향력을 주는 항을 기준으로 표기법 결정