본문 바로가기

파이썬183

[LEET CODE] 739. Daily Temperatures # Problem Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead. For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0]. Note: The length of temp.. 2021. 3. 29.
[LEET CODE] 622. Design Circular Queue # Problem Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer". One of the benefits of the circular queue is that we can make use of the spaces in front of the .. 2021. 3. 29.
[코딩 + 알고리즘 완주반] 15일차. 힙 # 힙 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 # 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용 # 힙 구조 힙은 최대값을 구하기 위한 구조(최대힙) 와, 최소값을 구하기 위한 구조( 최소 힙) 으로 분류 가능 1. 각 노드의 값은 해당 노드의 자식노드가 가진 값보다 크거나 같다(최대힙) 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같음 2. 완전 이진 트리 .. 2021. 3. 29.
[코딩 + 알고리즘 완주반] 14일차. 트리 # 트리 구조 트리 : Node 와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조 이진트리형태의 구조로 탐색 알고리즘 구현을 위해 많이 사용 # 알아둘 용어 Node : 트리에서 데이터를 저장하는 기본 요소( 데이터와 다른 연결된 노드에 대한 branch 정보 포함) Root Node : 트리 맨 위에 있는 노드 Level : 최상위 노드를 level 0으로 하였을 때, 하위 branch로 연결된 노드의 깊이 Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 Child Node : 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node(Terminal Node) : Child Node가 하나도 없는 노드 Silbinng(Brother node) : 동일한 Parent No.. 2021. 3. 28.
[코딩 + 알고리즘 완주반] 13일차. 해쉬 테이블 (Hash Table) # 해쉬 구조 해쉬 테이블: 키에 데이터를 저장하는 데이터 구조 키를 통해 바로 데이터를 받아올 수 있으므로 속도가 획기적으로 빨라짐 ex) 파이선 딕셔너리 (파이썬에서는 해쉬를 별도 구현할 필요없음) 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 ( 공간과 탐색을 맞바꾸는 기법) # 알아둘 용어 해쉬 (Hash) : 임의 값을 고정 길이로 변환하는 것 해쉬 테이블 (Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수 (Hashing Function) : 키에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 해쉬 값 (Hash Value ) 또는 해쉬 주소(Hash Address) : 키를 해싱 함수로 연산해서 해쉬 값을 알아내고, 이를 .. 2021. 3. 27.
[코딩 + 알고리즘 완주반] 13일차. 시간복잡도 # 알고리즘 시간 복잡도 계산이 필요한 이유 하나의 문제를 푸는 알고리즘이 다양함 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해 # 알고리즘 복잡도 계산 항목 시간 복잡도 : 알고리즘 실행 속도 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈 # 알고리즘 시간 복잡도의 주요 요소 입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행시간 지배 # 알고리즘 성능 표기법 Big O (빅 오) 표기법 : 최악의 시행 시간을 표기 오메가 표기법 : 최상의 실행 시간을 표기 세타 표기법 : 평균 실행 시간을 표기 # Big O (빅 오) 표기법 O(n) 입력에 따라 결정되는 시간 복잡도 함수 O(𝑙𝑜𝑔𝑛)의 베이스는 2- log 2 n O(1) < O(𝑙𝑜𝑔𝑛) < O(n) < O(n𝑙𝑜𝑔𝑛) <.. 2021. 3. 27.
반응형

티스토리툴바