on
알고리즘 수업 1주차 - ADL 작성연습, 복잡도, 순환과 점화식
알고리즘 수업 1주차 - ADL 작성연습, 복잡도, 순환과 점화식
ADL(Algorithm Description Language)
- 알고리즘 기술을 위해 정의한 언어
- 사람이 이해하기 쉽고, 프로그래밍 언어로의 변환이 용이
- 의사 코드(pseudo-code): ADL과 약간의 자연어로 기술한 것
- ADL 알고리즘에서 프로그램으로의 변환: ADL 알고리즘 -> ADL 변환기 -> C언어, Java, 파이썬 프로그램 등
ADL 설계 및 파이썬 코드 작성 연습
* 자연수 a,b의 최대공약수 g를 구하는 함수 gcd(a,b)
gcd(a, b)
i <- 1 ;
while ( i <= a and i<= b ) do {
if ( (a mod i = 0) and (b mod i = 0) )
then g <- i ;
i <- i+1 ;
}
return g ;
end gcd()
def gcd(a, b): i = 1 while i <= a and i <= b: if a % i == 0 and b % i == 0: g = i i += 1 return g A = int(input('a = ')) B = int(input('b = ')) print('최대공약수 :', gcd(A, B))
* 자연수 a가 소수이면 True, 아니면 False를 반환하는 함수 isPrime(a)
isPrime(a)
i <- 2 ;
while ( i <= a/2 ) do {
if ( a mod i = 0 )
then return false ;
i <- i+1 ;
}
return true ;
end isPrime()
def isPrime(a): i = 2 while i <= a/2: if a % i == 0: return False i += 1 return True A = int(input('a = ')) if isPrime(A): print('소수입니다.') else: print('소수가 아닙니다.')
* 자연수 a가 완전수이면 True, 아니면 False를 반환하는 함수 isPerfect(a)
isPerfect(a)
s <- 0 ;
i <- 1 ;
while ( i <= a/2 ) do {
if ( a mod i = 0 ) then s <- s+i ;
i <- i+1 ;
}
if ( s = a )
then return true;
else retrurn false;
end isPerfect()
def isPerfect(a): s = 0 i = 1 while i <= a/2: if a % i == 0: s += i i += 1 if s == a: return True else: return False A = int(input('a = ')) if isPerfect(A): print('완전수입니다.') else: print('완전수가 아닙니다.')
* 문자열 s가 회문이면 True, 아니면 False를 반환하는 함수 isPalindrome(s)
isPalindrome(s)
i <- 0 ;
j <- s의 길이 - 1 ;
while ( i < j ) do {
if ( s[i] ≠ s[j] )
then return false ;
i <- i+1 ;
j <- j-1 ;
}
return true;
end isPalindrome()
def isPalindrome(s): i = 0 j = len(s) - 1 while i < j: if s[i] != s[j]: return False i += 1 j -= 1 return True S = input('S = ') if isPalindrome(S): print('회문입니다.') else: print('회문이 아닙니다.')
* 에라토스테네스의 체를 이용한 소수 여부 판별 함수 eratos(a[], n)
eratos(a[], n)
a[1] <- 0 ;
i <- 2 ;
while ( i <= n/2 ) do {
j <- 2 ;
while ( i * j <= n ) do {
a[i * j] <- 0;
j <- j+1;
}
i <- i+1 ;
}
return a ;
end eratos()
def eratos(a, n): a[1] = 0 i = 2 while i <= n/2: j = 2 while i*j <= n: a[i*j] = 0 j += 1 i += 1 return a N = int(input('N = ')) A = list(range(N+1)) res = eratos(A, N) for i in range(N+1): if res[i]: print(res[i], end=' ')
알고리즘 성능 분석/측정
1. 공간 복잡도: 과거에는 중요했지만, 지금은 뭐..
2. 시간 복잡도: 얼마나 시간이 걸리나? (Big-Oh, Big-Omega, Big-Theta)
- 연산 시간의 순서 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)
순환 함수
예) 이진 탐색 알고리즘
binarySearch(a[], ket, left, right)
// a[mid] = key인 인덱스 mid를 반환
if (left <= right) then {
mid <- (left + right) / 2 ;
case {
key = a[mid] : return mid ;
key < a[mid] : return binarySearch(a, key, left, mid-1) ;
key > a[mid] : return binarySearch(a, key, mid+1, right) ;
}
}
else return -1 ; // key 값이 존재하지 않음
end binarySearch()
점화식
-> 순환이 한 번 반복될 때마다 입력 원소의 개수가 하나씩 감소하게 되고, 처리해야하는 원소는 N부터 시작하여 하나씩 감소하는 알고리즘을 표현.
-> 순환이 한 번 반복될 때마다 입력 원소의 개수가 절반인 1/2로 감소하게 되고, 매 순환시마다 하나의 원소를 처리하는 알고리즘을 표현.
-> 순환이 한 번 반복될 때마다 입력 원소의 개수가 절반인 1/2로 감소하게 되고, 처리해야 하는 원소는 N부터 시작하여 절반으로 감소하는 알고리즘을 표현.
-> 순환이 한 번 반복될 때마다 입력 원소의 개수가 절반인 1/2로 감소하게 되고, 왼쪽 절반과 오른쪽 절반을 모두 처리하면서 매 순환시마다 하나의 원소를 처리하는 알고리즘을 표현.
-> 순환이 한 번 반복될 때마다 입력 원소의 개수가 절반인 1/2로 감소하게 되고, 처리해야 하는 원소는 N부터 시작하여 절반으로 감소하면서 왼쪽 절반과 오른쪽 절반을 모두 처리해야하는 알고리즘을 표현.
반응형
from http://sweaterman.tistory.com/84 by ccl(A) rewrite - 2021-09-09 22:27:27