분류 전체보기144 알고리즘 개념 7. 병합정렬 Merge sort 개념 두개로 나누고 각각을 해결한 다음, 결과를 모아 원래의 문제를 해결한다. 두 개로 나눈 리스트를 재귀적으로 합병정렬을 이용해 정렬하고, 나중에 다시 합친다. 글로는 잘 이해가 안가니까 사진 참고. 분할 -> 정복(정렬) -> 병합 이때 걸리는 시간? O(n log n) 의 시간복잡도를 갖는다. 장점? - 데이터 특성과 상관없이 같은 양이면 정렬시간은 비슷하다. - 각각의 레코드를 Linked list 로 구성하면, 데이터 이동은 엄청 작아진다. 따라서 크기가 큰 것을 정렬할때 연결리스트를 사용한다면 매우 효율적이다. 단점? - 레코드가 Array면 임시배열이 필요하고, in-place sorting이 아니다 - 크기가 크면 이동횟수가 많아서 비효율적이다. ** Stable sort, Unstable.. 2020. 11. 10. 알고리즘 개념 6. 삽입정렬 (Insertion sort) 개념? - 자신보다 그 앞의 원소가 큰지, 작은지를 판단하여 자신의 위치를 찾아 삽입하는 정렬 - 오름차순,내림차순 - 자기자신이 n번째에 있으면 첫번째원소부터 n까지 비교 시간복잡도: O(n^2) -특정한 경우에 빠른 속도가 나지만(정렬이 되어있다고 가정), 배열이 길어지면 효율이 떨어진다. 예시 9 4 6 2 1 5 단계별 출력 9 4 9 4 6 9 2 4 6 9 1 2 4 6 9 1 2 4 5 6 9 def insert_sort(x): for i in range(1, len(x)): j = i - 1 key = x[i] while x[j] > key and j >= 0: x[j+1] = x[j] j = j - 1 x[j+1] = key return x python 코드 포인트 arr[i - 1], .. 2020. 11. 9. E: Unable to locate package python-pip 에러 해결법 가상환경에서 python module import 가 안되어서 pip install도 E: Unable to locate package python-pip 에러가 발생.. 해결 코드 차례대로 터미널에서 입력해줌 $ sudo apt-get install software-properties-common $ sudo add-apt-repository universe $ sudo apt-get update $ sudo apt-get install python-pip 2020. 11. 6. 알고리즘 개념 5. 버블 정렬 (Bubble sort) - 인접한 두 항목을 비교하여, 기준을 만족하면 서로의 값을 교환하는 형식 - 선택정렬과 기본 개념이 유사하다 예를 들어, 오름차순 정렬을 하고싶을때! 기준: 인접한 두 항을 비교하여, 더 큰수가 뒤로 가도록 바꾼다 1회전 수행결과: 가장 큰 수가 맨 뒤로 간다 2회전 수행결과: 가장 큰 수 2개가 맨 뒤에 있다. 2회전 수행시에는, 1회전에서 완료한 맨 끝의 값을 제외하고 연산한다. 비교연산횟수: n(n-1)/2 자리교환횟수: n(n-1)/2 시간복잡도: O(n^2) 장점? - 단순한 개념, 구현하기 쉬움 단점? - 비교횟수가 많아서 연산 속도가 느림, 대량데이터에 부적합 def bubbleSort(x): length = len(x)-1 for i in range(length): for j in ran.. 2020. 11. 4. 알고리즘 개념 4. 선택정렬 Selection sort - 제자리 정렬 알고리즘 - 입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법 순서 (1) 주어진 리스트에서 최솟값을 찾는다 (2) 그 최솟값을 맨 앞의 값과 교체한다. (pass) (3) 맨 앞 위치를 빼고 나머지 리스트를 같은 방법으로 계속 정렬한다. 걸리는 시간은? n개의 리스트가 있다고 한다면 Θ(n2)만큼 시간이 걸린다. * for loops 2개로 이루어짐 -> 첫번째 루프횟수 : (n-1) 두번째도 (n-1) * 값 교환 횟수 = 3(n-1) 장점? 자료의 이동횟수가 미리 정해져 있다 단점? 안정성을 만족하지 않고, 값이 같은 속성이 있는 경우 상대적 위치가 변경될 수 있다. python example def selectionSort(x): length = len(x) for i.. 2020. 11. 3. 알고리즘 개념 3. 점화식 Recurrence relation 점화식이란? - 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것 (ex) 등차수열, 팩토리얼 점근적 분석 방법의 종류? (1) 반복 대치 : 더 작은 문제에 대한 함수로 반복해서 대치함 (2) 추정 후 증명 : 식의 모양을 보고 점근적 복잡도를 추정한 다음, 그 것의 옳음을 수학적으로 귀납적 증명 (3) 마스터 정리 : 특정 형식에 맞는 점화식의 복잡도를 계산이나 증명없이 알수있는 정리 2020. 11. 2. 알고리즘 개념 2. 점근적 표기 (Asymptotic notation) 점근적 분석? - 주어진 문제에 대한 여러 알고리즘이 있을때, 효율성을 비교하기위한 분석 점근적 증가율? - 변수크기가 충분히 크면 변수증가에 따라 함수가 증가하는 비율(함수를 비교할 때, 상수나 작은 인풋은 무시) 점근적 표기법? (1) O-표기법 - 알고리즘이 아무리 안좋아도, 비교하는 함수와 같거나, 그거보다 좋다 - 점근적 상한선(Asymptotic upper bound)만 알고있다면 이 표기법 사용 - (ex)이 알고리즘은 적어도 00정도의 성능이 나온다 할때 사용 - (2) 𝛺-표기법 - 알고리즘이 아무리 좋아도, 기존 비교하는 함수 이하이다. - 점근적 하한선(Asymptotic lower bound) - O-표기법의 반대개념 - (3) 𝛩-표기법 - 알고리즘이 아무리 좋아도,나빠도, 기존 .. 2020. 10. 28. 이전 1 2 3 4 5 6 ··· 21 다음
