본문 바로가기

알고리즘/개념

 (8)
[알고리즘] 정렬 알고리즘 총 정리 Bubble sort (거품 정렬) n개의 원소를 가진 배열을 정렬할 때, 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식 가장 큰 값을 배열의 맨 끝에다 이동시키면서 정렬 두개의 중첩된 for문을 이용해 정렬 swap을 많이 하기 때문에 삽입 정렬과 선택 정렬보다 시간이 오래걸린다. Selection Sort (선택 정렬) 주어진 데이터 중 최소값을 찾고, 맨 앞자리와 바꿔준다. 최소값을 찾고 맨 앞자리+1 인덱스와 바꿔준다... 반복 삽입 정렬 (Insertion Sort) 두번째 인덱스부터 시작해서 해당 인덱스(key 값) 앞에 있는 데이터들과 비교해 key 값보다 작은 데이터를 만나면 그 뒤에 넣는다. 장점 거의 정렬 된 경우 매우 효율적이다. 최선의 경우 O(N)의 시간복잡도를 갖는다..
[알고리즘] 파이썬 시간복잡도 정리 Big-O 표기 1. O(1) 상수시간 입력값 n이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한단계만 거침 2. O(log n) 로그시간 입력값 n이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬 3. O(n) 직선적 시간 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐 4. O(n^2) 2차 시간 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱 5. O(c^n) 지수 시간 문제를 해결하기 위한 단계의 수는 주어진 상수값 c의 n 제곱 시간 복잡도 List deque dictionary 정렬 알고리즘
[알고리즘] 이진 탐색 (Binary Search) 이진 탐색 이란? 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 오름차순으로 정렬되어 있어야 한다 파이썬 코드 구현 def binary_search(data, search): print(data) if len(data) == 1 and search == data[0]: return True if len(data) == 1 and search != data[0]: return False if len(data) == 0: return False medium = len(data) // 2 if search == data[medium]: return True else: if search > data[medium]: return binary_search(data[medium+1:], sea..
[알고리즘] 퀵 정렬 (quick sort) 퀵 정렬 이란? 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)으로 모으는 함수를 작성 각 왼쪽(left), 오른쪽(right)은 재귀용법으로 다시 동일 함수를 호출하여 반복함 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 return 파이썬 코드 구현 def qsort(data): if len(data) item ] right = [ item for item in data[1:] if pivot
[알고리즘] DP (동적계획법) DP(Dynamic Programming) 란? 입력 크기가 작은 부분문제들을 해결하고 난 후, 이것을 활용하여 큰 크기의 부분문제를 해결, 최종적으로 전체문제를 해결 상향식 접근법임 - 가장 최하위 해답을 구한 후, 이를 이용해서 상위 문제를 풀어가는 방식 Memorization 기법을 사용 - 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 해서 전체 실행속도 빠르게 재귀 vs 동적계획법 n을 입력받았을 때 피보나치 수열로 결과값을 출력하시오 #재귀호출 def fibo(num): if num
[알고리즘] 선택정렬 (selection sort) 선택정렬이란? 주어진 데이터 중, 최소값을 찾음 해당 최소값을 데이터 맨앞의 값과 자리바꿈 맨앞의 위치를 빼고 동일한 방법으로 반복 알고리즘 구현 selection_sort(data): for stand in range(len(data)-1): lowest = stand for index in range(stand + 1, len(data)): if data[lowest] > data[index]: lowest = index data[lowest], data[stand] = data[stand], data[lowest] return data
[알고리즘] 삽입정렬 (insertion sort) 삽입정렬이란? 두번째 인덱스부터 시작한다 key값 앞에 있는 데이터(front)부터 비교해서 key < front 이면, front값을 뒤 인덱스로 복사 key보다 작은 데이터를 만날때까지 반복, 작은 데이터를 만나면 바로 뒤에 key값을 이동 예 : data_list = [9, 3, 2, 5] 1번째 실행 : key=9, [9,3,2,5] 2번째 실행 : key=3, front=9, 자리바꿈 [3,9,2,5] 3번째 실행 : key=2, front=9, 자리바꿈 / key=2, front=3, 자리바꿈 [2,3,9,5] 4번째 실행 : key=5, front=9, 자리바꿈 3보다 5가 크므로 끝 [2,3,5,9] 알고리즘 구현 def insertion_sort(data): for index in ran..
[알고리즘] 버블정렬 (bubble sort) 버블정렬이란? 두개의 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾼다 예 : data_list = [1, 9, 3, 2] 1차 로직 1, 9 비교 : 자리바꿈X [1,9,3,2] 9, 3 비교 : 자리바꿈O [1,3,9,2] 9, 2 비교 : 자리바꿈O [1,3,2,9] 2차 로직 1, 3 비교 : 자리바꿈X [1,3,2,9] 3, 2 비교 : 자리바꿈O [1,2,3,9] 3, 9 비교 : 자리바꿈X [1,2,3,9] 3차 로직 1, 2 비교 : 자리바꿈X [1,2,3,9] 2, 3 비교 : 자리바꿈X [1,2,3,9] 3, 9 비교 : 자리바꿈X [1,2,3,9] 알고리즘 구현 n개의 리스트가 있는 경우, 최대 n-1번의 로직 적용 로직이 경우에 따라 일찍 끝날수..

티스토리툴바