전산직공무원 자료구조론 요약 정리자료

소개글

탑스팟 전산직 공무원 대비 자료구조론 요약 정리

목차

1. 자료구조의 기본개념
2. 순서리스트
3. 배열
4. 연결리스트
5. 스택과 큐
6. 트리
7. 그래프
8. 정렬
9. 검색
10. 해싱
11. 탐색구조
12. 파일구조

본문내용

1. 자료구조의 기본개념


○ 자료(data) : 현실 세계(real world)로부터 단순한 관찰이나 측정을 통해서 수집된 사실이나 값
○ 정보(information)
- 자료가 프로그램에 의해 처리된 원하는 결과
- 어떤 상황에 대한 적절한 의사결정을 할 수 있게 하는 데이터의 유효한 해석이나 상호관계
1. 자료와 정보


○ 10진연산
- 팩 (pack) 형식 : 1바이트에 10진수 두자리 표현, -5678 -> 5678D
- 언팩(unpack)형식 : 1바이트에 10진수 한자리 표현, -5678 -> F5F6F7D8
○ 2진연산

- 부호화크기(절대치)
- 1의 보수
- 2의 보수
+0, -0, 표현범위: -(2n-1-1) ∼ +(2n-1-1)
+0, -0, 표현범위: -(2n-1-1) ∼ +(2n-1-1)
+0, 표현범위: -2n-1 ∼ +(2n-1-1)
→ 1,2의 보수를 사용하는 이유 : 뺄셈 수행 시 가산기를 이용하기 위함
○ 10진수를 다른 진수로 변환
- 정수 : 10진수를 해당진수로 나누어 몫은 두고, 나머지를 해당진수의 자리로 취함
- 소수 : 10진수를 해당진수로 곱한 다음, 소수부분이 0이거나 반복되는 수가 나올때까지 곱하기 반복
2. 자료의 종류와 표현


○ 객체의 명세와 객체에 대한 연산의 명세가 객체의 표현과 연산의 구현으로부터 분리된 데이터 타입
○ S = (D, F, A)
- S : 데이터 구조, D:데이터 구조의 정의영역(domain) 집합, F: 합수의 집합, A: 공리(axiom)의 집합
3. 추상데이터타입(ADT: Abstract Data Type)


○ 알고리즘 : 특정한 일을 수행하는 명령어들의 유한집합
○ 알고리즘의 요구조건
- 입력(input) : 외부로부터 자료의 입력이 0개 이상 있다
- 출력(output) : 최소 한가지 이상의 출력이 있어야 한다
- 명확성(definition) : 모든 명령은 명확해야한다
- 유한성(finiteness) : 반드시 종료되어야 한다
- 효율성(effectiveness)
- 유효성, 실제성
○ 알고리즘의 복잡도
- 시간복잡도 : 추상적인 실행시간, 명령어들의 실행횟수로 결정
- 공간복잡도 : 메모리의 양으로 표현
4. 알고리즘과 복잡도

참고 자료

없음