자료구조
자료구조란?
자료구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것입니다.
사실, 개발을 하다보면 데이터를 가지고 전처리 하는 방식도 여러 가지이고, 기능(함수)를 구현하는 것도 가지 각색일 것입니다. 그러한 모든 것들을 자료구조라고 할 수 있을텐데, 그 방법들 중에서 분명히 효율적인 방식이 존재할 것입니다.
여기서 말하는 효율적인 방식이란 각 원소들을 논리적으로 정의된 규칙에 의해 나열하고 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하는 방식이라고 생각하면 될 것 같습니다.
필요한 이유
위에서도 살펴봤지만 자료구조를 익힘으로서 효율적으로 데이터를 다루어 문제를 해결하기 위함이 클 것입니다.
정리하자면, 다음과 같습니다.
- 데이터를 체계적으로 저장하고, 효율적으로 활용하기 위해서 자료구조를 사용
- 대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있습니다.
- 많은 자료구조를 알아두면, 특정 문제를 해결하는 데에 상황에 가장 적합한 자료구조를 빠르게 찾아 데이터를 정리하고 활용하여 문제를 빠르고 정확하게 해결할 수 있습니다.
- 문제 해결 능력과 굉장히 밀접한 연관성이 있다.
데이터(data) 는 우리가 실생활에서 사용하는 모든 값을 의미한다고 생각할 수 있습니다.
따라서, 그 자체만으로 활용하기 힘들고 분석하고 정리하여 목적에 따라 형태를 구분하고, 분류하여 사용합니다.
선택 기준
- 자료의 처리 시간(시간 복잡도)
- 자료의 크기(공간 복잡도)
- 자료의 활용 빈도
- 자료의 갱신 정도
- 프로그램의 용이성
특징
1. 효율성
위에서 말했다 싶히 자료구조를 이해하고 사용하는 이유는 효율적인 데이터의 관리 및 사용입니다. 목적에 필요한 자료구조를 선택하여 활용한다면 시간적, 공간적 효율이 크게 올라갈 것입니다.
예를 들어, 100만개의 데이터가 존재할 때 선형 탐색(Linear Search)의 경우 시간 복잡도가 O(N)이므로 최악의 경우 100만개의 데이터를 전부 탐색해야 합니다. 하지만, 만약 이분 탐색(Binary Search)를 활용한다면 이분 탐색의 시간 복잡도는 O(logN)이므로 약 20번만에 탐색을 완료할 수 있을 것입니다.
2. 추상화
추상화란 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념만 간추려 내는 것입니다. 자료구조를 구현할 때 중요한 것은 어느 시점에 데이터를 삽입할 것이며, 어느 시점에 이러한 데이터를 어떻게 사용할 것인지에 대해서 초점을 맞출 수 있기 때문에 구현 외적인 부분에 더 시간을 쏟을 수 있습니다. 알고리즘 자체에는 중점을 두지 않습니다.
마찬가지로 자료구조 내부의 구현은 중요하지 않습니다. 어떻게 구현했는지 보다 어떻게 사용해야 하는지를 알고 있어야 합니다.
예를 들어 스택(Stack)의 경우 먼저 들어간 것이 나중에 나오는 FILO(First In Last Out)의 형태를 가지고 있습니다. 그리고 push() 함수를 이용해서 데이터를 삽입할 수 있고, pop() 함수를 이용해서 데이터를 추출할 수 있습니다. 사람마도 다른 코드를 작성할 것이고, 사용 언어, 개발 툴등 활경적인 변수에 의해서 다른 코드가 나올 것이기 때문에 추상적인 개념에 대해서만 이해하고 있다면 사용할 수 있습니다.
3. 재사용성
자료구조를 설계할 때 특정 프로그램에서만 동작하게 설계하지 않습니다. 다양한 프로그램에서 동작할 수 있도록 범용성 있게 설계하기 때문에 해당 프로젝트에만 국한되지 않습니다.
분류
자료구조는 크게 선형 자료구조와 비선형 자료구조로 나눕니다. 선형 자료구조의 경우 데이터가 일렬로 나열되어 있는 것을 뜻하고, 비 선형 자료구조는 특정한 형태를 띄고 있는 것을 뜻합니다.
알고리즘
알고리즘이란?
알고리즘(Algorithm)은 문제를 해결하기 위해 필요한 계산 절차나 처리 과정의 순서이다.
문제 해결을 위해 여러 개의 후보 알고리즘 중, 정확성과 효율성 등을 평가한 후에 최적의 알고리즘을 선택한다. 알고리즘은 연산, 데이터의 진행 또는 자동화된 추론을 수행합니다.
알고리즘의 조건
알고리즘은 아래의 5가지 조건을 만족해야 합니다.
- 입력: 외부에서 제공되는 자료가 0개 이상 존재해야 한다.
- 출력: 최소 1개 이상의 결과를 가져야 한다.
- 명확성: 각 단계는 명확하고 애매함이 없는 명령어로 구성되어야 하고, 모든 과정은 명백하게 실행 가능한 것이어야 한다.
- 유한성: 각 단계들은 유한한 횟수로 거친 후, 유한한 시간 내에서 문제를 해결하고 종료해야 한다.
- 효과성: 모든 연산들은 유한한 시간 내에서 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다.
이것들을 바탕으로 알고리즘은 어떠한 입력이 있을 때 입력에 따라 명령을 명확하게 실행하고, 입력에 따른 결과물을 효과적으로 도출해 낼 수 있다면 알고리즘(Algorithm) 으로 볼 수 있다는 말입니다.
좋은 알고리즘 기준
- 정확성: 적절한 입력에 대해서 유한 시간 내에 올바른 답을 산출하는 가를 판단
- 속도: 속도가 빠르다는 것은 시간이 짧게 걸린다는 것을 의미합니다. 결과가 같을 경우 더 빠른 시간내에 결과를 도출해내는 알고리즘이 더 좋은 알고리즘 입니다.
- 효율성: 다르게 말하면 프로그램을 실행할 때 사용하는 메모리 영역이 적어야 합니다. 대량의 메모리가 필요한 것은 프로그램의 효율이 낮다는 것으로, 비용 면에서 메모리 영역이 적은 것이 더 좋다고 말할 수 있습니다.
자료 구조와 알고리즘의 관계
알고리즘은 요리로 치자면 레시피(recipe)에 가깝습니다.
보통 자료 구조가 선택되면 그에 적용할 알고리즘은 거의 명확해집니다. 즉, 자료구조가 효율적인 알고리즘을 사용할 수 있게 함으로서 자료구조와 알고리즘은 밀접한 관계를 가질 수 밖에 없습니다.
예를 들어 생각해 봅시다.
책장에 책들이 있고 거기서 하나의 책을 찾으려고 할 때 어떤 순서나 규칙을 가지고 찾을 지에 대한 방법이라고 생각하면 될 것입니다. 왼쪽부터 찾을 수 있고, 오른쪽 부터 찾을 수 있고, 중간부터 탐색할 수도 있습니다.
다른 방식으론 만약 책이 IT 서적이라면 IT 서적 쪽으로 먼저 가서 탐색할 수 있습니다.
즉, 위와 같이 보통 자료 구조의 선택 -> 효율적인 알고리즘의 선택이 됩니다.
또한 알고리즘을 프로그램 명령어의 집합이라고도 합니다.
프로그램은 특정 문제를 해결하기 위한 처리 방법과 순서를 기록한 명령어들의 모음입니다. 이 프로그램이 실행되기 위해서는 메모레 올릴 데이터가 필요하며 이 데이터들을 담아내는 방식이 자료구조입니다.
즉, 넓은 의미에서 자료구조 + 알고리즘(+a) = 프로그램이라고 할 수 있습니다.
Reference
