자료구조 요약

소개글

"자료구조 요약"에 대한 내용입니다.

목차

Chapter 01. 자료구조와 알고리즘
Chapter 02. 순환
Chapter 03. 배열, 구조체, 포인터
Chapter 04. 스택
Chapter 05. 큐
Chapter 06. 연결 리스트 I
Chapter 07. 연결 리스트 II
Chapter 08. 트리
Chapter 09. 우선순위 큐
Chapter 10. 그래프 I
Chapter 11. 그래프 II
Chapter 12. 정렬
Chapter 13. 탐색

본문내용

Chapter 01 자료구조와 알고리즘
1.1 자료구조와 알고리즘
자료구조와 알고리즘
• 프로그램 = 자료구조 + 알고리즘
알고리즘의 조건
• 알고리즘의 조건
 입력 : 0개 이상의 입력이 존재하여야 한다.
 출력 : 1개 이상의 출력이 존재하여야 한다.
 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.
 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다.
 유효성 : 각 명령어들은 실행 가능한 연산이여야 한다.
알고리즘
• 알고리즘(algorithm): 컴퓨터로 문제를 풀기 위한 단계적인 절차

1.2 추상 자료형
ADT
1.3 알고리즘의 성능 분석
알고리즘의 성능분석
• 알고리즘의 성능 분석 기법
 수행 시간 측정
◼ 두개의 알고리즘의 실제 수행 시간을 측정하는 것
◼ 실제로 구현하는 것이 필요
◼ 동일한 하드웨어를 사용하여야 함
 알고리즘의 복잡도 분석
◼ 직접 구현하지 않고서도 수행 시간을 분석하는 것
◼ 알고리즘이 수행하는 연산의 횟수를 측정하여 비교
◼ 일반적으로 연산의 횟수는 n의 함수
Big-O?
• 알고리즘의 성능을 수학적으로 표기해주는 표기법
• 시간과 공간 복잡도를 표현
• 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는게 목표
단순하게 빅-오 구하기
∙ T(n)이 다항식으로 표현이 된 경우, 최고차항의 차수가 빅-오가 된다.
빅-오의 실질적인 의미
아무리 연산횟수의 증가율이 크다 한들 n2 증가율의 패턴이 을 넘지 못한다!
빅오 표기법의 종류

최선, 평균, 최악의 경우
• 알고리즘의 수행시간은 입력 자료 집합에 따라 다를 수 있다.
• 최선의 경우(best case): 수행 시간이 가장 빠른 경우
• 평균의 경우(average case): 수행시간이 평균적인 경우
• 최악의 경우(worst case): 수행 시간이 가장 늦은 경우
최선, 평균, 최악의 경우
• (예) 순차탐색
• 최선의 경우: 찾고자 하는 숫자가 맨 앞에 있는 경우 ∴ O(1)
• 최악의 경우: 찾고자 하는 숫자가 맨 뒤에 있는 경우 ∴ O(n)

참고 자료

없음