자료구조와 알고리즘이란?

 

 

공식을 증명하면서 깊이 생각하면서 하면 굳이 외우지 않아도 증명하면서 다른문제에 대해서 스스로 사고하는 능력이 생긴다. 

자료구조와 알고리즘도 마찬가지다. 자료구조와 알고리즘의 특징만 외우는 것이 아닌, 연결리스트를 완벽히 이해하고 있으면 머릿속으로 한번 그려보면 특징을 혼자 찾을 수 있다. 

 

각각의 잘구조와 알고리즘의 특성을 머리로 그려가며 이해하는것이 필요함.

구현을 하게되면 머리로 이해하는 것보다 더 많은 생각을 하게 된다. 

직접 그림을 그려가며 상황을 만들고 천천히 이해하기에 기억에 더 오래 남는다. 

 

다시 머릿속으로 그 과정을 떠올리면 특징을 금방 찾을 수 있다. 

자료구조와 알고리즘은 일반적인 비즈니스로직보다 난이도가 높다. 

 

어려워도 포기 하지 말자!!

 

프로그램은 자료구조와 알고리즘으로 이루어진다. 

 

자료구조

 

자료구조란, 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타낸다. 

자료구조를 배우지 않았어도 이미 프로그래밍을 하면서 사용해왔다. 가장 단순한 자료구조는 변수이다. 숫자나 문자열을 저장하기 위해 변수를 사용한다.  그리고 저장한 숫자나 문자열에 접근하고 싶다면 변수를 참조한다. 단순한 구조로 사용 방법도 단순하다. 또 다른 자료구조는 배열이다. 배열에 숫자나 문자열 등을 연속적으로 저장한다. 그리고 해당 숫자나 문자열에 접근하고 싶다면 인덱스로 해당데이터에 접근한다.  

 

성적의 평균을 구하는 코드를 작성한다고 가정해보면, 

1. 성적 데이터를 변수에 저장하기

let a = 87;
let b = 70;
let c = 100;

let average = (a+b+c) / 3





2. 성적을 배열에 저장해보기

let arr = [87, 70, 100]
let average = 0;
for (let i = 0 ; i < arr.lenght; i++) {
   average += arr[i]

}

average /= arr.length;

 

변수와 배열이 저장된 모양과 사용 방법이 다르기 때문이다.

이번엔 데이터를 추가해보자. 

1. 성적을 새로운 변수에 담고, 평균 값을 구할 때 추가를 더 해준다. 

let a = 87;
let b = 70;
let c = 100;
let d = 55;

let average = (a+b+c+d) / 4





2. 데이터 하나만 배열에 추가해주면 된다. 

let arr = [87, 70, 100, 55]
let average = 0;
for (let i = 0 ; i < arr.lenght; i++) {
   average += arr[i]

}

average /= arr.length;

유지보수를 생각한다면 배열로 이루어진 2번째 코드가 더 나은거 같다. 

이처럼 자료구조에 따라서 처리방법이 달라지고  코드가 더 단순해질 수 있다. 

 

알고리즘

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

알고리즘은 자료구조의 영향을 많이 받는다. 따라서 둘은 떼려야 뗄 수 없것이다. 

특정한 자료구조에 대해서 문제를 푸는 알고리즘은 하나만 존재하는 것일까?  꼭 그렇지만은 않다. 

 

알고리즘은 여러개가 있을 수 있고 동시에 여러가지를 사용할 수 없다. 

이처럼 알고리즘은 자료구조에 따라서 달라지기도 하고 같은 자료구조를 쓰더라도 알고리즘은 여러가지가 될 수 있다.

 

1. 자료구조를 선택해 데이터를 어떻게 저장하고 사용할지 결정한다. 

2. 이에맞는 알고리즘을 통해 데이터를 가공한다. 

3. 원하는 결과를 얻는 과정을 거치게 된다. 

 

개발자라면 상황에 맞는 적절한 자료구조를 택하고 이에 맞는 알고리즘을 적용할 수 있는 스킬을 키워야 한다. 

 

문제를 해결 할 때 더 좋은 알고리즘을 사용하는 것이 좋다. 그렇다면 더 좋은 알고리즘이란 무엇일까?

 

사용자의 요구에 따라 다를것이다. 

메모리를 더 적게 사용하는 알고리즘?

메모리를 더 많이 사용하더라도 속더가 더 빠른 알고리즘?

 

