부울 연산자: NOT, AND, OR (기본), XOR (보조) 기본 연산자를 조합해 보조 연산 가능 XOR: TT, FF 일때는 F 반환, TF, FT 일때는 T 반환 # XOR x = y = True (x and not y) or (not x and y) >>> False 비트 연산자 ~ : (2의 보수) - 1, 십진수로는 -x-1, 부울 변수 True에 적용하면 -1-1 = -2 True & False # Bitwise AND >>> False True | False # Bitwise OR >>> True True ^ True # Bitwise XOR >>> False ~ True # Bitwise NOT >>> -2 # 십진수와 마찬가지로 연산 bin(0b0110 + 0b0010) >>> '0b..
CS/algorithm & data structure
이진 검색: 정렬된 배열에서 타겟을 찾는 검색 알고리즘 값을 찾아내는 시간 복잡도가 O(logn) 704. Binary Search - 재귀로 이진 검색 * 파이썬은 재귀 호출 횟수 제한이 1000번으로 정해져있으므로 유의 (sys 모듈로 변경가능하지만 대부분 지원하지 않음) - 반복으로 이진 검색 - 이진 검색 모듈 bisect - index() * 최악의 경우 O(n)으로, 앞에서부터 탐색하므로 뒤에 위치할수록 느려진다 bisect.bisect(iterable, value)는 bisect.bisect_right(iterable, value)와 같으며 value 값이 iterable에 정렬되어 삽입된다면 위치할 인덱스 값 리턴 -> value 값과 동일한 값이 이미 iterable에 있다면 그 값 우측..
정렬 알고리즘: 목록의 요소를 특정 순서대로 넣는 알고리즘, 대게 숫자식 순서와 사전식 순서로 정렬 버블 정렬(O(n^2)): 배열의 요소를 끝까지 순차적으로 탐색하며 연달아 있는 2개의 요소의 순서가 맞지 않으면 스왑 병합 정렬(O(nlogn)): 배열을 더 이상 분할이 안될때까지 반씩 나누고, 요소들을 정렬하면서 이어붙힌다 대부분의 경우 퀵 정렬보다 느리지만 일정한 속도와 안정 정렬인 점 때문에 많이 쓰인다 퀵 정렬(O(nlogn)): 분할 정복 알고리즘에 피벗 개념을 추가해 피벗보다 작으면 왼쪽, 크면 오른쪽에 배치되게 분할 이미 정렬된 배열이 입력되는 등의 비효율적인 상황에서는 O(n^2) 가장 간단한 분할 알고리즘인 로무토 파티션은 피벗이 가장 오른쪽 요소 안정 정렬: 입력된 순서가 다른 기준으..
트라이: 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조 특히 자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다 검색을 뜻하는 'retrieval'에서 따옴 다진 트리의 형태 각 문자열 길이만큼만 탐색하면 원하는 결과 찾을 수 있다 208. Implement Trie (Prefix Tree) - TrieNode 클래스 생성해 딕셔너리로 노드 값 정보, 불리안으로 해당 노드에서 단어 완성 여부 정보를 각 노드에 담는다 -> 삽입이나 검색하려는 문자열 갯수만큼 반복하여 각 노드의 딕셔너리 확인하며 필요한 작업 수행 336. Palindrome Pairs - 부르트 포스 -> 시간 초과 O(n^2) - 트라이 구현 -> 입력..
힙: 힙의 특성(최소 힙에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리 파이썬에는 최소 힙만 구현(heapq 모듈) 우선순위 큐에서 가장 작은 값을 가져올때 매번 최소 힙의 루트를 가져오면 된다 부모 자식 간의 관계만 정의하므로 정렬된 구조가 아님 자식이 둘인 힙은 이진 힙이라 하며, 이진 트리와 마찬가지 이유로 대부분 이진 힙이 널리 사용됨 배열에 순서대로 표현하기 좋으며, 편한 계산을 위해 인덱스는 1부터 사용 다익스트라 알고리즘, 힙 정렬, 최소 신장 트리, 프림 알고리즘, 중앙값의 근삿값 힙 연산(최소 힙): 삽입(업힙) -> O(logn), 추출(다운힙) -> O(logn), 이진 힙은 조회할 때 O(1) 삽입: 요소를 최하위 레벨의 가장 왼쪽으로 삽입 -> 부모와 비교 ..
트리: 계층형 트리 구조를 시뮬레이션 하는 추상 자료형(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. 모든 원소들은 자식 원소들보다 작거나 같게 위치 * 두번째로 작은 값 확인하..
