728x90 반응형 책 리뷰/파이썬 알고리즘 인터뷰17 5장. 정렬(1) - 퀵정렬이란? 퀵 정렬피벗을 기준으로 좌우를 나누는 특징 때문에 파티션 교환 정렬이라고도 불린다.병렬 정렬과 마찬가리고 분할 정복 알고리즘피벗이라는 개념을 통해 피벗보다 작으면 왼쪽, 크면 오른쪽과 같은 방식으로 파티셔닝하면서 쪼개 나간다.이 중에서도 로무토 파티션이란 항상 맨 오른쪽의 피벗을 택하는 단순한 방식으로, 토니 호어가 고안한 최초의 퀵 정렬 알고리즘보다 훨씬 더 간결하고 이해하기 쉽기 때문에 퀵 정렬 소개 시 항상 맨 처음에 언급됨 퀵 정렬 수도코드Quicksort(A, lo, hi) if lo 기본 조건 확인: Quicksort(A, lo, hi)는 lo 피벗 분할:partition(A, lo, hi) 함수는 A[lo]부터 A[hi]까지의 구간에서 피벗을 기준으로 요소들을 나눈다.이 함수는 피벗 위치를.. 2024. 11. 25. 9장 스택,큐(3) - 스택이란? (예제-일일 온도) 매일의 화씨 온도 리스트 T를 입력 받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라.입력: T = [73, 74, 75, 71, 69, 72, 76, 73]출력: [1,1,4,2,1,1,0,0] def dailyTemperatures(T: list[int]) -> list[int]: answer = [0] * len(T) # 결과를 저장할 리스트, 초기값은 0 stack = [] # 인덱스를 저장하는 스택 for i, cur in enumerate(T): # 인덱스(i)와 현재 온도(cur)를 함께 순회 # 스택이 비어 있지 않고, 현재 온도가 스택의 마지막 인덱스에 해당하는 온도보다 높다면 while stack and cur.. 2024. 11. 20. 9장 스택,큐(2) - 스택이란? (예제-중복문자제거) 중복된 문자를 제외하고 사전식 순서로 나열하라입력: "bcabc" / 출력: "abc"입력: "cbacdcbc" / 출력: "acdb" 풀이. 스택을 이용한 문자 제거import collectionsdef removeDuplicateLetters(s: str) -> str: counter, seen, stack = collections.Counter(s), set(), [] for char in s: counter[char] -= 1 # 현재 문자의 개수를 하나 줄임 if char in seen: # 이미 스택에 추가된 문자라면 건너뜀 continue # 스택에서 문자를 제거할 조건: .. 2024. 11. 19. 9장 스택,큐(1) - 스택이란? (예제-유효한 괄호) 스택(Stack)과 연결 리스트를 활용한 ADT 구현 및 유효한 괄호 문제 풀이스택(Stack)은 LIFO(Last In, First Out) 구조를 가지는 대표적인 자료구조이다. 이는 가장 나중에 들어간 데이터가 가장 먼저 나오는 구조로, 다음 두 가지 주요 연산을 지원한다.push(item): 스택의 맨 위에 데이터를 추가하는 연산pop(): 스택의 맨 위 데이터를 제거하고 반환하는 연산 1. 연결 리스트를 활용한 스택 ADT 구현스택은 배열 또는 연결 리스트를 이용하여 구현할 수 있다. 여기서는 연결 리스트를 활용한 스택 구현 방식을 살펴보려고 한다. 연결 리스트 기반 스택 구현 코드# 연결 리스트의 노드를 나타내는 클래스class Node: def __init__(self, item, ne.. 2024. 11. 18. 이전 1 2 3 4 5 다음 728x90 반응형
