[자료구조*알고리즘] 0-2.자료구조와 알고리즘 기본 정리

 

 

 

 

 

 

 

자료구조 - 데이터를 표현하는 방법 및 구조

알고리즘 - 데이터를 처리하는 방법

 

 

 

 

 

시간복잡도

 

• 문제를 해결하는데 걸리는 시간으로 Big-O 표기법을 사용한다
• 빅오를 구할 때 계수와 낮은 차수의 항은 제거한다
• 시간 복잡도를 구하는 방법은 핵심 연산의 반복횟수를 구하면 된다

 

 

 

 

 

 

 

 

 

 

알고리즘에서 재귀함수를 사용하는 경우

• 재귀로 접근하여 문제가 쉽게 풀리는 경우에 사용한다
• 비재귀를 사용할 때보다 가독성이 높은 경우에 사용한다

 

 

 

 

 

 

 

 

 

선형 자료구조

• 자료를 구성하는 원소들을 순차적으로 나열한 구조
• 자료구조는 선형 자료구조와 비선형 자료구조로 구분된다

 

선형 자료구조 예시

• 배열: 데이터의 주소가 일정하게 붙어있다.
• 배열리스트: 배열을 이용하여 항목의 추가, 삭제 등의 연산이 효과적으로 이루어지는 리스트 자료구조
• 연결리스트: 포인터에 의하여 인접데이터들이 연결된 자료구조, 동적할당을 기반으로 한 리스트
• 스택: 위에서 삽입, 삭제 ex) 프링글스 통
• 큐: 앞에서 삽입, 삭제 ex) 줄 서기

 

 

비선형 자료구조 예시

• 트리: 노드와 간선들로 이루어진 자료구조로 계층적 관계를 표현한다
• 그래프: 연결되어 있는 객체 간의 관계를 표현하는 구조

 

 

 

 

 

 

 

 

 

 

 

모름

ADT(추상 자료형)

• 데이터 구조를 명세한 것
• 다루는 데이터와 데이터를 다루는 작업의 집합

 

 

 

 

 

 

 

리스트(List)

• Ex) 물품, 사람의 이름 따위를 일정한 순서로 적어놓은 것
• 순차 리스트(배열 기반 리스트)
• 연결 리스트(동적할당 기반 리스트)
• 데이터를 나란히 저장한다
• 데이터의 중복 저장을 허용한다

 

 

 

 

 

 

 

 

스택(Stack)

• 데이터 위에 데이터가 쌓이는 구조
• LIFO(Last In First Out) -> 선입후출

 

 

 

 

 

 

 

큐(Queue)

• 데이터 앞에 데이터가 쌓이는 구조
• FIFO(First In First Out) -> 선입선출

 

 

 

 

 

 

 

 

 

트리(Tree)

• 루트노드가 존재한다
• 각 노드는 0개 이상의 자식노드를 가질 수 있으며 간선을 통해 노드를 연결한다.