알고리즘
알고리즘
문제를 해결하기 위해 일련의 절차를 정의하고, 공신화한 형태로 표현한 일종의 문제 풀이 방법
알고리즘의 충족 조건
- 입력(Input) : 출력에 필요한 자료를 입력받아야 한다.
- 출력(Output) : 한 가지 이상의 결과가 반드시 출력되어야 한다.
- 유한성(Finiteness) : 유한한 시간 내에 종료되어야 한다.
- 명확성(Definiteness) : 각 단계는 단순하고 명확해야 한다.
- 효율성(Efficiency) : 가능한 한 효율적이어야 한다.
알고리즘의 중요성
좋은 알고리즘은 절차가 명확하고 효율적이다. 따라서, 다양한 문제 해결 과정에서 나타나는 불필요한 작업을 줄여준다.
단, 정확하지 않은 알고리즘은 정확하지 않은 결과를 내놓게 됨으로, 정확하게 짜는 것이 중요하다.
알고리즘 푸는법
- 문제 이해하기 : 주어진 조건을 바탕으로 문제가 무엇인지 이해하는 것이 필요하다.
- 문제 해결 전략 세우기 : 코드 작성에 앞서, 수도코드를 먼저 작성해본다.
- 전략을 코드로 옮기기 : 세운 전략을 코드로 옮겨본다.
시간 복잡도(Time complexity)
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는지를 나타내는 것
시간 복잡도 표기법
- Big-O(빅-오) -> 최악
- Big-Ω(빅-오메가) -> 최선
- Big-θ(빅-세타) -> 평균
이 중 Big-O 표기법을 가장 자주 사용되는데, 최악의 경우도 고려하여 대비하는 것이 바람직하기 때문이다.
Big-O 표기법의 종류
O(1)
O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.
O(n)
O(n)은 linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
O(log n)
O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 갖는다.
O(n2)
O(n2)은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
O(2n)
O(2n)은 exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 갖는다.
공간 복잡도(Space Complexity)
공간 복잡도는 알고리즘이 수행되는 데에 필요한 메모리의 총량을 가리킨다. 즉 프로그램이 필요로 하는 메모리 공간을 산출하는 것을 의미한다.
공간 복잡도도 시간 복잡도와 비슷하게 빅오(Big-O) 표기법으로 표현한다.