알고리즘 기본

참고페이지
- 리브레위키

알고리즘의 필요성

• 동일한 결과를 내는데 다양한 알고리즘이 적용될 수 있다.
• 이때, 결과가 동일하더라고 사용하는 알고리즘에 따라 프로그램의 속도나 처리방식 등이 크데 차이가 난다.
• 또, 데이터의 크기/개수 (n)에 따라 이의 계산횟수, 수행 시간이 크게 달라지기 때문에 데이터가 클수록 알고리즘은 중요하다.

시간복잡도

• 입력받는 데이터의 크기에 따른 알고리즘의 수행시간의 변화
• 주로 빅오표기법으로 나타낸다.
  

자료구조

• 데이터를 저장하는 방식. 수많은 자료구조 중 데이터에 맞는 특성을 지닌 자료구조를 선택하는 것은 효율적인 알고리즘 작성에 필수적이다.
• 이 페이지에선 전체적 구조만 살펴보고 자세한 내용과 구현은 자료구조 페이지를 따로 구성해서 공부한다.

선형자료구조

• 랜덤접근가능 - 모든 자료에 O(1)으로 접근이 보장되는 자료구조
  1. 배열
  2. 해시
• 랜덤접근불가능
  1. 스택 : 후입선출, push, pop
  2. 큐 : 선입선출, enqueue, dequeue
  3. 데크 : 스택과 큐의 융합형태
  4. 연결리스트 : 값, 다음노드, 가장 간단하게 구현한 것이 큐

비선형 자료구조

• 선형 자료구조가 아닌 모든 자료구조이다. 다만,사전적인 정의를 하자면 i 번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조를 의미한다.

1. 그래프 : 순회알고리즘(깊이우선탐색 DFS, 너비우선탐색 BFS)

2. 트리 : 이진검색트리

3. 문자열 : java에서는 기본 자료형으로 제공

   정렬 알고리즘

   안정정렬

• 버블정렬
• 삽입정렬

  불안정정렬

• 선택정렬
• 퀵정렬
• 힙정렬