자료구조 정리

자료구조 정리

 

---

1주차 1강

 

자료구조의 개요

최적의 프로그램 작성

 

자료형태에 따른 분류

단순구조 : 정수, 실수, 문자, 문자열

선형구조 : 1대1선형관계, 리스트, 연결 리스트, 큐, 덱

비선형구조 : 1대N N대N, 트리 그래프

파일구조 : 레코드의 집합 파일, 순차파일, 색인파일, 직접파일

 

자료표현

2진수 코드로 표현, n개의 비트로 2의 n제곱개의 상태 표현

 

---

1주차 2강

 

수치자료의 표현

• 10진수의 표현
• 존(Zone) 형식의 표현
• 10진수 한자리를 표현하기 위해 1바이트(8비트)를 사용하는 형식
• 존영역 : 상위 4비트, 1111로 표현
• 수치영역 : 하위 4비트
• 여러자리의 10진수를 표현하는 방법
• 10진수의 자릿수만큼 존형식을 연결
• 마지막자리의 존 영역 부호를 표시
• 양수 : 1100
• 음수 : 1101
• 팩(Pack) 형식의 표현
• 10진수 한자리를 표현하기 위해서 존 영역없이 4비트를 사용
• 마지막 비트에 부호표시
• 양수 : 1100
• 2진수의 정수 표현
• n비트의 부호 절대값 형식
• 최상위 1비트 : 부호표시
• 양수 : 0
• 음수 : 1
• 나머지비트 : 이진수 표시
• 1의 보수 형식
• 음수 표현에서 부호 비트 대신 1의 보수를 사용
• n비트의 2진수를 1의 보수로 만드는 방법
• n비트를 모두 1로 만든후 이진수를 뺀다
• 2의 보수 형식
• n비트의 2진수를 2의 보수로 만드는 방법
• 1의 보수에 1을 더해준다
• 2진수 정수의 세가지 표현 방법에서 양수 표현은 같고 음수표현만 다름
• 2진수의 실수 표현
• 고정 소수점
• 부동 소수점

 

문자자료의 표현

• BDC 코드
• 6비트를 사용
• 상위 2비트 : 존비트
• 하위 4비트 : 2진수 비트
• EBCDIC 코드
• 8비트를 사용
• 상위 4비트 : 존비트
• 하위 4비트 : 2진수 비트
• ASCII 코드
• 7비트를 사용
• 상위 3비트 : 존비트
• 하위 4비트 : 2진수 비트

 

논리자료의 표현

• 논리자료
• 참 거짓, 1 0
• 1바이트를 사용하여 논리자료
• 포인터 자료
• 메모리의 주소를 표현하기 위한 자료형식
• 변수의 주소나 메모리 특정위치 주소를 저장

 

문자열 자료표현

• 여러 문자로 이루어진 문자의 그룹을 하나의 자료로 취급하여 메모리에 연속적으로 저장
• 하나의 문자열 자료에 포함된 부분 문자열을 표현하는 방법
• 구분자를 사용하는 방법 : 메모리 효율적, 탐색시간 비효율적
• 고정길이로 저장하는 방법 : 메모리 비효율적, 탐색시간 효율적
• 포인터를 사용하는 방법 : 메모리 효율적, 탐색시간 효율적

 

---

2주차 1강

 

소프트웨어 생명주기

• 소프트웨어를 체계적으로 개발하기 위해 개발과정을 단계별로 나눈것
• 요구분석 > 시스템 명세 > 설계 > 구현 > 테스트 > 유지보수
• 요구분석
• 제약조건, 목표 정의
• 요구명세서 작성
• 시스템명세
• 수행정의, 입출력정의
• 시스템 기능 명세서 작성
• 설계
• 시스템 명세에서 정의한 기능을 실제 논리적 방법 결정
• 시스템 구조설계
• 프로그램 설계
• 사용자 인터페이스 설계
• 설계 방법
• 하향식 설계
• 상향식 설계
• 객체지향 설계
• 구현
• 실제 프로그램 작성
• 프로그래밍 기법
• 구조화 프로그래밍
• 모듈러 프로그래밍
• 테스트
• 단위테스트
• 통합테스트
• 하향식 테스트
• 상향식 테스트
• 하향식/상향식 점진적 테스트
• 인수 테스트
• 유지보수
• 시스템이 인수되고 설치된후
• 소프트웨어에서 가장긴 기간
• 유지보수 유형
• 수정형 유지보수 : 사용중에 오류수정
• 적응형 유지보수 : 환경적 변화에 적응하기위해
• 완전형 유지보수 : 시스템 향상 개선작업
• 예방형 유지보수 : 대비작업
• 개발된 소프트웨어 품질 평가
• 정확성 : 요구되는 기능을 정확하게 수행하는지
• 유지보수성 : 효율적 유지보수 정도
• 무결성 : 외부 공격의 보안성
• 사용성 : 사용자가 쉽게 사용하는지

 

