본문 바로가기

Python/알고리즘 및 자료구조

 (6)
스택(Stack) 스택 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있음 데이터를 밀어넣는 것 즉 저장은 push, 데이터를 꺼내는 것 즉 처리(삭제) 는 pop 이라고 함 top 을 이용하면 데이터를 삭제하지 않고 맨 위의 값을 가져옴 스택 구현 class Stack_ex: #스택 생성하는 클래스 def __init__(self,max): self.__top = -1 self.__stack_list = [] self.__max = max def push(self,data): #데이터 push if self.__top == self.__max -1: print("저장 공간 부족") return False self.__top += 1 self.__sta..
퀵 정렬(quick sort) 퀵 정렬 퀵 정렬은 합병 정렬과 같이 분할 정복 알고리즘의 종류중 하나로 기준값(pivot) 을 두어 기준값 보다 작으면 왼쪽 크면 오른쪽에 정렬하는 방식의 알고리즘 이다. 시간복잡도 평균: O(n log n) 최악: O(n2) -> 배열이 이미 정렬되 있거나 역순으로 정렬될경우 import random def quick_sort(li,start,end): l = start #시작을 왼쪽 인덱스에 저장 r = end #마지막을 오른쪽 인덱스에 저장 pivot = li[int((l+r)/2)] #배열의 중간값을 피벗으로 설정 while l pivot: #오른쪽값이 피벗보다 작거나 같으면(피벗값이 가장 작을경우 대비) 종료 r = r-1 #종료전까지 인덱스를 감소시킴 if l start:#만약 오른쪽 인덱스..
합병 정렬(merge sort) 분할 정복 알고리즘 커다란 문제를 작은 문제로 분할하여 해결해 나가는 방법론 합병정렬(merge sort) 알고리즘 분할 정복 알고리즘을 적용하여 정렬할 배열을 더이상 나눠질 수 없는 배열로 나누어 배열 단위별로 정렬 시간복잡도: O(n log n) 배열을 비교하여 정렬 tmp = [None] #임시배열 def merges(li,left,mid,right):#쪼갠 배열을 비교하여 정렬하는 메서드 l_idx = left # 왼쪽 배열 인덱스 r_idx = mid +1 # 오른쪽 배열 인덱스 c_idx = left # 작은수가 들어가는 배열 현재위치 t_idx = 0 #남은 원소를 한꺼번에 저장할때 사용할 임시 인덱스 while l_idx
선택정렬 선택정렬 선택 정렬이란 가장 작은(혹은 큰) 원소를 선택하여 그 값을 맨앞에 위치한 값과 바꿔주는 정렬이다. 시간복잡도:O(n2) def select_sort(li): for i in range(0,len(li),1): # 0 부터 배열의 길이 -1 만큼 반복 min = i #i 를 min 에 저장(최소값의 인덱스) for j in range(i,len(li),1):#i 부터 배열의길이 -1 만큼 반복 if li[min] > li[j]: #인덱스 min 자리보다 j의 자리가 더 클 경우 min = j # min 을 j 로 변경 temp = li[i] #비교 후 i 인덱스 의 값을 li[i] = li[min] # min 인덱스 의 값과 변경 li[min] = temp print(li) return li s..
팩토리얼(factorial)과 재귀호출 재귀호출 재귀호출 이란 함수 내에서 자기 자기 자신을 또다시 호출하는 것을 의미한다. 팩토리얼 팩토리얼 이란 그 수보다 작거나 같은 모든 양의 정수의 곱으로 재귀호출을 이용한 간단한 알고리즘 이다. def factorial_func(n): print("호출과정 = ",n) if n == 1: #n이 1 일경우 더 작은 양의 수가 없으니 1 리턴 return 1 return n * factorial_func(n - 1) #n 과 n-1을 매개변수로 준 자기 자신을 곱함 #결과적으로 n * n-1 * n-2 .... 1 의 결과가 리턴됨 result = factorial_func(5) print("결과 = ",result) 과정 및 결과 호출과정 = 5 호출과정 = 4 호출과정 = 3 호출과정 = 2 호출과..
버블정렬(Bubble Sort) 버블정렬 버블정렬이란 인접한 두 원소를 비교하여 순서에 맞지 않을 경우 변경하는 정렬이다. 속도가 느린 알고리즘 이지만 코드가 비교적 간단하다. 버블정렬 시간복잡도: O(n2) def bubble_func(li): for i in range(len(li)-1,-1,-1):# 배열의 길이-1 부터 0 까지 반복 for j in range(0,i,1): # 0 부터 i-1 까지 반복 if li[j] > li[j+1]: # j번인덱스와 다음 인덱스 비교하여 temp = li[j] # 이전 인덱스가 더 큰경우 li[j] = li[j+1] # 이전인덱스와 다음 인덱스의 숫자 변경 li[j+1] = temp print(li) return li bubble_list = bubble_func([1,5,3,8,2,6,7..

티스토리툴바