자료구조

트리의 순회 방법에 대해 알아보기에 앞서 트리에 대한 기본적인 배경지식은 아래의 포스팅을 참고하면 좋을 것 같다. https://go2gym365.tistory.com/274 [자료구조] Tree & Binary Tree 1. Tree / 트리 한개 이상의 노드로 이루어진 유한 집합이며, 비선형 자료구조이다. 하나의 루트 노드 아래에 0개 이상의 자식 노드로 구성된다. 그리고 그 자식 또한 0개 이상의 자식 노드를 가지 go2gym365.tistory.com 1. 전위 순회 / PreOrder 순회 순서 : [ 루트 노드(부모 노드) > 왼쪽 노드 > 오른쪽 노드] 순서로 방문한다. 위의 그림에서 전위 순회한 결과 : [1 > 2 > 4 > 8 > 5 > 3 > 6 > 7 ] 2. 중위 순회 / InOr..

트리에 대한 기본적인 배경지식은 아래의 포스팅을 참고하면 좋을 것 같다. https://go2gym365.tistory.com/274 [자료구조] Tree & Binary Tree 1. Tree / 트리 한개 이상의 노드로 이루어진 유한 집합이며, 비선형 자료구조이다. 하나의 루트 노드 아래에 0개 이상의 자식 노드로 구성된다. 그리고 그 자식 또한 0개 이상의 자식 노드를 가지 go2gym365.tistory.com 1. Node 구조체 노드는 값과 자식 노드로 left, right노드를 가지고 있다. struct Node { int data; Node* left; Node* right; Node() { left = nullptr; right = nullptr; } }; 2. Binary Tree Cl..

1. Tree / 트리 한개 이상의 노드로 이루어진 유한 집합이며, 비선형 자료구조이다. 하나의 루트 노드 아래에 0개 이상의 자식 노드로 구성된다. 그리고 그 자식 또한 0개 이상의 자식 노드를 가지고있고 무한히 반복가능하다. 컴퓨터의 디렉터리 구조가 대표적인 트리 구조로 이루어져 있다! 1-2. Tree 용어 루트 노드(root node) : 부모가 없는 노드. 트리에는 오직 하나의 루트 노드만이 존재한다. 리프 노드, 단말 노드(leaf node, terminal node) : 자식이 없는 최말단 노드 내부 노드, 비단말 노드(internal node, nonterminal node) : 단말 노드를 제외한 나머지 노드 가지, 링크(branch, link, edge) : 노드와 노드를 연결하는 선...

1. 이중 연결 리스트란? 이중 연결 리스트란 단일 연결리스트와 다르게 양방향으로 노드가 이어진 리스트이다. 이중 연결 리스트는 이전 노드와 이후 노드가 이어져 있기 때문에 삽입 삭제 연산 시 이전, 이후 노드를 저장하지 않아도 되기 때문에 훨씬 유연하게 사용할 수 있다. 2. 이중 연결 리스트 구현 이번 이중 연결 리스트 구현은 Head와 Tail에 data가 들어있지 않은 더미(dummy)노드를 사용해서 구현했다. 2-1. 구조체 및 클래스 선언부 이중 연결 리스트는 노드 두개가 서로 연결 되어있기 때문에 이전 노드와 다음 노드를 포인팅하는 prev, next 구조체 포인터를 선언해줬다. struct Node { Node* prev; Node* next; int data; }; class Doubly..

1. 단일 연결 리스트란? 각 요소들이 데이터부분과 다음 값 주소를 포인팅하는 노드라는 형태로 이루어져 있으며 체인 형태로 선형으로 이루어진 자료구조이다. 값을 추가할 때 배열은 정해진 사이즈를 넘으면 Overflow가 발생하지만 Linked List는 동적으로 할당해서 노드들을 이어주면 되기 때문에 메모리 사이즈 문제에서 벗어날 수 있다. 하지만 노드들이 서로 체인형태로 이어져 있어 배열처럼 인덱스 개념으로 접근이 불가하기 때문에 순회하여 값을 찾아야 하으로 탐색에 있어서는 배열보다 느리다. 하지만 값을 중간에 넣는 경우 배열은 중간에 값을 삽입하고 한칸씩 뒤로 미뤄줘야 하기 때문에 원소의 갯수에 따라 시간이 차이가 나는 방면, 연결 리스트의 경우 단지 노드의 포인팅만 바꿔주면 되기 때문에 최악의 경우..

