#4 [C 자료구조] 그래서 알고리즘이 뭔데?

1. 알고리즘이란?

알고리즘은 크게 우리가 고등학교 때 풀었던 수학문제의 '풀이법'이라고 볼 수 있다.

풀이법에는 여러 방법이 존재하고 어떻게해야 명확하게 빨리 풀 수 있는지, 방법이 존재한다.

때로는 경우의 수를, 때로는 정형화된 공식을 사용할 수 있어야한다.

알고리즘은 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로, 컴퓨터 언어로 표현한 것이다.

이 것이 알고리즘이 동작하는 방식이다.

 

2. 알고리즘의 종류 예시

순차탐색

최대 숫자를 찾는 방법은?

임의의 숫자를 찾을 때 뒷 숫자와 앞 숫자를 비교해서 큰 숫자만을 계속 들고 있는 방식으로 가장 큰수를 찾을 수 있다.

*이진탐색: 정렬된 데이터를 반으로 나누고, 숫자를 비교하고 다시 반으로 나누고 하는 작업을 반복 한 뒤에 원하는 데이터를 찾는 방식. 기존 순차 탐색에 비해 훨씬 빠름

 

그리디 알고리즘

가장 적은 숫자의 동전을 지불하는 방법은?

가장 큰 액면의 동전부터 지불하면서 동전을 소비해나가는 방식을 선택한다.

 

한붓 그리기(오일러 트레일)

시작점 부터 모든 선분을 한 번만 지나서 출발점으로 돌아오는 방법은? 선분은 겹치면 안되지만 점을 겹쳐도된다.

모든 꼭지점이 짝수점이거나 단 두개의 꼭지점만 홀수점이면 가능. 

 

3. 알고리즘 표현 방식

종류	내용	특성
자연어	일반적인 언어	부적절
순서도	알고리즘 도식화	쉬움, 단순한 것만 가능
의사 코드	유사 프로그래밍 언어	가상코드, 유사코드, 슈도 코드라 불림. 프로그래밍 언어에 비해 덜 엄격한 문법
프로그래밍 언어	C와 같은 실제 프로그래밍 언어	복잡한 것 가능. 너무 엄격해서 비효율적일 수도 있음

실제로 알고리즘은 순서도와 프로그래밍 언어를 가장 많이 쓴다.

머리 속에서 구성할 때는 순서도를 그려서 간단하게, 실제로 도출할 때는 프로그래밍 언어를 사용한다.

 

4. 알고리즘의 조건

• 입력: 외부에서 제공되는 자료가 0개 이상이다.
• 출력: 적어도 1개 이상의 결과를 생성한다.
• 명백성: 각 명령어는 의미가 모호하지 않다.
• 유한성: 무한히 동작해서는 안된다.
• 유효성: 불필요한 연산을 포함해서는 안된다. 

 

지금까지의 알고리즘은 그다지 어렵지 않을 것이다. 뭔가 수학 공식이라고 생각하고 구하면 되니까!그건 니생각이고

다음번에는 알고리즘을 제일 먼저 포기하게 된다는 복잡도에 대해서 '쉽게' 알아보도록 하자.