unordered_map과 배열의 성능 차이오프라인 쿼리 문제를 풀다가 unordered_map을 이용하면 시간초과가 나고 배열을 사용하면 시간이 단축되는 경험을 했다. 둘 다 접근할 때 O(1)으로 알고 있었는데, 어디서 차이가 날까 생각해보았다. 해시충돌 때문이라고 넘어갈까 했지만 자세히 알아보고 기록해두는 게 좋을 거 같아서 포스팅하기로 결정했다. 1. unordered_map vs 배열a) unordered_map의 특성시간 복잡도평균적으로 O(1) 시간에 접근 가능핮만 최악의 경우 O(N)으로 느려질 수 있음 (해시 충돌 발생 시)캐시 활용도unordered_map은 내부적으로 해시 테이블을 사용하며 데이터가 메모리 상에 분산되어 저장된다.따라서 캐시 적중률(cache hit rate)가 낮아질..
자료구조
펜윅트리 (Fenwick Tree, Binary Indexed Tree, BIT)펜윅트리는 트리 구조를 1차원 배열로 구현한 자료구조로, 각 위치에서 특정 구간을 대표하는 값을 저장하여 빠르게 구간 합 등을 계산할 수 있다. 업데이트와 쿼리 연산의 시간 복잡도는 O(logN)이다. 1기반 인덱싱을 사용하기 때문에 배열의 크기를 N + 1 (N은 데이터의 크기)로 설정하는 경우가 많다. 세그먼트 트리보다 상대적으로 구현이 간단하고 메모리 사용량이 적다. 주요 연산 비교연산펜윅 트리세그먼트 트리구간 쿼리O(logN)O(logN)단일 업데이트O(logN)O(logN)구간 업데이트O(NlogN)O(logN) (Lazy Propagation 사용 시)메모리 사용량O(N)O(4 * N) 펜윅 트리 코드#inclu..
느리게 갱신되는 세그먼트 트리 (Lazy Propagation)느리게 갱신되는 세그먼트 트리(Lazy Propagation)는 세그먼트 트리에서 구간 업데이트를 더 효율적으로 처리하기 위해 사용하는 기법이다. 구간의 여러 값을 한 번에 갱신하고, 그 후에 구간에 대한 정보를 빠르게 얻어야 할 때 사용된다. 1. 느리게 갱신되는 세그먼트 트리란?기본 세그먼트 트리는 특정 구간의 값(합, 최대값 등)을 빠르게 쿼리할 수 있게 해준다. 그런데 만약 구간 내 모든 값에 동일한 연산(ex. 더하기)을 여러 번 적용해야 하는 경우, 기본 세그먼트 트리로는 비효율적일 수 있다. 최악의 경우 nlogn의 시간이 걸릴 수 있기 때문이다. 이때 느리게 갱신되는 세그먼트 트리를 사용하면 구간 전체에 대한 업데이트를 지연시..
세그먼트 트리세그먼트 트리는 효율적인 구간 연산을 처리하기 위해 사용되는 트리 구조이다. 주어진 배열에서 특정 구간의 합이나 최대값/최소값 등과 같은 정보를 빠르게 구해야 할 때 유용하다. 이 구조를 사용하면 배열의 값을 업데이트하거나 구간의 값을 구하는 작업을 빠르게 처리할 수 있다. 1. 세그먼트 트리란 무엇인가세그먼트 트리는 주어진 배열을 관리하는 트리 구조로, 배열의 특정 구간에 대한 연산(예: 합, 최대값, 최소값 등)을 효율적으로 처리하는 데 사용된다. 일반적으로 배열의 크기가 커질수록 배열의 구간 합이나 구간 최대/최소를 구하는 시간이 오래 걸리는데, 세그먼트 트리를 사용하면 로그 시간(O(logN)))에 이런 연산을 처리할 수 있다. 즉, 세그먼트 트리는 배열의 구간 정보를 미리 저장해 두..
트리 트리는 그래프의 일종으로 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다. 트리 용어 Node: 트리 구조의 교점으로 node는 데이터를 가지고 있고, 자식 노드를 가질 수 있음. Root Node: 트리 구조에서 가장 위에 있는 노드. 즉, 트리의 시작점이 되는 노드. Edge: 트리를 구성하기 위해 노드와 노드를 연결하는 선. Level: 트리의 특정 깊이를 가지는 노드의 집합. Degree: 각 노드가 가진 가지의 수. '차수'라고도 함 Leaf Node (Terminal Node): 하위에 다른 노드가 연결되어 있지 않은 노드. Internal Node: Leaf Node를 제외한, 중간에 위치한 노드들. 트리의 특징 트리 자료구조는 일반적으로 대상 정보의 각 항목들을 계층적으로 구..
서로소 집합 서로소 집합은 집합 관계를 표현하는 자료구조로, 공통 원소가 없는 두 집합을 말한다. 서로소 집합 알고리즘은 union-find 연산으로 구성된다. 그래서 서로소 알고리즘을 union-find 알고리즘으로 부른다고도 한다. union(합집합 연산), find(찾기) union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. union(x,y): x가 속한 집합과 y가 속한 집합을 합친다. find(x): x가 속한 집합의 대표 번호(루트 노드)를 반환한다. 1. union 연산을 확인하여 서로 연결된 두 노드 A,B를 확인한다. 1-1. A와 B의 루트 노드 A', B'를 찾는다 1-2. A'를..
Heap 1. 힙은 완전이진트리를 기본으로한 자료구조로, O(logN)의 시간복잡도를 가지고 있다. 2. 여러 개의 값 중 최대값, 최소값을 빠르게 찾아내도록 만들어진 자료구조이다. 우선순위 큐 구현 시에 사용한다. 3. 힙은 반정렬 상태(느슨한 정렬 상태)를 유지한다. 이를테면 최소힙일 때, 작은 값이 상위 레벨에 있고 큰 값이 하위 레벨에 있다는 정도. 4. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙의 종류 최대힙 부모노드의 키 값이 자식노드의 키값보다 항상 크거나 같 힙. 최대 힙에서는 루트 노드에 이는 값이 제일 크므로 최대값을 찾는데 소요되는 연산의 시간복잡도는 O(1)이다. 그리고 완전 이진 트리이기 때문에 배열을 사용하여 효율적으로 관리할..
우선순위 큐 우선순위 큐는 데이터를 추가한 순서대로 삭제하는 큐와 달리, 데이터 추가는 어떤 순서로 해도 상관 없지만 데이터를 제거할 때는 가장 작은 값을 제거하는 특성을 가지는 자료구조이다. 이는 내부적으로 정렬 메커니즘이 있다는 것을 의미한다. 우선순위 큐는 내부적으로 힙이라는 완전 이진 트리로 되어있다. 힙 트리의 루트노드에는 데이터들 중에 가장 큰 값 혹은 가장 작은 값을 담게 되는데 전자는 최대힙(Max-heap) 후자는 최소힙 (Min-heap)이라고 한다. 어떤 값을 넣어도 항상 루트에 가장 큰 값 또는 가장 작은 값이 위치하도록 자동으로 갱신한다. 이 과정이 꽤 효율적이라 우선순위 큐의 값 삽입/삭제 시간 복잡도는 O(logN)이다. 무작위 숫자들을 힙에 전부 넣고 하나를 빼면 정렬된 결과..
큐 Queue가 어떻게 쿠웨웨가 아니라 큐인지 모르겠지만... 큐는 스택의 특징과 다르게 선입선출(FIFO)의 성격을 가지고 있다. 따라서 큐는 순서대로 대기하고 실행시키고 싶을 때 사용하는 자료구조이다. 급식실에서 밥 먹으려고 줄 서있는 학생들을 생각하면 이해하기 쉬울 것 같다. 코드 큐 또한 파이썬에서는 리스트로 구현가능한데, pop을 해줄 때 앞의 값을 제거 해야하므로 pop(0)을 해주어야 한다. pop(0)의 시간복잡도는 O(n)이므로 O(1)보다는 효율적이지 못하다. O(1)인 방법으로 해결하기 위해 collections에서 deque를 import해주어 queue를 구현해볼 수 있다. 참고로 Queue 모듈에서 queue를 사용할 수 있지만, Queue 모듈은 멀티 스레딩 환경까지 고려해 스..
스택 스택은 컴퓨터에서 자주 쓰이는 자료구조 중 하나로, 후입선출(LIFO)의 특징을 가지고 있다. 나중에 들어온 것이 먼저 나간다는 뜻인데, 이는 쌓아둔 접시 혹은 프링글스를 생각하면 이해하기 쉬울 것이다. 이런 특징을 이용해서 뒤로 가기를 구현할 수도 있다. 코드 파이썬에서는 스택을 따로 구현해놓지 않았는데 리스트 자료형이 스택과 유사하게 동작하기 때문이다. push - append(x) -> 리스트의 가장 뒤에 새로운 값을 추가 pop - pop() -> 리스트 가장 뒤에 있는 값을 삭제 stack = [] #파이썬에선 이게 스택이다 import sys input = sys.stdin.readline a = int(input()) stack = [] for _ in range(a): x = inpu..
