자료구조 실습 2주차

자료구조 실습 2주차

논리 연산
not - 부정을 긍정으로, 긍정을 부정으로 0 -> 1, 1 -> 0
and - 모두 참일 경우 참
or - 어느 하나만 참이면 참 
xor - 베타적 논리합 -> 반대일 경우
논리 곱 = and연산 = 직렬 회로

직렬 회로일 경우
a b
0 0 -> 0
0 1 -> 0
1 0 -> 0
1 1 -> 1

병렬 회로일 경우
a b
0 0 -> 0
0 1 -> 1
1 0 -> 1
1 1 -> 1

2진수의 실수 표현
 a가 32비트 일때 1비트는 부호, 8비트는 지수, 23비트는 소수부(가수부)가 차지한다.
 4바이트를 사용하는 부동 소수점 형식
 b가 64비트 일때 1비트는 여전히 부호이며, 11비트는 지수부, 52비트는 소수부(가수부)가 차지한다.
 8바이트를 사용하는 부동 소수점 형식

맨 앞자리 부호가 0일경우 127 이하, 1일 경우 128 이상
 01111111 127 (바이어스 127일 경우)
 10000000 128
 126일 경우 2^-1

정수,실수에서 정수는 0과 1만 올 수 있고, 실수는 23자리가 온다.
계산할때 0과 1일을 넘어설때 다시 되돌리는것을 정규화라고 한다. ( 예로 10이 되었다고 할때 1.0으로 바꾸고 2^n+1을 해준다.)

부동 소수점 형식의 표현
 피 연산자가 0인지 확인, 0이 아니면 2단계로 넘어감
 작은 지수를 갖는 피 연산자인 1.0101*2^2을 지수가 4가 되게 조절
 지수가 같으면 소수를 더함
 연산결과가 다음과 같은데 정규화가 되어있지 않음으로 정규화.
 10.001011*2^4 => 1.000101*2^5 (바이어스 = 127+5 = 132)
 IEEE 754 형식으로 나타내면 0 10000100 001010000 0000000000 000

문자 자료의 표현
 문자에 대한 이진수 코드를 정의하여 사용
 BCD 코드 (Binary-Coded Decimal code)
 EBCDIC 코드 (Extended Biary-Coded Decimal Interchange Code)
 ASCII 코드 (American Standard Code for Information Interchange) (미국 정보 교환용 표준 부호)

유니코드 (Unicode = Universal)
 EBCDIC 코드나 ASCII 코드는 최대 8비트로 숫자, 몇 가지 특수문자, 알파벳
 정의하므로 문자 코드 표에 정의되어 있지 않은 문자 표현 불가능 
 이런 문제 해결 위해 세계 여러 나라의 언어를 통일된 방법으로 표현할 수 있도록 정의한 국제 표준 코드(ISO/IEC 10646)
 2바이트를 조합하여 하나의 글자를 표현하기 때문에 1바이트 코드로 표현할 수 없었던 다양한 언어를 표현.
 일반화, 현재는 표현의 한계를 극복한 유니코드가 일반화
 XML, Java, CORBA 3.0, WML 등 인터넷 기반 프로그램과 제품에 사용

논리자료
 논리값을 표현하기 위한 자료형식
 참(Ture)과 거짓(False), 1과 0
 1바이트를 사용하여 논리자료를 표현하는 방법

방법 1)
 참 : 최하위 비트를 1로 표시 00000001
 거짓 : 최하위 비트를 0으로 표시 00000000

방법 2)
 참 : 전체 비트를 1로 표시 11111111
 거짓 : 전체 비트를 0으로 표시 00000000

방법 3)
 참 : 하나 이상의 비트를 1로 표시 00000001 or 00000100
 거짓 : 전체 비트를 0으로 표시 00000000

CUI(디렉토리) = dos
GUI(윈도우) = 폴더

포인터 자료
 메모리의 주소를 표현하기 위한 자료 형식
 변수의 주소나 메모리의 특정 위치에 대한 주소를 저장하고 주소연산을 하기위해 사용

문자열(String) 자료
 여러 문자로 이루어진 문자의 그룹을 하나의 자료로 취급하여 메모리에 연속적으로 저장하는 자료 형식

방법 1) 구분자를 사용하는 표현 : 구분자로 ; 사용
방법 2) 고정길이를 사용하는 표현
방법 3) 포인터를 사용하는 표현

뇌의 추상화 기능
 기억할 대상의 구별되는 특징만을 단순화하여 기억하는 기능

컴퓨터를 이용하는 문제 해결에서의 추상화
 크고 복잡한 문제를 단순화 시켜 쉽게 해결하기 위한 방법

