일어나..공부해야지..

학교에서 들은 알고리즘 분석 강의 내용을 복습하면서 작성한 글입니다. April 8, 2024 6:07 PM divide-and-conquer top-down의 recursive approach 서로 관련되지 않은 더 작은 요소들로 나눠준다 Dynamic Programming(DP) bottom-up으로 작은 요소 먼저 해결 후 → 해당 결과를 저장해놓았다가 → 필요 시 가져다 쓴다 (다시 해결할 필요없이, 기존에 저장해놓은것 이용하면 됨) 나눠진 요소들이 서로 연관있는 것 → 중복이라 비효율적 → dp 사용이 더 나음 💡 과정 recursive property 찾아내기 아래 → 위로 계산 Binomial Coefficient Dynamic Programming 사용 - Recursive Property..

학교에서 들은 알고리즘 분석 강의 내용을 복습하면서 작성한 글입니다. March 25, 2024 12:17 AM 기존의 행렬 곱셈 방식 for (i = 1; i

학교에서 들은 알고리즘 분석 강의 내용을 복습하면서 작성한 글입니다. March 18, 2024 4:24 PM Quicksort pivotting: 기준이 되는 것 중심으로 비교 중간값으로 pivot을 구하지 않는 이유: 중간값 구하는게 sorting만큼 오래걸림 → 포기 → 다 비슷하므로 → 맨 왼쪽 것을 pivot으로?? (교수님이 이렇게 설명햇음..) pivot을 기준으로 pivot보다 작은 요소들은 왼쪽, 큰 요소들은 오른쪽에 있도록 (내부 순서는 신경X) pivot 제외한 왼쪽 리스트, 오른쪽 리스트를 다시 정렬 분할된 부분 리스트에 대해 recursion 하게 Q(n) = Q(l) + Q(r) +(n-1) n-1: 나 빼고 다 보기 divide-and-conquer ? 분할: 기준점을 중심으로..

학교에서 들은 알고리즘 분석 강의 내용을 복습하면서 작성한 글입니다. March 14, 2024 5:54 PM Divide-and-Conquer Binary Search 중간 값 기준으로 반쪽 날림 → shrink f(n)=f(n/2)+1 →log n번만 비교해도 ok : sequential search보다 훨씬 효율적 이진 탐색의 각 탐색 단계마다 탐색 범위가 절반으로 줄어들기 때문에, 로그함수적으로 줄어들다가 K번 째 단계에서 배열의 크기가 n/(2^k) = 1 이 됨 (이유: 탐색이 완료되기 위해서는 탐색범위가 1이어야 하기 때문) → n = 2^k 양변에 로그 취하면, k=logn -> 시간복잡도: logn index location(index low, index high) { index mid;..

학교에서 들은 알고리즘 분석 강의 내용을 복습하면서 작성한 글입니다. March 14, 2024 5:51 PM Order (차수) Big O - 최악 알고리즘 효율성을 상한선 기준으로 표기 g(n) =c * f(n) Θ (theta) Θ(f(n)) = O(f(n)) ∩ Ω(f(n)) 공통부분임 (상한, 하한) c * f(n)

학교에서 들은 알고리즘 분석 강의 내용을 복습하면서 작성한 글입니다. March 12, 2024 4:29 PM Algorithm Definiteness - clear and unambigiuous Finiteness - 크고 길 수는 있지만 terminate 해야함 Effectiveness - 간단하고, 구현가능해야함 P-NP 문제 Deterministic (P) Non-deterministic (NP) -deterministic polynomial time : 다항 시간 내에 yes-no 대답 가능 예: 3n^3+2n^2+7n+2 다항 시간 내에 해결할 수 있는 결정 문제 -쉽게 해결할 수 있는 비결정적 결정 문제들의 집합 -여러 가지 풀이 가능성을 고려할 수 있음 다항 시간 내에 검산할 수 있는 문제..