Untitled

Fold the Video

알고리즘 (+ KMA lecture)

a process or set of rules to be followed in calculations or other problem-solving operations

+) 언어에 구애 x , 간단 명료

`모델 : 이론적인 원리에 근거한 실제 시스템의 서술`

실제 시스템 : 모델링의 대상이 되는 현실 세계의 시스템

모델 : 행위 데이터를 생성하는 명령어들의 집합

function ; method ; routine ; procedure

분리성 ; 구조적 프로그래밍 ; 용량 down ; 활용성 ; 캡슐화 ; 내부 구현과 함수의 기능 분리

<논리와 명제>

명제 : 참, 거짓 둘 중 하나로 구분가능. "상수화"

변수가 들어간 문장을 명제로 활용하기 위해서는 한정기호가 必

어떨 때 참, 어떨 땐 거짓 : 어떤 ; 존재한정

항상 : 모든 ; 전칭한정

공리 : 자명한 진리. 증명 必x

cf)

아날로그: 연속적

디지털: 비연속적

논리연산 ) a.k.a bool 연산 / T,F >> 진리값, 이들의 집합 >> 환

https://ko.wikipedia.org/wiki/%EB%85%BC%EB%A6%AC_%EC%97%B0%EC%82%B0

>>p가 조건/원인으로 제시되고,q가 결론/결과로 제시되는 명제

AND ; 하나라도 거짓이면 겆시

OR ; 하나만 참이면 참

XOR ; 같으면 거짓, 다르면 참 (0,1 뺀 것에 절댓값)

함축 ; 명제 자체에 의미가 없다! 결과만을 의미!

명제는T,F 중 하나로 반드시 판명나야!

전제가 거짓이면 결과에 상관없이 참!

p→q ≡ ~p∨q

> 동치 : 논리적으로 같음 ; 명제의 단순화를 가능케 하여 알고리즘 개선 및 검증에 유용

+) p∨F ≡ p

> 논리합에서 하나만 참이어도 참

> 따라서 p가 그대로 나옴!

명제함수)

논의영역

P(x)를 거짓으로 만드는 x = 반례

~(∀xP(x)) ≡ ∃x ~P(x)

절차적으로 실행되는 프로그램

제어문

선택문(조건문) ; select ; '맞다면 a하고, 아니면 b해라'

반복문 ; iterate

for > 정해진 횟수만큼

while > 정해진 조건 동안

자연어 기반 > 모든 언어 구조의 기반을 제공하는 역할

코딩의 명확성, 검토 용이, 코드 수정 용이, 자료관리, 프로그래머 外 '도'

특정 문법x, 논리에 집중!

조건문과 반복문을 통해 구조화

구성 : sequence / while / if-then-else / repeat-until / for / case / set / search / swap / increment

<증명>

: 어떤 알고리즘이 더 좋은지 증명하는데 활용

: 정리가 성립함을 논리적으로 증명

직접증명 : p 가정하고, q가 유효함을 증명

간접증명 : 결론 부정 > 모순되는 가정 발견 > 따라서 원래의 명제가 참

>> 직접증명이 불가능한 case

수학적 귀납법 : 연쇄적으로 증명

: n=1 직접증명 > n=k (1<k<n인 k 존재)된다면, n=k+1 가정부터 직접증명

> 결론까지 도달하여 n=k+1 만족 증명

수학적 체계)

공리 : 다른거 증명할 때 쓰임 ; no need to 증명

정의 : to make new 개념 > 용어 및 개념 정리 ; 합동

미정의 용어 : 기본 단위 ; 점, 선 등

정리 : p->q 형태의 명제

p가 참임을 가정 > 유효함을 증명

보조정리 : to 증명 큰정리

따름정리 : from 다른 증명, 증명 가능한 새로운 정리

<알고리즘 분석>

: 알고리즘은 성능에 많은 영향을 미친다

외적인 요소

하드웨어

프로그래밍언어

데이터 표현법 등

알고리즘의 시간복잡도

기준)

시간 측정 > 실효성

작업 수행

공간 측정 > 소모할 자원의 양

메모리 용량

하드디스크가 비교적 단위용량이 크고 가격이 쌈

따라서 저장공간의 문제는 알고리즘 분석에 미비한 영향

방법)

> code 기반으로, 대략적인 실행시간 추론!

> 기초 연산, 할당, 변수 및 인덱스 접근, 비교 등 일정한 시간 소모(상수)

> 중요한 기준 : 입력값이라는 변수 ! 입력에 따른 데이터처리가 알고리즘에 의해 일어나는 것.

실행시간 분석 : Run-time analysis

직접 코드를 짜서 시간 측정

경험적 방식 <-> 이론 및 수학적 기준

같은 성능이 아니면, 비교 불가

입력 데이터의 크기에 따라 언제나 역전가능!

성능의 외적 요소에 종속적

코딩, 즉 프로그래밍이라는 구현을 수행 : 인력+시간 = 비용소모 불가피

입력값에 따라 결과 천차만별 > 실행시간 차이!

어떤 입력값이 올지는 예측 x

알고리즘 분석은 정확한 분석이 아니라, 점근적 분석임. n이라는 변수에 종속적

