Algorithm 알고리즘이란?

velog에서 정리 한 것들을 블로그 이전하는 김에 다시 재정리를 하려고 한다. 
2023년 2월 15일 - https://velog.io/@yujin-17/TIL-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 

알고리즘이란?

알고리즘은 어떠한 문제를 해결하려는 방법과 절차입니다. 

우리가 하려는 프로그래밍에 꼭 필요한 요소로 볼 수 있습니다.

 

이러한 알고리즘에는 조건이 있습니다. 

 

1. 입력 : 외부에서 제공되는 자료 
2. 출력 : 적어도 2개 이상의 서로 다른 경로가 출력
3. 명확성 : 수행과정은 무엇을 하기 위한 것인지 명확하게 정의
4. 유한성 : 알고리즘의 명령어 대로 수행하였을 때 처리된 후 종료
5. 효율성 : 시공간적 효율성을 가져야하며, 명백하게 실행 가능 

좋은 알고리즘이란? 

밑의 4가지를 충족하는 것을 좋은 알고리즘이라고 판단하고 있습니다. 

• 복잡도(시간, 공간)
• 정확성 : 입력에 대해 일정 시간 내에 올바른 답을 산출하는지 판단
• 작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량 측정하며, 해결하고자 하는 문제의 중요 연산이 여러개인 경우에는 각각의 중요 연산들의 힘으로 간주하거나 중요 연산들에 가중치를 두어 계산 
• 최적성 : 작업을 수행하기 위한 알고리즘이 가장 효율적인지 

여기서의 시간복잡도란? 

알고리즘이 특정 크기 입력에 대한 수행시간을 의미합니다. 

알고리즘이 수행하는 필요 연산 횟수도 포함됩니다. 

 

여기서의 공간복잡도란?

알고리즘이 특정 크기의 입력에 대한 메모리 소요량을 의미합니다. 

알고리즘이 수행되기 위해 필요한 저장공간의 양도 해당됩니다. 

총 필요 저장공간 

> 고정공간(알고리즘 무관) : 코드 저장공간, 상수

> 가변공간(알고리즘 관련) : 실행 중 동적으로 필요한 공간 

 

Big-O Notation (빅O표기법)

• 접근적 상한선(Asymptotic upper bound)
• 계수와 낮은 차수의 합을 제외시키는 방법입니다. 
• 상수는 포함되지 않습니다(모두 1)

 

이번 포스트는 알고리즘, 그리고 그와 관련된 사소한 정의를 설명해보았습니다. 
감사합니다 :)