[SOS CLASS] 자료구조기초 - 2차시

 

---

✅ 오늘의 진도

1. 알고리즘

- 알고리즘의 이해

- 알고리즘의 표현 방법

- 알고리즘의 예

 

2. 시간 복잡도

- 빅-오 표기법

- 빅-세타 표기법

- 빅-오메가 표기법

 

3. 배열

- 일차원 배열

- 다차원 배열

- 배열과 포인터

 

4. 포인터

- 포인터와 주소

- 포인터 연산

---

 ✅ 알고리즘

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

---

✅ 알고리즘의 조건

1. 입력(input)

: 알고리즘 수행에 필요한 자료가 외부에서 입력으로 제공될 수 있어야 한다. 

2. 출력(output)

: 알고리즘 수행 후 하나 이상의 결과를 출력해야 한다. 

3. 명확성(definiteness)

: 수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어들은 명확하게 명세되어야 한다.

4. 유한성(finiteness)

: 알고리즘은 수행 뒤에 반드시 종료되어야 한다.

 
5. 효과성(effectiveness)

: 알고리즘의 모든 명령어들은 기본적이며 실행이 가능해야 한다. 

---

✅ 알고리즘의 표현 방법

1. 자연어를 이용한 서술적 방법

 

2. 순서도(Flow chart)를 이용한 도식화 표현 방법

ex) 1 ~ 5까지의 합을 구하는 알고리즘

 

3. 가상코드(Pseudo-code)를 이용한 추상화 방법

1) 가상코드 = 알고리즘 기술언어 (ADL, Algorithm Description Language) 를 사용

2) 프로그래밍 언어의 일반적인 형태와 유사하게 알고리즘 표현
3) 특정 프로그래밍 언어가 아니므로 직접 실행은 불가능 (But, 프로그래밍 언어로의 변환 용이!)

 

⚡ 가상코드의 형식

- 기본요소

1) 기호୎
− 변수, 자료형 이름, 프로그램 이름,  레코드 필드 명, 문장의 레이블 등
− 문자나 숫자의 조합 (문자는 반드시 영문자)
2) 자료형
− 정수형과 실수형의 수치 자료형, 문자형, 논리형, 포인터, 문자열 등의 모든 자료형
3) 연산자
− 산술연산자, 관계연산자, 논리연산자

 

- 지정문 형식과 예

1) 형식변수 ⬅ 값

 

2) 예시a ⬅ 5a ⬅ 3 + 2a ⬅ b

 

4. 프로그래밍 언어를 이용한 구체화 방법 

---

✅ 알고리즘 표현 방법 (2)

⚡ 조건문

조건에 따라 실행할 명령문이 결정되는 선택적 제어구조

 

1) 단일 if문

조건식이 참이면 명령문 1 실행

거짓이면 명령문 2 실행

if (조건식) then 명령문 1;
else 명령문 2;

조건식이 참이면 명령문 1 실행

if (조건식) then 명령문 1;

 

2) 중첩 if 문

조건식 1이라면 명령문 1 실행

조건식 1이 아니고, 동시에 조건식 2라면 명령문 2 실행

조건식 1과 2가 모두 아니라면 명령문 3 실행

if(조건식 1) then 명령문 1;
else if (조건식 2) then 명령문 2;
else 명령문 3;

 

3) case 문

case{
    조건식 1 : 명령문 1;
    조건식 2 : 명령문 2;
    ...
    조건식 n : 명령문 n;
    else : 명령문 n+1;
}

 

⚡ 반복문

일정한 명령을 반복 수행하는 루프(loop) 형태의 제어구조

 

1) for 문

- 초깃값 : 반복문을 시작하는 값

- 조건식 : 반복 수행 여부를 검사하는 식

- 증감값 : 반복 횟수를 계산하기 위해 반복문을 한번 수행할 때마다 증감시키는 값

for (초깃값; 조건식; 증감값) do 명령문;

 

2) while-do 문

조건식이 참이면 명령문 실행

while (조건식) do 명령문;

 

3) do-while문

조건식과 관계없이 명령문을 일단 한번 실행한 후,

조건식이 맞으면 계속해서 실행

do 명령문;
while (조건식);

---

✅ 알고리즘의 성능분석

⚡ 알고리즘 성능 분석 기준

