자료구조

왜 자료구조를 배워야 할까 ? 

-자료들의 효율적 관리와 구조화를 다루는 분야로 컴퓨터 공학에서 매우 중요함

-최근 각광받는 데이터 사이언스 분야의 이해를 위한 선행지식임

1. 자료구조 알고리즘의 정의 및 필요성

1.자료를 정리하고 조직화하는 이유 

-사물을 편리하고 효율적으로 사용하기위해 

-다양한 자료를 효율적인 규칙에 따라 정리하기 위해 

2. 컴퓨터에서의 자료구조란?(Data Structure)

컴퓨터에서 자료를 정리하고 조직화하는 다양한 구조

1) 선형 자료구조 *항목들을 순서대로 나열하여 저장 

-리스트: 자유로운 선형 자료구조 

-스택,큐,덱: 항목의 접근을 전단이나 후단으로 제한 

2) 비선형 자료구조 

-트리: 회사조직도나 폴더와 같은 계층구조 

-그래프 : 다양한 문제 해결을 위해 복잡한 연결관계를 표현한 구조 

 

2.알고리즘의 의미

*컴퓨터로 문제를 풀기 위한 단계적 절차 

ex) 사전에 단어는 어떻게 찾나? 

프로그램 = 자료구조 + 알고리즘

3. 알고리즘의 조건 

-입력:      0개이상의 입력 존재 

-출력:      1개 이상의 출력 존재 

-명백성:   각 명령어의 의미는 모호하지 않고 명확해야 함 

-유한성:   한정된 수의 단계 후에 반드시 종료되어야 함

-유효성 :  각 명령어들은 실행 가능한 연산이어야 함

4. 알고리즘 기술 방법

1) 자연어 표현 

*가독성이 좋으나 단어정의가 정확하지 않으면 의마가 모호함

ex) find_max( A )

2) 흐름도 표현 

*직관적이나 복잡한 알고리즘 기술 시 매우 복잡해질 우려가 있음 

3) 유사코드 표현

*알고리즘 핵심내용에 집중하며 프로그램 구현시 문제들을 감출 수 있음 

4) 특정언어 표현 

*가장 정확하게 알고리즘을 기술하지만, 알고리즘 핵심내용의 이해를 방해할 수 있음 

파이썬은 C나 JAVA에 비해 간결한 표현 가능 

추상자료형(ADT,Abstract Data Type)

*데이터 타입(자료형)을 프로그래머가 추상적(수학적)으로 저으이 한 것

알고리즘의 성능 분석 및 순환 알고리즘 

1. 알고리즘 성능 분석 방법

실행시간 측정 

-두개의 알고리즘의 실제 실행 시간을 측정 비교 

-동일한 하드웨어 환경에서 구현해야 함 

복잡도 분석 

-직접 실행하지 않고 알고리즘의 연산 횟수를 계산 

-일반적으로 연산의 횟수는 n의 함수임 

시간복잡도 -> 수행시간 

공간 복잡도 -> 메모리 공간 

 

복잡도 분석 방법 

시간 복잡도 

-산술, 대입, 비교, 이동의 기본적인 연산 고려

-알고리즘 수행에 필요한 연산의 개수를 계산 

1.빅오 표기법

1) 차수가 가장 큰 항이 절대적인 영향을 줌 

->다른 항들은 상대적으로 무시됨 

2)연산의 횟수를 대략적(점근적)으로 표기함 

빅오메가와 빅세타 

빅오메가 표기법 : 작을 때 

빅세타 표기법: 사이에 있을 때 

최선, 평균, 최악의 경우 

입력에 따라 실행시간이 다를 수 있음 

최선의 경우(Best Case) 가장 빠른 경우롤 보통 의미 없음 

평균의 경우(Average Case) 평균적인 경우로 계산이 어려움 

최악의 경우 (Worst Case) 가장 늦은 경우로 중요하게 널리 사용 

순환 알고리즘 

*알고리즘이나 함수가 수행도중 자기자신을 다시 호출하는 기법임 

*정의자체가 순환적으로 되어 있는 경우에 적합함