자료구조7 Trie (트라이 자료 구조) 본인이 이해하기 위해 작성한 글입니다. 이 포스팅은 트라이가 뭔지는 알겠는데 막상 짜려면 기억이 잘 안나시는 분이 보면 유용할 것입니다. 링크: www.notion.so/Trie-875eeb41921f4559b87a38f1e4136e7e 틀린 내용이 있다면 피드백 주시면 감사하겠습니다. 2020. 8. 6. [깡구현] STACK 문제: https://www.acmicpc.net/problem/10828 t (=top)라는 변수 하나만 가지고 스택을 컨트롤하면 됩니다. 스택이 비어있는 조건은 top이 초기값일 때 입니다. #define STACK_SIZE 10005 typedef struct STACK { int S[STACK_SIZE]; int t, sz; STACK() : t(-1), sz(0) {} bool empty() { return (t == -1); } int size() const { return sz; } void push(int val) { S[++t] = val; sz++; } int top() { if (empty()) return -1; else return S[t]; } int pop() { if (emp.. 2020. 5. 16. [깡구현] QUEUE_2 문제: https://www.acmicpc.net/problem/10845 값을 넣을 때는 r (=rear)을 사용합니다. 값을 뺄 때는 f (=front)을 사용합니다. 큐가 비어있는 조건은 front == rear 일 때 입니다. #define QUEUE_SIZE 100001 typedef struct QUEUE { int Q[QUEUE_SIZE]; int f, r, sz; QUEUE() { f = r = sz = 0; } bool empty() { return (f == r); } int front() { if (empty()) return -1; else return Q[f]; } int back() { if (empty()) return -1; else return Q[(r-1 + QUEUE_S.. 2020. 5. 16. 배열(Array) 출처: https://blog.encrypted.gg/725?category=773649 배열은 메모리 상에 원소를 연속하게 배치한 구조입니다. 1. 장점 다른 자료구조와 달리 원소를 저장하는 것 이외에 추가적으로 소모되는 메모리 양이 거의 없다는 점 2. 단점 반드시 메모리상에 연속한 구간을 잡아야하기 때문에 할당에 다시 제약이 걸린다는 점이 단점. 배열을 사용하는 경우 1. 인덱스에 해당하는 원소를 빠르게 접근해야 할 때 2. 아카이브처럼 데이터를 자주 바꾸거나 확인하는 일 없이 쌓아두고 싶을 때 (만약 데이터의 삽입/삭제가 빈번한 상황이라면 배열은 비효율적) 배열연산 시간복잡도 1. 임의의 위치에 있는 원소를 확인/변경 : 원소가 연속하게 배치되어 있으므로, 임의의 위치의 원소를 O(1)에 확인/변.. 2020. 5. 15. 이전 1 2 다음