1. 정확성 : 올바른 자료 입력 시 유한한 시간 내에 올바른 결과 출력 여부
2. 명확성 : 알고리즘이 얼마나 이해하기 쉽고 명확하게 작성되었는가?
3. 수행량 : 일반적인 연산은 제외, 알고리즘의 특성을 나타내는 중요 연산을 모두 분석
4. 메모리 사용량 : 명령어, 변수, 입출력 자료와 정보 저장
5 최적성 : 시스템의 사용 환경과 요구 사항이 다르므로 조건에 맞는 최적의 알고리즘 필요

 

⚡ 알고리즘 성능 분석 방법

1. 공간 복잡도

- 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간의 양

- 공간복잡도 = 고정 공간 + 가변 공간

 

2. 시간 복잡도
- 알고리즘을 프로그램으로 실행하여 완료하기까지의 총 소요시간
- 시간 복잡도 = 컴파일 시간 + 실행 시간
1) 컴파일 시간 : 프로그램마다 거의 고정적인 시간 소요
2) 실행 시간 : 실제 실행시간 보다는 명령문의 실행 빈도수에 따라 계산

 

- 실행 빈도수의 계산
: 하나의 단위시간을 갖는 기본 명령문으로 취급

 

⚡ 시간 복잡도 계산

ex) 피보나치 수열

행 번호	실행 빈도수	행 번호	실행 빈도수
1	1	8	n-1
2	X	9	n-1
3	1	10	n-1
4	X	11	X
5	1	12	1
6	1	13	X
7	n

 총 실행 빈도 수 = 1+1+1+1+n+n-1+n-1+n-1+1 = 4n+2

---

✅ 알고리즘 성능 분석 표기법

⚡ 빅-오 표기법

: 함수의 상한을 나타내기 위한 표기법 (아무리 늦어도 이 안에는 끝난다!!)

 

1. 수학적 정의
: 함수 f(n)이 주어졌을 때, 모든 n≥ n0에 대하여 |f(n)| ≤ c |g(n)|을 만족하는 상수 c와 n0이 존재하면,

f(n) = O(g(n))이다.

 

2. 빅-오 구하는 방법

1) 실행 빈도수를 구하여 실행 시간 함수를 찾기

2. 이 함수값에 가장 큰 영향을 주는 n에 대한 항을 한 개 선택

3. 계수는 생략하고 O의 오른쪽 괄호 안에 표시

ex) 피보나치 수열의 경우 4n이지만, 4를 생략하여 O(n)으로 표시함

 

3. 빅-오 표기법의 예

1) f(n) = 3n + 2 = ?
(since 3n + 2 <= 4n for n > = 2)

n=1?
5 <= 4 (X)

n=2?
8 <= 8 (O)

c: 4, n0: 2, f(n) = O(n)

2) f(n) = 10n^2 + 4n + 2 = ?
(since 10n2 + 4n + 2 <= 11n^2 for n >= 5)

n=1?
16 <= 11 (X)

n=2?
50 <= 44 (X)
...
n = 5?
272 <= 275 (O)

c: 11, n0: 5, f(n) = O(n^2)

 

⚡빅 - 오메가 표기법

: 함수의 하한을 나타내기 위한 표기법 ( Ω(f(n))과 같이 표기 )

 

1. 수학적 정의
: 함수 f(n)이 주어졌을 때, 모든 n≥ n0에 대하여 |f(n)| ≥ c |g(n)|을 만족하는 상수 c와 n0이 존재하면,

f(n) =  Ω(g(n))이다.

 

⚡빅 - 세타 표기법

: 상한과 하한이 같은 정확한 차수를 표현하기 위한 표기법 ( θ(f(n))과 같이 표기 )

 

1. 수학적 정의
: 함수 f(n)이 주어졌을 때, 모든 n≥ n0에 대하여 c1|g(n)| ≤ f(n) ≤ c2|g(n)을 만족하는

상수 c1, c2와 n0이 존재하면,  f(n) = θ(g(n))이다.

 

📛 시간 복잡도를 정확히 계산할 수 있다면 '빅 - 세타' 사용

📛 시간 복잡도를 정확히 계사할 수 없다면 '빅 - 오' 사용

---

✅ 오늘의 과제

SOS CLASS 자료구조기초 - 2차시 과제.hwp

0.04MB

SOS CLASS 자료구조기초 - 1차시 답지.hwp

0.03MB