힙: 힙의 특성(최소 힙에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리 파이썬에는 최소 힙만 구현(heapq 모듈) 우선순위 큐에서 가장 작은 값을 가져올때 매번 최소 힙의 루트를 가져오면 된다 부모 자식 간의 관계만 정의하므로 정렬된 구조가 아님 자식이 둘인 힙은 이진 힙이라 하며, 이진 트리와 마찬가지 이유로 대부분 이진 힙이 널리 사용됨 배열에 순서대로 표현하기 좋으며, 편한 계산을 위해 인덱스는 1부터 사용 다익스트라 알고리즘, 힙 정렬, 최소 신장 트리, 프림 알고리즘, 중앙값의 근삿값 힙 연산(최소 힙): 삽입(업힙) -> O(logn), 추출(다운힙) -> O(logn), 이진 힙은 조회할 때 O(1) 삽입: 요소를 최하위 레벨의 가장 왼쪽으로 삽입 -> 부모와 비교 ..
leetcode
트리: 계층형 트리 구조를 시뮬레이션 하는 추상 자료형(ADT)으로, 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합 재귀로 정의된 자기 참조 자료구조 트리는 항상 하나의 루트(Root)에서 시작되며, 자식(Child) 노드를 가지고, 간선(Edge)으로 연결되어 있다 차수(Degree): 자식 노드의 개수, 크기(Size): 자신을 포함한 모든 자식 노드의 개수 높이(Height): 현재 위치에서부터 리프까지의 거리, 깊이(Depth): 루트에서부터 현재 노드까지의 거리 레벨은 루트에서 0이고, 노드 A의 자식노드는 A의 레벨 + 1 트리는 순환 구조를 갖지 않는 그래프, 단방향, 하나의 부모 노드, 하나의 루트 이진 트리: 가장 널리 사용되는 트리 자료구조 m-ary 트리(..
최단 경로 문제: 각 간선의 가중치 합이 최소가 되는 두 정점(또는 노드) 사이의 경로를 찾는 문제 정점: 교차로, 간선: 길, 가중치: 거리 & 시간 등의 이동 비용 다익스트라 알고리즘: 항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디 알고리즘 -> BFS 이용 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단거리는 계산이 끝났다는 확신을 가지고 더한다 743. network delay time - 다익스트라 알고리즘 -> 시작점에서 각 노드까지 최단시간 계산하고 저장(BFS) 및 계산되지 않는 노드 여부 확인 heapq 모듈에는 우선순위 업데이트 기능 없음 이전 노드의 값이 무엇인지 필요없으므로 생략 787. cheapest flights within k stops - 다익스트라 알고리..
그래프: 객체의 일부 쌍들이 연관되어 있는 객체 집합 구조 오일러 경로: 모든 간선(edge)을 한 번씩 방문하는 유한 그래프 경로(= 한붓그리기) 모든 정점(vertex)이 짝수 개의 차수(degree)를 갖는다면 오일러 경로 해밀턴 경로: 각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로 최적 알고리즘이 없는 대표적인 NP-완전 문제 (NP문제 중 NP-난해 문제) 해밀턴 순환: 원래의 출발점으로 돌아오는 경로 외판원 문제: 최단거리인 해밀턴 순환을 찾는 문제 -> 다이나믹 프로그래밍으로 최적화 그래프 순회 (그래프 탐색): 그래프의 각 정점을 방문하는 과정 깊이 우선 탐색(DFS)이 너비 우선 남색(BFS)에 비해 더 널리 쓰임 DFS는 주로 스택이나 재귀로 구현(재귀 선호), BFS는 주로..
해시 테이블(해시 맵): 키를 값(해시)에 매핑할 수 있는 구조인, 연관 배열 ADT를 구현하는 자료구조 대부분의 연산이 분할 상환 분석에 따라 시간 복잡도가 O(1) 해시 함수: 임의 크기 데이터를 고정 크기 값(해시)으로 매핑하는 데 사용할 수 있는 함수 해시 함수가 값을 매핑할 때 충돌을 최소화하는 것이 무엇보다 중요함 로드 팩터: 해시 테이블에 저장된 데이터 개수를 버킷의 개수로 나눈 것 해싱: 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것 개별 체이닝: 충돌 발생 시 연결리스트로 연결 오픈 어드레싱: 충돌 방생 시 탐사를 통해 빈 공간을 찾는 방식 전체 슬롯 개수 이상 저장 불가, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없음 데이터들이 고르지 않고 뭉치는 ..
- 데크 (double-ended queue): 양 쪽에서 삽입 및 삭제 가능 - ADT는 이중연결리스트로 구현 641. design circular deque - 이중 연결 리스트로 구현(빈 head, tail) * 배열은 첫 인덱스에 삽입 시 O(n) - 우선순위 큐: 특정 조건에 따른 우선순위가 가장 높은 순으로 추출 (ex. 최댓값 추출) -> 정렬 알고리즘으로 구현 가능 - 다익스트라 알고리즘이나 힙 자료구조와 관련이 깊음 23. merge k sorted lists - 파이썬 heapq 모듈 (최소 힙): 이진 트리 기반 1. 원소들이 정렬된 상태(키 기준)로 삽입, 삭제 2. 가장 작은 원소가 첫 인덱스에 위치 3. 모든 원소들은 자식 원소들보다 작거나 같게 위치 * 두번째로 작은 값 확인하..
- 스택: lifo, 큐: fifo - 파이썬 리스트는 스택과 큐의 모든 연산 수행 가능 - 그러나 성능을 고려한다면 큐는 데크를 사용해야 좋음 - 스택 ADT에서는 차곡차곡 쌓이지만, 실제 연결리스트로 구현 시 무작위로 배치되고 포인터로 처리 ※ 참고: 클래스의 메소드에서 self는 인스턴스 자체, 인스턴스로 메소드 호출하면 자동으로 인스턴스(self) 인자로 넣음 20. valid parentheses - 딕셔너리 활용 - 스택에 왼 괄호 쌓기 316. remove duplicate letters - 재귀(분리 가능하냐로 접근) - 스택에 문자 쌓으면서 비교 - collections.Counter() 739. daily temperatures * [0] * len(T) - 스택에 인덱스 쌓으면서 온도..
234. palindrome linked list - 리스트로 변환 - 데크 - 런너 * 다중할당: 동시에 일어남 21. merge two linked lists - 재귀 (함수 안에서 다시 함수 호출) - 괄호가 연산순위 제일 높음 206. reverse linked list - 재귀 - 반복 - 내 풀이: 런너 2. add two numbers - 연결 리스트 만들때 더미 노드 생성 필수 - 전가산기 응용 - divmod() * map() * functools 모듈(reduce 메소드) * operator 모듈(add, mul 메소드) ※ b가 a를 참조할 때, a가 가변객체인 경우(list, set, dict) b에서 값을 조작하면 두 객체 모두에게 적용 (불변객체인 경우 b는 더이상 a를 참조하지..
125. valid palindrome - str.isalnum()이나 정규식으로 전처리 - 데크로 최적화 - pop()이나 슬라이싱으로 판별 344. reverse string - 투포인터로 스왑 - list.reverse() - s[:] 937. reorder log files - str.isdigit() - 람다 표현식, 리스트 + - list.sort(key=) 819. most common word - 정규식으로 전처리 - collections.defaultdict(int), collections.Counter() 49. group anagrams - ''.join() - collections.defaultdict(list) 5. longest palindrome substring - 투포인터 ..
