컴퓨터 알고리즘 초급 #1 ( 컴퓨터 알고리즘 개요 )

컴퓨터 알고리즘이란?

 

 

 

문제를 해결하는 방법을 의미한다.

 

컴퓨터 알고리즘을 배우는 이유는 그 문제를 효율적으로, 단계적으로 해결하기 위한 방법을 익히기 위해서이다.

 

컴퓨터 알고리즘과 혼동하는것이 컴퓨터 언어와 컴퓨터 프로그램인데

 

컴퓨터 언어 - 컴퓨터와 대화하기 위한 언어 - 그 자체이다. (EX. C, C++, JAVA, Pthyon 등)

 

컴퓨터 알고리즘 - 컴퓨터를 이용해서 문제를 푸는 절차 (ex. 정렬, 해시, 최단거리 등 )

 

컴퓨터 프로그램 - 특정 작업을 위한 수행을 하는 것을 의미한다.

 

 

 

컴퓨터를 이용해서 문제해결을 원한다면 어떻게 해야할까? 

 

우선 컴퓨터에게 할 일을 알려줘야한다.

그리고 컴퓨터가 할 수 있는 일이어야한다.

 

 

 

이러한 것을 분석하는 컴퓨터 알고리즘 분석 4단계가 있다.

 

1. 문제 정의 : 문제가 무엇인지, 입력과 출력이 어떻게 되는지, 컴퓨터로 해결할 수 있는 문제인지에 대한 정의가 필요하다.

 

2. 알고리즘 설명 : 그 문제를 어떻게 해결할 것인지. 예를들어 라면을 끓인다고 한다면, 설명서가 있다. 물 500ml를 냄비에 담는다.  가스레인지를 이용해 냄비에 있는 물을 끓여준다. 물이 끓으면 스프와 면을 넣고 3분을 기다린다. 라면이 다 익으면 먹는다.

이런식으로 라면을 끓이는 문제를 해결하는 과정을 의미한다.

 

3. 정확성 증명 : 이건 어떤 알고리즘이 잘못된 결과를 가져오지는 않는가? 항상 내가 원하는 답을 도출하는가 등에 대한 연구인데 일반적으로 대학원같은 연구실에서 한다고 한다.

 

4. 성능 분석 : 말 알고리즘의 성능을 분석한다. 실행 시간과 사용 공간 ( 비용 ) 을 기준으로 생각한다.

 

 

여기서 성능 분석은 애매한 부분이 있어. 사용하는 기기, 환경 등에 따라 성능이 달라지기 떄문이다.

 

그래서 성능분석을 할 때에는 수행연산의 횟수를 비교하는 방식으로 성능을 분석한다.

 

ex, 곱셈 10번을 하는데 기기마다 각 안드로이드 - 10초 pc -1초 server -0.1초 가 걸렸다. 즉 연산에 대한 성능은 기기에 따라 달라지기 때문에 비교하기가 힘들다. 하지만, 연산에 대한 횟수는 모두 동일하다.

 

그래서 성능을 분석할때에는 곱셈( 특정 함수) 에 대한 시간을 줄이는게 아닌, 곱셈( 특정 함수 ) 자체의 횟수를 줄이는게 더 좋은 성능이라고 말할 수 있다.

 

이것과 관련된 키워드가 입력 크기 n 이다. 입력이 많을수록 수행횟수가 증가하기 때문이다.

 

 

성능 분석의 비교 대상으로는 

 

산술 연산 ( 덧셈 곱셈 뺼셈 나누기 등)

 

데이터 입출력 ( 복사, 이동, 저장, 불러오기 등 )   : 현재 컴퓨터와 메모리가 좋아져서 이게 얼마나 걸리나 싶을지 모르지만, 빅데이터 시대인 지금은 많으면 1000조개 정도의 데이터도 다루기 때문에, 영향이 있다.

 

제어 연산 ( if, while, register ) : 브런치, 파이프라인 등의 이슈가 있어서 성능에 영향을 준다.

 

 

일반적으로는 산술 연산으로 비교한다.

 

성능분석의 표기법으로는 빅오 표기법, 오메가 표기법, 쎄타 표기법 등이 있다.

 

우리는 기본, 기반이 되는 함수를 몇번 실행하는가로 분석한다고 알고있다.

 

그 분석한 것을 표현하는 방법이 빅오, 오메가, 쎄타 표기법인것이다.

 

 

 

원리를 설명하자면, 3n +1 와 n^2이 있다.

 

여기서 3n +1 은 n^2보다 절대 커질수가 없다.

 

즉 n^2이 더 성능이 느린것을 알 수 있다.

 

빅오 표기법에 대한 자세한 설명은 아래 블로그를 참조하기를 바란다.

 

https://blog.naver.com/jinp7/221634498995

 

지금 우리가 중요한 것은, 컴퓨터 알고리즘을 공부하는 것이기 때문에 성능 분석에 대한 이야기는 여기서 마치도록 하겠다.