Techbrad

프로그래머스의 도넛과 막대 그래프 문제를 풀면서 시간초과가 발생했다.  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr from collections import defaultdictdef solution(edges): answer = [0, 0, 0, 0] graph = defaultdict(list) out_ = defaultdict(int) in_ = defaultdict(int) for e in edges: graph[e[0]].append(e[1]) out_[e[0]] += 1 in_[e..

코테 공부를 하다가 접두사 관련 시간 초과가 계속 나서 문제를 찾아보다가 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는 같은 해시 ..

해시테이블이란 key에 data를 저장하는 데이터 구조이다. 파이썬의 딕셔너리 구조와 동일하다. key를 통해 data를 찾아가는 과정은 다음과 같다. key를 hash 함수에 넣고 일정한 길이의 해시 코드를 얻게 된다. 이후 3으로 나눈 나머지인 0, 1, 1이 index가 되며 이를 통해 data를 찾을 수 있다. 해시 테이블의 장점은 저장/읽기의 속도가 빠르다는 것이다. 따라서 검색, 조회가 빈번한 작업인 경우에 해시테이블을 활용하면 빠르게 데이터를 관리하는 효과를 얻을 수 있다. 하지만 장점이 있으면 단점이 있는법! index가 중복되는 경우 저장시에 충돌이 발생한다는 것이 단점이다. 해시 함수가 10을 나눈 나머지를 구하는 것이라고 가정해보자. 이러면 숫자 28을 10으로 나누면 8이 나머지이다..