★ 「2019학년도 1학기」 수/업/노/트 ★
by. 동동매니저 >_<
▶ 일자 : 2019년 03월 13일 (수)
▶ 과목 : 이산수학 연습
▶ 담당 교수님 : SCH 박진수 교수님
※ 이번 수업의 핵심 키워드!!
알고리즘
시간 복잡도
빅오 표기법
※ 수업 내용을 요약해보면?
– 하노이 탑 원판 개수 별 이동 횟수
▶ P(1) = 1
▶ P(2) = 2P(1)+1 = 3
▶ P(3) = 2P(2)+1 = 7
...
▶ P(n) = 2P(n-1)+1 = 2n-1
☆ 알고리즘의 특성
▶ 입력 : 문제 해결을 위한 입력이 필요함.
▶ 출력 : 문제 해결의 답이 있어야 함.
▶ 유한성 : 유한 번 조작 후 반드시!! 끝내야 함. (무한 루프 금지!!)
▶ 확정성(명확성) : 일의적으로 규정돼야 함.
▶ 실제성(효율성) : 실제적이고 정확해야 함.
☆ 시간 복잡도의 종류 (빅오 표기법, 아래로 갈수록 비효율적)
▶ O(1) : 상수형, 입력 크기에 관계 없이 항상 일정한 수행 시간은 가짐.
▶ O(logn) : 로그형
▶ O(n) : 선형
▶ O(nlogn)
▶ O(n2) : 2차
▶ O(n3) : 3차
▶ O(2n) : 지수형
☆ 알고리즘의 시간 복잡도 직접 구해보기!!
(func 함수 기준입니다. 편의상 main 함수는 생략합니다.)
★ 알고리즘 1
void func(int n)
{
int i=0;
while(i<n) i=i+1;
}▶ 반복 횟수 = n 이므로, O(n)
★ 알고리즘 2
void func(int n)
{
int i=0;
while(i<n) i=i+3;
}▶ 반복 횟수 = n/3 이므로, O(n)
★ 알고리즘 3
void func(int n)
{
int sum=0;
int i,j;
for(i=0;i<n;i++) for(j=0;j<n;j++) sum=sum+i*j;
}▶ 반복 횟수 = n*n 이므로, O(n2)
★ 알고리즘 4
void func(int n)
{
int sum=0;
int i,j;
for(i=0;i<n;i++) for(j=i;j<n;j++) sum=sum+i*j;
}▶ 반복 횟수 = n(n+1)/2 이므로, O(n2)
★ 알고리즘 5
void func(int n)
{
int i=1,sum=0;
while(i<=n)
{
int j=1;
while(j<=n)
{
sum=sum+i;
j=j+1;
}
i=i+1;
}
}▶ 반복 횟수 = n*n 이므로, O(n2)
★ 알고리즘 6
void func(int n)
{
int i=0;
while(i<3*n)
{
int j=10;
while(j<=50) j=j+1;
j=0;
while(j<n*n*n) j=j+2;
i=i+2;
}
}▶ 반복 횟수 = (n3/2+41)*3n/2 이므로, O(n4)
★ 알고리즘 7 (꽤 까다롭지만... 필자가 풀어낸 문제!!)
void func(int n)
{
int i,j;
for(i=n;i>1;i/=2)
{
j=n;
while(j>1) j=j/2;
}
}▶ 반복 횟수 = (logn)2 이므로, O((logn)2)
(상용 로그가 아닌, 밑이 2인 로그임에 유의!!)
• i = 0일 때, n
• i = 1일 때, n/2
• i = 2일 때, n/22
...
• i = k일 때, n/2k
여기에서 n/2k ≤ 1이 되면 반복이 종료
이는 1 ≤ 2k/n 이고, n ≤ 2k 이 되므로,
여기에 log를 취해주면, logn ≤ k 가 됨.
따라서, log의 시간 복잡도를 갖는 반복문이 2개 중첩되어 있으므로, 함수 전체의 시간 복잡도는 O((logn)2)
☆ 교수님의 착각을 바로잡은 부분!!
▶ 아래 함수의 반환 값은?
int func(int N)
{
int X=N;
int Y=1;
while(Y!=N)
{
X=X+N;
Y=Y+1;
}
return X;
}▶ 교재에는 X = N2이 되어 반환이 된다고 나와 있음.
▶ 하지만, 교수님께서 착각을 하셨는지, N+2N+3N+...으로 이해하셔서, N2이 나올 수 없다고 말씀하셨지만,
▶ 의심이 많던(?) 필자가 쉬는 시간에 여쭤보았고, 긴 시간의 설명 끝에, 교수님께서 이해를 하셨음.
▶ 이 알고리즘은, N번의 반복문 내에서 X에 N씩 더하는 알고리즘으로, 결과적으로는 N*N = N2이 됨.
※ 수업을 듣고 나서 느낀 점!!
특히, 위의 알고리즘 7의 시간 복잡도 계산이 꽤 까다롭다고 말씀하셨음.
하지만, 필자는 알고리즘을 보고 나서 logn 이라는 것을 떠올렸고, 처음에는 nlogn, lognlogn(?) 등의 답도 도전했지만,
logn의 제곱(?)이라고 도전하자, 교수님께서 앞에 나와서 칠판에 설명을 해 보라는 말씀을 하셨음.
하지만, 막상 칠판 앞에서 설명을 하려니 떨렸고, 교수님께서 약간의 도움(?)을 주셔서, 무사히 마칠 수 있었음.
반복문을 돌 때 마다 변수의 값이 절반으로 줄어든다는 점을 알아냈지만, 이것이 logn이 되는 이유에서 가물가물했음.
그래도 미리 예습한 효과가 있는 것 같았고, 특히 효율적인 알고리즘 분석에도 많은 노력을 하고 싶다는 생각을 하였음.
또, 교수님의 착각(?)을 바로잡아드렸을 때, 뿌듯함(?)을 느끼기도 하였음. 앞으로도 열심히!!
※ 기타 참고 사항!!
없음