[2017.05.15~2017.05.19] 자료구조 1/5

자료구조를 다시금 리마인드하고 싶어서 수강

//

자료구조란?

자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업

자료구조를 배우는 이유?

컴퓨터는 사람이 원하는 것을 알아서 처리할 수 없음

컴퓨터가 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여 그에 대한 최적의 프로그램을 작성해 야 한다.

자료의 형태에 따른 분류

• 단순구조(기본 자료형)
• 선형구조(자료들 간의 앞뒤 관계가 1:1 선형 관계, 예:리스트,링크드리스트,스택,큐,덱 등)
• 비선형구조(자료들 간의 앞뒤 관계까 1:다, 다:다의 관계, 예:트리,그래프 등)
• 파일구조(레코드의 집합인 파일에 대한 구조 예:순차파일,색인파일,직접파일 등)

이미지 출처 : 교재

자료구조는 메모리 관리 / 운영체제(라운드엔 로빈 등)에도 사용된다.

추상 자료형

• 컴퓨터를 이용한 문제를 단순화시켜 쉽게 해결하기 위한 방법
• 자료 추상화

추상 자료형

자료와 연산자의 특성을 논리적으로 추상화하여 정의한 자료형

추상화와 구체화

추상 자료형

	자료	연산
추상화	추상 자료형	알고리즘 정의
구체화	자료형	프로그램 구현

알고리즘(문제 해결 방법을 추상화하여 각 절차를 논리적으로 기술해 놓은 명세서)

알고리즘의 조건

• 입력
• 출력
• 명확성
• 유한성
• 효과성

알고리즘의 표현 방법

• 자연어를 이용한 서술적인 표현 방법
• 순서도(Flow chart)를 이용한 도식화 표현 방법
• 프로그래밍 언어를 이용한 구체화 방법
• 수도코드를 이용한 추상화 방법

수도코드

• 일반적인 형태와 유사하게 알고리즘 표현
• 특정 프로그래밍 언어가 아니므로 직접 실행은 불가능

수도코드 형식의 기본요소

• 기호
• 자료형
• 연산자

알고리즘 성능 분석 방법

• 공간 복잡도
• 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간량
• 공간 복잡도 = 고정 공간 + 가변 공간

시간 복잡도

• 알고리즘을 프로그램으로 실행하여 완료되기까지의 총 소요시간
• 시간 복잡도 = 컴파일 시간 + 실행 시간
• 실행 빈도수의 계산

시간 복잡도 표기법

• Big-Oh 표기법
• 실행 빈도수를 구하여 실행시간 함수 찾기
• 실행시간 함수의 값에 가장 큰 영향을 주는 n에 대한 항을 선택하여 계수는 생략하고 O(Big-Oh)의 오른쪽 괄호  안에 표시

시간복잡도의 크기 비교

이미지 출처 : http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation

선형 리스트

• 순서리스트
• 자료들 간에 순서를 갖는 리스트

선형 리스트의 저장

• 원소들의 논리적 순서와 같은 순서로 메모리에 저장
• 순차 자료구조(원소들의 논리적 순서 = 원소들이 저장된 물리적 순서)

순차 자료구조의 원소 위치 계산

• 선형 리스트가 저장된 시작 위치:a
• 원소의 길이:l
• i번째 원소의 위치 = a + (i-1)*l

-선형 리스트에서의 원소 삽입시 비효율적

원소 삽입시 빈 자리 만들기(한자리씩 뒤로 자리 이동 시키기)-)준비한 빈 자리에 원소 삽입하기

-원소 삭제도 해당

원소 삭제하기->삭제한 빈 자리 채우기(삭제한 자리 이후의 원소들을 한자리씩 앞으로 자리 이동시키기)

순차 자료 구조의 장점

-원소들의 순서를 따로 표시할 필요없이 간단히 구성가능

-인덱스를 사용하여 특정 원소를 쉽게 액세스

순차 자료 구조의 단점

-원소 삽입, 삭제 연산은 오버헤드가 발생, 삽입삭제가 많이 필요한 경우에는 순차 자료구조는 비효율적