추상 자료형

• 컴퓨터를 이용한 문제 해결의 추상화
• 크고 복잡한 문제를 단순화시켜 쉽게 해결하기 위한 방법
• 자료 추상화
• 추상 자료형 (ADT, Abstract Data Type)
• 자료와 연산자의 특성을 논리적으로 추상화하여 정의한 자료형
• 추상화와 구체화
• 추상화 : 무엇인가 를 논리적정의
• 구체화 : 어떻게 할것인가 를 실제적 표현

 

 

---

2주차 2강

 

알고리즘

• 알고리즘 이해
• 알고리즘
• 문제해결방법을 추상화하여 단계적 논리적으로 기술한 명세서
• 알고리즘 조건
• 입력, 출력
• 명확성
• 유한성 : 반드시 종료되어야한다
• 효과성 : 실행이 가능해야한다
• 알고리즘 표현 방법
• 자연어로 서술적 표현 방법
• 순서도(Flow chart) 도식화 방법
• 프로그래밍 언어 구체화
• 가상코드로 추상화방법
• 순서도
• 장점 : 알고리즘의 파악용이
• 단점 : 복잡한 알고리즘 표현 어려움
• 가상코드
• 프로그래밍 언어가 아니므로 실행불가능
• 프로그래밍 언어로 변환 용이
• 가상코드 형식
• 지정문
• 조건문

성능분석

• 알고리즘 성능분석 방법 존(Zone) 형식의 표현
• 공간 복잡도
• 알고리즘 저장공간양
• 공간복잡도 = 고정 공간 + 가변 공간
• 시간 복잡도
• 알고리즘 실행완료 소요시간
• 시간 복잡도 = 컴파일 시간 + 실행시간
• 시간 복잡도 표기법
• 빅-오(Big-Oh) 표기법 사용

 

---

3주차 1강

 

배열

• 배열 (array)
• 같은 자료형을 가진 자료들을 나열하여 메모리에 연속으로 저장해 만즌 그룹
• 인덱스 (index)
• 배열의 요소를 구별하기 위해 사용하는 번호
• 0부터 시작
• 모든 자료형에 대해서 배열로 구성 가능
• 1차원 배열
• 선언 형식
• 자료형 배열이름[배열 요소개수];
• 1차원 배열의 초기화
• 자료형 배열이름[배열크기] = { 초기값 리스트 };
• 문자 배열
• 문자의 나열
• " 와 " 사이에 표시
• 배열의 자료형은 문자 자료형 (char)
• 다차원 배열
• 다차원 배열 선언 형식
• 자료형 배열이름[배열크기][배열크기];
• 3차원 배열 선언 형식
• 자료형 배열이름[배열크기1][배열크기2][배열크기3]
• 배열그기1 : 면의 개수
• 배열그기2 : 행의 개수
• 배열그기3 : 열의 개수

포인터

• 포인터
• 변수의 메모리 주소값
• 포인터 변수
• 주소값을 저장하는 특별한 변수
• 포인터 선언 형식
• 자료형 *포인터변수이름;
• 포인터 연산
• 주소 연산자 : &
• 변수의 주소를 구하기 위해 사용
• 변수 앞에 & 사용하여 그변수의 주소를 사용
• 포인터 변수 = & 변수;
• 참조 연산자 : *
• 저장된 주소에 있는 값을 액세스 하는 연산자

 

---

3주차 2강

 

구조체

• 구조체
• 구조체도 배열처럼 여러개의 데이터 그룹을 묶어 하나의 자료형으로 정의하고 사용하는 자료형
• 레코드 : 자료를 체계적으로 관리하기 위한 일정한 단위 형식
• 필드 : 레코드를 구성하는 하위 항목
• 파일 : 레코드가 모여 하나의 파일구성
• 여러 자료형의 필드를 가지고 있는 레코드를 만들때 구조체 사용
• 구조체 선언
• 여러 자료형 변수들을 그룹으로 묶어 하나의 자료형으로 선언
• 구조체이름, 자료형, 데이터 항목으로 구성
• struct 구조체이름 구조체변수;
• 구조체 데이터 항목의 참조
• 점 연산자 : .
• 화살표 연산자 : ->

재귀호출

• 재귀호출 (순환호출)
• 자기 자신을 호출하여 순환 수행하는것

 

---

4주차 1강

 

선형리스트

• 리스트
• 자료를 나열한 목록
• 선형리스트
• 순서리스트
• 자료들간의 순서를 갖는 리스트
• 선형 리스트의 저장
• 원소들의 논리적 순서와 같은 순서로 메모리에 저장
• 순차 자료구조
• 원소들의 논리적 순서 = 원소들이 저장된 물리적 순서

 

---

4주차 2강

 

다항식의 순차 자료구조 표현

 

 

---