행정고시(5급공채) 전산직 DS(자료구조) 합격자 서브노트

소개글

서브노트 특성상 주요하지 않다고 생각되거나 교재로 확인할 수 있는 일부내용 작성되어있지 않을 수 있음.

목차

없음

본문내용

1장 기본 개념

1.1 개요 : 시스템 생명 주기
o 요구사항, 분석, 설계, 정제와 코딩, 검증

1.2 포인터와 동적 메모리 할당
1.2.1 포인터
1.2.2 동적 메모리 할당
1.2.3 포인터의 위험성

1.3 알고리즘 명세
1.3.1 개요
o 알고리즘: 특정한 일을 수행하는 명령어들의 유한 집합
- 입력, 출력, 명확성, 유한성, 유효성
- 프로그램은 ‘유한성’을 반드시 만족하지 않는다는 점에서 알고리즘과는 다르다 (ex. 운영체제)
* 예제 1.1 : 선택 정렬(selection sort)
* 예제 1.2 : 이원 탐색(binary search)
1.3.2 순환 알고리즘
o 직접 순환(자기 자신을 호출), 간접 순환(자신을 호출하는 다른 함수를 호출)
* 예제 1.3 : 이원 탐색을 순환 함수로 변환
* 예제 1.4 : 순열

1.4 데이타 추상화
* 예제 1.5 추상 데이타 타입 NaturalNumber

1.5 성능 분석
1.5.1 공간 복잡도
o 고정 공간 요구, 가변 공간 요구
- S(P) = c + Sp(I)
- 보통 가변 공간 요구에 대해서만 관심을 둔다
- 함수의 인자에서 배열을 call by value로 전달하는 경우, 가변 공간 요구는 n이 된다(예: Pascal)
- 함수의 인자에서 배열의 첫번째 요소의 주소만 전달하는 경우, 가변 공간 요구는 0이 된다(예: C)
- 순환 함수는 반복 함수보다 공간복잡도에서 큰 오버헤드를 가진다
1.5.2 시간 복잡도
o 컴파일 시간, 실행 시간
- 컴파일 시간은 고정이므로, 실행 시간만 관심을 둔다
* 예제 1.9 리스트에 있는 수의 반복적 합산
* 예제 1.10 리스트에 있는 수의 순환적 합산
1.5.3 점근 표기법(Ο, Ω, Θ)

※ AtoI 책의 ‘4. Recurrences' 꼭 보자! - 시간복잡도 계산에 유용한 공식들이 많이 나와있음

참고 자료

없음