2. 기본자료 구조

1. 비선형구조

트리

트리는 비선형구조로 노드와 branch로 연결된 그래프의 형태다.

트리의 종류

-> 이진트리, 완전이진트리, 기타이진트리, 경사이진트리

• 이진트리란?
  2개의 서브트리를 가지고 있는 트리
  n개의 노드를 가진 이진트리는 n-1개의 branch를 가진다.
  높이가 H인 경우 h개의 노드를 가지며 2h-1개의 높이를 가진다.
  

  

• complete binary tree
  

  

• fully binary tree
  자식노드가 없거나 최대 둘뿐인것, 자식을 하나만 가진 노드가 없다.
  

  

• 이진트리 운행법

• preorder: root-left-right

• inorder: left-root-right

• postorder: left-right-root

그래프

그래프란 각각의 정보를 링크로 연결해서 구조화시킨 비선형자료구조다.

• 그래프 순회 알고리즘

• 깊이 우선 탐색
  끝까지 그래프를 진행하다가 더이상 진행 할 수 없으면 거슬러 올라가면서 가보지 않은 노드를 가보는 방식

• 넓이 우선 탐색
  가까운 정점을 보두 방문한 후 다음 가까운 정점을 방문하는 순

2. 알고리즘 설계 방법

1) 그리디 알고리즘
-> 최적화 문제를 해결하는 알고리즘이다. 최적화 문제 가장 좋은 해를 찾는 문제다.
동전 거스름돈 찾기, 최단경로찾기, 최소신장트리, 집합커버문제, 작업스케줄링 등이 있다.

2) 동적 프로그래밍
입력크기가 작은 부분문제들을 모두 해결한 다음 그 해를 이용해서 큰 크기의 부분문제를 해결해서 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘이다.
모든 쌍 최단경로, 배낭문제, 동전 거스름돈, 연속행렬곱셈등이 있다.

3) 분할 정복 알고리즘
주어진 문제의 입력을 분할하여 문젤르 해결하는 방식의 알고리즘이다.
합병정렬, 퀵정렬, 선택문제 등이 있다.

알고리즘의 효율성 분석

알고리즘 계산이 얼마나 복잡한지 나타내는 것을 계산 복잡도라고 하며 빅오표기법을 가장 많이 사용한다.
알고리즘의 계산 복잡도는 시간복잡도와 공간 복잡도로 나눌 수 있다.
시간 복잡도는 알고리즘을 수행하는데 얼마나 오랜 시간이 걸리는지 분석한 것이다.
공간 복잡도는 알고리즘을 수행하는데 얼마나 많은 공간이 필요한지 분석한 것이다.

• 빅오표기법
  O(n): 필요한 계산 횟수가 입력 크기 N과 비례할때
  O(1): 필요한 계산 횟수가 입력 크기 N과 무관할때

예를 들어) N=100이라면 1-100까지의 n의 제곱을 다 계산하는 프로그램이다.
이 프로그램의 계산 복잡도는 무엇일까요? => O(n) N의 갯수에 따라 계산되기 때문에!

재귀알고리즘

재귀알고리즘은 어떤 함수 안에서 다시 자기 자신을 부르는 것을 의미한다.
팩토리얼을 계산할때 팩토리얼 n!을 하면 팩토리얼(n-1)!만큼을 계산하는데 이는 직관적이지만 비효율적이다.
이런 경유는 순환을 사용하지 않고 반복구조를 사용하면 더 효율적으로 계산할 수 있다.

하노이탑

하노이탑은 원반 옮기기다.
하노이탑을 할때 정해진 규칙은 이와 같다.

• 원반은 한번에 1개
• 크기가 다른 원반 n개를 출발점에서 도착점으로 모두 옯겨야한다.
• 원반을 옮길때는 한 기중의 만위를 뽑아 다른 기둥의 맨위로만 가능하다. (중간에 원반을 빼거나 다른 기중의 중간으로 넣을 수 없다.
• 원반을 옮길때 작은 원반위에 큰원반을 옯길 수 없다.