자료구조 2주차
- 수학적 귀납법
- base , step 이 존재해야 함.
- P(1)이 참이고, P(n-1) → P(n)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.
- 명제 P → Q 의 의미
- “p→q” vs “p→q&q→p”
- 100점 → chicken
- T → T ⇒ T
- T → F ⇒ F
- F → T ⇒ T (?) vacuous true
- F → F ⇒ T
- if n>3 then n^2>10
- n=1? → vacuously true다.
- 100점 → chicken
- P(1)이 참이고(base), P(n-1)→P(n)이 참이면(step) P(n)은 모든 자연수 n에 대해서 참이다.
- P(n-1)
- False 경우는 결과는 Vacuously True이므로 이야기를 안함.
- True인 경우에만 할 이야기가 있음.
- 그래서 참일 때만 언급을 함.
- ( == 참이라고 가정하는 이유 )
- 보통 재귀를 이해할 때
- 코드를 따라 들어가려고 함
- 그냥 맞다고 믿어라..?
- 믿으세요!
- P(n-1)
- “p→q” vs “p→q&q→p”
// 코드 예시
int sum(int x)
{
int i, S;
S = 0;
for (i = 1; i <= x; i++) {
S += i;
}
return 0;
}
int sum(int x){
if x<=0{
return 0;
}
return x+sum(x-1);
}- Array(배열)
- 정의 : 연속된 주소, 동일한 Type
- 장점 : n개 중 k번째 access(만진다)가 상수 시간에 가능. Search가 빠름
- 단점 : 크기 변화 비용이 크다. Insert, Delete가 느릴 수 있다.
- 사용 : 변화가 없거나 드문 자료
- k번째 위치 찾기는 빠른데 n을 찾을 때는 힘들 수도..
- Linear Search
int search(int a[], int n, int x) {
int i;
for (i = 0; i < n; i++) {
if (a[i] == x)return i;
}
return -1;
}
int search(int a[], int n, int x) {
int i;
for (i = 0; i < n; i++) {
if (*(a+i) == x)return i;
}
return -1;
}
// 시간 : O(n)- Sorting 이 되어 있으면 더욱 빨리 찾을 수 있음.
- Binary Search
int search(int a[], int n, int x) {
int l, r, m;
l = 0; r = n - 1;
while (l < r) {
m = (l + r) / 2;
if (a[m] < x) {
l = m + 1;
}
else if (a[m] > x) {
r = m - 1;
}
else {
return m;
}
}
return -1;
}
// l, r이 차이가 많이 나지 않으면 따져봐야함.- Proof by Invariant
- Invariant(변하지 않는 성질) : Sorting 되어 있다는 가정 하, 만약 어떤 i에 대해서 a[i]=x 라면 l≤i≤r이 항상 성립한다.
- Invariant는 최초에 성립하고, invariant 를 깰 수 있는 코드가 전혀 없음.
- a[i]=x인 i가 없으면 루프가 반드시 끝나고, -1이 리턴된다.
- a[i]=x인 i가 있다면 루프 안에서 반드시 리턴 됨.
- Invariant(변하지 않는 성질) : Sorting 되어 있다는 가정 하, 만약 어떤 i에 대해서 a[i]=x 라면 l≤i≤r이 항상 성립한다.
- Recursive Binary Search v1
int search(int a[], int n, int x)
{
int m;
if(n==0) return -1; // base case
m = n/2;
if(a[m]==x){
return m;
}
else if(a[m]>x){
return search(a, m, x);
// 0~m-1까지
}
else{ // a[m]<x
return m+1 + search(a+m+1, n-(m+1), x);
}
}- Recursive Binary Search v2
int search(int a[], int n, int x)
{
int m;
if(n==0) return -1; // base case
m = n/2;
if(a[m]==x){
return m;
}
else if(a[m]>x){
return search(a, m, x);
// 0~m-1까지
}
else{ // a[m]<x
return search(a+m+1, n-(m+1), x);
}
}
// 있는 지 없는 지만 확인- Proof by Induction
- 주장 : 만약 어떤 i에 대해서 a[i]=x라면 위 함수는 i를 리턴한다.
- Base : n=0인 경우 “어떤 i에 대해서 a[i]=x”가 성립할 방법이 없고, 함수는 항상 -1을 리턴한다.
- Step // Sorting 되어 있다고 가정
- Case 1: a[m]=x인 경우 m을 리턴하므로 주장이 성립
- Case 2: a[m]>x인 경우 a[m], a[m+1]….a[n] 중에서는 x와 같은 값이 없다. 따라서 a[i]=x인 경우가 있다면 i는 0,1,…,m-1 중 하나이다. 귀납적으로 search(a,m,x)가 정확하다고 가정하면, 즉 , 제일 위 주장이 search(a,m,x)에서 성립한다고 가정하면 제일 위 주장이 성립함
- Case 3: Case 2와 유사함
- 상수시간 : 값이 안 변하는 시간
- The Complexity
- T(n) = 1+T(n/2);⇒ T(n) = O(logn)
= 1+1+T(n/4) = … = logn
- What is Log?
- k=logn ↔ 2^k = n
- logn은 2를 몇 번 곱하면 n이 되느냐의 질문에 대한 답
- n을 2로 몇 번 나누면 1이 되느냐의 질문에 대한 답
- logn은 n보다 월등히 작다
- Selection Sort // 선택 정렬
int sort(int a[], int n)
{
int i, j, mn, tmp;
for (i = 0; i < n; i++)
{
mn = i; // 여태까지 본 것중 가장 작은 값의 index = mn
for (j = i + 1; j < n; j++)
{
if (a[j] < a[mn])
{
mn = j;
}
}
tmp = a[i];
a[i] = a[mn];
a[mn] = tmp;
}
}- Proof of Correctness of Sorting
- Sorting이 됐다는 증명을 어떻게?
- 입력 : a[0],a[1],…a[n-1] ← (정수) 집합
- Sorting이 완료된 후 다음이 만족되어야 함
- Sorting이 끝난 후 배열에 저장된 값들을 b[0],b[1],…,b[n-1]라고 부르자
- 조건 1: {a[0],a[1],…,a[n-1]} = {b[0],b[1],…,b[n-1]} 집합으로 같음
- 조건 2: b[0]<b[1]<…b[n-1](편의상 같은 값은 없다고 가정)
- Proof by Invariant
- 집합 조건을 깰 수 있는 코드는 없음
- Invariant : k번째 루프가 끝난 후에
- (1) a[0]<a[1]<…<a[k-1]→a[0]<a[1]<…<a[n-1] ( 결국에 k가 n까지 가면 )
- (2) a[k-1]<a[x] if x>k-1
- Prove Invariant by induction
- Base : k=0. (1)은 null condition, true.(2)도 null condition, true.
- 애초에 Invariant가 의미가 없음
- Step : k번째 루프가 끝났을 때 Invariant가 성립한다면, k+1번째 루프가 끝났을 때도 Invariant가 성립하는 거를 보여야.
- Base : k=0. (1)은 null condition, true.(2)도 null condition, true.
- Invariant : k번째 루프가 끝난 후에
- (1)
- (2) 모두 사실이라고 하자.
- a[k],…,a[n-1] 중 최소값을 a[k]로 옮겼음
- Invariant : k+1번쨰 루프가 끝난 후에
- (1) Invariant에 따라 a[0]<a[1]<…<a[k-1]<a[k]가 성립.
- a[k]는 a[x]들 중 하나.
- (2) a[k]<a[x] if x>k
- a[k]는 a[k]…a[n-1] 중 최소값이기 때문
- (1) Invariant에 따라 a[0]<a[1]<…<a[k-1]<a[k]가 성립.
- Recursive Selection Sort
int sort(int a[] ,int n)
{
int i, mn, tmp;
if (n == 0) return;
mn = 0;
for(int i = 1; i < n; i++)
{
if (a[i] < a[mn]) mn = i;
}
tmp = a[0];
a[0] = a[mn];
a[mn] = tmp;
sort(a + 1, n - 1);
}- Proof by Induction
- 집합 조건을 깰 수 있는 코드는 지금도 없음
- Base : n=1. 할 일이 없음
- Step :
- k-1일 때 sort()함수가 성공한다면
- ⇒ 즉, 재귀 호출이 끝난 후 a[0]<a[1]<a[2]<…<a[k-1]이라면
- k일 때 sort()함수가 성공한다
- ⇒ 함수가 끝날 때 a[0]<a[1]<a[2]<…<a[n-1]성립
- k-1일 때 성공한다고 가정하면, 마지막엔 최소값이 mn에 해당하여 들어가 있으므로 성립
- 시간 복잡도
- T(n) = n+T(n-1)
- = n+n-1+T(n-2)=…
- =⇒ T(n)=0(n^2)
- = n+n-1+T(n-2)=…
- T(n) = n+T(n-1)
Merge Algorithm
- merge라는 알고리즘을 이용하는 sorting
- ⇒ merge sorting
- sorting 된 배열 2개가 주어짐
- 앞에 있는 거 중에 작은 거를 옮김 ( 새로운 배열로 )
- O(n*logn)시간에 돌아간다
int sort(int a[], int n)
{
int m;
int b[n];
if (n <= 1) return;
// copy array a to array b;
m = n / 2; // n=2일때 m=1
sort(b, m); // 좌측
sort(b + m, n - m); // 우측
//merge b and b+m back to a
return;
}- Proof by Induction
- 집합 조건을 깰 수 있는 코드는 지금도 없음
- Base: n=1. 할 일이 없음
- Step:
- n/2일 때 sort() 함수가 성공한다면
- ⇒ 즉, 재귀 호출이 끝난 후 a[0]<a[2]<…<a[n/2-1] and a[n/2]<a[n/2+1] < … < a[n-1] 이라면
- 재귀적으로 믿으면
- n일때 sort() 함수가 성공한다.
- ⇒ 함수가 끝날 때 a[0]<a[1]<a[2]<…<a[n-1] 성립
- merge 함수의 정확성에 의하면 맞아야함.
- ㅠ
- The Complexity
- T(n) = n+2T(n/2) (n=copy array + merge array)→ T(n) = O(n*logn)
- == n * (logn개) 나오기 때문에 성립
= n+2(n/2 + 2T(n/4)) = n+2(n/2+2(n/4+2T(n/8)) = … = nlogn
반응형
자료구조 2주차
- 수학적 귀납법
- base , step 이 존재해야 함.
- P(1)이 참이고, P(n-1) → P(n)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.
- 명제 P → Q 의 의미
- “p→q” vs “p→q&q→p”
- 100점 → chicken
- T → T ⇒ T
- T → F ⇒ F
- F → T ⇒ T (?) vacuous true
- F → F ⇒ T
- if n>3 then n^2>10
- n=1? → vacuously true다.
- 100점 → chicken
- P(1)이 참이고(base), P(n-1)→P(n)이 참이면(step) P(n)은 모든 자연수 n에 대해서 참이다.
- P(n-1)
- False 경우는 결과는 Vacuously True이므로 이야기를 안함.
- True인 경우에만 할 이야기가 있음.
- 그래서 참일 때만 언급을 함.
- ( == 참이라고 가정하는 이유 )
- 보통 재귀를 이해할 때
- 코드를 따라 들어가려고 함
- 그냥 맞다고 믿어라..?
- 믿으세요!
- P(n-1)
- “p→q” vs “p→q&q→p”
// 코드 예시
int sum(int x)
{
int i, S;
S = 0;
for (i = 1; i <= x; i++) {
S += i;
}
return 0;
}
int sum(int x){
if x<=0{
return 0;
}
return x+sum(x-1);
}- Array(배열)
- 정의 : 연속된 주소, 동일한 Type
- 장점 : n개 중 k번째 access(만진다)가 상수 시간에 가능. Search가 빠름
- 단점 : 크기 변화 비용이 크다. Insert, Delete가 느릴 수 있다.
- 사용 : 변화가 없거나 드문 자료
- k번째 위치 찾기는 빠른데 n을 찾을 때는 힘들 수도..
- Linear Search
int search(int a[], int n, int x) {
int i;
for (i = 0; i < n; i++) {
if (a[i] == x)return i;
}
return -1;
}
int search(int a[], int n, int x) {
int i;
for (i = 0; i < n; i++) {
if (*(a+i) == x)return i;
}
return -1;
}
// 시간 : O(n)- Sorting 이 되어 있으면 더욱 빨리 찾을 수 있음.
- Binary Search
int search(int a[], int n, int x) {
int l, r, m;
l = 0; r = n - 1;
while (l < r) {
m = (l + r) / 2;
if (a[m] < x) {
l = m + 1;
}
else if (a[m] > x) {
r = m - 1;
}
else {
return m;
}
}
return -1;
}
// l, r이 차이가 많이 나지 않으면 따져봐야함.- Proof by Invariant
- Invariant(변하지 않는 성질) : Sorting 되어 있다는 가정 하, 만약 어떤 i에 대해서 a[i]=x 라면 l≤i≤r이 항상 성립한다.
- Invariant는 최초에 성립하고, invariant 를 깰 수 있는 코드가 전혀 없음.
- a[i]=x인 i가 없으면 루프가 반드시 끝나고, -1이 리턴된다.
- a[i]=x인 i가 있다면 루프 안에서 반드시 리턴 됨.
- Invariant(변하지 않는 성질) : Sorting 되어 있다는 가정 하, 만약 어떤 i에 대해서 a[i]=x 라면 l≤i≤r이 항상 성립한다.
- Recursive Binary Search v1
int search(int a[], int n, int x)
{
int m;
if(n==0) return -1; // base case
m = n/2;
if(a[m]==x){
return m;
}
else if(a[m]>x){
return search(a, m, x);
// 0~m-1까지
}
else{ // a[m]<x
return m+1 + search(a+m+1, n-(m+1), x);
}
}- Recursive Binary Search v2
int search(int a[], int n, int x)
{
int m;
if(n==0) return -1; // base case
m = n/2;
if(a[m]==x){
return m;
}
else if(a[m]>x){
return search(a, m, x);
// 0~m-1까지
}
else{ // a[m]<x
return search(a+m+1, n-(m+1), x);
}
}
// 있는 지 없는 지만 확인- Proof by Induction
- 주장 : 만약 어떤 i에 대해서 a[i]=x라면 위 함수는 i를 리턴한다.
- Base : n=0인 경우 “어떤 i에 대해서 a[i]=x”가 성립할 방법이 없고, 함수는 항상 -1을 리턴한다.
- Step // Sorting 되어 있다고 가정
- Case 1: a[m]=x인 경우 m을 리턴하므로 주장이 성립
- Case 2: a[m]>x인 경우 a[m], a[m+1]….a[n] 중에서는 x와 같은 값이 없다. 따라서 a[i]=x인 경우가 있다면 i는 0,1,…,m-1 중 하나이다. 귀납적으로 search(a,m,x)가 정확하다고 가정하면, 즉 , 제일 위 주장이 search(a,m,x)에서 성립한다고 가정하면 제일 위 주장이 성립함
- Case 3: Case 2와 유사함
- 상수시간 : 값이 안 변하는 시간
- The Complexity
- T(n) = 1+T(n/2);⇒ T(n) = O(logn)
= 1+1+T(n/4) = … = logn
- What is Log?
- k=logn ↔ 2^k = n
- logn은 2를 몇 번 곱하면 n이 되느냐의 질문에 대한 답
- n을 2로 몇 번 나누면 1이 되느냐의 질문에 대한 답
- logn은 n보다 월등히 작다
- Selection Sort // 선택 정렬
int sort(int a[], int n)
{
int i, j, mn, tmp;
for (i = 0; i < n; i++)
{
mn = i; // 여태까지 본 것중 가장 작은 값의 index = mn
for (j = i + 1; j < n; j++)
{
if (a[j] < a[mn])
{
mn = j;
}
}
tmp = a[i];
a[i] = a[mn];
a[mn] = tmp;
}
}- Proof of Correctness of Sorting
- Sorting이 됐다는 증명을 어떻게?
- 입력 : a[0],a[1],…a[n-1] ← (정수) 집합
- Sorting이 완료된 후 다음이 만족되어야 함
- Sorting이 끝난 후 배열에 저장된 값들을 b[0],b[1],…,b[n-1]라고 부르자
- 조건 1: {a[0],a[1],…,a[n-1]} = {b[0],b[1],…,b[n-1]} 집합으로 같음
- 조건 2: b[0]<b[1]<…b[n-1](편의상 같은 값은 없다고 가정)
- Proof by Invariant
- 집합 조건을 깰 수 있는 코드는 없음
- Invariant : k번째 루프가 끝난 후에
- (1) a[0]<a[1]<…<a[k-1]→a[0]<a[1]<…<a[n-1] ( 결국에 k가 n까지 가면 )
- (2) a[k-1]<a[x] if x>k-1
- Prove Invariant by induction
- Base : k=0. (1)은 null condition, true.(2)도 null condition, true.
- 애초에 Invariant가 의미가 없음
- Step : k번째 루프가 끝났을 때 Invariant가 성립한다면, k+1번째 루프가 끝났을 때도 Invariant가 성립하는 거를 보여야.
- Base : k=0. (1)은 null condition, true.(2)도 null condition, true.
- Invariant : k번째 루프가 끝난 후에
- (1)
- (2) 모두 사실이라고 하자.
- a[k],…,a[n-1] 중 최소값을 a[k]로 옮겼음
- Invariant : k+1번쨰 루프가 끝난 후에
- (1) Invariant에 따라 a[0]<a[1]<…<a[k-1]<a[k]가 성립.
- a[k]는 a[x]들 중 하나.
- (2) a[k]<a[x] if x>k
- a[k]는 a[k]…a[n-1] 중 최소값이기 때문
- (1) Invariant에 따라 a[0]<a[1]<…<a[k-1]<a[k]가 성립.
- Recursive Selection Sort
int sort(int a[] ,int n)
{
int i, mn, tmp;
if (n == 0) return;
mn = 0;
for(int i = 1; i < n; i++)
{
if (a[i] < a[mn]) mn = i;
}
tmp = a[0];
a[0] = a[mn];
a[mn] = tmp;
sort(a + 1, n - 1);
}- Proof by Induction
- 집합 조건을 깰 수 있는 코드는 지금도 없음
- Base : n=1. 할 일이 없음
- Step :
- k-1일 때 sort()함수가 성공한다면
- ⇒ 즉, 재귀 호출이 끝난 후 a[0]<a[1]<a[2]<…<a[k-1]이라면
- k일 때 sort()함수가 성공한다
- ⇒ 함수가 끝날 때 a[0]<a[1]<a[2]<…<a[n-1]성립
- k-1일 때 성공한다고 가정하면, 마지막엔 최소값이 mn에 해당하여 들어가 있으므로 성립
- 시간 복잡도
- T(n) = n+T(n-1)
- = n+n-1+T(n-2)=…
- =⇒ T(n)=0(n^2)
- = n+n-1+T(n-2)=…
- T(n) = n+T(n-1)
Merge Algorithm
- merge라는 알고리즘을 이용하는 sorting
- ⇒ merge sorting
- sorting 된 배열 2개가 주어짐
- 앞에 있는 거 중에 작은 거를 옮김 ( 새로운 배열로 )
- O(n*logn)시간에 돌아간다
int sort(int a[], int n)
{
int m;
int b[n];
if (n <= 1) return;
// copy array a to array b;
m = n / 2; // n=2일때 m=1
sort(b, m); // 좌측
sort(b + m, n - m); // 우측
//merge b and b+m back to a
return;
}- Proof by Induction
- 집합 조건을 깰 수 있는 코드는 지금도 없음
- Base: n=1. 할 일이 없음
- Step:
- n/2일 때 sort() 함수가 성공한다면
- ⇒ 즉, 재귀 호출이 끝난 후 a[0]<a[2]<…<a[n/2-1] and a[n/2]<a[n/2+1] < … < a[n-1] 이라면
- 재귀적으로 믿으면
- n일때 sort() 함수가 성공한다.
- ⇒ 함수가 끝날 때 a[0]<a[1]<a[2]<…<a[n-1] 성립
- merge 함수의 정확성에 의하면 맞아야함.
- ㅠ
- The Complexity
- T(n) = n+2T(n/2) (n=copy array + merge array)→ T(n) = O(n*logn)
- == n * (logn개) 나오기 때문에 성립
= n+2(n/2 + 2T(n/4)) = n+2(n/2+2(n/4+2T(n/8)) = … = nlogn
반응형
