안녕

1. 차수란? 앞선 글에서 0.001\(n^{2}\)보다 100\(n\)이 궁극적으로 더 빠른 알고리즘이라고 말씀드렸습니다. 왜일까요? 100n은 1차식으로 증가하는 반면, 0.001\(n^{2}\)은 2차식으로 증가하기 때문에 증가율이 더 높습니다. 이렇게 알고리즘의 효율성을 비교하기 위해서는 앞에 붙은 계수보다는 차수가 더 중요합니다. 극단적인 예로 100000000000000000000\(n\)이 0.00000000000001\(n^{2}\)보다 더 빠르다고 설명할 수 있습니다. 이때, 100\(n\)은 1차시간 알고리즘, 0.001\(n^{2}\)은 2차시간 알고리즘이라고 설명할 수 있겠습니다. 5\(n^2\) +100 같은 함수는 순수 2차함수라고 할 수 있습니다. 그에 반해 0.1\(n^2\)..

1. 알고리즘의 분석 알고리즘 분석에는 두 가지 방법이 있습니다. The correctness of an algorithm The efficiency of an algorithm how efficiency the algorithm solves a problem in terms of either time or space 이때, 정확도 분석은 학부생의 레벨이 아니고 대학원생의 레벨입니다. 그리고 수학적 증명이 필요하기 때문에 학부생 레벨에서는 패스하겠습니다. 그러면 이제 알고리즘의 효율성 분석이 있습니다. 이때, 시간과 공간 측면에서 분석을 해야합니다. 하지만 공간은 그렇게 중요한 부분이 아닙니다. 메모리는 부족하면 언제든지 추가 구매하면 되니까요. 하지만 시간은 매우 중요합니다. 공간을 많이 먹어도 시간이..

1. 슈도코드 앞선 시간에는 리스트 S안에 x가 있는지 해결해봤습니다. 하지만 현실의 문제는 이렇게 단순하지 않고, 점점 더 복잡합니다. 모든 문제 해결 전략을 말로 설명할 수도 없고,,,그렇다고 코드로 다 짜자니 복잡하고,, 이때 중요한 것이 슈도코드(pseudo-code)입니다. 말 그대로 가짜 코드입니다. 코드와 말을 적절히 섞어가며 모두가 이해할 수 있는 코드이죠. 물론 실행은 안 됩니다 ㅎㅎ 한 번 직접 해봅시다. 예시) Problem : Add all the numbers in the array S of n numbers Inputs : positive integer n, array of numbers S indexed from 0 to n-1 Outputs : sum, the sum of t..

안녕하세요 .. 개강하고 나서 글을 아무것도 못 썼네요 ..... 너무 바빠서 .. 이제부터 수업 듣는거 정리하는 겸 공부할 겸 글 다시 쓰려구요.. 1. 알고리즘이란? 알고리즘은 step-by-step precedure for solving a problem 이라고 합니다. 즉 문제를 해결하는 단계별 절차라고 해석할 수 있습니다. 그러면 저희는 왜 알고리즘을 알아야할까요? 단어장에서 hello 라는 단어를 찾는다고 가정해봅시다. 이 때, a부터 시작하면 너무 비효율적이겠죠?? 당연히 h부터 시작하는 페이지를 열고, 그 다음 he로 시작하는 단어를 찾고 이런 식으로 찾지 않을까요? 이처럼 문제를 해결하는 절차는 너무나도 중요합니다. 하지만 컴퓨터는 너무나도 빠르고, 메모리는 갈수록 가격이 싸지고 있는데 ..