자료구조란
일상생활에서 흔히 볼 수 있는 데이터의 구조: 영화를 보기 위해 줄을 서는 구조(큐), 물건을 위에서 부터 쌓았을 때의 구조(스택) 등이 있다.
자료구조가 프로그래밍에서 필요한 이유는 알고리즘과의 결합에 있다. 좋은 자료구조를 활용하여 좋은 알고리즘을 사용할 경우, 기존의 프로그래밍보다 더 효율적인 프로그래밍을 할 수 있게 된다.
시간 복잡도와 공간 복잡도
시간 복잡도 : 소요되는 시간을 기호로 표시한 것, 빅오(최악의 경우), 빅오메가(최선의 경우), 쎄타(평균의 경우) 표기법을 사용할 수 있으며 프로그래밍에서 최악의 경우를 생각해야 대처할 수 있는 일들이 많기 때문에 빅오 표기법을 흔하게 쓰게 된다.
공간 복잡도 : 사용되는 공간을 기호로 표시한 것, 사용되는 메모리라고 생각하면 된다. 현대 과학의 발달로 시간 복잡도보다는 우선순위가 떨어진다.
우선순위
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2**n) < O(n!)
상수 < 로그 < 선형 < n로그 < 제곱 < 세제곱 < n승 < n팩토리얼 식이며 직관적으로 알기 어려운 부분은 logn 부분인데 쉽게 생각하면 n보다 반정도 덜 드는 시간 복잡도 라고 생각하면 된다. 이진 탐색 알고리즘이 logn의 대표격인데 아래 그림을 보고 이해해 보자.
두번째 직관적으로 알기 어려운 부분은 시간복잡도 계산인데 이것도 간단하게 보면 n일 경우 "모든 것들을 한번씩 계산한다" 이고 n**2 일 경우 모든 것들을 한번씩 보는데 하나를 볼 때마다 다시 모든 것들을 본다는 뜻이다. 코드로 설명하자면
n은
for (let key of object)느낌으로 생각할 수 있다. object의 element 개수만큼 본다.n**2은
for (let key of object) { for (let key of object){ code } }로 생각할 수 있다. object의 element를 하나 갖고 다시 object의 element을 처음부터 본다. 총 n * n이니 n ** 2이다.
Reference
인프런 - 비전공자의 전공자 따라잡기 (제로초)
C언어로 쉽게 풀어쓴 자료구조 - 천인국,공용해,하상호
chamdom velog 그림
여기까지 공부 정리
(내 생각) 자료구조를 이용하여 효율적인 프로그래밍을 하자.
FE, BE, DX 등등 모든 프로그래머는 결국 데이터를 활용하여 프로그래밍을 하게 된다. 현재 현대 과학의 발전으로 공간 복잡도를 생각하지 않지만 이전에는 생각했듯이 언젠가는 자료구조를 생각하지 않아도 AI 같은 기술들이 자동으로 변환해 주는 세상이 오게 될 수도 있다. 그러면 프로그래머는 필요 없는 것일까?
프로그래머는 또 다른 문제를 생각해야 될 것이다. 상상해보자면 AI에 관련된 복잡도를 생각해야 될 수도 있고 혹은 다른 사람들이 상상하는 것들처럼 코드라는 곳에서 벗어나, 배포, 운영 관리에 대한 문제, 기획에 대한 문제가 주 업무가 될 수도 있다.
자료구조는 완성된 학문이라고 한다. 이미 많은 개발이 이루어졌기 때문에 우리가 해야하는 것은 "이해"라고 교수님께서 말씀하셨던 것이 생각난다. 완성된 학문을 익히고 그것이 생겨나게 된 원리 과거의 프로그래머들이 이것을 해결하게 된 과정을 익히면서 과거의 경험들로 미래의 문제를 해결하는 법을 생각하는 지극히 프로그래머적인 생각을 할 수 있게 될 것이라는 생각을 그때 당시에 했었다. 겸사겸사 지금은 필요한 분야이기도 하고 말이다.
현 시대의 문제인 시간 복잡도를 해결하며 미래의 문제를 해결하는 과정을 살펴보자 라는 것이 이유라고 생각한다.
