[Algorithm] 알고리즘과 자료구조의 차이점
👻 알고리즘
알고리즘(Algorithm), 셈법은 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산절차 또는 처리과정의 순서를 뜻한다. 프로그램 명령어의 집합을 의미하기도 한다.
🌱 복잡성
입력의 크기가 n일 경우, 점근 표기법 O를 사용하여 다음과 같이 나타낸다. 빅 오(Big-O) 표기법이라고도 한다.
- O(1) : n에 관계없이 일정 시간 이하에 수행되는 알고리즘이다.
- ex) 파일의 첫 번째 바이트가 널(null)인지 검사하는 것
- O(log n) : log n에 비례하는 시간 이하에 수행되는 알고리즘이다.
- ex) 이진 탐색
- O(n) : n에 비례하는 시간 이하에 수행되는 알고리즘이다.
- ex) 기수 정렬
- O(n log n) : n에 대략 비례할 수 있는 시간 이하에 수행되는 알고리즘이다.
- ex) 정렬 알고리즘
- O(n^2) : n^2에 비례하는 시간 이하에 수행되는 알고리즘이다.
- ex) 최장 공통 부분 수열 문제
- O(n^3) : n^3에 비례하는 시간 이하에 수행되는 알고리즘이다.
- ex) 행렬 곱셈
- O(a^n) : 2^n과 같은 꼴의 수행 시간 이하에 수행되는 알고리즘이다.
- ex) 충족 가능성 문제
- O(n!) : n! 즉 n * (n -1) * (n - 2) * … * 1과 같은 꼴의 수행 시간 이하에 수행되는 알고리즘이다.
- ex) 배열의 모든 순열을 검사하는 것
대문자 O 표기법의 정의상 아래의 복잡도는 그 위의 복잡도를 포함하므로, 대부분의 알고리즘은 O(n!)의 수행 시간을 가진다.
👻 자료구조
자료구조(Data Structure)란, 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해 자료구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다.
🌱 자료구조의 종류
- 배열(array) : 가장 일반적인 구조이다. 메모리 상에 같은 타입의 자료가 연속적으로 저장된다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다.
- 튜플(tuple) : 둘 이상의 자료형을 묶음으로 다루는 구조이다.
- 리스트(list) : 데이터가 하나의 리스트처럼 연결되어있는 구조이다. 연결 리스트, 원형 연결 리스트, 이중 연결 리스트가 있다.
- 해시 테이블(hash table) : 개체가 해시값에 따라 인덱싱된다.
- 스택(stack) : 스택 자료구저에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다. 반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다. 만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀐다.
- 큐(queue) : 스택과 반대로 큐 자료구조에 먼저 저장된 것이 제일 먼저 나온다. 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다. 환형 큐 등이 있다.
- 덱(deque) : 양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조이다.
- 그래프(graph) : 꼭짓점과 꼭짓점을 잇는 변으로 구성된다. 유향 그래프, 무향 그래프가 있다.
- 트리(tree) : 뿌리와 뿌리, 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조이다. 부모 자식 관계는 변으로 표현된다.
- 힙(heap) : 이진트리의 일종으로 이진트리에 어떤 특성을 부여한 것이라 할 수 있다.
이진 트리 : 자식이 최대 두 개인 트리를 의미한다.
👻 알고리즘과 자료구조의 차이
간략하게 말하자면 알고리즘과 자료구조는 엄연히 다른 의미이다.
자료구조는 자료를 보관하는 곳의 설계라 한다면, 알고리즘은 자료구조에 입출력, 탐색 등의 방법을 의미한다. 고로 자료구조를 이용하여 우리가 데이터를 어떻게 저장할 지 고민하게 되고, 그렇게 저장한 데이터들에 접근해 어떻게 입출력하고 탐색하는 지는 알고리즘을 이용하게 된다. 언뜻보면 비슷해보이지만 둘 다 데이터에 접근하는 범위가 다르니 그 점의 차이를 명확하게 구분해야 한다.
👻 글을 마치며
이번 시간에는 알고리즘 입문을 기념으로 알고리즘과 자료구조의 차이점에 대해 알아보았다. 처음에는 알고리즘, 자료구조 하면 한 데 묶어 비슷한 개념으로 생각했지만 확실히 자세하게 공부해보니 엄연히 다른 범위인 것을 알 수 있었다. 크게 보면 자료구조 안에 알고리즘이 있다고 보면 될 것 같다. 앞으로는 C++로 자료구조에 대해 공부하고, 해당 공부를 할 때 항상 고려해야 할 알고리즘을 자세하게 공부 할 예정이다. 알고리즘의 목적은 오로지 프로그램의 효율이 1순위이므로 생각해야 할 게 많으니 공부를 확실하게 해둬야 할 것 같다.
출처
Leave a comment