본문 바로가기

알고리즘3

[알고리즘 공부] 2. Selection Sort (선택 정렬) 버블 정렬과 비해도 크게 어렵지 않은 쉬운 정렬 중 하나인 Selection Sort(선택 정렬)입니다. 선택 정렬은 수열을 배회하다가 가장 작은 수를 찾아 맨 앞으로 내보내고 그 다음 숫자부터 반복하는 쉬운 정렬 입니다. 버블 정렬과 마찬가지로 구현의 간단함을 대가로 시간 복잡도를 잃었습니다. 선택 정렬의 시간 복잡도는 O(n^2)으로 버블 정렬과 동일합니다. 크게 어려운 것이 없으니 마찬가지로 파이썬 구현으로 넘어가겠습니다. input = [14,54,5,2,1,36,324,34,213,6,7,4] def SelectionSort(input): length = len(input) # 한바퀴 돌때 마다 시작 숫자는 한칸씩 뒤로 for x in range(length): for y in range(x, .. 2021. 5. 25.
[알고리즘 공부] 1. Bubble Sort (버블 정렬) Bubble Sort(이하 버블 정렬)은 가장 구현하기 쉬운 형태의 정렬 알고리즘입니다. 앞에서부터 숫자 2개씩 비교하여 작은 원소와 큰 원소의 자리만 바꿔주며 반복하는 형태입니다. 버블 정렬은 구현하기도 정말 쉽지만 쉬운 대가로 시간 복잡도를 잃었습니다. ㅠㅠ 버블 정렬의 시간 복잡도는 O(n^2) 입니다. 대부분의 경우에서 쓰이지 않는다고 하니 간단하게 구현만 하고 거품 정렬은 넘어가도록 하겠습니다. def BubbleSort(input): # 두개씩 비교하므로 길이에서 -1 length = len(input) -1 # 한바퀴 돌때마다 가장 큰 수는 맨 뒤로 가니까 # 비교해도 되는 숫자는 하나씩 줄여도 된다. for x in range(length, 0, -1): for y in range(x): .. 2021. 5. 25.
알고리즘 문제 풀때 보이는 O(n) 은 무엇일까? (시간 복잡도, 공간 복잡도) 알고리즘 문제를 풀 때 보면 시간 복잡도니, 공간 복잡도니, O(n)이니 무슨 소리인지 모르겠는 말이 많습니다. Big O 그러니까 O(n) 같은 표시가 무엇인지 궁금해서 클릭하셨겠지만 시간복잡도랑 공간 복잡도부터 정리해보겠습니다. 시간 복잡도는 쉽게 말하면 들어오는 데이터 갯수 n에 대해 몇 번 연산을 하는가 라고 보시면 되겠습니다. input_data = [x for x in random.sample(range(1000), 10)] 예를 들어 위와 같은 길이 10 짜리 랜덤 수열이 생성 되고 (정렬 연산 없이) 가장 큰 수를 찾는다고 가정해봅시다. 그러기 위해서는 모든 수를 돌아봐야겠죠? 그러면 input_data[0]에서 input_data [9]까지 모두 돌게 될 것입니다. 주어진 데이터 n 만큼.. 2021. 5. 25.

티스토리툴바