2022.03.23(수)
🗒 목차
-
자료구조와 알고리즘
-
시간복잡도
-
배열과 연결 리스트
✅ 1. 자료구조와 알고리즘
맛있는 요리는 적절한 요리도구와 올바른 조리 방법으로 완성된다.
자료구조와 알고리즘은 바늘과 실처럼 항상 같이 붙어다니는 단어지만 각 단어에 대해서 깊게 생각해본적이 없었다. 이번 기회에 자료구조와 알고리즘에 대해서 정리해보았다.
자료구조란 메모리를 효율적으로 사용해서 빠르고 안정적으로 데이터를 처리하는 것을 궁극적인 목표로 하는 도구라 할 수 있고 알고리즘이란 특정 문제를 효율적이고 빠르게 해결하는 것을 궁극적인 목표로 수학적으로 표현하는 것을 말한다.
요리에 따라, 즉 만들고자 하는 소프트웨어에 따라 적절한 도구 선택이 중요하고. 그 도구를 사용해서 올바른 방법대로 실행해야 맛있는 요리 즉 소프트웨어가 완성된다. 따라서 개발을 위해 필요한 도구를 선택할 수 있는 능력을 키워야 한다.
자료 구조의 종류로 단순 구조, 선형 구조, 비선형 구조가 있다. 그 중 선형 구조에는 배열, 연결 리스트, 스택, 큐가 있고 비선형 구조에는 트리와 그래프가 있다.
| 선형 구조 | 비선형 구조 |
|---|---|
| 배열 | 트리 |
| 연결리스트 | 그래프 |
| 스택 | |
| 큐 |
여기서 말하는 선형구조란 자료들이 말 그대로 선형적으로 (Linear)하게 나열되어 있는 구조를 의미한다.
✅ 2. 시간복잡도
우리는 프로그램의 성능을 정확하게 측정할 수 없다. 하지만 대략적으로 예측할 수는 있다.
시간 복잡도란 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 의미하며, 계산 복잡도를 표기하는 대표적인 방법이 빅 오 표기법이다.
빅 오 표기법의 종류로 상수 시간, 로그 시간, 선형 시간, 선형로그 시간, 이차 시간, 지수 시간, 팩토리얼 시간이 있다.
O(1) : 입력값에 상관없이 일정한 실행시간을 최고!의 알고리즘이라 할 수 있다. 하지만 상수 시간에 실행된다 해도 상수값이 상상 이상으로 클 경우 사실상 일정한 시간의 의미가 없다. 최고의 알고리즘이 될 수 있지만 그만큼 신중해야 한다.
O(log n) : 로그는 매우 큰 입력값에서도 크게 영향을 받지 않는 편이다. 매우 견고한 알고리즘으로 이진 탐색의 경우가 이에 해당한다.
O(n) : 알고리즘을 수행하는데 걸리는 시간은 입력값에 비례한다. 이러한 알고리즘을 선형 시간 알고리즘이라 부른다. 정렬되지 않은리스트에서 최대 또는 최솟값을 찾는 경우가 해당되며 모든 입렵값을 적어도 한 번 이상은 살펴봐야 한다.
O (n log n) : 병합 정렬등의 대부분 효율이 좋은 알고리즘이 이에 해당 한다. 아무리 좋은 알고리즘이라 할지라도 n log n 보다 빠를 수 없다. 입력값이 최선일 경우, 비교를 건너 뛰어 O(n)이 될 수 있다.
O(n^2) : 버블 정렬 같은 비효율저긴 정렬 알고리즘이 이에 해당 한다.
O(2^n) : 피보나치의 수를 재귀로 계산하는 알고리즘이 이에 해당 한다. n^2와 혼동되는 경우가 있는데 2^n이 훨씬 더 크다.
O(n!) : 가장 느린 알고리즘으로 입력값이 조금만 커져도 계산이 어렵다.
✅ 3. 배열과 연결리스트
배열은 탐색은 쉽지만 추가와 삭제가 어렵고 연결리스트는 추가와 삭제는 쉽지만 탐색이 어렵다.
자바스크립트에서 배열은 기본적으로 객체이기 때문에 동적으로 크기가 증감되도록 만들어져 있으며 스택 처럼 push, pop을 사용할 수 있다. 배열에서 원하는 원소의 index값을 알고 있다면 O(1)로 빠르게 삭제 또는 추가할 수 있다.
하지만 배열의 요소를 삭제 하거나 추가한 후 순서를 맞춰야 할 경우 시간 복잡도는 O(n)이 된다.
따라서 요소를 자주 추가하거나 삭제하는 로직이 반복될 경우 배열을 사용하면 좋은 성능을 얻을 수 없다.
연결리스트는 배열과 상반되는 특성이 있다. 노드마다 데이터와 포인터를 갖고 있기 때문에 노드를 추가하거나 삭제하는 방법이 쉽다 하지만 노드를 탐색하는데는 많은 시간이 소요될 수 있다.
연결리스트에는 단일 연결 리스트와 이중 연결리스트 그리고 환형 연결리스트가 있다. 세 가지 리스트를 구현하는 방법에 대해서 좀 더 학습을 해야겠다...
