안녕

만약 하드웨어의 저장 공간을 넘어서는 숫자들의 연산을 해야 한다면 어떻게 해야 할까요? 이 경우에 유일한 대안은 소프트웨어적으로 숫자들을 표현하고 처리해야 합니다. 방법은 숫자들을 하나씩 쪼개서 배열에 넣는 방법이 있습니다. 이때 배열에는 역순으로 넣어야 합니다. 1. 알고리즘 및 코드 우선 긴 숫자를 쪼개 봅시다. $u=x\times {10}^m+y$ $v=w\times {10}^m+z$ 일 때, $uv=(x\times {10}^m+y)(w\times {10}^m+z)$ 이고, 이는 $xw\times {10}^{2m}+(xz+wy)\times {10}^m+yz$ 입니다. 이것을 통해 쉽게 계산할 수 있습니다. Problem : 큰 정수의..

1. 알고리즘 및 코드 Problem : 오름차순으로 주어진 리스트를 정렬 Input : 양의 정수 n, 리스트 S Output : 오름차순으로 정렬된 리스트 S 알고리즘) 1. pivot을 기준으로 나눈다. 2. 나눈 pivot의 왼쪽, 오른쪽을 재귀적으로 다시 적용한다. 3. 리스트를 더 이상 나눌 수 없을 때까지 반복한다. (원소가 1개 이하로 남았을 때) 생각의 흐름) pivot은 리스트의 맨 앞을 넣는다. pivot을 기준으로 나누면 되는데, j에 low 위치를 넣고, i를 low + 1의 위치부터 high까지 넣는다. 그러면 for문으로 i를 돌리고, 이때 S[i]가 pivot보다 작으면 j에 1을 더하고, i 위치와 j 위치를 swap한다. 쭉 반복하면 결국 최종적으로 j의 위치가 pivot..

1. Binary Search의 알고리즘 및 코드 분할 정복의 기본은 재귀이기 때문에 반복문이 아닌 재귀를 통해서 binary search를 하겠습니다. 반복문을 통한 binary search는 앞 글을 참고해주세요. Problem : 원소가 n개인 (오름차순)정렬된 리스트 S안에 검색하려는 수 x가 있는가? input : 양의 정수 n, 정렬된 리스트 S, 검색키 x output : x의 위치, 만약 없다면 -1를 반환 알고리즘 구상) 1) x와 S의 중간 값과 비교해 같다면 그대로 끝 2) 만약 다르다면 두 가지 방법을 이용한다. 2.1) x가 S의 중간 값보다 작다면 중간 위치를 기준으로 왼쪽 리스트를 탐색한다. 2.2) x가 S의 중간 값보다 크다면 중간 위치를 기준으로 오른쪽 리스트를 탐색한다...

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 이때, 정확도 분석은 학부생의 레벨이 아니고 대학원생의 레벨입니다. 그리고 수학적 증명이 필요하기 때문에 학부생 레벨에서는 패스하겠습니다. 그러면 이제 알고리즘의 효율성 분석이 있습니다. 이때, 시간과 공간 측면에서 분석을 해야합니다. 하지만 공간은 그렇게 중요한 부분이 아닙니다. 메모리는 부족하면 언제든지 추가 구매하면 되니까요. 하지만 시간은 매우 중요합니다. 공간을 많이 먹어도 시간이..