본문 바로가기

전체 글

 (50)
파이썬의 시스템 정렬 1. 파이썬 기본 정렬: sorted() vs .sort()2. key 매개변수로 정렬 기준 지정하기words = ['apple', 'banana', 'kiwi', 'mango']# 길이 기준 정렬 (오름차순)sorted(words, key=len) # ['kiwi', 'mango', 'apple', 'banana']# 길이 기준 정렬 (내림차순 / reverse=True)sorted(words, reverse=True, key=len) # ['banana', 'apple', 'mango' ,'kiwi'] 3. 2차원 배열(리스트) 정렬 students = [ ["Charlie", 85], ["Alice", 85], ["Bob", 95]]# 점수 기준 오름차순 정렬students.so..
Kadane's 알고리즘 (MCSS Maximum Contiguous Subsequence Sum) 주어진 배열에서 연속된 부분 구간의 합 중 최댓값을 구하는 문제 MCSS(Maximum Contiguous Subsequence Sum)arr = [1, 2, 3, 4]max_sum = arr[0] # 전체 중 최댓값 저장current_sum = arr[0] # 현재 구간의 누적합for i in range(1, len(arr)): if current_sum + arr[i] > arr[i]: current_sum += arr[i] # 누적합 유지 else: current_sum = arr[i] # 새 구간 시작 if current_sum > max_sum: max_sum = current_sum # 최댓값 갱신print..
특수 정렬 (기수 정렬, 계수 정렬) 기수정렬(radix sort) : 각 자릿수를 기준으로 정렬숫자나 문자열의 자릿수를 기준으로 데이터를 정렬자릿수의 개수가 같은 경우 유용ex) 계좌번호, 날짜, 주민등록번호, 인터넷 주소, 전화번호오른쪽에서 왼쪽으로 기수(radix, base)별로 안정성을 유지하면 정렬 계수 정렬(counting sort) : 숫자의 크기를 비교하지 않고, 각 숫자가 몇 번 나오는지를 세서 정렬하는 방법과정 1 : array의 각 값을 인덱스로 하는 counting배열의 값을 1씩 증가시킨다 0은 1번1은 2번2는 1번..7은 3번 과정 2 : counting의 배열의 값을 누적합으로 변환시킨다 과정 3 array의 오른쪽부터 탐색한다counting 배열은 "해당 값 이하의 원소가 몇 개인가"를 알려준다원소를 resul..
계산복잡도 vs 시간복잡도 계산복잡도는:→ “문제 자체가 풀리는 데 필요한 최소 시간”→ 이건 문제 전체의 하한선시간복잡도에서의 최선은:→ “어떤 알고리즘이 특별히 좋은 경우에 걸리는 시간”→ 이건 특정 알고리즘의 최선의 경우즉,계산복잡도는 “문제 입장”에서의 최선시간복잡도는 “알고리즘 입장”에서의 성능 (평균, 최악, 최선) ✈️ 비행기를 타고 서울 → 부산 간다고 하자계산복잡도:✨ "서울에서 부산까지 갈 수 있는 가장 빠른 수단으로 걸리는 최소 시간"→ 비행기 타면 1시간. 이게 계산복잡도.시간복잡도의 최선:🚗 어떤 사람이 차를 타고 갔는데평소엔 5시간 걸리지만오늘은 도로가 뻥 뚫려서 3시간 걸림→ 이게 특정 알고리즘(=차) 의 최선 시간🚨 즉, 비행기(=최고 알고리즘)가 있을 수 있는데,자동차(=다른 알고리즘) 가 최선일..
분할 알고리즘과 퀵정렬 퀵정렬(Quick sorting) 알고리즘 분할 알고리즘으로 분할된 부분 배열을 재귀적으로 정렬하는 알고리즘 분할(partition) 알고리즘분할 원소(partition element 혹은 pivot item)보다 작은 원소는 왼쪽 배열로, 큰 원소는 오른쪽 배열로 분할하는 알고리즘def partition(a, low, high): pivot = a[low] # 배열의 첫 요소를 pivot으로 설정 i = low + 1 # 왼쪽 포인터는 pivot 다음 위치에서 시작 j = high # 오른쪽 포인터는 배열의 끝에서 시작 while 1: while i = low + 1 and a[j] > p..
병합 알고리즘과 병합 정렬 병합(merge) 알고리즘2개의 정렬된 배열을 하나의 정렬된 배열로 합치는 알고리즘각 부분 배열의 맨 앞 키를 비교하여 더 작은 원소를 새로운 배열로 순차적으로 카피 예시2개의 분리된 정렬된 배열을 병합하는 알고리즘#크기가 h인 정렬된 배열 a와 크기가 m인 정렬된 배열 b를 배열 list1로 병합하는 알고리즘def merge(a,h,b,m): list1 = [] i = 0 #a index j = 0 #b index k = 0 #list1의 인덱스 while k = b[j]: list1.append(b[j]) j += 1 k += 1 return list1  병합정렬(merge sorting)반으로 나눈 부분 배열을..
분할정복 & 재귀 알고리즘 기본 개념 분할정복법 (Divide and Conquer)문제를 작게 쪼개서 해결한 뒤, 다시 합쳐서 전체 문제를 푸는 방식3단계 과정분할(Divide): 문제를 더 작은 하위 문제로 나눈다.정복(Conquer): 하위 문제를 재귀적으로 해결한다.통합(Combine): 하위 문제들의 해를 합쳐서 원래 문제를 해결한다.특징하향식(Top-Down) 접근대표 알고리즘: 병합정렬, 퀵정렬동적 프로그래밍은 이와 반대로 상향식(Bottom-Up) 방식 사용 재귀 알고리즘 (Recursion)자기 자신을 호출해서 문제를 해결하는 방식특징문제를 더 작은 동일한 문제로 줄여나감종료 조건(Base Case) 꼭 있어야 함 → 없으면 무한 호출 = 스택 오버플로우 발생구조가 간단하고 우아한 코드 작성 가능일부 **꼬리 재귀(Tail ..
알고리즘_선택 정렬 선택 정렬은 가장 작은(또는 가장 큰) 원소를 선택하여 앞쪽으로 이동시키는 정렬 알고리즘. 안정적이지 않다.단순하지만 비효율적인 정렬 방법 중 하나로, 작은 데이터셋에서는 사용될 수 있지만, 큰 데이터에서는 성능이 좋지 않다.= O(N^2) 주어진 리스트에서 가장 작은 원소를 찾아 맨 앞 원소와 교환한다.그다음 두 번째 작은 원소를 찾아 두 번째 위치로 이동한다.이 과정을 마지막 원소 전까지 반복하면 정렬이 완료된다. arr = [7,4,6,6,8,9,2,5]for i in range(len(arr)): min_index = i for j in range(i + 1, len(arr)): if arr[min_index] > arr[j]: min_index = j ..

티스토리툴바