1. Queue란? 선입 선출(First In First Out) 즉 먼저 들어간 데이터가 제일 먼저 나오는 성질을 가지는 자료구조이다. 우리의 실생활에서 가장 많이 볼 수 있다. ex) 대기열, 프린터 큐 시간 복잡도 : O(1) 2. Queue 구현 구현해본 기능은 1. Push : 원소를 큐에 넣음 2. Pop : 큐에 가장 먼저 들어간 원소를 제거 3. Front : 큐에 가장 먼저 들어간 원소를 출력 4. Size : 큐에 들어가있는 원소의 갯수를 출력 5. IsEmpty : 큐가 비었는지 확인 6. IsFull : 큐가 다 찼는지 확인 나는 처음에 사용자한테 queue의 사이즈를 입력받아서 구현했고, 원형 큐 형태로 구현했기 때문에 실제로 사용자가 입력한 큐의 사이즈보다 -1만큼 적게 사용한다..

1. Stack이란? 후입선출(Last In First Out) 즉 나중에 들어간 데이터가 제일 먼저 나오는 성질을 가지는 자료구조이다. 시간복잡도 : O(1) 2. Stack구현 Push(int value) : value를 스택의 최상단에 삽입 Pop() : 최상단의 원소를 스택에서 제거. 만약 스택이 비었다면 프로그램 종료 Top() : 스택의 최상위 원소를 반환. 만약 스택이 미었다면 프로그램 종료 Size() : 스택의 원소의 갯수를 반환. isEmpty() : 스택이 비어있는지 여부를 반환. #include #include using namespace std; class Stack{ private: int *arr; int top; int capacity; public: Stack(int siz..

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 1. Logic - 메모리 제한이 12MB밖에 안되기 때문에 자료구조에 들어가는 데이터의 갯수를 최대한 적게 넣어야한다. 우선순위 큐를 활용해 -를 붙혀서 오름차순으로 정리해 주고 갯수는 N개 만큼 가지고 있는다. 우선순위 큐의 가장 앞에 있는 수는 -를 떼고 나면 가장 작은 숫자이기 때문에 N개만큼 유지하면서 가장 작은 숫자인 -pq.top보다 큰 숫자가 오면 pq.top을 pop하고 새로운 숫자를 p..

https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 1. Logic 1. pair를 원소로 가지는 stack 하나를 선언한다. pair는 이다. 2. 현재 입력받은 키보다 작은 애들은 무조건 볼 수 있기 때문에 pairCnt를 올려주고 어짜피 나보다 작은애들이기 때문에 나보다 큰 애가 들어오게 되면 내 뒤의 작은애는 보지 못하기때문에 스택에서 pop해주고 다시 넣어주지 않는다. > 이 방식으로 스택을 항상 내림차순으로 정렬해..

https://www.acmicpc.net/problem/17503 17503번: 맥주 축제 첫 번째 줄에 축제가 열리는 기간 N (1 ≤ N ≤ 200,000) 과, 채워야 하는 선호도의 합 M (1 ≤ M 도수기준 오름차순 정렬 2. 선호도를 sum에다 누적해주고 우선순위 큐에 도수가 낮은거부터 순서대로 선호도에 -를 붙혀서 오름차순으로 정렬해준다. 3. 우선순위 큐pq의 사이즈 pq.size()값이 n이랑 같아지면 sum이 m 이상인지 확인 후 이상이면 현재 beer의 도수를 출력한다. 이유는 beer 벡터를 알콜 도수가 높은 순서대로 알콜도수 기준 오름차순 정리를 했기 때문에 지금 조건의 알콜 도수가 최소 도수이다. 4. 만약 3번에서 안걸러지고 우선순위 큐의 갯수가 n을 넘었다면 pq.top()..