728x90 반응형 SW Expert Academy3 알고리즘 - 버블 정렬 / 거품 정렬 (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. 자료구조 - 우선 순위 큐(Priority Queue) 1. 우선순위 큐란? 우선순위 큐(Priority Queue)는 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리되는 자료구조이다. 큐는 선형 자료구조이고, 우선순위 큐는 비 선형 자료구조이다. 우선순위 큐는 자료가 들어온 순서와 상관 없이 미리 정한 우선순위대로 나간다. 주로 정의된 우선 순위를 heap condition으로 가지는 heap을 이용해 구현된다. 그 이유는 시간 복잡도와 관련이 있는데, 배열 기반 데이터 삽입의 시간 복잡도는 O(n) 이고 배열 기반 데이터 삭제의 시간 복잡도는 O(1)이다. 또 연결 리스트 기반 데이터 삽입과 삭제의 시간 복잡도도 위와 같다. 하지만 힙 기반 데이터 삽입과 삭제의 시간 복잡도는 각각 O(logn)이다. 따라서 힙을 먼저 공부해야 한다... 2021. 1. 7. 자료구조 - 큐 (Queue) 1. 큐란? 큐(Queue)는 데이터를 일시적으로 쌓아두기 위한 자료구조로, 먼저 들어온 데이터가 가장 먼저 나가는 First In First Out인 구조를 말한다. 위 Reference Code처럼 배열로 큐를 구현해도 되지만, 표준 라이브러리에 정의되어 있기 때문에 include하여 사용하면 편리하다. enqueue란 큐 맨 뒤에 데이터를 추가하는 것을 의미하며 dequeue란 큐 맨 앞쪽의 데이터를 삭제하는 것을 의미한다. 데이터가 삽입되는 곳을 front, 제거되는 곳을 back이라고 한다. 선언 queue 큐 이름; 형태로 선언한다. #include queue s1; queue s2; queue s3; 기본 메소드 1. push() : 큐 맨 뒤에 데이터 추가 = enequeue 2. pop(.. 2021. 1. 6. 이전 1 다음 728x90 반응형