"알고리즘 평가 != 구현된 프로그램 평가"

알고리즘 분석 case

최악의 경우 : 가장 많이 이용

최선의 경우 : 의미 x, 얻을 수 있는 정보 한정적

평균의 경우 : 실제 적용에 있어 어려움, 입력을 모르므로 현실적으로 못구함

<점근적 분석의 표기법>

점근적 상한 : f(n)은 시간이 아무리 걸려도 O(n) 보다 적음

O(Big Oh) Notation

점근적 하한 : f(n)은 적어도 Ω(n)의 시간이 걸림

Ω(Big Omega) Notation

절충하는 표기법 : f(n)은 대략 Θ(n)만큼 시간이 걸림

Θ(Big Theta) Notation

Big-O : 알고리즘의 시간 복잡도의 상한선 (적어도 실제시간이 얘보다 크지 않음)

>> 시간이 지날수록 편차가 매우 커지고, 이러한 추세가 유지

>> 적어도 이 지점부터는 경향성 유지 100%

>> 어느 시점부터 (g>f) ; 여기서의 g를 찾는게 목적!

>> 최악의 점근적 해석 : upper - bound 표현

완벽한 수치 x , 상수(선형변화)(계수) ㅗ

점근적 표기법 : 비중요 항목 제거

로그의 밑도 일종의 계수-상수

낮은 차수의 영향은 적음.

최고차항을 이끌어내자!

그래프로 판단하자!

표기법)

Big-Omega)

Big-theta)

> 상한과 하한은 여러개 존재!

>> 상한과 하한을 모두 만족시키는 것 = 근삿값 = big theta

** 상한, 하한, 근사치의 개념을 혼동하지 말 것 >> 정의를 기준으로 판단!

자주하는 실수 : Θ(f(n))를 의미할 때, 대신 O(f(n))를 사용

tight bound(세타)를 표현할 때, 종종 O(...)를 사용

예를 들어 f(n)=n 일 때,

f(n)은 O(n) 이지만, 이는 upper-bound만을 의미함.

O(n)이 항상 Θ(n)로 표현될 수 있는것은 아님.

( g(n)이 같더라도, 각 표기법이 의미하는 바가 다르다는 것 )

: 10마리의 비둘기가 9개의 비둘기 집에 모두 들어갔다면, 적어도 하나 이상의 비둘기 집에는 2마리 이상의 비둘기가 들어가 있다.

활용)

주어진 특성을 가진 항목의 존재여부'만'

얼마나 있는지, 어떻게 찾는지는 알려주지 않음

Form)

만약 n마리의 비둘기가 k개의 비둘기집에 날아 들어가고 n>k 라면, 어떤 비둘기집은 최소 두마리의 비둘기가 들어가 있다.

비둘기와 비둘기 집으로 분류해야 응용가능

f가 유한집합 X에서 유한집합 Y로의 함수이고, |X| > |Y|라고 할 때, x1,x2 ∊ X이고, x1≠x2이면서 f(x1) = f(x2)가 되도록 하는 x1,x2가 반드시 존재한다.

(1대1대응이 아닌, 함수값이 동등한 서로 다른 x)

재귀(기말)

자기 자신(함수)를 이용

반복문 無

매개변수-패러미터에 변화 (n / n-1)를 줘서 함수 호출 >> 종료될 때 까지(보통 첫 조건문에 등장)

(얘가 없으면 무한,,얘부터 파악하자)

(전제 파트)

매 호출시마다 매개변수-입력값-패러미터 변화!

-> keep 호출 & 마지막에 호출이 멈춰지는 부분(주로 첫 조건문)에서부터 함수의 내용 시행

유클리드 알고리즘

: 두 정수 간의 최대공약수(Greatest Common Divisor)를 구하기 위한 효과적인 알고리즘

gcd(a, b) = gcd(b, a mod b ;나머지)

Example

a = 105, b = 30

gcd(105, 30) = gcd(30,105 mod 30) = gcd(30, 15) = gcd(15, 30 mod 15) = gcd(15, 0)

gcd(15, 0) = 15 >> 더이상"최대" 안나눠질때"공약수" 까지! (b=0이 될 때 까지)

∴gcd(105,30) = 15

<좌항이 참이면 우항도 참, 우항이 참이면 좌항도 참임을 보인다>

** 0으로 나눌수는 없어도, 0을 나눌 수는 있다

** a=0(o) b=0(x)

1. 단사 함수(One-to-one fuctions) : 1대1 함수 (!= 대응;공역=치역)

>> f(x1) != f(x2) 이면 x1 != x2 (역도 성립)

2. 전사 함수(Onto functions) : 공역 = 치역

>> 공역의 모든 원소가 정의역에 모든 원소와 대응이 되는가

3. 전단사 함수(Bijective functions) : 1대1 대응

>> 관계는 부분집합이다! / 데카르트곱은 모든 순서쌍의 집합

>> 쌍방과 단방

1. 반복(iteration)

주로 단항

(n과 관련된 항)

2.

상계수 선형 동차 점화 관계(linear homogeneous recurrence relations with constant coefficients)

주로 다항

<풀이법: 2차일때>

Last Updated:

Summarize & share videos seamlessly