DevLog

알고리즘/기술면접 완전 정복 올인원 패키지 Online 최소 신장 트리의 이해 2 - 참고_개선된 프림 알고리즘 최소 신장 트리의 이해 2 - 개선된 프림 알고리즘의 시간 복잡도 백트래킹 - 백트래킹 기법의 이해 시간 복잡도 최악의 경우, while 구문에서 모든 간선에 대해 반복하고, 최소 힙 구조를 사용하므로 O(𝐸𝑙𝑜𝑔𝐸ElogE) 시간 복잡도를 가짐 개선된 프림 알고리즘 간선이 아닌 노드를 중심으로 우선순위 큐를 적용하는 방식 초기화 - 정점:key 구조를 만들어놓고, 특정 정점의 key값은 0, 이외의 정점들의 key값은 무한대로 놓음. 모든 정점:key 값은 우선순위 큐에 넣음 가장 key값이 적은 정점:key를 추출한 후(pop 하므로 해당 정점:key 정보는 우선순위 큐에서 삭제됨), (e..

알고리즘/기술면접 완전 정복 올인원 패키지 Online 20. 해쉬 테이블 - 4 21. 해쉬 테이블 - 5 기본 자료구조 - 01. 기초 문제풀이 기억에서 잊히기 전에 해쉬 테이블 복습과 추가 개념 학습을 했고, 애매하게 흐름이 끊길 것 같아서 이전에 학습한 배열 개념이 적용된 문제를 푸는 강의를 추가로 들었다. 기존의 해쉬 테이블에서 충돌이 일어날 때, 해결방법 01. Chaining 기법 (이전 게시물) 해결방법 02. Linear Probing 기법 폐쇄 해슁 또는 Close Hashing 기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈 공간에 저장하는 기법 저장공간 활용도를 높이기 ..

알고리즘/기술면접 완전 정복 올인원 패키지 Online 14. 링크드 리스트 (Linked List) - 4 15. 시간 복잡도 - 알고리즘 복잡도 표현 방법 - 1 16. 시간 복잡도 - 알고리즘 복잡도 표현 방법 - 2 지난 강의에서 연결 리스트의 기본적인 개념과 구현 방식을 알아보았다면, 이번 시간에는 연결 리스트의 '기본 구조'가 아닌 파생된, 연결 리스트 기본 구조의 단점을 보완한 구조인 더블 링크드 리스트에 대하여 배우게 되었다. 자료구조를 공부하면서 처음 들어보는 구조였기에 신기하기도 했고, 확실히 연결리스트의 단점이었던 특정 데이터 노드를 검색하고 찾을 때 무조건 head 데이터인 첫 데이터를 찾아야 하고, 그를 시작으로 모든 노드의 데이터를 거치면서 찾아야 하는 단점을 보완할 수 있는 구..