정렬 알고리즘은 단골 면접 질문이다. 최근에 본 면접에서도 특정 정렬 알고리즘에 대해 설명해 보라는 질문을 받았다. 학교 수업 때나 코테 준비를 하면서 여러 가지 알고리즘을 접해 보았고 전반적으로 이해는 하고 있지만 막상 면접 때 일목요연하게 답하려 하니 만만치 않았다. 그래서 이번에 한꺼번에 다시 정리를 하면서 면접 때 답변한 방식도 대강 정해 놓으려 한다. 1. 거품 정렬 Bubble Sort 시간복잡도: O(n^2) 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 각 리스트를 한 번씩 훑을 때마다 가장 끝 자리의 원소는 정렬에서 제외된다. 각 회전마다 하나의 원소씩 제외하고, 각 원소의 길이 -1(두 개씩 비교하기 때문) 만큼 회전을 반복하기 때문에 ..

백준 문제를 풀다가 계수 정렬에 대해 알게되었다. 상황에 따라서는 상당히 매력적인 배열 방식인 것 같다. 원리는 간단하다. A = [ 4, 5, 4, 6, 3, 3, 3, 1, 2, 7] 라는 리스트가 있을 때, 리스트를 차례대로 돌면서 해당 원소가 몇 번 나왔는지 체크하면 된다. 코드로 살펴보면 다음과 같다. A = [ 4, 5, 4, 6, 3, 3, 3, 1, 2, 7] cnt = [0 for _ in range(8)]# A에서 나올 수 있는 원소의 최댓값 + 1 for a in A: cnt[a] += 1 print(cnt) # [0, 1, 1, 3, 2, 1, 1, 1] for i in range(1, 8): for _ in range(int(cnt[i])): print(i, end= ' ') # ..

Key 기준으로 정렬 sorted( dic.items() ) : 오름차순 정렬 , 정렬된 딕셔너리를 딕셔너리 리스트 형으로 반환 sorted( dic.keys() ) : 오름차순 정렬 , key값만 정렬해서 리스트로 반환 둘 다 sorted를 거치면 [] 안에 씌워져 나오게 된다. reverse = True를 추가하면 내림차순으로 변경됨! dic = {} dic['a'] = 1 dic['c'] = 2 dic['b'] = 4 dic['e'] = 3 print(dic) #{'a': 1, 'c': 2, 'b': 4, 'e': 3} print(sorted(dic.items())) #[('a', 1), ('b', 4), ('c', 2), ('e', 3)] print(sorted(dic.items(), revers..

- 최소 힙(min-heap)의 구조 - 삽입/삭제: O(logN) import heapq로 사용 가능 push: heapq.heappush(hq, item) pop: heapq.heappop(hq) import heapq pq = [] heapq.heappush(pq, 6) heapq.heappush(pq, 12) heapq.heappop(pq) heapify - 리스트 x를 heap으로 변환 x = [4, 3, 1, 2, 5, 6] print(x) # [4, 3, 1, 2, 5, 6] heapq.heapify(x) print(x) # [1, 2, 4, 3, 5, 6] heapq를 사용하는 이유? from queue import PriorityQueue로 일반 우선순위 큐도 사용할 수 있다. 하지만 이..