Techbrad

코테 공부를 하다가 접두사 관련 시간 초과가 계속 나서 문제를 찾아보다가 Trie자료구조를 알게되었다. 일반 검색할때 자동완성에 이러한 자료 구조가 쓰여졌다는 것이 흥미로웠다. 그래서 ChatGPT에 물어보았다.ChatGPT 답변Trie 자료구조는 문자열이나 텍스트 데이터를 효율적으로 저장하고 검색하는 데 사용되는 트리 기반 자료구조입니다. 주로 접두사와 관련된 문제를 해결하는 데 유리한 특징을 가지고 있습니다. 예를 들어, 많은 단어들에서 같은 접두사가 있을 때, 그 부분을 공유하여 공간을 절약하고 빠르게 검색할 수 있습니다.Trie의 구조Trie는 각 노드가 문자를 가지고 있으며, 루트에서부터 자식 노드를 따라가면서 하나의 문자열을 구성합니다. 이때, 각 노드는 해당 문자가 접두사가 되는 위치에 있습..

이전 포스팅 체이닝 기법에 이어 클로즈 기법에 대해 알아보자. [자료구조] 해시테이블 체이닝 기법 개념 및 구현 with 파이썬(Python) 해시테이블이란 key에 data를 저장하는 데이터 구조이다. 파이썬의 딕셔너리 구조와 동일하다. key를 통해 data를 찾아가는 과정은 다음과 같다. key를 hash 함수에 넣고 일정한 길이의 해시 코드를 얻 techbrad.tistory.com 클로즈 기법에 하나로 Linear Probing 이 있다. hash address 충돌로 인해 다른 hash address를 찾아 저장하는 방법이다. 체이닝 처럼 링크드 리스트 자료구조를 사용하지 않아도 되어 메모리 공간을 효율적으로 사용할 수 있다는 장점이 있다. 아래 그림처럼 Jack 과 Andrew는 같은 해시 ..

Heap 자료구조- 완전 이진트리의 일종이다.- 중복된 값을 허용- 최댓값, 최솟값을 빠르게 찾아내기 위한 자료 구조이다. (우선순위 큐) 파이썬의 heapq 모듈- heappush: 힙에 값을 추가, 추가 후에 정렬이 되지 않는다.- heappop: 힙에서 가장 작은 값을 꺼내옴- heapify: 리스트를 힙으로 변환 프로그래머스 더맵게 문제 heapq 적용 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.krimport heapqdef solution(scoville, K): answer = 0 heapq.heapify(scoville) while 1: ..