22년 7월 8일_알고리즘이란?

어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것

 

작업을 수행하는 방법을 정의하는 단계들의 집합

 

알고리즘의 어원흔 9세기경의 수학자 알콰리즈미의 이름에서 유래되었음

 

프로그램 = 자료구조 + 알고리즘

 

 

알고리즘으로 해결할 수 있는 문제의 예

 

내비게이션 ; 두 지점간의 최단 경로나 최단 시간이 걸리는 경로를 찾아주는 최단 경로 알고리즘이 필요

인터넷검색 : 수조 페이지 이상의 데이터가 존재하는 인터넷에서 원하는 정보를 최대한 빨리 정확하기 검색해주는 알고리즘이 필요

등 제조공정, 현금 자동인출기 ..

 

알고리즘의 개념

 

알고리즘의 조건

입력 : 0개이상의 데이터 입력이 있어야함

출력 : 적어도 하나 이상의 결과를 출력해야함

명확성 : 각 단계와 명령을 모호하지 않고 명확해야함

유한성 : 유한한 단계를 거친 후에는 반드시 종료해야함

우효성 : 각 명령어들은 실행이 가능해야 함

 

효율적인 알고리즘 설계 기법 

1. 분할정복(divide and conquer)

2. 동적 프로그래밍(dynamic programming)

3. 그리디 알고리즘(greedy algorithm)

4. 백트래킹(backtracking)

 

1. 분할정복

 

작은 여러 개의 부분 문제로 분할하여 문제를 해결하는 방법

분할, 정복, 결합의 과정을 거침

 

2. 동적 프로그래밍

 

문제를 여러개의 하위 문제로 나누어 푼 다음 그것을 결합하여 최종적인 목적에 도달하는 것

동적 프로그래밍의 부분 문제들은 의존적 관계가 존재

 

3. 그리디 알고리즘

 

선택해야 할 방법이 여러가지일 때 현재 상황에서 가장 최선인 것을 먼저 선택하는 기법

그 순간 최적이라고 생각되는 것을 선택해 나가는 방식

 

4. 백트래킹

 

우선 어떤 하나의 가능한 경우를 확인하고 가능하지 않다면 다시 되돌아가고 다시 다른 가능성이 있는 경우를 확인해 감

알고리즘의 구조 특성상 재귀 함수를 사용하여 구현됨