data structure3 [4] 큐 Queue는 자료구조 중의 하나로, 먼저 입력되는 정보가 먼저 나오는 형태의 구조를 지닙니다. 이를 First in First Out 이라 하고, 앞 글자를 따서 FIFO 라 부릅니다. 자료구조로서의 정의가 있기 전에, queue 라는 단어는 "줄 지어 서있는" 것을 의미하는데요 위 사진 처럼 인기 있는 레스토랑에서 식사를 하려고 줄을 서면, 먼저 온 사람이 먼저 식당에 들어가게 됩니다. 자료구조로서의 큐는 그런 특성을 본따서 지은 이름이 아닐까 생각되네요. 큐가 지원하는 메소드는 다음과 같습니다. Enqueue : Queue의 front(맨 앞)에 값을 넣는 것을 의미합니다. Dequeue : Queue의 Back(맨 뒤)에서 값을 빼는 것을 의미합니다. 큐도 스택과 같이 Array와 LL으로 구현할 .. 2020. 10. 25. [3] 스택 스택 자료구조에 대해 알아보고, 이를 직접 구현하며 자세히 알아보겠습니다. 스택은 자료구조의 한 종류로, 나중에 입력한 정보를 가장 먼저 꺼낼 수 있는 구조를 갖는 자료구조입니다. 이러한 구조를 LIFO (Last In First Out) 라고 합니다. 항상 넣은 순서의 반대로 꺼낼 수 있게 한쪽 방향이 막혀있습니다. Stack의 의미를 생각해보면, 무언가가 쌓여있는 것을 생각하게 되는데, 쌓여있는 것의 맨 마지막 것 부터 뺄 수 없는것과 같은 이치입니다. 스택을 구현한다는 것은, 한쪽으로만 꺼낼 수 있는 구조를 만들어 주는 것이라고 볼 수 있겠습니다. 구현 구현은 Array로 해도 되고 Linked List로 해도 되지만, 이 글에선 Linked List를 이용하여 구현합니다. typedef struc.. 2020. 10. 20. [1] Segment Tree Segment Tree 는 다양한 유형의 문제를 빠르게 해결해주는 자료구조이다. 구간에 대한 정보를 구하는 경우, 단순히 정렬한 후 Prefix Sum 을 이용해서 구간합을 빠르게 구할 수 있지만 만약 개별 쿼리 도중 배열에서 특정 요소의 값이 변경되야 하는 경우엔 매번 다시 정렬을 해야 되어 비효율적이다. 이러한 경우, 구간에 대한 정보를 담는 Tree를 구성할 수 있는데, 이를 세그먼트 트리라고 한다. 세그먼트 트리는 기본적으로 Complete Binary Tree이고, 모든 Element에 대한 정보가 트리의 Leaf Node에 포함된다. 그리고 그 위 node들은, 자식 node를 포함하는 구간에 대한 정보를 담는 것이다. 간단하게, 세그멘트 트리를 이용해서 구간합을 구하는 코드의 예시를 보자. .. 2020. 9. 13. 이전 1 다음
