[개인 공부] 알고리즘 공부(시간복잡도 분석 시작하기에 앞서, 기초)

안녕하세요, HoonIOS입니다.

개인적인 공부를 하다가 드디어 첫 포스팅을 하게 되었는데요, 저의 발전을 위해서 꾸준히 업로드하겠습니다 :)

 

우선 시간복잡도을 알아보기에 앞서 알고리즘에 대해 알아봐야겠죠!

 

알고리즘이란?

- 어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 방법을 말합니다. 즉 한 개의 작업에 대한 알고리즘의 경우의 수는 매우 많을 거 같네요

 

- 단!!!!!!!!!!!!!!!!!!!!! 알고리즘이란 한가지 방법을 명료하게 써놓아야 하지 주관적이고 애매 모호하게 써놓은 것은 알고리즘이라고 할 수 없습니다.

 

(예를 들어, 어느 목적지를 가기위해 a라는 버스를 타고 b라는 지하철을 타서 c라는 목적지에 도착한다라는 정확한 방법이 쓰여있어야 한다는 뜻입니다.)

 

- 가능한한 명료하고 정확한 표현을 위해 알고리즘을 의사코드(아래에 설명)를 구현한 소스코드의 형태로 설명한다고 한다.

 

- 알고리즘을 여러 언어로 문제를 풀어보신적이 있으시면 같은 방식으로 다른 언어로 풀면 어느 언어로 푼 문제가 패스를 했는데 다른 언어로 푼 문제는 시간 초과가 일어난 것을 간간히 보실 수 있을 겁니다.

그런 경우는 각 함수나 원리 동작이 언어마다 다르므로 이런 현상이 나오는 거라고 할 수 있습니다.

 

- 이렇게 알고리즘을 평가하는 기준은 시간과 공간이 있다.

1. 시간: 알고리즘이 적은 시간을 사용한다는것은 더 빠르게 동작한다는 이야기로 최대한 빠르게 처리할 수 있도록 작성을 해야 한다.
   대표적으로, 시간에 가장 많이 관여하는 문법은 반복문이 있다, 따라서 반복문을 사용할 때 최대한 효과적으로, 이중 포문은 적게 사용하는 것이 좋다.!
2. 공간: 알고리즘이 적은 공간을 사용하게 다시말해서 적응 메모리 용량을 사용하게 코딩을 해야 된다는 이야기입니다.

여기서 의사코드를 간단히 알아보자면?

 

- 저도 잘 몰라서 위키백과를 찾아봤는데요, 위키백과 말로는 프로그래밍 언어의 문법에 따라 쓰는 게 아니라 일반적인 언어로 코드를 흉내 내어 알고리즘을 써놓은 코드를 말한답니다, 비유를 하자면 미술에서 스케치 정도는 되겠네요!

 

 

지금까지 기본적인 알고리즘에 대해서 알아봤는데요!

다음 포스팅에는 시간 복잡도 분석에 대해,  기본적인 선형 시간 알고리즘, 선형 이하 알고리즘, 이진 탐색...에 대해 포스팅을 해보겠습니다 ㅎㅎ