알고리즘 공부

Algorithm

알고리즘 : 문제 해결을 위한 전략 (Strategy to solve problem)

Issue of Algorithm

1. 단계별로 어떤 작업을 수행하는가?
2. 작업들을 어떻게 배치시킬 것인가?
3. 얼마나 효율적인가?
4. 문제를 해결할 수 있는가?

문제 해결을 위해 가장 먼저 해야하는 것 :

​ 주어진 문제를 알고리즘을 적용할 수 있도록 명확하게 정의하는 것

알고리즘의 종류

1. 순차 탐색(Sequential Search) :

   모든 데이터를 순차적으로 탐색하는 알고리즘

   모든 문제에 적용가능하다.

   비효율적이다.

2. 이진탐색(Binary Search) :

   오름차순(또는 내림차순)으로 정렬된 데이터를 반으로 나누고 나누어진 데이터를 다시 반으로 나누는 과정을 반복해 원하는 데이터를 찾는 알고리즘

3. 그리디 알고리즘(Greedy Algorithm) :

   미래를 고려하지않고 선택할 때마다 가장 최선의 선택을 하는 알고리즘

   잔돈을 거슬러줄 때 사용하는 알고리즘

4. 백트래킹(Back tracking) :

   조건이 만족하는 경우에만 모든 조합의 수를 살펴보는 알고리즘

   미로탈출

오일러 경로 :

​ 오일러 경로 :그래프의 모든 변을 한번씩만 방문하는 연속된 경로

​ 정점에 연결된 변의 개수가 홀수인 정점이 2개여야한다(시작점, 끝점)

​ 오일러 회로 : 시작점과 끝점이 같은 오일러 경로

​ 정점에 연결된 변의 개수가 모두 짝수개이다.