알고리즘 시작 - 알고리즘을 배워야하는 이유

최근 많은 회사가 코테를 보고 그 중 하나가 알고리즘이 있다.
2학년 1학기때 저희학교도 알고리즘 수업을 배웠는데, 자료구조가 코딩에서 제일 중요하다는 것을 깨달았다.
오늘은 자료구조 알고리즘에 대해서 기초적인 내용을 적어보겠다.

해당 기본 내용은 한국공학대학교 김평수 교수님의 수업을 바탕으로 작성하였습니다.

저장공간에 대해 알아보자

우리가 초반에 코딩할 때는 단순히 반복문, 조건문 등을 이용해서 만들었다면 이제는 그거에 저장하는 공간을 아껴야 된다.
내용을 일시적으로 저장하는 부품인 RAM은 컴퓨터가 돌아갈 때 필요한 부분들을 임시로 저장해준다.
기본적으로 배경화면, 프로그램을 실행할 때 나오는 화면 등 모두 RAM에 포함되어 있다.
필요한 프로그램을 동작하면 RAM에 공간이 쌓이면서 임시 데이터를 저장해주고 닫게 되면 RAM할당량이 줄어든다.

자료 구조는 뭘까?

RAM을 알아둔 이유는 우리가 프로그램에서 공간을 잘 활용해야 된다.
예를 들어 공간 1을 충분히 사용할 수 있는 프로그램을 공간 10이나 사용해야 된다면 이는 효율적이지 못한 프로그램이다.
이에 알고리즘을 짤 때 제일 효율적이고 사용 환경에 최적인 것을 결정해야 된다.
여기서 사용하는 개념이 공간 복잡도와 시간 복잡도 이다.

공간 복잡도

알고리즘을 프로그램으로 실행하여 완료하는 데까지 필요한 총 저장 공간이다.
고정 공간과 가변 공간을 합하여공간 복잡도라 부르는데,
고정 공간은 프로그램 크기나 입출력 횟수와는 상관없이 고정적으로 필요한 저장 공간으로
프로그램 저장 공간과 변수 및 상수를 저장하는 공간입니다.
가변 공간은 실행 과정에서 사용하는 자료와 변수를 저장하는 공간과 함수,
즉 변하는 부분들을실행하는데 관련 있는 정보를 저장하는 공간입니다.

시간 복잡도

알고리즘을 프로그램으로 실행하여 완료하는 데까지 소요되는 시간입니다.
프로그램 컴파일 시간과 실행 시간을 합하여 시간 복잡도라고 부르는데,
컴파일 시간은 프로그램 자체의 특성과는 관련이 없어 고정되며
실행 시간은 같은 프로그램이라도 실행되는 컴퓨터의 성능에 따라 달라지기 때문에 이를 고려해야 됩니다.
이때, 실제 실행 시간을 측정하기 보다는 명령문의 실행 빈도수를 계산하여 추정하는 것이 좋습니다.

정리하자면,

• 알고리즘이 빠른 정도 - 시간 복잡도 (속도)
• 알고리즘이 메모리를 쓰는 정도 - 공간 복잡도 (메모리 사용량)

알고리즘 속도 측정하기

알고리즘의 시간 복잡도는 단순히 시간을 재는 것이 아니라 연산의 횟수를 통해 수행속도를 평가합니다.
연산의 횟수가 많으면 느린 것이고, 연산의 횟수가 적으면 빠른 것이라 할 수 있죠.
이를 통해 연산의 횟수를 계산하는 함수를 만듭니다.

이 표기법을 빅-오 표기법 O(f(n))으로 부릅니다.
시간복잡도가 n^2이면 O(n^2)으로 표기합니다. 수학적 정의는 다음과 같습니다.
함수 f(n)과 g(n)이 주어졌을 때, 모든 n>=n0에 대하여 |f(n)| <= c|g(n)|을 만족하는 상수 c와 n1이 존재하면, f(n) = 0(g(n))이다.

알고리즘에 따라 longn, n, nlogn, n^2, n^3, 2^n을 실행 시간 함수를 비교해 봅시다.
n값이 커질수록 실행 시간 함수값의 크기는 logn<n<nlogn<n^2<n^3<2^n 순서로 커집니다.
이를 통해 걸리는 시간은 logn<n<nlogn…임을 알 수 있습니다.

• 참고 자료 : 한빛아카데미 [C로 배우는 쉬운 자료구조]

기본적으로 알아야되는 아스키코드

문자	2진수	ASCII코드
‘A’	100 0001	65
‘a’	110 0001	65
‘0’	001 0000	48