1 자료 구조와 알고리즘
1.1 자료와 정보
- 자료
- 현실 세계에서 관찰이나 측정을 통해 수집된 값이나 사실
- 정보
- 어떤 상황에 대해서 적절한 의사결정을 할 수 있게 하는 지식
- 자료를 처리해서 얻어진 결과
- 수식 : I = P(D)
- I : 정보
- P : 처리
- D : 자료
- 자료 처리
- 자료 자체가 내포하고 있는 자료 상호 간의 관계에서 어떤 정보를 추출(처리)한다는 것
- 정확성과 현재성이 확보 되어야 한다.
1.2 알고리즘
# 유용한 정보 얻기 위한 방법
1) 처리하고자 하는 문제를 정확히 분석
2) 그 분석에 따라 자료를 기억 공간에 어떻게 표현하고 저장할 것인가 하는 자료 구조를 결정
3) 이러한 자료 구조를 사용하여 유용한 정보를 얻기 위해 자료를 어떻게 변환할 것인가 하는 알고리즘, 즉 프로그램을 기술해야 한다.
# 정의
알고리즘이란 특정한 일을 수행하는 명령어들의 유한 집합이다.
특정 문제를 해결하기 위해 논리적으로 기술해 놓은 일련의 명령문.
# 알고리즘의 조건
1) 입력 : 외부에서 제공되는 자료가 있을 수 있다.
2) 출력 : 적어도 한 가지 결과를 생성한다.
3) 명확성 : 각 명령어들은 명확하고, 모호하지 않아야 한다.
4) 유한성 : 알고리즘의 명령대로 수행하면, 어떤 경우에도 한정된 수의 단계 뒤에는 반드시 종료한다.
5) 유효성 : 기본적으로 모든 명령들은 종이와 연필만으로 수행될 수 있어야 한다. 알고리즘은 각 연산이 명확해서만은 안 되고 반드시 실행 가능해야 한다.
2. 단순 자료
2.1 정수형 자료
- 10진법 : 인간이 사용하는 수의 체계
- 2진법 : 컴퓨터내에서 사용하는 수의 체계
- 8진법/16진법 : 컴퓨터 내에 자료를 출력하여 프로그래머가 분석할 때 사용
- 일반적으로 32비트를 필요로 함
# 고정소수점
- 부호부 : 최상위 비트(왼쪽) 1비트에부호를 나타냄
- 정수부 : 나머지 31비트에 10진 정수를 2진수로 변환하여 표현.
2.2 실수형 자료
- 일반적으로 32비트의 저장 공간을 필요로 함.
- 부호부 : 최상위 비트(왼쪽) 1비트에 부호를 나타냄. 0은 양수, 1은 음수.
- 지수부 : 7비트(1에서 7까지)는 지수를 나타냄.
- 가수부 : 나머지 24비트(8에서 31까지)에는 16진수로 변환한 6자리의 수를 표현.
2.3 문자형 자료
- 문자를 저장하기 위한 자료형
- 영문은 1바이트를, 한글은 2바이트 완성형과 2바이트 국제 문자 코드 혼용하여 사용.
- 컴퓨터 내부 저장 공간에는 문자료 저장되는 것이 아니라 ASCII 코드로 저장된다.
# ASCII 코드
- 8비트로 구성된 코드
2.4 논리형 자료
- 값이 참(True, 1) 또는 거짓(false, 0)을 나타내는 것.
# 논리 연산자의 종류
- && (AND)
- | (OR)
- ! (NOT)
2.5 포인터형 자료
- 자료를 저장할 수 있는 저장 장소의 위치를 나타내는 주소값(주소는 1바이트).
- 이 주소를 포인터라 한다.
- & : 주소 연산자. 변수 i 앞에 붙여서 &i와 같이 기술하면 그 변수 i의 주소값이 반환된다.
- * : 포인터 변수 *는 변수에 주소값을 저장한다. 변수 i 앞에 포인터변수 *를 붙이면 된다.
- 포인터 값을 표현할 때 프로그래머는 10진수를 사용하지만 시스템은 기본적으로 16진수를 사용한다.
# C언어에서 포인터에 수행할 수 있는 또다른 연산
1) 한 포인터가 다른 저장 공간을 가리킬 수 있도록 설정할 수 있다.
2) 사칙연산( +, -, ×, ÷ )이 가능하다.
3) 포인터들의 크기를 비교할 수 있다.
4) 널 포인터(NULL)를 들 수 있다.
3. 추상 자료형
- 자료 추상화 : 복잡한 관계를 가진 자료에 대해 먼저 추상화 개념을 적용하여 단순화시킨 다음 문제 해결 방법을 찾는 것
- 자료 : 프로그램의 처리 대상이 되는 모든 것
- 타입(type) : 어느 한 부류에 속하는 값들의 집합
- 연산 : 어떤 일을 달성하는 과정. 보통은 연산자로 표현.
- 자료형 : 타입과 연산자의 집합으로 구성. 즉, 자료의 집합과 이 자료에 적용할 수 있는 연산의 집합을 말한다.
- 시스템 정의 자료형 : 시스템에서 직접 정의하여 제공
- 원시 자료형 : 원자값만을 원소로 갖는다. 더이상 분해할 수 없다.
- 단순 자료형
- 복합 자료형 : 자료형 속에 또 다른 잘형을 원소로 가질 수 있다.
- 구조화 자료형 : 처리를 위해 다시 분해할 수 있다.
- 사용자 정의 자료형 : 사용자가 필요에 따라 정의하여 사용
- 추상 자료형 : 자료의 표현이나 연산의 구현은 제외하고 자료와 연산의 본질에 대한 명세만 정의한 자료형.
- 사용자 정의 자료형을 총칭한다고 말할 수 있다.
- 추상 자료형을 기초로 자료를 기술하고, 알고리즘을 개발하면, 그 과정이 매우 단순해지고, 통제하기가 용이해지는 이점이 있다.
- 자료 구조 : 문제 해결을 위해 자료값들을 연산자들이 효율적으로 접근하여 처리할 수 있도록 체계적으로 조직하여 표현하는 것.
- 프로그램 = 자료 구조 + 알고리즘
- 추상 자료형은 연간의 기능이 무엇이라는 것에만 중점을 두고 명세를 하는 것이지, 어떻게 수행하느냐 하는 내부 구현은 명세에 포함시키지 않는다.
4. 순환 알고리즘
- 직접 순환 : 프로그램에서 함수가 직접 자신을 호출
- 간접 순환 : 다른 제 3의 함수를 호출하고 그 함수가 다시 자신을 호출
- 순환 : 풀기 어려운 문제에 대하여 간단하면서도 세련된 해결책을 만드는 데 사용. 문제를 간단하면서도 엄밀하게 정의하는 데도 사용.
- 순환 방식
- 분할 정복의 특성을 가진 문제에 적합.
- 어떤 복잡한 문제를 직접 간단하게 풀 수 있는 작은 문제로 불할하여 해결하려는 방법.
5. 알고리즘의 성능 문석
- 성능 분석
- 프로그램을 실행하는데 필요한 시간과 공간 추정
- 성능 측정
- 컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간 측정
5.1 공간 복잡도
- 프로그램을 실행시켜 완료하는 데 필요한 총 저장 공간을 말함.
- Sp = Sc + Se
- 고정공간(Sc) + 가변공간(Se)
- 고정공간 Sc : 고정적으로 필요한 저장 공간
- 가변공간 Se : 자료 구조와 변수들이 필요로하는 저장 공간
5.2 시간 복잡도
- 프로그램을 실행시켜 완료하는데 걸리는 시간.
- Tp = Tc + Te
- Tc : 컴파일 시간
- Te : 실행 시간
5.3 연산 시간 표기법 (Ο, Ω, θ)
- Big-Oh (Ο), Big-Omega (Ω), Big-Theta (θ)