[C++] 알고리즘, 시작 전에 자료구조

코딩테스트를 대비하기 위해서 알고리즘 공부를 다시 시작하려고 하니, 자료구조는 무시하고 알고리즘부터 무작정 공부한다는 생각이 들었습니다. 우리가 알고리즘을 잘 짜기 위해서 잘 선택해야 하는 게 무엇보다도 자료구조인데….

 

지금부터라도 두 가지를 잘 합쳐서 공부해보려고 합니다.

 

---

> 먼저 자료구조는 뭘까요?

 

자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상 자료형의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다.

 

위키백과에 따르면 그렇다고 합니다. 

요약해서 말하자면 데이터를 효율적으로 표현하고 저장할 수 있게끔하려면 자료구조를 잘 선택해야 한다는 거군요.

 

알고리즘은 자료구조로 되어있는 데이터들을 사용해서 문제를 해결하기 때문에 자료구조에 의존적일 수 밖에 없습니다. 따라서 어떤 자료구조를 사용해서 문제를 풀었냐에 따라 알고리즘이 달라질 수 밖에 없는거죠. 그렇기 때문에 같은 문제에 모두 같은 자료구조를 사용한다고 보장할 수 없습니다. 언제 어떤 자료구조를 사용해서 문제를 푸느냐는 자기 자신이 알아서 결정해야 하고 잘 판단해서 적절하게 사용해야 되기 때문입니다. 

 

딱 정답이 없어요!

 

그렇기 때문에 알고리즘이 더 어려운 것 같습니다.

하지만 어떤 걸 선택해야지 더 좋은 알고리즘이 되는지에 대한 기준은 존재합니다.

 

대표적으로는 시간복잡도(속도)와 공간복잡도(메모리)가 있겠죠. 어떤 자료구조를 사용해서 문제를 풀었는가에 따라서 해당 알고리즘이 엄청나게 빠를수도, 또는 엄청나게 느릴수도 있습니다. 혹은 엄청 빠르지만 많은 메모리를 잡아먹을 수도 있구요.

 

알고리즘의 효율은 자료구조가 꽉 잡고 있기 때문에 우리는 자료구조가 알고리즘을 어떻게 쥐고 흔드는지 봐야합니다.

물론, 알고리즘을 실행시키고 정답이 나오기까지 얼만큼의 시간이 걸리는 지 하나하나 돌려볼 수도 있겠지만… 너무 비효율적이기 때문에 

이를 식으로 나타내주는 Big-O 표기법이 있습니다.

 

---

> Big-O notation?

 

Big-O notation은 시간복잡도와 공간복잡도를 간소화해서 나타낸 것으로 알고리즘의 효율성을 나타냅니다. Big-O는 데이터 수 증가에 따른 연산횟수 증가율의 상한선입니다. 한 마디로 가장 알고리즘의 효율이 최악이었을 때, Big-O notation으로 나타낸 것만큼의 효율이 난다고 생각하시면 될 것 같습니다. 

 

Big-O말고도 다른 표기법들이 존재하는데요, 모두 Running time보다는 데이터나 사용자가 증가함에 따라 알고리즘의 성능 예측을 보여줍니다. 하지만 각각의 표기법마다 보여주고자 하는 성능이 다르기 때문에 Big-O notation말고 다른 표기법들도 찾아보시면 좋을 것 같습니다.

 

Big-O notation를 가볍게 설명하자면,

 

O(1) : 언제나 동일한 성능을 냅니다.

return isActivated ? true : false

이런 상황에서 O(1)의 효율이 납니다.

 

O(n) : 들어온 데이터의 크기만큼

반복문(for문)을 하나 돌렸을 때 최악의 경우 들어온 데이터를 모두 돌려보게 됩니다. 

이런 경우 O(n)의 효율이 납니다.

 

O(n^2) : 반복문을 두 번 돌렸을 때

이 경우에는 데이터가 기하급수적으로 많아졌을 때 알고리즘의 속도에 굉장한 영향을 끼칩니다.

 

O(n^3) : 삼중반복문

낮은 수의 데이터만 들어온다면 상관없지만 굉장히 큰 수가 들어온다면 당장 삼중반복문을 지우시고 새로운 방식을 찾아보세요.

 

O(log n) : 이진 검색

안에 있는 배열의 원소들을 하나하나 살펴보는 순차 검색은 원소를 하나하나 살펴봐야 하기때문에 모든 원소를 살피는 n만큼의 효율이 나지만 이진 검색은 1/2만큼 필요한 부분만 살펴보기 때문에 순차 검색보다는 빠른 log n만큼의 효율이 납니다.

log n 그래프를 보면 아시겠지만, log n은 많은 데이터가 들어온다고 해서 급격하게 속도가 느려지지 않습니다. 그렇기 때문에 log n만큼의 효율을 내는 것이 알고리즘에서는 중요하다고 볼 수 있습니다.

 

O(2^n) : 피보나치 수열

피보나치 수열은 해당 인덱스의 인덱스 - 2 한 값과 인덱스 - 1 한 값을 구해서 해당 인덱스 안에 들어갈 값을 구합니다. 따라서 한 인덱스의 값을 구할 때마다 2개씩 호출하게 됩니다. 따라서 O(2^n)의 복잡도를 가집니다.

2^n의 그래프에서 알 수 있듯, 수가 커질수록 급격하게 복잡도가 증가합니다. n^3보다 더 빠르게 복잡도가 증가하기 때문에 2^n의 복잡도에서는 큰 수를 넣는다면 정말 오랜시간을 기다려야 한다는 걸 알 수 있습니다.

 

 

---

깊이 파지않고 복잡도에 대해서만 알아보았습니다.

정말 제대로 된 자료구조에 대해서는 알고리즘 공부를 하면서 하나하나 제대로 공부해보려고 합니다.