[알고리즘] 알고리즘의 개념

[알고리즘] 알고리즘의 개념

 

 

1. 알고리즘의 개념

-컴퓨터 과학은 컴퓨터를 활용해 주어진 문제를 해결하기 위한 학문이다.

-알고리즘(Algorithm)은 주어진 문제를 해결하기 위한 일련의 단계적인 처리 과정 (ex: 음식의 조리법)

-알고리즘은 다양한 분야에서 사용되지만, 특히 컴퓨터를 활용해 문제를 해결하기 위한 분야라고 할 수 있다.

 

 

2. 대표적인 알고리즘

(1) 퀘닉스버그 다리 문제 (오일러 경로 문제 Eulerian Path)

-그래프의 모든 간선을 오직 한 번만 지나가는 경로를 찾는 문제를 '오일러 경로 문제'라고 부른다. 이는 퀘닉스버그 다리 문제에서 유래되었다.

-오일러 경로 문제 해결 알고리즘: 각 정점의 차수가 홀수인 정점이 없거나, 2개이면 오일러 경로가 존재한다. 만약 차수가 홀수인 정점이 2개 이상 존재시, 반드시 홀수 정점에서 시작해야 한다.

 

(2) 다익스트라 알고리즘(Dijkstra Algorithm)

-다익스트라 알고리즘은 하나의 출발점을 기준으로 다른 모든 정점으로의 최단 경로를 구하는 문제이다.

 

 

3. 알고리즘의 조건

1. 입출력(Input & Output): 외부에서 0개 이상의 입력을 받아 1개 이상의 출력을 생성해야 함
2. 명확성 (Definiteness): 각 단계는 모호하지 않고 단순하고 명확해야 함
3. 유한성(Finiteness): 한정된 수의 단계를 거친 후에는 반드시 끝나야 함
4. 유효성(Effectiveness): 모든 명령은 컴퓨터에서 수행할 수 있어야 함

-> 알고리즘은 궁극적으로 컴퓨터에서 수행되어 결과를 생성하는 것을 목표로 한다.

-> 실용적인 관점에서는 알고리즘이 효율적이어야 한다는 조건 역시 만족해야 함

=> 효율적인 알고리즘이 되어야만 현실적인 시간 내에 원하는 결과를 얻을 수 있기 때문!