20210612

Array와 LinkedList

	Array	LinkedList
특정 원소 조회	O(1)	O(N)
중간에 삽입 삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 한다	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
정리	데이터에 접근하는 경우가 빈번하다면 Array를 사용하자	삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다.

이진 탐색

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식

재귀 함수

자기 자신을 호출하는 함수

• 재귀 : 어떠한 것을 정의할 때 자기 자신을 참조하는 것

정렬

정렬이란 데이터를 순서대로 나열하는 방법

• 버블 정렬 : 두 인접한 원소를 검사하여 정렬하는 방법
• 선택 정렬 :
  1. 주어진 리스트 중에 최소값을 찾는다.
  2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
  3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
• 삽입 정렬 : 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입
• 병합 정렬 : 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복

스택

• Last In First Out (LIFO)
  ex ) 빨래통, 되돌리기(ctrl + z)

큐

• First In First Out (FIFO)
  ex ) 놀이공원