7급 전산직 공무원 자료구조론 요약본 [핵심 단어 및 문장위주 정리]

소개글

"7급 전산직 공무원 자료구조 요약본 [핵심 단어 및 문장 위주 정리]"에 대한 내용입니다.

(보조자료로 이동시에 가볍게 들고 참고하시면 좋습니다.)

목차

1. 자료구조 기본개념
2. 순차 데이터 표현
3. 연결 데이터 표현
4. 제한된 자료구조
5. 트리
6. 그래프
7. 정렬 & 탐색

본문내용

Chapter 1. 자료구조 기본개념
자료구조 = 데이터를 조직해 표현하는 개념
알고리즘 = 문제를 해결하는 절차
프로그램 = 알고리즘 + 자료구조
적합한 자료구조를 선택해야 효율적이다.

선형구조 = 1:1
비선형구조 = 1:N 혹은 M:N

자료구조 선택 시 고려사항
1. 데이터 양
2. 삽입과 삭제 빈도수
3. 기억용량
4. 최악, 평균 처리시간
5. 저장방식

추상데이터 타입(ADT)
데이터 = 모든 처리의 대상
데이터 타입 = 데이터에 적용할 수 있는 연산집합
추상화 = 핵심 구조에 집중하는 것
추상데이터 타입 = 데이터 타입을 추상적으로 정의
추상데이터 타입은 What은 정의됨

알고리즘의 조건
1. 입력 = 외부로부터 0개 이상 데이터 받음
2. 출력 = 적어도 하나의 결과 생성
3. 명확성 = 각 명령은 명확함
4. 유한성 = 한정된 단계가 있다
5. 유효성 = 각 명령은 실행할 수 있음

알고리즘 기술 방법
(자연어 / 흐름도 / 유사코드 / 프로그래밍 언어)

알고리즘과 프로그램 차이
● 프로그램은 유한성을 항상 만족하는건 아니다. (OS)

자료구조를 포함한 알고리즘 = 프로그램

공간복잡도 (필요 저장공간)
● 고정공간 = 입출력에 관계없이 고정필요 공간
● 가변공간 = 런타임 스택을 위한 공간
공간복잡도는 가변공간에 중점

시간복잡도 (완료까지 필요한 소요시간)
● 컴파일시간 = 고정적
● 실행시간 = 실행 빈도수

차수 표기법 = 차수가 가장 큰 항이 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있다.

빅오 표기법
f(n) <= cg(n)을 만족. 상한을 보장한다.

오메가 표기법
f(n) => cg(n)을 만족. 하한을 보장한다.

세타 표기법
cg(n) <= f(n) <= cg’(n)을 만족. 상하한을 보장.

● 똑같은 알고리즘도 입력에 따라 다른 실행시간을 보일 수 있다.

참고 자료

없음