list, tuple : O(n)의 시간복잡도를 갖는다.set, dict : 평균적으로 O(1)의 시간복잡도를 갖는다.해시 테이블(hash table)은 키(key)와 값(value)으로 데이터를 저장하는 자료구조이다.해시 테이블은 검색, 삽입, 삭데 등의 연산을 평균
(1) 방법 1
최대 시간에 대한 계산이 중요하다. (2번 케이스는 1e+14도 실패한다.)시간에 대한 금과 은의 최대 최소 값을 구한 후, 필요한 양이 가능한지 판단하는 것이 핵심
(시간 복잡도는 최선, 평균, 최악 순서)시간 복잡도 : O(n^2), O(n^2), O(n^2)공간 복잡도 : O(1)안정 : X시간 복잡도 : O(n), O(n^2), O(n^2)공간 복잡도 : O(1)안정 : O시간 복잡도 : O(n^2), O(n^2), O(n^
이번에는 최소 신장 트리(Minimum Spanning Tree)에 대해 알아본다.Spanning Tree그래프 내의 모든 정점을 포함하는 트리이다.즉, 그래프의 최소 연결 부분 그래프이다.n개의 정점을 가지는 그래프의 최소 간선의 수는 n-1이다.역으로, n개의 정점
Dijkstra
트라이 노드를 정의한다.이후 트라이 자료구조를 정의한다.그리고 삽입, 검색, 삭제 함수를 만든다.삽입 함수는 해당 단어의 모든 글자를 확인하며, 글자의 자식 노드에 다음 글자가 없다면, 빈 노드를 만든다.그리고 이제는 자식 노드는 무조건 있으므로, 자식 노드로 노드를
Greedy는 문제를 정확히 이해하는 것이 중요하다.프로그래머스 level2 조이스틱원으로 연결한다고 생각하고, 교체 대상 index 간의 간격 중 가장 큰 값을 빼준다.이때, 0은 언제나 출발 지점이므로, 고려하지 않고 계산하는 것이 핵심그 후, 0에서 양 끝 지점