알고리즘이란?

알고리즘이란

: 어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한 것

ex) 집에서 학교로 가는 길 찾기, 샌드위치 만드는 방법, 매점에 가서 물건 구매하기 등등

프로그래밍에서 알고리즘은 input 값을 통해 output 값을 얻기 위한 계산 과정이고

이러한 문제를 해결 할 때 정확하고 효율적으로 결과값을 얻기 위해서 알고리즘이 필요하다.

 

프로그래밍을 통해서 어떤 문제를 해결 하려면 기본적으로 다음과 같은 순서로 작업을 하게 된다.

문제의 이해/분석 -> 해결방안 구상(알고리즘 구상) -> 프로그래밍(코딩) -> 실행 및 검증(디버깅)

문제를 이해하고 해결방안을 구상하는 것이라고 할 수 있고, 해결방안 구상이라는 것은 단순히 머리로만 생각하는 것이 아니라 논리적으로 명세화(데이터형의 논리적 구성을 표현한 것) 시켜놓는 것을 말합니다.

즉, 알고리즘은 논리적이여야 하고 반드시 명세화가 되어 있어야 합니다.

명세화 시키는 방법에는 여러가지가 있습니다. 순서도를 이용 할 수도 있고, pseudo code를 짜거나 글로 기술 할 수도 있습니다. 중요한 것은 명세화, 즉 적어놔야 한다는 것입니다.

 

알고리즘 조건

- 입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.

- 출력 : 적어도 2개 이상의 서로 다른 값을 내어야 한다.

즉, 모든 입력에 하나의 출력이 나오면 안된다.

- 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성 되어야 한다.

- 유한성 : 유한 번의 명령어를 수행 후 유한 시간 내에 종료한다.

- 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.

 

좋은 알고리즘이란?

알고리즘을 짤 때는 항상 성능을 고려 하여야 합니다.

성능을 분석 할 때는 공간 복잡도(space complexity, 총 저장공간의 양)와 시간 복잡도(time complexity, 총 소요시간)를 고려합니다. 공간 복잡도는 프로그램 실행 시 필요한 고정 또는 가변 메모리의 양을 의미하고 시간 복잡도는 프로그램의 컴파일 시간과 실행시간의 합을 의미합니다.

 

좋은 알고리즘은 공간 복잡도와 시간 복잡도가 작은 알고리즘을 말합니다.

즉, 저장 공간을 적게 사용하고 프로그램 수행시간이 적어야 한다는 것입니다.

최근에는 공간 복잡도 < 시간 복잡도를 더 중요하게 생각합니다.

(요즘에는 하드웨어 비용이 저렴하기 때문에 메모리 비용에 대한 부담이 적어졌기 때문입니다.)

 

시간 복잡도에서는 실행시간이 중요합니다. 컴파일 시간은 사람이 제어 할 수 없는 경우가 많기 때문입니다.

즉, 알고리즘을 구상 할 때 반복문의 실행빈도에 따른 명령문의 실행횟수가 중요하다고 할 수 있습니다.

(간단하게 말하면 좋은 알고리즘 -> 반복문이 몇 번 실행 되는가라는 물음으로도 답할 수 있다.)

 

https://gomcine.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%98-%EC%A0%95%EC%9D%98%EC%99%80-%EA%B8%B0%EB%B3%B8%EA%B0%9C%EB%85%90

[알고리즘 #1] 알고리즘의 정의와 기본개념

 

위 사이트보다 좀 더 쉽게 설명을 해주고

알고리즘을 풀 수 있는 사이트를 추천 해줘서 좋은 사이트인 것 같다.

https://blog.yena.io/studynote/2018/11/14/Algorithm-Basic.html

[Algorithm] 알고리즘 공부 시작 방법 및 순서