알고리즘 복잡도 분석

알고리즘이란 문제해결 전략이다.

• 자료구조 : array, list, stack, queue
• 알고리즘 : 문제해결방법 (자료구조를 바탕으로 문제를 해결한다)

기본 자료구조

• 배열

  ex) int a[] = new int[5]
  // a = int의 배열이다. 타입과 갯수가 정해져 있다.
  // 크기가 고정되어있지만, 읽을때 엄청 빨리 읽는다.
  O(1)읽기
  

• 리스트 : LinkedList(참조 혹은 포인터) O(n)번만에 읽을 수 있다. O(1)만에 추가가 된다. 읽기는 오래걸리지만 쓰기는 굉장히 빠르다. 각각의 노드마다 주소값이 저장되어있기때문에 공간의 낭비가 심하다.
• 스택 : LIFO
• 큐 : FIFO
• 트리 : 일방향(싸이클이 없다)
• 그래프 : 그래프는 트리랑 구조가 유사한데, 각 노드들이 연결되어있다? 그래프는 트리의 일종이지만 싸이클이 생기지 Object를 통해 만든다. key의 중복이 안된다. key로 값을 읽어 오고 싶을때 사용.

배열과 해시를 이용하면 대부분의 코딩문제들이 해결된다.

정렬

• 선택 정렬
• 버블 정렬
• 삽입 정렬
• 쉘 정렬
• 퀵 정렬
• 기수 정렬
• 힙 정렬
• 병합 정렬
• 외부 정렬

동작코드를 다 외어야 된다.

트리와 검색

• 순차 검색
• 2진 검색
• BST 검색
• AVL 트리
• 레드블랙 트리
• MST
• B TREE

그래프와 탐색

• 전위 중위 후위
• 다익스트라 최단거리
• 플로이드 알고리즘
• A* 알고리즘

알고리즘 전략

• 휴리스틱 알고리즘
• 그리디 알고리즘
• 몬테카를로 알고리즘
• 분할 정복
• 다이나믹 프그로래밍
• 백 트래킹

정렬

• 정렬을 할때는 비교기준이 있어야한다. 그 비교기준을 내가 세운다.

  arr = [1, 11, 2, 20, 3, 5, 9];
  arr.sort(function(a, b) {
    return a-b;
  });
  

  b = [
  { name: 'honux', money: 100, score: 100 },
  { name: 'crong', money: 50, score: 500 },
  { name: 'jimmy', money: 999, score: 10 } ]
  b.sort((a, b) => (b.score - a.score) );