본문 바로가기

파이썬72

알고리즘 - 병합 정렬 병합 정렬은 배열을 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘입니다. 먼저, 정렬된 배열 a, b를 반복문을 이용한 단순 병합을 해보겠습니다. 이럴 경우 병합하는데 필요한 시간 복잡도는 O(n)입니다. def merge_sorted_list(a, b, c) -> None: pa, pb, pc = 0, 0, 0 # 각 배열의 커서 na, nb, nc = len(a), len(b), len(c) # 각 배열의 크기 print(f'배열 a: {a}') print(f'배열 b: {b}') while pa None: if left < right: center =.. 2020. 12. 8.
알고리즘 - 퀵 정렬(2) 퀵 정렬을 비재귀적으로도 만들 수 있습니다. 스택을 사용해 만들어보겠습니다. 먼저 사용할 스택 코드입니다. from typing import Any class FixedStack: #고정 길이 스택 클래스 class Empty(Exception): #비어 있는 FixedStack에 팝 또는 피크할 때 내보내는 예외 처리 pass class Full(Exception): # 가득 찬 FixedStack에 푸시할 때 내보내는 예외 처리 pass def __init__(self, capacity: int = 256) -> None: # 스택 초기화 self.stk = [None] * capacity # 스택 배열 self.capacity = capacity # 스택의 크기 self.ptr = 0 # 스택 포인.. 2020. 12. 4.
알고리즘 - 퀵 정렬(1) 퀵 정렬은 가장 빠른 정렬 알고리즘으로 알려져 있으며 널리 사용됩니다. 퀵 정렬은 배열 어느 한 기준(피벗)으로 나누어 두 배열로 만들고 나누어진 배열에서도 기준(피벗)을 잡고 계속해서 두 배열로 나누어 모든 그룹에 원소 하나가 남으면 정렬이 완료됩니다. PC가 기준이고 PL, PR은 각각 왼쪽, 오른쪽 커서입니다. 기준이 6이므로 왼쪽에는 6보다 작은 수, 오른쪽에는 6보다 큰 수를 이동시키면 됩니다. 먼저 5와 8은 정렬 시킬 필요가 없습니다. 다음으로 7과 9인데 둘 다 6보다 커서 정렬을 할 수 없습니다. 이럴 때는 PR이 정렬 가능한 수를 찾을 때까지 왼쪽으로 이동시켜 줍니다. 7과 3은 정렬 가능하므로 3과 7의 차리를 바꿔줍니다. 이번에는 1, 2 두 수 모두 기준인 6보다 큽니다. 6보다 .. 2020. 12. 1.
백준 - 1946번 문제 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 코드 import sys T = int(input()) for _ in range(T): N = int(input()) cnt = 1 lst = [] for _ in range(N): x = list(map(int, sys.stdin.readline().rstrip().split())) lst.append(x) lst.sort() min = lst[0][1] for i .. 2020. 11. 25.

티스토리툴바