자료 추상화
 처리할 자료, 연산, 자료형에 대한 추상화 표현

자료 : 프로그램의 처리 대상이 되는 모든 것을 의미
연산 : 어떤 일을 처리하는 과정 연산자에 의해 수행됨
자료형 : 처리할 자료의 집합과 자료에 대해 수행할 연산자의 집합

추상 자료형 (ADT, Abstract Data Type)
 자료와 연산자의 특성을 논리적으로 추상화하여 정의한 자료형

추상화와 구체화
 추상화 - "무엇(what)인가?"를 논리적으로 정의
 구체화 - "어떻게(how) 할 것인가?"를 실제적으로 표현

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


알고리즘의 조건
 입력(input) : 알고리즘 수행에 필요한 자료가 욉에서 입력으로 제공 될 수 있어야 한다.
 출력(output) : 알고리즘 수행 후 하나 이상의 결과를 출력해야 한다.
 명확성(definiteness) : 수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어들은 명확하게 명세 되어야 한다.
 유한성(finiteness) : 알고리즘은 수행 두에 반드시 종료되어야 한다.
 효과성(effectiveness) : 알고리즘의 모든 명령어들은 기본적이며 실행가능해야 한다.

알고리즘의 표현방법의 종료
 자연어를 이용한 서술적 표현방법
 순서도(Flow chart)를 이용한 도식화 표현방법
 프로그래밍 언어를 이용한 구체화 방법
 가상코드(Pseudo-code)를 이용한 추상화 방법

알고리즘 성능 분석 기준
 기준에는 정확성, 명확성, 수행량, 메모리 사용량, 최적성 등 있음
 정확성 : 올바른 자료 입력 시 유한한 시간 내에 올바른 결과 출력 여부
 명확성 : 알고리즘이 얼마나 이해하기 쉽고 명확하게 작성되었는가
 수행량 : 일반적인 연산 제외, 알고리즘 특성 나타내는 중요 연산 모두 분석
 메모리 사용량 
 최적성 : 가장 중요

알고리즘 성능 분석 방법
 공간 복잡도
  알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간의 양
  공간 복잡도 = 고정 공간 + 가변 공간 
  공간에 남은 부분을 단편화 라고 부름

 시간 복잡도
  알고리즘을 프로그램으로 실행하여 완료하기까지의 총 소요시간 
  시간 복잡도 = 컴파일 시간 + 실행 시간
  컴파일 시간 : 프로그램마다 거의 고정적인 시간 소요
  실행 시간 : 컴퓨터의 성능에 따라 달라질 수 있으므로 실제 실행시간 보다는 명령문의 실행 빈도수에 따라 계산
  지정문, 조건문, 반복문 내의 제어문과 반환문은 실행시간 차이가 거의 없으므로 하나의 단위시간을 갖는 기본 명령문으로 취급

알고리즘 성능 분석 표기법
 빅오 표기법 (big-O notation) 이란?
 빅오 표기법은 알고리즘의 효율성을 표기해주는 표기법이다. 
 알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다.
 빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용함.
 시간 복잡도는 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다.
 그런데 시간과 공간 복잡도를 나타내는 방법으로는 점근 표기법이라고 해서 빅오(Big-O), 빅오메가(big-Ω), 빅세타(big-Θ) 표기법이 있다.

빅 오의 자료구조 적용 예
 1. O(1) : 스택에서 Push, Pop
 2. O(log n) : 이진트리
 3. O(n) : for문
 4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬((heap sort)
 5. O(n^2) : 이중for문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
 6. O(2^n) : 피보나치 수열

배열(array)
 같은 자료형을 가진 자료들을 나열하여 메모리에 연속으로 저장하여 만든 자료들의 그룹
 인덱스index 
 배열의 요소를 간단히 구별하기 위해 사용하는 번호
 C에서 인덱스는 항상 0부터 시작 ★
 모든 자료형에 대해서 배열로 구성 가능
 구성 형태에 따라 1차원 배열, 2차원 배열, 3차원 배열, …

stdio.h = StanDard Input Output. Head의 약자
실행 (전)처리기

printf() => f=format

문자 배열
 “와 ”사이에 표시
 문자열을 저장하기 위해서는 문자열을 구성하는 문자들을 연속적으로 저장해야 하기 때문에 char형 배열을 사용
 배열의 자료형은 문자 자료형(char)
 문자 배열의 초기화는 문자열 그대로 지정하거나 초기 값 문자 리스트 사용
 문자 배열의 마지막은 \0으로 Null값이 들어간다.