BOJ75 [깡구현] 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. [BOJ]4358번: 생태학 문제: https://www.acmicpc.net/problem/4358 map이나 트라이 알고리즘으로 해결할 수 있는 문제입니다. 정해는 트라이입니다. 위 코드가 트라이로 해결한 방법이고, 아래 코드가 map으로 해결한 방법입니다. 둘 사이에 왜 이런 시간 차이가 생기냐면, 나무 이름: T (30) 나무의 종류 갯수: N (10,000) 주어지는 나무의 그루 수: M (1,000,000) 트라이를 사용 경우: 하나의 나무를 트라이에 넣을 때 O(T) 만큼의 시간이 걸립니다. map을 사용하는 경우: 하나의 나무를 map에 넣을 때 O(logN * logN)의 시간이 걸립니다. (나무가 map에 있는지 체크하는데 logN, 그리고 map에 나무를 넣는데 logN) 그러므로 트라이 알고리즘의 시간복잡도는 .. 2020. 5. 10. [BOJ]14425번: 문자열 집합 트라이로 해결한 문제입니다. Map을 통해 해결해도 되지만, 트라이를 사용하면 O(500 * 10000) 정도에 해결할 수 있습니다. 주의해야할 점은, 아래 그림처럼 포함관계가 있는 경우에는 false를 리턴하도록 코드를 짜야합니다. baekjoononlinejudge (트라이에 있는 문자) bakjoon (쿼리로 들어온 문자) 2020. 5. 8. 이전 1 ··· 15 16 17 18 19 다음
