개념 특정 배열이 있을 때, 구간의 합을 말한다. 예를 들어, 다음과 같은 배열이 있을 때 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..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 이해 우선순위 큐를 이용하여 풀 수 있는 문제 파이썬 내장함수인 Heapq를 사용하면 간단하게 풀 수 있지만, 직접 구현해봄 구현 내장함수 사용 import heapq 를 사용하여 절댓값과 실값을 같이 저장하여 비교하여 사용 직접 구현 class를 통해 실 값을 저장하면 절댓값을 기준으로 비교하여 트리를 구성 코드 # 11286 절댓값 힙 import sys input = s..

→ 큐(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 노드..

https://www.acmicpc.net/problem/1149 이해 완전 탐색을 통해 해결할 수 있지만, 완전 탐색시 O(3000^3)으로 시간 초과 동적 계획법을 통해 빨강, 초록, 파랑으로 칠하는 경우 중 비용이 가장 작은 경우만 저장하는 배열을 통해 해결 구현 빨강, 초록, 파랑으로 칠할 경우 드는 비용을 저장할 dp배열 생성 N개의 집을 칠하기에 빨강, 초록, 파랑 각각 칠해온 비용을 저장할 N*3배열 생성 dp 배열은 최대의 경우를 가정했을 때 나오는 수보다 1큰 수로 저장 dp = [[1000 * 1000+1] * 3 for _ in range(N)] dp배열의 첫번째 줄은 첫 집을 빨강, 초록, 파랑을 칠할 경우의 비용으로 채움 for i in range(3): dp[0][i] = cos..

https://www.acmicpc.net/problem/15684 이해 사다리를 모두 놓아보면서 판별해야하는 문제 DFS 를 통해 완전 탐색을 하되, 중간 가지치기를 이용한 시간을 단축해야함 구현 사다리 타기를 통해 i → i 가 모두 가능한 지 체크 하는 함수 DFS를 통해 사다리를 놓는 경로를 모두 탐색해야하는 함수 사다리 조작에 있어 사다리를 추가할 때, 추가한 사다리가 3개가 초과되면 가지치기 만약 이전에 확인된 사다리의 조작한 사다리 수가 현재 돌고 있는 사다리의 조작한 사다리 수 보다 높은 경우 가지치기 사다리를 놓음에 있어 만약 2개 혹은 3개째 사다리를 놓을 때는 이전에 놓았던 사다리 위치보다 위에 놓을 필요가 없음 코드 # 15684 사다리 조작 import sys input = sys..

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