알고리즘 들어가기

알고리즘에 문제들을 풀어보기 전에 기본적으로 사용되는 알고리즘에 대하여 정리 해보겠습니다.

(아래 내용들의 출처는 Topcit 에센스 내용을 참고 했습니다.)

(https://www.topcit.or.kr/edubox/essence/topcitEssence.do)

* 알고리즘이란 ? 

- 문제 해결을 위한 과정을 단계적으로 기술한 것.

  명확성(Definitness), 유한성(Finiteness), 유효성 (Effectiveness)를 만족해야 한다.

* 분석 기준

- 정확성 : 시간 내에 결과를 산출해야 한다

- 작업량 : 결과가 나올때까지 수행하는 횟수

- 기억 저장소 사용량 : 메모리 사용량

- 최적성 : 최적합 여부

- 단순성 : 작성 및 디버깅이 수월해야함

또 알고리즘에 대한 성능을 분석하는 방식이 있는데, 다음 2가지 방식이 있습니다.

* 성능 분석

- 공간 복잡도

프로그램으로 실행하여 완료하기까지 필요한 총 저장공간(고정 공간량 + 가변 공간량)

•  고정 공간량 : 입출력에 상관 없이 고정적으로 필요한 공간
•  가변 공간량 : 수행 과정에 사용되는 공간

- 시간 복잡도

프로그램을 실행하여 완료하기까지 걸리는 컴파일 시간과 실행 시간의 합

tip) 알고리즘 성능

log n < n < nlogn < n^2 < n^3 < 2^n

주로 알고리즘 문제를 풀때는 시간복잡도를 이용하여 계산을 많이하지요 ㅎㅎ

본격적으로 알고리즘 기초인 정렬에 관하여 공부해 보겠습니다.

알고리즘 코드를 들어가기 전! 어떤 정렬 방식들이 있는지 살펴 보아요!

내부 정렬은 다음과 같이 10가지로 나눌 수 있습니다. 

전공 수업을 들었을땐  계수정렬과 기수정렬은 안배워서 저도 이번에 알게 되었네요!

* 정렬

- 내부 정렬의 분류

내부 정렬은 아래 그림과 같이 나눌 수 있고 수행시간도 같이 적어 놓았습니다.

이상으로 알고리즘 기초와 정렬에 관하여 정리를 했고

다음 시간부터는 각 정렬에 관하여 공부를 해보도록 합시다!