하고 싶은 말

Data Science에서 하나의 큰 영역을 차지하는 Computer Science(이하 CS), 이 문서는 CS의 개념을 담고 있다. 내용이 정말 많지만 최대한 쉽게 정리하였다. 용어는 되도록 영어로 외우는 게 좋다.

알고리즘의 정의

알고리즘(Algorithm)은 수학과 컴퓨터과학에서 사용되는, 문제 해결 방법을 정의한 '일련의 단계적 절차'이자 어떠한 문제를 해결하기 위한 '동작들의 모임'이다. 컴퓨터 과학에서 알고리즘은 주로 데이터를 처리하고 계산을 수행하며 의사 결정을 내리는 방법을 제공한다. (유한 시간 내에 최적의 해결책을 보장하는 유한 개의 문장들의 집합)

알고리즘의 필수 요건

• 정확성: 입력에 대해 적절한 값을 출력 (필수!)
• 효율성: 빠른 실행 속도와 적은 메모리 공간 사용

좋은 알고리즘은?

• 알고리즘이 실행되는데 소요되는 시간이 적을수록 좋다. (★)
• 알고리즘이 실행될 때 소모하는 메모리 공간이 적을수록 좋다.

알고리즘 비교 척도

• 보안
• 명확성/난독화: 코드가 얼마나 쉽게 쓰여져 있는지/어렵게 쓰여져 있는지
• 성능 (★)

알고리즘 성능에 대하여

성능을 비교할 때,

• 대규모 입력(large input)을 사용한다. ($n$이 작으면 어떤 알고리즘이든 빠르게 끝난다.)
• 답변은 CPU속도, 프로그래밍 언어, 코드 트릭 등과 독립적이어야(independent) 한다.
• 답변은 일반적(general)이고 엄격(rigorous)해야 한다. (반복 실행해도 결과가 일반화되어야 한다.)

알고리즘 성능 평가: 시간 복잡도 분석(Time Complexity Analysis)