[Algorithm] 퀵 정렬(quick sort)
퀵 정렬- 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 동작- 호어 분할 방식 -> 리스트에서 첫번째 데이터를 pivot(기준)으로 정한다. -> 왼쪽에서부터 피벗보다 큰 데이터를, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. -> 큰 데이터와 작은 데이터의 위치를 서로 교환- 분할된 두 개의 배열에 대해 재귀적으로 이 과정을 반복- 한번 진행될 때마다 최소한 하나의 피벗은 최종적으로 위치가 정해진다- 퀵 정렬의 시간복잡도 : O(NlogN) -> 삽입 정렬과 달리 데이터가 거의 정렬되어 있는 최악의 경우 시간복잡도가 O(N^2) 이다예시array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]def quick_sort(array,..
2024. 4. 4.
[백준] 16926번 파이썬 - 배열 돌리기 1
첫번째 풀이2 ≤ N, M ≤ 3001 ≤ R ≤ 1,000min(N, M) mod 2 = 01 ≤ Aij ≤ 108 사실 문제 제한이 다음과 같아서 풀면서도 아.. 시간 초과 날 것 같은데 라는 생각을 하긴 했다.내 풀이대로라면 r * min(n,m) // 2 * (각 for문에서 돌아가는 while 문의 수) 만큼 계산하는데대충 계산해보아도 시간 제한 1초가 넘어가게 생겼다.진작 풀이 갈아엎을껄.. 혹시나 해서 짰는데 역시나 시간초과 문제가 생겼다. n,m,r = map(int,input().split())array = []# 하우상좌dx = [1,0,-1,0]dy = [0,1,0,-1]for _ in range(n): array.append(list(map(int,input().split())..
2024. 3. 29.
