[알고리즘] 알고리즘이란?

program은  자료구조 + 알고리즘으로 이루어져있다. 

예를 들어 최대값 탐색 프로그램을 짠다고 하면 그 안에는 탐색할 요소가 담긴 자료구조(ex. List) + 해당 알고리즘(ex. 순차탐색)이 들어있을 것이다.

이때 자료구조는 쉬운 접근과 수정을 위해 데이터를 조직하고 저장하는 방법이다.

자료구조에는 아래 표와 같이 크게 다섯가지가 있다.

List

Stack

Queue

Tree

Graph

알고리즘의 유래

알고리즘은 Al-Khowarizmi (알콰리즈미)라는 한 수학자의 이름에서 착안되었다.

알고리즘의 정의

전형적으로 입력을 출력으로 변환하는 일련의 계산 단계를 의미한다.

알고리즘의 두가지 조건

• 정당성 - 모든 인풋에 대하여 정확한 아웃풋이 나오고 종료되어야 한다. (무한루프는 정당하지 않음)
• 효율성 -  많은 알고리즘 중에서 상대적으로 효율성이 좋은걸 선택해야한다.

효율적인 알고리즘의 예

1. 물건을 사고 거스름 돈을 동전으로만 받아야하는 상황에서 가장 적은 수의 동전을 받을 수 있는 방법은? (단 , 동전으로는 500원 100원, 50원, 10원이 사용된다.
   • Greedy method : 매 단계 가능한 해들 중 가장 좋은 해를 찾는 기법을 사용하면 가장 적은 수의 동전을 구할 수 있다. 이 기법은 700원을 거스름돈으로
     • 항상 이 방식으로 이러한 문제가 풀리는 것은 아니다.  예를 들어 180원을 거스름돈으로 받아야하는데 100원, 90원, 50원, 10원이 있다고 하자. 이때 우리는 90원 2개로 거스름돈을 해결할 수 있지만, 그리디 방법으로 찾는다면 100원 1개 10원 8개로 총 아홉개의 동전을 받게된다. 
     • 그리디 방법으로 해결하려면 동전과 동전 사이의 관계가 약수관계여야 한다.
2. 엄청 많은 n개의 동전이 있고, 그 속에 가짜 동전이 섞여있다. 이 가짜 동전은 매우 정교하게 만들어져서 눈으로는 가까인지 식별할 수 없지만, 무게가 정상적인 동전보다 약간 가벼워. 1개의 양팔 저울만을 사용해서 이 가짜 동전을 최소한의 저울질로 찾아낼 수 있는 방법은?
   • Divide and conquer : 주어진 문제의 입력을 분할해 문제를 해결하는 기법 
     • 짝수라면 동전들을 절반으로 나눠서 가벼운 쪽의 분할을 반복한다.
     • 홀수라면 동전을 하나빼고 절반을 나눠서 가벼운 쪽의 분할을 반복한다. (이때 두 동전꾸러미의 무게가 같으면 빼놓은 동전이 가짜이다.)