728x90 반응형 BASE/Alogorithm15 알고리즘 - 삽입 정렬 (Insertion Sort) 알고리즘 - 삽입 정렬 (Insertion Sort) 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 최악의 경우 시간복잡도 : (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2= O(n&2) (최악의 경우) 최선의 경우 시간복잡도 : O(n) (정렬이 모두 되어있는 경우에는 한 번 씩만 비교하면 되기 때문) [예시] 각 회전 마다 연두색 밑줄이 되어 있는 부분이 이미 정렬된 배열 부분! [ 코드 ] def insertion_sort(arr): for end in range(1, len(arr)): for i in range(end, 0, -1): if arr[i - 1] >.. 2021. 1. 11. 알고리즘 - 버블 정렬 / 거품 정렬 (Bubble Sort) 알고리즘 - 버블 정렬 / 거품 정렬 (Bubble Sort) 버블 정렬은 서로 인접한 두 원소를 검사해 정렬하는 알고리즘이다. 첫 번째 자료와 두 번째 자료, 두번째 자료와 세 번째 자료, ... , 마지막-1 번째 자료와 마지막 자료의 대소를 비교해 교환한다. 1회전 할 때 마다 마지막 자료는 가장 큰 값이 되므로 (조건이 오름차순일 경우) 정렬에서 제외한다. [ 시간복잡도 ] (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 = O(n^2) [ 예시 ] [ 코드 ] size = int(input()) arr = [] for i in range(size): arr.append(int(input())) for i in reversed(range(size)): for j in ra.. 2021. 1. 8. 알고리즘 - 재귀 (Recursion) 알고리즘 - 재귀 (Recursion) 재귀는 수학이나 컴퓨터 과학 등에서 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. 주로 이 방법은 함수에 적용한 재귀 함수(Recursion Function)의 형태로 많이 사용된다. 재귀함수를 왜 사용해야 할까? 점화식을 세웠을 때, 인자만 바뀌고 같은 로직을 사용해야하는 함수가 필요한 경우 반복문보다 재귀 함수가 적합하다. 변수 사용을 줄여주는 장점도 있기 때문에 사이드 이펙트를 최소화할 수 있고 코드의 가독성도 향상된다. 예시문제 주어진 수의 Factorial 값을 구해 아래와 같이 출력하시오. 주어지는 수는 1 이상 20 이하의 수이다. def factorial(num): if num == 0: return 1 else: return num * f.. 2021. 1. 5. 이전 1 2 3 다음 728x90 반응형
