자료구조
데이터를 구성하고 저장하는 방법을 말하며 데이터를 식별하는 방법을 제공하고 데이터의 관계를 보여주는 개념이다.
데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.
자료구조의 분류
자료의 특성과 크기, 주요 사용법과 연산 종류, 기억 공간 크기에 따라 여러 가지 종류의 자료 구조 중 하나를 선택할 수 있다. 자료 구조의 종류로는 단순 구조와 자료 간 관계가 1대 1인 선형 구쥬, 비선형 구조, 파일 구조가 있다.
구현에 의한 분류
- 배열 - 가장 일반적인 구조, 메모리 상 같은 타입의 자료가 연속적으로 저장
- 튜플 - 둘 이상의 자료형을 묶음으로 다루는 구조
- 연결 리스트 - 자료와 다음 노드를 가르키는 참조값으로 구성된 노드를 단위로 구성되어 있으며 다음 노드로 아무 것도 가르키지 않으면 리스트의 끝원형 연결 리스트 - 노드는 다음 노드를 가르키며 마지막 노드가 처음 노드를 가르키는 연결 리스트
- 이중 연결 리스트 - 각 노드는 이전 노드와 다음 노드를 가르키는 참조 값으로 구성되며 처음 노드의 이전노드와 마지막 노드의 다음 노드는 없음환형 이중 연결 리스트 - 처음 노드가 이전 노드로 마지막 노드를 가르키고, 마지막 노드가 다음 노드로 처음 노드를 가르키는 이중 연결 리스트
- 해시 테이블 - key, value 형태로 매핑할 수 있는 구조인 연관 배열 추가에 사용도는 자료 구조
형태에 따른 분류
- 선형 구조
- 스택 - 먼저 저장된 것이 나중에 나오는 형태, 자료의 나열 순서를 바꾸고 싶다면 스택에 넣었다가 꺼내면 역순으로 바뀐다
- 큐 - 스택과 반대로 큐 자료구조에 먼저 저장된 것이 제일 먼저 나온다
- 덱 - 양쪽에 넣기와 빼기를 할 수 있는 일반화된 선형 구조
- 비선형 구조
- 그래프 - 꼭짓점과 꼭짓점을 잇는 변으로 구성
- 트리 - 트리와 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조, 부모 자식 관계는 변으로 표현
- 이진 트리 - 자식이 최대 두 개의 트리힙 - 이진 트리의 일종으로 이진 트리에 어떤 특성을 부여한 것
알고리즘
문제를 해결하기 위해 사용하는 일련의 단계. 알고리즘을 정하는 여러 관점이 있지만 한가지 공통점은 문제를 해결하는 논리적 단계를 의미한다. 조금 더 정확한 의미를 따진다면 어떠한 행동을 하기 위해 만들어진 명령들의 유한 집합을 말한다. 알고리즘은 정렬 알고리즘, 검색 알고리즘, 최단 경로 알고리즘, 그래프 알고리즘 등의 다양하 종류로 나뉘게 된다.
알고리즘의 조건
알고리즘은 다음과 같은 조건을 만족해야한다.
- 입력 - 0 또는 그 이상의 제공된 자료가 존재
- 출력 - 최소 1개 이상의 결과
- 명확성 - 각 단계는 명확하여 애매함이 없어야함
- 유한성 - 유한의 횟수를 거친 후 문제를 해결하고 종료해야함
- 효과성 - 모든 연산들이 유한한 시간 내에 정확하게 수행할 수 있을 정도록 단순해야함
쉽게 말하면 어떤 입력이 있으면 입력에 따라 명령을 명확하게 실행하고 입력에 따른 결과물을 도출할 수 있다면 알고리즘으로 볼 수 있다는 의미이다. 반대로 명령에 애매함이 있거나 시간 내 종료가 보장되지 않는다면 메서드(Method)라고 한다.
자료구조와 알고리즘의 관계
서로 다른 개념이면서 상호 보완적인 개념이다. 자료구로는 데이터의 저장 및 조직화를 담당하고 알고리즘은 이러한 데이터를 처리하고 조작하는 로직을 제공한다. 데이터가 어떻게 저장되고 구성되어 있는지에 따라 알고리즘의 성능 및 복잡성이 결정된다.
공간 복잡도(Space Compliexity)
컴퓨터의 메모리 공간을 뜻하며 자원이 제한된 시스템에서 동작하는 프로그램을 구현하는 것과 같이 특별한 경우에 사용하는 분석 방법 중 하나로 시간 복잡도와 마찬가지로 빅오 표기법을 주로 사용한다.
시간 복잡도(Time Complexity)
주어진 입력에 따라 문제를 해결할 때 걸리는 시간을 뜻하며, 알고리즘의 성능이 얼마나 효율적이니 알 수 있는 가장 일반적인 방법이다. 시간 복잡도를 분석하는 방법은 실제적인 방법과 수학적인 방법으로 나뉜다
실제적인 방법 : 입출력 데이터의 양의 알고리즘 동작에 미치는 영향을 관찰하고 기록하는 것으로 정확성이 떨어지고 사용 범위가 제한적이다
수학적인 방법 (점근적 분석): 알고리즘의 성능이 최악이 되는 경계를 판단하거나 알고리즘의 평균 성능을 찾으며 알고리즘 사이의 점근적 증가율을 비교하기 위해 빅 오 표기법을 사용하는데 몇 가지 범주로 나눌 수 있다.
이 중 가장 많이 사용하는 표기법은 빅 오 표기법이다
빅오 표기법
대문자 O는 시작 복잡도의 정도를 나타내는 표기법인 차수를 뜻하는데 복잡도를 주로 대문자 O또는 빅 오를 사용해서 표기하는 관례가 생기면서 자연스레 빅 오 표기법이라고 부르게 되었다. 알고리즘을 실행하는데 걸리는 최대 시간을 측정하며 이 본질은 알고리즘의 실행 시간이 최악인 경우를 나타낸다.
빅 오 표기법은 주로 다음과 같이 분류된다.
상수형 알고리즘은 O(I)의 성능이 가장 좋고 계승(팩토리얼) 알고리즘의 성능이 가장 나쁘다.
