# Computer System
- 소프트웨어(알고리즘과 데이터)와 하드웨어
* 알고리즘: 문제를 해결하기 위한 절차들
데이터: 측정한 값들의 집합
# Definition
- 자료구조(Data Structures)란?
문제를 해결하기 위해 대량의 데이터를 효율적으로 처리하고 구성하는 방법 또는 구조
- 선형(리스트, 스택, 큐, 데큐) / 비선형(트리, 그래프) / 고급DS(BST, Weight networks)
/ 탐색, 정렬, 해싱 알고리즘 등을 배운다.
# Algorithm
- 특정 작업을 수행하기 위한 유한한 명령의 집합
- Criteria <알고리즘의 조건>
a. Input(입력): 명시적 입력(키보드, 파일 등)은 필요x (*묵시적 입력: 코드 상에서 주어지는 범위)
b. Output(출력): 적어도 하나 이상의 출력 필요
c. Definiteness(명확성): 구체적이고 모호하지 않아야 함
d. Finiteness(유한성): 유한한 수의 명령어. 프로그램이 종료되어야 함
e. Effectiveness(효과성): 불필요한 명령어 없이, 효율적으로
- Description <표현>
의사코드(pseudo code), 플로우 차트(flow chart) *flow chart는 복잡할 경우 나열하기 힘듦. 간단한 알고리즘에 사용!
자연어, 프로그래밍 언어
# System Life Cycle
1. 요구사항(requirement): 개발하려는 소프트웨어의 목표 정의
사용 환경(platform), 기능(function), 입출력, 사용자 인터페이스(interface) 등
2. 분석(analysis): 구체적인 세부 문제들로 분할
- Devide and Conquer strategy <쪼개서 정복하는 전략>
Top-down approach(하향식): 프로그램-> 서브루틴 -> 명령어
Bottom-up approach(상향식): 하향식의 반대.
3. 설계(design): 각 모듈에 대한 객체와 함수 정의
4. 구현(implementation): 객체와 알고리즘을 실행가능한 코드로 만드는 코딩 과정
5. 검증(verification): 오류가 없는지 확인
- Program test
Black-box test (내부는 x) & White-box test (내부까지 o)
# Fibonacci Numbers
# Prime Numbers 소수 찾기
# Data Types
Built-in data types(내장형) / Abstract data type(추상 자료형)
# Abstract Data Type (ADT) 추상자료형
- Object data type = 객체
속성(attributes, 멤버 변수)과 메소드(methods, 멤버 함수)
ex) 학생(틀)~ object, 홍길동(개별화)~ instance
- OOPL(Object Orient Programming Language) 예
: C++, C#, Java, Python
# Fraction 분수 (ADT 예제) * 컴퓨터는 정수, 실수(소수) 연산만 가능. 분수의 연산을 위해서는 별도의 처리를 해주어야 함.
- Numerator(분자), Denominator(분모)
- Addition, Multiplication, DecToFraction, Abbreviation (gcd(x,y))
# Performance Analysis 성능평가
- Qualitative Criteria 정성적 분석
- Quantitative Criteria 정량적 분석
ㄴ Space complexity 공간복잡도: 프로그램이 실행을 완료하는 데 필요한 메모리 사이즈
ㄴ Time complexity 시간복잡도: 프로그램이 실행을 완료하는 데 걸리는 시간
참고 <알고리즘 복잡도 계산이 필요한 이유?>
: 하나의 문제를 푸는 알고리즘은 다양할 수 있다.
이때, 다양한 알고리즘 중 어떤 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산하게 된다.
# Space complexity 공간복잡도
S = Sc +Sv // 고정은 무시하고 가변만 고려!
- 배열처리 방식 (크게 2가지)
◎ call by value * 비효율적이므로 최근 언어들은 이 방법을 잘 쓰지 x
- 배열 요소가 기능에 복사됨
- 배열 사이즈에 비례하여 추가 메모리 공간이 필요
- Sv(sum) = n
◎ call by reference * 원본 이외에 추가적 필요 x => Sv=0
- 배열의 기본 주소가 함수에 전달됨
- 추가 메모리 공간 필요 없음
- Sv(sum) = 0
# Time complexity 시간복잡도
T = Tc +Te // 컴파일 타임은 안전하기에, 실행 시간만 고려하면 됨!
- 실행시간(Execution time)은 컴퓨터 환경에 따라 변화하기에, 물리적 시간을 재는 것은 의미가 없다.
=> 따라서, 명령어의 갯수를 센다!
<표 작성하기>
Steps * Frequency = Total steps
- 알고리즘 시간 복잡도의 주요 요소는 반복문이다!
(입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행 시간을 지배함)
<알고리즘 성능 표기법 3가지> "시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 익히면 된다"
# Big O(빅-오) Notatio: n이 매우 커질 경우 최고차항만 표기!
- 최악의 실행 시간을 표기 (적어도 이것보단 빠르다!)
- 가장 많이/일반적으로 사용함
- 아무리 최악의 상황이더라도, 이 정도의 성능은 보장한다는 의미.
- 점근적 상한선
※<주의> 빨리 증가한다 ≠ 수행시간이 빠르다 (반대 개념!)
ex) O(n^2) 와 O(n) 중 빠른 건 O(n)이고, 수행시간이 긴 건 O(n^2)
"Big-O Notation은 상한선 의미" ~ 이것보다는 적게 걸린다.
- 주어진 함수 f(n)은 n0보다 큰 범위에서 c*g(n)보다 작다. => 상한선 존재 시, Big-O로 표기 가능.
EX.
f(n) = n^2 + n ≤ n^2 + n^2 = 2n^2 ≤ 2g(n) = O(n^2)
f(n) = 2n2 + n ≤ 2n^2 + n^2 = 3n^2 ≤ 3g(n) = O(n^2)
~ c와 n0 구해라. 하지만, 답은 여러 개일 수도 있다. 이때는 f(n)과 좀 더 가까운 것이 좋다.(물론 애매한 경우도 O)
예를 들어, 위 슬라이드의 4번째 예시처럼 3n^2와 4n 둘 다 가능한 예제가 있다. 이 경우, 그래프를 그려 둘 중 어떤 것이
f(n)과 가까운 지 판단하면 된다.
# Big-Omega(오메가 Ω) Notation: 하한선 ~ 적어도 이 이상은 걸린다.
- 알고리즘 최상의 실행 시간을 표기
- 점근적 하한선
# Big-Theta(세타 Θ) Notation
: 아래 그래프와 같이 상한선, 하한선을 구해,
f(n)은 상한선보다는 적게, 하한선보다는 많은 시간이 걸린다고 표현할 수 있다.
- 알고리즘 평균 실행 시간을 표기
- 점근적 상한선과 점근적 하한선의 교집합
# Time complexity Class
<O 표기법>
: O(1) < O(logn) < O(n) < O(n) < O() < O() < O(n!)
* 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있다.
'CS > 자료구조' 카테고리의 다른 글
| Data Structures 2. Python Data Type (0) | 2022.12.29 |
|---|