[Python] 부분집합 - 순열1
1. [1,2,3]의 부분집합 구하기 def f(i,N): # i부분집합에 포함될지 결정할 원소의 인덱스, N 전체 원소개수 if i == N : # 한개의 부분집합 완성 print(bit, end=' ') for j in range(N): if bit[j]: sum += a[j] print(a[j],end=' ') print() else: bit[i] = 1 f(i+1,N) bit[i] = 0 f(i+1,N) return a = [1,2,3] bit = [0,0,0] f(0,3) 2. 부분집합 합 구하기(sum추가) def f(i,N): # i부분집합에 포함될지 결정할 원소의 인덱스, N 전체 원소개수 if i == N : # 한개의 부분집합 완성 print(bit, end=' ') sum = 0 fo..
2022. 3. 5.
[Python] 퀵 정렬
퀵 정렬 주어진 배열을 두 개로 분할하고, 각각을 정렬 최악의 시간 복잡도 O(n^2), 합병정렬보다 좋지 못하다 평균적으로 가장 빠름( O(nlogn)) 합병정렬과 다른점 합병정렬은 그냥 두 부분으로 나누는 반면에, 퀵정렬은 분할할 때, 기준 아이템(pivot item) 중심으로, 기준보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 위치 각 부분 정렬이 끝난 후, 합병정렬은 합병이란 후 처리 작업이 필요하나, 퀵정렬은 필요하지 않음 def quickSort(a,begin,end): if begin < end: p = partition(a,begin,end) quickSort(a,begin,p-1) quickSort(a,p+1,end) def partition(a,begin,end): pivot = (begi..
2022. 3. 1.
