📦 스택(Stack)스택(Stack)은 데이터를 한쪽 방향으로만 넣고 꺼내는 자료구조입니다. 후입선출(LIFO, Last In First Out)방식으로 동작하여 가장 마지막에 들어온 데이터가 가장 먼저 나가는 구조입니다.예를들어, 접시를 쌓아두고 위에서부터 하나씩 사용하는 것과 같습니다.스택의 핵심은 “순서대로 데이터를 넣고, 마지막 데이터를 삭제한다.” 이며, 핵심을 이해하려면 스택이 동작하는 과정을 살펴보면 다음과 같습니다. 🏓 동작 방식1. 데이터 추가(push)앞에서부터 순서대로 데이터를 추가합니다.2. 데이터 제거(pop)가장 마지막 데이터를 제거합니다.3. 스택의 가장 마지막 데이터 확인마지막에 있는 데이터를 확인합니다.4. 스택이 비어있는지 확인스택이 비어있는지 확인하는 방법은 스택의 ..

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

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

큐(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를 활용..

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

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