안녕

앞선 시간에 merge sort에 대해 설명 드렸습니다. 이번에는 in-place 정렬로 merge sort하는 법을 보여드리겠습니다. 1. 코드 n = int(input()) S = list(map(int, input().split())) def mergesort(low, high): # 두 개로 분할함 if low < high: mid = (low + high) // 2 mergesort(low, mid) mergesort(mid+1, high) merge(low, mid, high) def merge(low, mid, high): # 병합함 i = low; j = mid + 1; U = list() while i

1. Merge Sort의 알고리즘 및 코드 Problem : n개의 원소를 가지고 있는 정렬되지 않은 리스트 S를 오름차순으로 정렬 input : n과 정렬되지 않은 리스트 S output : 정렬된 리스트 S Merge Sort의 알고리즘) 1. 배열을 반으로 분할한다. 2. 분할한 배열을 정렬한다 (배열에 원소가 2개 이상이면 merge sort를 재귀 호출하여 정렬한다) 3. 분할한 배열을 합병하여 정렬한다. 그러면 결국엔 정렬은 배열에 원소가 1개 일 때 일어나겠죠? 근데 원소가 하나밖에 없으면 정렬할 필요가 없습니다. 따라서 merge sort는 배열의 원소가 하나가 될 때까지 쪼개고, 쪼개진 그 배열을 정렬하면서 합병하는 알고리즘이라 볼 수 있겠습니다. 그러면 한 번 코드로 작성해보겠습니다...

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. 분할 정복이란? 분할 정복은 이름에서 볼 수 있듯이 말 그대로 분할 정복입니다. 분할 정복의 접근법) 1. divides an instance of a problem into two or more smaller instances. 2. if they are too large to be sorved, they can be divided into still smaller instances 3. if solutions to them can be obtained readily, these smaller solutions can be combined into original solution 즉, 문제를 두 개 이상의 instance로 쪼갠다. 그래도 instance가 여전히 크면 또 쪼갠다. 만약 분할한 i..

앞 글들에서 피보나치 수열의 문제를 풀어봤었습니다. 1. 재귀를 이용한 피보나치 수열 이렇게 재귀를 이용해서 풀면 너무 많은 중복 계산이 일어나서 성능이 안 좋습니다. 따라서 이미 해결한 문제는 메모리에 저장해서 나중에 필요할 때 뽑아서 쓰기로 했었습니다. 2. 반복문을 이용한 피보나치 수열 반복문을 이용하여 재귀를 쓰지 않고, 이미 계산한 값에 대해서 리스트에 저장했습니다. 이를 메모이제이션 기법이라고 합니다. 아래는 1번과 2번의 코드입니다. n = int(input()) def fib1(n): if n 0.004057884216308594# 2번 >>> 0.0016162395477294922# 3번 두 배보다 더 빠른 시간 차이가 나네요 참고로 1번에 10,000을 넣으면 아마 평생 걸려도 못 찾으..

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로 시작하는 단어를 찾고 이런 식으로 찾지 않을까요? 이처럼 문제를 해결하는 절차는 너무나도 중요합니다. 하지만 컴퓨터는 너무나도 빠르고, 메모리는 갈수록 가격이 싸지고 있는데 ..