자료구조와 알고리즘 이란?

자료구조와 알고리즘이란?

• 공부를 할 때마다, 자료구조, 알고리즘은 중요하다는 이야기는 많이 들어왔는데 정확한 차이가 무엇인지를 구분할 수 없어, 문득 찾아보게 되었다.

자료구조

자료구조란?

서비스나, 어플리케이션에 필요한 데이터를 정리해서 담는 구조 , 즉 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 자료구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.

자료구조의 분류

자료구조는 크게, 구현과 형태에 따라 나뉜다.

구현에 따른 자료구조

종류	설명
배열	가장 일반적인 구조이다. 메모리 상에 같은 타입의 자료가 연속적으로 저장된다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다.
튜플	둘 이상의 자료형을 묶음으로 다루는 구조이다.
연결 리스트	노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.
원형 연결 리스트	각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트이다.
이중 연결 리스트	각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.
환형 이중 연결 리스트	처음 노드가 이전 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 이중 연결 리스트이다.
해시 테이블	개체가 해시값에 따라 인덱싱된다.

형태에 따른 자료구조

종류	구분	설명
선형 구조	스택	스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다. 반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다. 만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀐다.
선형 구조	큐	스택과- 반대로 큐 자료구조에 먼저 저장된 것이 제일 먼저 나온다. 반대로, 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.
선형 구조	큐(환형 큐)	한정된 길이 안에서 부수적인 작업 없이 읽고 쓰기를 할 수 있는 큐이다.
선형 구조	덱	양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조이다.
비선형 구조	그래프	꼭짓점과 꼭짓점을 잇는 변으로 구성된다.
비선형 구조	그래프(유향 그래프,무향 그래프)	변이 방향성을 갖는지 갖지 않는지에 따른 그래프의 분류이다. 무향 그래프의 경우, 순환이 없는 연결 그래프를 뜻한다. 유향 그래프의 경우 변의 방향은 보통 부모를 가리키도록 구현된다.
비선형 구조	트리	뿌리와, 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조. 부모 자식 관계는 변으로 표현된다.
비선형 구조	트리(이진트리)	자식이 최대 두 개인 트리
비선형 구조	트리(힙)	이진트리의 일종으로 이진트리에 어떤 특성을 부여한 것이라 할 수있다.

알고리즘

알고리즘이란?

제한된 공간과 시간안에서 데이터를 어떻게 처리할 것인지를 정해놓은 로직 이다. 즉, 알고리즘(algorithm)은 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법이다. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 문제 풀이를 예로들면 문제 풀이에 필요한 계산 절차 또는 처리 과정의 순서를 의미한다.

알고리즘의 분류

종류	설명
구현	재귀적 알고리즘, 연역적 알고리즘, 결정론적 알고리즘, 근사 알고리즘, 양자 알고리즘
설계	무차별 대입 공격, 분할 정복 알고리즘, 그래프 순회, 분기 한정법, 확률적 알고리즘, 리덕션, 백트래킹
최적화 문제	선형 계획법, 동적 계획법, 탐욕 알고리즘, 휴리스틱 함수
이론적 분야	검색 알고리즘, 정렬 알고리즘, 수치 알고리즘, 그래프 알고리즘, 문자열 알고리즘, 암호학적 알고리즘, 기계 학습, 데이터 압축

알고리즘 구현

알고리즘은 자연어, 의사코드, 순서도, 프로그래밍언어, 인터프리터가 작업하는 제어테이블, 유한상태기계의 상태도 등으로 표현할 수 있다.

알고리즘 개발의 정형적 단계
문제 정의 -> 모델 고안 -> 명세 작성 -> 설계 -> 검증 -> 분석(복잡도 등) -> 구현 -> 테스트 -> 문서화

좋은 알고리즘의 특징

특징	설명
정밀성	변하지 않는 명확한 작업 단계를 가져야 한다.
유일성	각 단계마다 명확한 다음 단계를 가져야 한다.
타당성	구현할 수 있고 실용적이어야 한다.
입력	정의된 입력을 받아들일 수 있어야 한다.
출력	답으로 출력을 내보낼 수 있어야 한다.
유한성	특정 수의 작업 이후에 정지해야 한다.
일반성	정의된 입력들에 일반적으로 적용할 수 있어야 한다.

자료구조, 알고리즘

"자료구조"는 메모리를 어떻게 효율적으로 사용하며, 실행 속도를 빠르고, 정확하게 처리할 수 있을까를 궁극적인 목표로 두고 있다.

"알고리즘"은 이러한 자료구조의 목표를 바탕으로 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현하는 것이다.

"자료구조가 무엇인지, 알고리즘이 무엇인지에 대한 답변과 함께 왜? 자료구조와 알고리즘이 중요한지에 대한 충분한 답변이 된 것 같다. 좋은 프로그램을 만들기 위해서는 알맞은 자료구조와, 좋은 알고리즘이 합쳐져서 좋은 프로그램을 이룬다."

References

Youtube 드림코딩
위키피디아 자료구조
위키피디아 알고리즘
자료구조와 알고리즘의 차이
자료구조와 알고리즘 왜 공부해야 할까?