[자료구조] 힙(heapq)
힙(heapq)이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 최소 힙(min heap) 루트 노드가 가장 작은 값을 가진다. 따라서 값이 작은 데이터가 우선적으로 제거된다. 즉, 부모 노드가 항상 자식 노드보다 작다. 최대 힙(max heap) 루트 노드가 가장 큰 값을 가진다. 따라서 값이 큰 데이터가 우선적으로 제거된다. 즉, 부모 노드가 항상 자식 노드보다 크다.파이썬에서 heapq 모듈을 사용하여 구현할 수 있다.import heapqq= []a = [4,9,6,11,8]for i in range(len(a)): heapq.heappush(q,a[i])print(q)#q = [4, 8, 6, 11, 9]for i in range(len(a)): prin..
2024. 6. 24.
[Algorithm] 파이썬 정렬, lambda 사용
우선 파이썬에서 sort()와 sorted() 함수를 통해 정렬을 할 수 있다.sort() 원본 자체를 정렬시켜 준다.a = [1,5,2,7]a.sort() print(a)#a = [1,2,5,7] sorted() 원본을 변형시키지 않고 새로운 list를 반환한다.a = [1,5,2,7]b = sorted(a)print(a)print(b)#a = [1,5,2,7]#b = [1,2,5,7] reverse 정렬 기능은 기본적으로 오름차순으로 제공한다. 내림차순으로 정렬하고 싶은 경우, reverse 파라미터를 통해 정렬할 수 있다.a = [1,5,2,7]a.sort(reverse=True)print(a)#a = [7,5,2,1] key 정렬 조건을 설정할 함수를 넣을 수 있다.a = ['love','i','..
2024. 6. 20.
[Algorithm] Backtracking(백트래킹) 순열 및 조합 구현하기 itertools
우선 순열과 조합의 차이를 알아보자. 순열 : 원소들의 순서를 고려하여 나열하는 것 (원소의 순서가 다르면 다른 순열로 취급) 조합 : 원소들의 순서를 고려하지 않고 나열하는 것 (선택된 원소의 순서는 고려되지 않음) 파이썬 라이브러리 중 하나인 itertools를 사용하면 조합과 순열을 쉽게 구할 수 있다. from itertools import permutations, combinations arr = [1,2,3] k = 2 npr = list(permutations(arr, 2)) # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)] ncr = list(combinations(arr, 2)) # [(1, 2), (1, 3), (2, 3)] 그러나.. 라이브러리..
2024. 4. 13.
