Table of Contents 개요 기본 구조 반환 삽입 삭제 코드 문제 C++ STL stack 1. 개요 스택은 선형 자료구조 중 하나로서 추상화에 큰 도움을 주는 자료구조입니다. 요약하면 선형 구조의 양 끝 중에서 한쪽에서만 자료를 삽입하고 삭제할 수 있는 자료구조를 뜻합니다. 이 요약의 의미는 이후의 '기본 구조'란에서 자세히 설명하겠습니다. 스택은 간단한 선형 자료구조인 만큼, 배열만을 활용해도 간단히 구현할 수 있습니다. 굳이 스택이라는 새로운 이름을 붙여야 하나 싶을 정도로 간단하지요. 게다가 배열보다 자유도도 낮기 때문에 오히려 할 수 있는 일은 더 줄어들게 됩니다. 하지만 스택은 선형 자료구조를 공부할 때 빼놓지 않고 등장하는 주제로서, 꽤 중요한 자료구조 취급을 받습니다. 이는 스택의..
Table of Contents 개요효율성추상화재사용분류 1. 개요 자료구조란 자료를 저장하는 방법을 뜻합니다. 프로그램 대다수가 자료를 저장하고 사용하기 때문에, 자료구조는 프로그래밍에서 빼놓을 수 없는 요소로 분류되며, 프로그래밍 언어를 익힌 후에 학습해야 할 필수 과목 리스트에 항상 올라와 있습니다. 그런데 사실, 자료구조를 배우고자 하는 분이시라면 이미 자료구조를 사용하고 계실 가능성이 높습니다. C언어, 자바, 파이썬과 같은 언어를 배울 때 사용하는 변수, 배열, 구조체도 자료구조의 일종이기 때문이지요. 여러분들은 언어를 배우실 때 이들을 이용해 자료들을 잘 저장하고 사용해 오셨을 겁니다. 어쩌면 변수와 배열을 이용해 자료를 저장하고 처리할 자신이 있는데, 굳이 자료구조를 배워야 하나 생각하실 ..
개요 간단한 정렬 문제를 생각해보자. 먼저 자연수N을 입력받는다. (1
Table of Contents 개요 기본 구조 값 삽입 최대값 삭제 힙 정렬 C++ STL priority_queue 1. 개요 힙은 이진 트리를 활용한 자료구조이며, 종류로는 최소 힙과 최대 힙이 있습니다. 최대 힙을 알면 최소 힙을 만드는 건 어렵지 않으므로, 이 문서에서는 최대 힙을 기준으로 설명하도록 하겠습니다. 최대 힙 자료구조는 기본적으로 아래의 세 연산을 빠르게 수행하기 위한 자료구조입니다. 연산 1) 최대 힙에 새로운 값을 삽입. 연산 2) 최대 힙 안의 최대값을 삭제. 연산 3) 최대 힙 안의 값 중에 최대값 찾기. 이 세 연산을 배열로 간단하게 처리하려고 하면, 삽입은 O(1)로 가능하더라도 최대값을 찾기에서 O(N) 이 필요함을 알 수 있습니다. 배열에서 최대값을 찾기 위해선, 배열..
Table of Contents 개요방법 1 - 동적계획법방법 1 코드방법 2 - 탐욕법방법 2 코드방법 2 의 정당성방법 2 로 far 배열 찾기문제 1. 개요 트리의 지름이란, 트리 내에서 가장 먼 두 정점 사이의 거리를 뜻합니다. 이 글에서는 트리의 지름을 구하는 2가지 방법에 대해 소개합니다. 참고로 이 두 가지 방법은 모두 시간 복잡도를 늘리지 않는 선에서 'far [ v ] = 정점 v와 v에서 가장 먼 정점 사이의 거리'를 모든 정점에 대해 구할 수 있습니다. far 배열을 구하면 지름 = MAX(far [ v ])로 쉽게 구할 수 있으며, 지름만 구할 때 보다 더 다양한 상황에 쓸 수 있게 됩니다. 때문에 이 문서에서는 far [ v ] 을 구하는 방법까지 소개하도록 하겠습니다. 방법 1은..
Table of Contents 개요최소 스패닝 트리 ( minimum spanning tree )크루스칼 알고리즘 ( Kruskal's algorithm )크루스칼 알고리즘의 구현크루스칼 알고리즘 코드문제크루스칼 알고리즘의 정당성 1. 개요 크루스칼 알고리즘은 무향 연결 그래프가 주어질 때, '최소 스패닝 트리' 라고 부르는 서브 그래프를 찾는 알고리즘입니다. 크루스칼 알고리즘은 유니온 파인드 자료구조를 사용하므로, 해당 자료구조를 모른다면 유니온 파인드 설명을 보고 오시는 걸 추천합니다. 2. 최소 스패닝 트리 ( minimum spanning tree ) 스패닝 트리란, 해당 그래프의 모든 정점을 포함하는 트리 형태의 서브 그래프를 뜻합니다. 왼쪽의 그래프에서 스패닝 트리를 하나 찾아보면 오른쪽의 ..
Table of Contents 개요초기화간단한 방법최적화 단계 1최적화 단계 2 - 유니온 파인드 트리유니온 파인드 트리 - 코드문제 1. 개요 유니온 파인드는 집합을 관리하는 자료구조로서, disjoint set 이라고 부르기도 합니다. 이 자료구조를 활용하면 아래의 두 가지 연산을 사용할 수 있습니다. 연산 1) 요소 A와 요소 B가 같은 집합에 속하는 지 확인.연산 2) 요소 A가 속한 집합과 요소 B가 속한 집합을 병합. 유니온 파인드 연산의 이해를 위해 일단, 위와 같이 4개의 요소가 있다고 해보겠습니다. 초기 상태는 아직 병합을 한 번도 안 한 상태이기 때문에 각자 다른 집합에 속합니다. 이 상태에서 1번 연산, 예를 들어 요소 1과 요소 2가 같은 집합 인지에 대한 질의가 들어오면 이 자료..
Table of Contents 개요 1D sparse table 쿼리를 O(1)으로 처리하기 2D sparse table 문제 1. 개요 스파스 테이블은 배열 Array[1...N], 함수 Function, 범위 [L, R] 이 주어질 때 Function(Array[L], Array[L+1], ..., Array[R]) 계산을 빠르게 하기 위한 자료구조입니다. 간단하게 예를 들면, 'A[3] ~ A[7] 사이의 최소값을 구하라.'같은 식입니다. 여기에서 함수는 최소값 찾기, L = 3, R = 7이 되겠지요. 스파스 테이블은 아래의 두 조건이 성립할 때 사용할 수 있습니다. 조건 1) Array에 저장된 값이 변하지 않야야 한다. 조건 2) Function은 결합 법칙이 성립해야 한다. (즉, F(a,..