알고리즘(Algorithm)

개요

알고리즘이란 어떠한 문제를 해결하기 위한 일련의 수행 과정이다. 실제 개발에 자주 등장하며, 그렇기에 프로그래머에게는 피할 수 없는 숙명이다.

조건

알고리즘을 사용함으로써 우리는 효율적인 개발이 가능해진다. 이러한 효과를 발휘하기 위해서는 다음과 같은 조건을 만족해야 한다.

• 입력 : 외부에서 제공된 자료가 존재해야 한다.
• 출력 : 최소 1개 이상의 결과를 가져야한다.
• 효과성 : 모든 연산은 사람이 유한한 시간 안에 수행할 수 있을 정도로 충분히 단순해야 한다.
• 명학성 : 각 단계는 명확하여 애매함이 없어야 한다.
• 유한성 : 모든 단계들을 실행하는 횟수는 유한해야 한다.

종류

• 길찾기 알고리즘 (dijkstra, A* 등)
• 정렬 (선택 정렬, 위상 정렬, 버블 정렬 등)
• ...

시간 복잡도(Time Complexity)

같은 결과를 도출해내는 여러 알고리즘이 모두 좋은 것은 아니다. 내가 개발한 또는 사용하고자 하는 알고리즘이 효율적인지 판단하기 위해서는 어떠한 기준이 있어야 한다. 그중 하나가 시간 복잡도이다. 시간 복잡도는 사용하는 자료의 수를 토대로 알고리즘의 예상 소요 시간을 예측할 수 있다.
만약 자료의 크기가 N이라면, N^2의 반복 횟수를 가지는 알고리즘과 Nx2의 반복 횟수를 가지는 알고리즘의 차이는 N의 크기가 커질수록 명확하다.
시간 복잡도를 표기할 때는 Big-O 표기법을 사용한다. 위 2가지를 Big-O 표기법으로 표기한다면, O(N^2), O(Nx2)로 표기할 수 있다.

공간 복잡도(Space Complexity)

시간 복잡도처럼 Big-O 표기법을 사용하며 중요도는 떨이지는 편이다. 하지만 임베디드, 펌웨어 등 하드웨어 환경이 극도로 한정되어 있을 경우에는 그 중요도가 상당히 올라간다.

참고

https://namu.wiki/w/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://m.blog.naver.com/ndb796/221226794899