알고리즘 (6) 썸네일형 리스트형 정렬의 stability 안정정렬과 불안정정렬을 예시를 들어 정리해봤다. 정렬 전 데이터베이스 이름 학년 1 가케니 3 2 다스탠 3 3 라카트먼 3 4 나버터스 2 5 마카일 1 이름을 오름차순으로 처음 정렬할때 어떤 정렬기법을 사용하든 결과는 똑같다. 첫번째 이름 기준 정렬 결과 이름 학년 1 가케니 3 2 나버터스 2 3 다스탠 3 4 라카트먼 3 5 마카일 1 하지만 여기서 학년 기준 오름차순으로 한번 더 정렬한다면 사용한 정렬기법에 따라 결과가 바뀐다. case 1. 불안정 정렬 ex )선택정렬, 퀵정렬 (아래는 첫번째 정렬결과에 추가로 학년기준 선택정렬을 한 것이다. 3학년들의 정렬 상태를 확인해보자 ) 이름 학년 1 마카일 1 2 나버터스 2 3 다스탠 3 4 라카트먼 3 5 가케니 3 학년은 잘 정렬이 됐으나 이름.. algorithm, part1 | Coursera 과제 하는법 (mac) 영어를 못해서 첫번째 테스트용 과제 세팅하느라 하루를 다썼다. 그래도 단어 하나씩 찾아가면서 과제 제출하고 통과했다. (영어 잘하는분은 원문 읽으면서 하는게 더 빨라요!) 세팅 하는 방법 lift.cs.princeton.edu/java/mac/ Hello World in Java (Mac OS X) Tip Typically, you should compile from IntelliJ (because IntelliJ highlights the lines on which any compile-time errors or warnings occur) and execute from the command line (because the command line makes it is easy to specify com.. quickSort 파이썬 구현 (백준 2750) import sys sys.setrecursionlimit(99999) input = sys.stdin.readline # 파티션 구현 (분할) #pivot보다 작은값은 앞으로 큰값은 뒤로 def partition(array, left, right): pivotValue = array[right] pivot = left for i in range(int(pivot), int(right)): if array[i] 15일차 - 똑똑똑똑똑 오늘은 음악없이 차분하게 보냈다. 어제는 왜인지 몰라도 잠들기가 힘들었다. 눈 감고 2시간을 보낸후에야 겨우 잠에 들었다. (세상 힘든시간이었음) 그런데 이상하게도 오늘하루는 쌩쌩하다. 마치 8시간은 잔것 같다. 눈만 감고있어도 잠든걸로 치는건가? 아침에 급하게 챙기느라 이어폰 챙기는것을 깜빡했다. 덕분에 오늘하루는 음악없이 보내게 됐는데 하루종일 차분하고 공부하는것 마저 즐거웠다. 그러고보니 음악 때문에 마음이 심하게 뜨는거 같기도하다. 당분간 생각을 해봐야겠다.. 음악 없이 지내볼까? 불편한점 : x 오늘 한 일 : 이산수학 트리 전반부, 병합정렬 Devide and Conquer(mergeSort) 재귀 알고리즘 설계를 기반으로 한다. 따라서 1. 탈출조건 2. 각 하위문제는 본문제보다 작은 문제여야한다. 위 두조건을 만족해야한다. 3단계로 간단히 말하면 1. 분할 : n크기의 배열을 n/2크기의 하위배열 2개로 나눔 2. 정복 : 배열의 크기 1이 될때까지 반복해 재귀적으로 정렬함. 3. 결합 : 하위배열을 합해서 정렬함. 시간 복잡도 1. 분할 : 중간값을 구함, (상수시간) O(1) 2. 정복 : 재귀 횟수는 트리의 level인 log2n임. 3. 결합 : 정렬된 하위배열 요소들을 한번씩 비교후 정렬함 O(n) 각 트리 계층마다 O(n)번의 연산을 하므로 시간복잡도는 트리의 level(재귀횟수) * O(n) 이다. O(nlogn) 선택 정렬 시간복잡도 1. 각 반복마다 최소값 찾기 탐색 횟수는 n번 탐색에서 1번 탐색할때까지 감소 n + n-1 + n-2 + ... + 2 + 1 = 등차수열 (n^2+n/2) 2. swap 상수(c)시간안에 끝남 , n번 호출 c * n 3. 나머지 연산들 마찬가지로 상수시간안에 끝남(c), n번 호출 c *n 합산 결과 = n^2+ n/2 + c*n + c*n = θ(n^2) 선택 정렬은 best 케이스 이든 worst케이스이든 최소값 찾는 범위는 바뀌지 않는다. 따라서 입력 크기 n에 관계없이 θ(n^2) 이전 1 다음
