[알고리즘] 누적합(Prefix Sum)

[알고리즘] 누적합(Prefix Sum)

개념 특정 배열이 있을 때, 구간의 합을 말한다. 예를 들어, 다음과 같은 배열이 있을 때 3번째부터 5번째까지의 누적합은 12이다. 구현 일반적으로 누적합을 구함에 있어, i번째부터 j번째까지의 누적합을 구하라고 할 때마다 하나씩 더하면 i~j까지를 m개의 원소라고 하면 시간 복잡도가 m(j-i+1)의 제곱으로 늘어난다. 하지만 간단한 개념을 도입하면 시간복잡도를 O(2)까지 줄일 수 있다. 전체 누적합을 구한다. i번째부터 j번째까지 누적합을 구하려면 전체 누적합의 j번째 인덱스에서 i-1번째 인덱스를 빼면 된다. 응용 자료구조 응용 세그먼트 트리 2042 구간 합 구하기 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N..

  • format_list_bulleted Algorithm/개념
  • · 2024. 4. 2.
  • textsms
[알고리즘] 우선순위 큐와 힙(Priority Queue & Heap)

[알고리즘] 우선순위 큐와 힙(Priority Queue & Heap)

→ 큐(Queue) 란? 선입선출(FIFO, First In First Out) 형식을 갖는 자료구조 → 먼저 들어간 입력이 먼저 나옴 2024.03.12 - [Algorithm/개념] - [자료구조] 큐(Queue) [자료구조] 큐(Queue) 큐(Queue) 란? 선입선출(FIFO, First In First Out) 형식을 갖는 자료구조 → 먼저 들어간 입력이 먼저 나옴 종류 선형 큐(Linear Queue) 일반적인 리스트 형태를 갖으며, 선입선출 형식을 갖음 원형 큐(Circular l1m3kun.tistory.com 힙(Heap) ? 우선순위 큐를 위해 고안된 완전 이진 트리 형태의 자료구조 우선순위 큐 최대 우선순위를 부모 노드에서 자식 노드로 갈 수록 우선순위가 내려간다. → Root 노드..

  • format_list_bulleted Algorithm/개념
  • · 2024. 3. 12.
  • textsms
[자료구조] 큐(Queue)

[자료구조] 큐(Queue)

큐(Queue) 란? 선입선출(FIFO, First In First Out) 형식을 갖는 자료구조 → 먼저 들어간 입력이 먼저 나옴 종류 선형 큐(Linear Queue) 일반적인 리스트 형태를 갖으며, 선입선출 형식을 갖음 원형 큐(Circular Queue) 처음과 끝이 있는 것이 아닌, 회전하며 인덱싱 삽입, 출력에 있어 메모리 효율을 높일 수 있음 우선순위 큐(Priority Queue) 먼저 입력한 순서가 아닌, 우선순위를 두고 우선순위가 높은 순서로 출력 구현 리스트 생성 list의 append를 활용하여 구현 queue = [] index를 이용한 구현 front = 0 rear = -1 queue = [0 for _ in range(N)] 삽입(EnQueue) list의 append를 활용..

  • format_list_bulleted Algorithm/개념
  • · 2024. 3. 12.
  • textsms
[알고리즘] 문자열 - 트라이(Trie)

[알고리즘] 문자열 - 트라이(Trie)

문자열을 빨리 찾을 순 없을까? 개념 문자열은 문자들을 이어붙여 만든 개념으로 이를 빠르게 탐색하고 싶을 때 문자열들을 문자 하나를 기준으로 앞에는 어떤 문자가 오는지, 뒤에는 어떤 문자가 오는지를 체크 해놓으면 여러 문자열을 저장할 때 더 적은 비용을 들여 탐색할 수 있다. 말은 쉽지.. 트라이(Trie) 알고리즘 문자열 집합을 표현하는 트리 자료구조 문자열을 탐색하는데 있어 시간을 줄이기 위한 알고리즘(문자열 탐색 알고리즘) 장점 빠른 탐색 시간( O(M *L) → O(M) ※M: 문자열의 수, L: 가장 긴 문자열 길이) 단점 정렬이 되어 있어야 함 비효율적인 메모리 기존 : 문자열 길이(개행포함) * 문자열의 총 개수 트라이 형식 : 문자열 * (다음 노드의 수 + 끝인 경우의 문자열) * 문자열..

  • format_list_bulleted Algorithm/개념
  • · 2024. 2. 4.
  • textsms
크루스칼(Kruskal) - 최소 신장 트리(MST)

크루스칼(Kruskal) - 최소 신장 트리(MST)

개념 신장 트리(Spanning Tree) 모든 정점을 포함하면서 사이클이 없는 그래프 특징 원 그래프의 모든 정점을 포함 간선(node) 수 = 정점 수 - 1 노드 간 사이클을 형성하지 않음 한 그래프 내에서 여러 개의 신장 트리를 가질 수 있음 최소 신장 트리(Minimum Spanning Tree) 간선(node) 가중치의 합이 가장 작은 신장 트리 간선(node) 가중치가 가장 낮은 간선부터 탐색하여 신장트리를 구성하는 방식 대표 알고리즘 : Kruskal 알고리즘, Prim 알고리즘 차이점 Kruskal 알고리즘 : 간선(node)를 중심으로 하여 신장 트리를 구성 Prim 알고리즘 : 정점(spot)을 중심으로 하여 신장 트리를 구성 크루스칼(Kruskal) 알고리즘 가장 작은 가중치를 갖는..

  • format_list_bulleted Algorithm/개념
  • · 2024. 1. 10.
  • textsms
[알고리즘] Union-Find

[알고리즘] Union-Find

개념 그래프 이론으로, 상호 배타적 집합(서로소집합:Disjoint-Set) 알고리즘이라고도 부름 주로 크루스칼(Krusckal) 알고리즘에서 사용하며, 순환하지 않는 트리 를 만들기 위해 사용 단계별로 이해하기 만약 아래 표와 같이 4개의 노드를 가진 서로소 집합이 있다면, 노드 번호 1 2 3 4 대표 번호 1 2 3 4 1번과 2번이 같은 집합이라면? 대표번호를 변경하여 같은 집합을 표현할 수 있음 Union 결과 노드 번호 1 2 3 4 대표 번호 1 1 3 4 아래 표와 같이 있을 때 2번은 어떤 집합에 있는지 알 수 없을까? 노드 번호 1 2 3 4 대표 번호 1 3 4 1 노드 번호를 따라가며 확인할 수 있음 2번 👉 3번 👉 4번 👉 1번 (모두 같은 집합) Find 다른 표현 노드 번호 ..

  • format_list_bulleted Algorithm/개념
  • · 2024. 1. 7.
  • textsms
반응형