힙

정렬 알고리즘 비교

bubble: 인접한 두개의 원소를 비교하여 자리를 교환하는 방식 첫번쨰 원소부터 인접한 원소끼리 계속 자리를 교환 한 단계가 끝나면 가장 큰 원소가 마지막 자리에 고정 정렬이 되어있어도 모든 수를 다 확인하기 때문에 가장 비효율적인 정렬 알고리즘 selection: 기준 위치에 맞는 원소를 선택하고 자리를 교환하는 방식 원소를 돌며 가장 작은 값을 찾는다. 첫번째 원소와 바꿔준다. 첫번째 원소를 제외하고 원소를 돌며 가장 작은 값을 찾는다. 두번째 원소와 바꿔준다. 계속 진행 버블 정렬을 일부 개선함 insertion: 정렬되어 있는 부분 집합에 정렬할 새로운 원소의 위치를 삽입하는 방식 정렬된 집합 S와 정렬되지 않은 집합 U로 나눈다. U에서 맨 앞의 원소를 꺼내서 S의 맨 뒤부터 비교해준다. 자신..

[python] 프로그래머스 - 디스크 컨트롤러

🤔문제 해결 Lv3 | 우선순위 큐 파이썬에서는 heapq 를 사용합니다. 먼저 현재 시간을 항상 계산해 줍니다. 현재 시간보다 투입시간이 작은 작업들을 힙큐에 넣어줍니다. 힙큐에 값이 여러개 들어있더라도, heappop() 을 하게 되면 작업시간이 가장 짧은 작업이 나오게 됩니다. ( 힙큐에서는 최솟값이 나오게 됩니다 ) 작업시간만큼 현재시간 을 늘려주고, 해당 작업의 대기시간+작업시간 을 따로 저장해 둡니다. 한 작업이 끝나고 나면 시간이 흘렀기 때문에 다시 현재 시간보다 투입시간이 작은 작업들을 힙큐에 넣어줍니다.(아까 넣은 작업 제외) 똑같이 heappop() 으로 현재시간과 작업시간을 저장합니다. 💨 업무투입시간이 오름차순 정렬이 안되어있어서 먼저 정렬을 해줘야 합니다. 💻소스 코드 import..