사용자에 따라 선호하는 알고리즘이 다르지만, 일반적으로는 알고리즘의 속도를 성능의 척도로 사용한다.  

이를 시간 복잡도라고 한다. 

 

 

시간복잡도

 

특정 알고리즘이 문제를 해결하는데 걸리는 시간을 말한다. 

하지만 시간을 측정해서 알고리즘을 평가하기엔 현실적으로 어렵다. 사용자마자 컴퓨터 사양이 다르기 때문이다. 

같은 알고리즘이더라도 성능이 좋은 컴퓨터와 안 좋은 컴퓨터의 실행 시간이 다르다. 

따라서 알고리즘을 평가할 때는 시간을 측정하는 방식이 아닌 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측하는 것이다. 

 

코드에서 성능에 많은 시간을 주는 것은 어느것일까?  정답은 반복문이다. 

반복문이 여러번 반복될 수 록 실행시간이 길어진다. 

특정 알고리즘의 시간을 평가할 때는 해당 알고리즘의 반복문을 보고 성능을 평가한다. 

 

문제 1. 주어진 배열에서 5를 찾으시오

[1, 3, 5, 7]

배열의 0번 인덱스부터 끝까지 순회하며 5인지 아닌지를 찾는 것

길이가 4인 배열에서 3번째만에 정답을 찾을 수 있게 되었다. 

 

하지만 우리가 찾는 데이터가 배열의 어디에 있는지에 따라 성능은 천차 만별이다. 

 

최선의 경우 한번만에 찾을 수 있고, 찾는 데이터가 마지막 원소데이터에 있다면 최악의 경우 배열의 길이만큼 순회해야 찾을 수 있다. 어떤 경우는 데이터가 배열의 중간인덱스에 있다면, 평균의 경우 배열의 중간정도 가서 찾을 수 있다. 

 

때에 따라서 성능이 달라질 수 있다. 

따라서 경우를 나누어서 성능을 평가하는데, 

최선의 경우 한번에 찾음: Ω(Big Omega) 

최악의 경우 배열의 길이만큼 걸림: O(Big O) 

평균의 경우 배열의 길이 중간 만큼 걸림: Θ(Big Theta) 

 

 

가장 많이 사용하는 것은 big O이다. 

 

마지막 원소까지 비교하며 찾으므로 최악의 경우는 찾는 데이터가 가장 뒤에 있는 경우이다. 

만약 입력이 n이라면, 즉 배열에 데이터가 n개가 있다면 이 알고리즘은 최악의 경우 n번만에 데이터를 찾을 수 있다. 

빅오표기법으로 O(n) 으로 표기한다. 

 

n에 1을 넣으면 계산량은 1, 5를 넣으면 5  그에 비례해서 계산량이 많아진다는 그래프로 표기된다. 

 

선형시간 알고리즘이라고 부른다. 선형시간 알고리즘 외에도 다른 종류의 알고리즘이 있다. 

 

상수시간 알고리즘 : O(1)으로 표기한다. 입력의 크기에 상관없이 상수시간이 걸린다는 의미로 계산량이 꼭 한 번일 필요는 없다. 문제를 해결하는데 입력의 크기에 상관없이 100번의 계산이 걸린다 하더라도 상수 이기 때문에 O(1)으로 표기한다. 

 

사실 bigO표기법은 성능을 정확하게 표기하지는 못한다. 계산량이 얼마나 늘어나는지 표기하는 방법이기 떄문이다. 

그외에도 O(1),  O(n), O(logn), O(nlogn), O( n^2 ), O(N^2) , O(n!) 등이 있다. 

보라색으로 갈 수록 성능이 좋지 않은 알고리즘이다.  

 

 

빅오 표기법 

n2 + 2n + 100의 성능을 보이는 알고리즘이 있다면 이를 어떻게 표현해야 할까? 

계산에 가장 많은 영향을 미치는 항만 표기하는 것이다. 

여기선 n2이 가장 많은 영향을 미치므로 2n + 100 은 버리고 O(n2)으로 표기한다. 

 

만약 3n2 + 100n이라면 어떻게 표현할 까?

100n 보다 3n2이 더 크기 때문에 O(3n2)로 표현하지만, 빅 오표기법으로 표기할 떄는 상수는 큰 의미가 없으므로 제거해준다. 따라서 O(n2)으로 표기해준다.