알고리즘 공부 1일차

알고리즘이란?

 

알고리즘이란 어떤 문제를 해결하기 위한 방법을 말한다.

 

우리가 알고리즘을 배우는 것은 그 중에서도 가장 효율적인 방법을 찾기 위함이다. 

얼마나 효율적이고 논리적인 컴퓨팅을 할 수 있을지는 이러한 사고 방식에 달려 있다.

 

예를 들어 1에서 10까지의 자연수의 합을 구해야한다고 생각해보자. 

단순히 생각하면 1+2+3+4+5+6+7+8+9+10=55 가 나오겠지만

그 안에서 규칙을 발견한다면 더욱 쉽게 계산할 수 있다.

 

{(n+1)*n}/2를 사용하면 단숨에 구할 수 있다.

이를 통해 계산의 시간복잡도를 낮출 수 있으며 이러한 효과가 알고리즘의 힘이다.

 

 

선형탐색과 이진탐색

책장에 책이 20권정도 꽂혀있다고 가정하자. 그 중에서 나는 어린왕자 책을 찾으려고 한다. 그 책을 찾기 위해서는 여러 탐색 방법이 있을 것이다. 이 중에서 소개할 것은 선형탐색과 이진탐색법이다.

 

먼저, 선형탐색이란 순차적으로 접근해서 원하는 데이터를 찾는 방식이다. 쉽게 생각하자면 책장의 왼쪽부터 한 권 한 권 보면서 탐색한다는 것이다. 직관적이지만 탐색 횟수가 많아진다는 단점이 있다.

 

그리고 이진탐색에 대해 알아보자. 이진탐색이란 책장을 반으로 쪼개서 그걸 또 반으로 쪼개고 대소비교를 통해 책을 찾을 수 있는 방법이다. 다만 정렬된 데이터에서만 사용할 수 있다는 단점이 있다.

 

그러므로 이진탐색이 탐색 횟수는 적을지언정 정렬되지 않은 데이터에서는 선형탐색을 사용할 수밖에 없다.