목록동적계획법(Dynamic Programming) (1)

개발 기록장

05. 자료구조/알고리즘 풀기(5)

학습 주제: 힙(Heap), 동적계획법(Dynamic Programming), 깊이/너비 우선 탐색(DFS/BFS) 연습 문제 풀이 힙(Heap): 더 맵게 문제의 해결 - 방법(1) 알고리즘의 복잡도 -최악의 경우: 수가 하나 남을 때까지 섞어야 하는 경우(n-1)회 -각 단계('섞는 일')에서 요구되는 계산량: 정렬된 리스트에 순서에 맞춰 원소 삽입: O(n) -전체 문제 풀이의 복잡도: O(n^2) 지나치게 복잡도가 높음 문제의 해결 - 방법(2) -최소/최대 원소를 빠르게 꺼내기 -힙(heap) *max heap *min heap 힙(Heaps) -성질: 최대/최소 원소를 빠르게 찾을 수 있음 -연산: 힙 구성(heapify): O(NlogN) 삽입(insert): O(logN) 삭제(remove..
데브코스(DE)/자료구조와 알고리즘 2024. 3. 29. 17:13
이전 Prev 1 Next 다음