sorting4 [Python] Leader https://codility.com/media/train/6-Leader.pdf Leader는 크기 N인 배열A 에서 과반수 이상 (N//2+1) 의 갯수를 가지고 있는 요소를 말한다. Leader를 조사하는 방법을 아래와 같이 정리하였다. 1. Sorting 정렬 후 중앙값의 카운트를 계산한다. 카운트가 n//2 보다 크다면 Leader에 해당한다. Detected time complexity O(N * log(N)) def solution(A): n = len(A) s_A = sorted(A) leader = None count = 0 for i in range(n): if s_A[i] == s_A[n//2]: count += 1 if count > n // 2: leader = s_A[n//2] .. 2021. 4. 5. [Python] 6.4. Triangle https://app.codility.com/demo/results/trainingX6JCFR-MQJ/ Test results - Codility An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P A[R], A[Q] + A[R] > A[P], A[R] + A[P] > A[Q]. For example, consider array A such that: A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A app.codility.com 인풋 데이터의 사이즈가 10만 아래이기 때문에 완전탐색하기로 결정하였다. 순열을.. 2021. 3. 26. [Python]Insertion Sorting 삽입정렬은 자기 위치를 기준으로 앞 인덱스의 값과 비교해서 크기가 작다면 앞에다가 삽입(swap)하는 것이다. 장점은 N의 크기가 작을때 효과적이라는 것 단점은 성능이 좋지 않다는 것이다. 평균 시간복잡도 O(N^2) 정리 현재 인덱스를 정렬될 리스트의 끝으로 보고 전체 순회 현재 인덱스 값을 앞 인덱스 값과 비교/스와핑 후 인덱스 업데이트 반복 업데이트 반복 조건은 idx > 0 and arr[idx-1] > arr[idx def insertion_sort(a): n = len(a) for i in range(n): for j in range(i-1, -1, -1): if a[i] < a[j]: a[i], a[j] = a[j], a[i] i = j 2019. 5. 10. [Python]Bubble Sorting 버블정렬은 거품이 올라오는 모양처럼 정렬한다고 해서 붙여진 이름이다. 장점은 구현하기 가장 간단하다는 특징을 가지고 있다 단점은 성능이 좋진 않다는 것. 평균 시간 복잡도 O(N^2) 정리 인접한 값과 비교 후 교환 스와핑 위한 공간 1개 필요 총 n-1번 루핑 def bubble_sort(arr): for _ in range(len(arr)-1): for j in range(len(arr)-1): if arr[j] > arr[j+1]: arr[j],arr[j+1] = arr[j+1],arr[j] return arr 2019. 5. 9. 이전 1 다음 728x90 반응형