내 세상

head / tail을 사용해서 양쪽 끝단을 시용한다. → Double Linked List의 특징 단, head의 경우 next의 값부터 사용하는 것을 전제로 함. 이유는 head->next를 첫번째 값으로 사용했을 경우, null 상태일때 대처를 손쉽게 할 수 있기 때문임. const int MAX_N = 30001; struct node { int val; node* next; node* prev; node* alloc(int _val, node* _next, node* _prev) { val = _val; next = _next; prev = _prev; return this; } }buf[MAX_N], *head, *tail; int bCnt; void init() { for (int i = 0..

#define _CRT_SECURE_NO_WARNINGS #include const int LM = 5e5 + 100; const int MOD = 65537; int strcmp(const char* a, const char *b){ while (*a && *a == *b){ a++; b++; } return *a - *b; } int bCnt; struct Node { char id[14]; int isLogin; Node* next; Node* alloc(Node* np){ isLogin = 0, next = np; return this; } }buf[LM], htab[MOD]; int N, cmd; int memberCnt, loginCnt; unsigned int djb2(char* s){ un..

/// === main.cpp === #define _CRT_SECURE_NO_WARNINGS #include const int MAX_LEN = 1100000; int N, bn; struct Node { char val; Node* prev; Node* next; Node() : prev(NULL), next(NULL), val(0) {} Node* alloc(char _val, Node *_prev, Node *_next){ val = _val; prev = _prev; next = _next; return this; } }buf[MAX_LEN]; Node* Head; Node* cursor; void insert(char ch){ Node* temp = buf[bn++].alloc(ch, NULL..

#ifndef NULL #define NULL 0 #endif const int SIZE = 100010; struct Node{ int num; Node* next; Node() : num(0), next(NULL) {} Node(int n, Node* np){ num = n, next = np; } ~Node() { delete next; } void erase(Node*& ref){ ref = next; next = NULL; delete this; } }buf[SIZE]; int bcnt; struct Queue{ Node*head, *tail; int cnt; Queue(){ cnt = 0; head = tail = new Node(); } ~Queue(){ cnt = 0; delete head..

#define _CRT_SECURE_NO_WARNINGS #include const int MAX_N = 50050; int N, M; int group[MAX_N]; int ans; int find(int k){ if (group[k] == k) return k; return group[k] = find(group[k]); } int main() { freopen("input.txt", "r", stdin); scanf("%d %d", &N, &M); ans = N; int i, u, v; for (i = 1; i

#define _CRT_SECURE_NO_WARNINGS #include const int MAX_N = 1004; int N, arr1[MAX_N], temp[MAX_N]; void input() { scanf("%d", &N); for (int i = 0; i = en) return; int m = (st + en) / 2; mergeSort(arr, st, m); mergeSort(arr, m + 1, en); int i = st, j = m + 1; for (int k = st; k en) temp[k] = arr[i++]; else if ..

보호되어 있는 글입니다.

MST (Minimum Spanning Tree) - https://sga8.tistory.com/32 [Data Structure] Graph, etc Graph는 기본적인 형태이다. 방향의 여부, 가중치의 여부, 연결의 여부, 순환의 여부 등에 따라서 이름이 변경되고 결정된다. 예를 들어, Minimum Spanning Tree의 의미를 하나씩 분석해보자. Tree? 순환(Cycle)이.. sga8.tistory.com Kruskal Algorithm (간선 위주의 알고리즘) - Greedy Method - 과정 1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 2. 정렬된 간선 리스트에서 가장 낮은 가중치를 선택한다. 3. 사이클이 형성된다면, 해당 간선을 제외하고 2번 과정을 다시 진행한다...

Inserting Sort - N 크기의 배열 - 두 번째 index부터 시작해서, 앞 부분에 자신보다 작은 값이 있을 때까지 지나가는 값을 (현재 위치+1)로 이동시킴 - 시간복잡도 O(N^2) Counting Sort - N 크기의 배열, K 크기의 배열 (counting 용도) - 배열 내 각 값들의 개수를 counting → counting된 array를 누적해가며 index 계산 → N 크기 배열 순회하며 배치 - 시간복잡도 O(N+K) - reference) http://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html Quick Sort - N 크기의 배열 - Divide and Conquer 방법 - 과정 (..

Topological Sort - DAG(Directed Acyclic Graph)를 활용해 노드들 사이에 선후관계를 중심으로 정렬하는 알고리즘 - DFS(Depth-First Search, 깊이우선탐색) 사용 → 결과를 역으로 나타냈을 때 위상정렬 결과와 동일함. - '그래프'를 정렬하는 것으로 정렬 기준은 '진입 차수(해당 노드로 들어오는 간선의 개수)의 비 내림차순' 순서 - 진입차수가 0인 노드들 제거 - 진입차수가 0이 아닌 노드들은 점점 0으로 수정되며 제거 # 참고 : https://ratsgo.github.io/data%20structure&algorithm/2017/11/21/Topological/

DFS (Depth-First Search, 깊이 우선 탐색) - 방식 : - 모든 노드를 탐색 후 자신에게 돌아와야 끝난다. - 역추적(Backtracking) 과정이 있어 Stack / Recursion을 사용 - 자기 자신을 호출하는 순환 알고리즘의 형태 - 사용 예시 - 미로 생성 - Cycle Detection - Topological Sorting - 시간복잡도 (정점 N, 간선 E) - 인접 리스트로 표현된 그래프 O(N+E) - 인접 행렬로 표현된 그래프 O(N^2) - 장점 - 현 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 비교적 적다. - 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. - 단점 - 해가 없는 경로에 깊이 빠질 가능성이 있음. → 임의로 지정한 ..

백준 13460번 구슬 탈출 2 https://www.acmicpc.net/problem/13460 문제 풀이 해당 문제는 bfs 느낌보다 dfs 느낌으로 접근하여 진행함 !!!!!!!! 1. 보드 - 크기 NxM (세로 N, 가로 M) - 가장 바깥 행과 열은 막혀져 있음. - 구멍이 하나 있음. - 입력 데이터 "O" - 상, 하, 좌, 우 4가지 방향으로 기울이기 가능함. (최대 10회) 2. 빨간 구슬 - 구멍에 들어가야 함. - 입력 데이터 "R" 3. 파란 구슬 - 절대 구멍에 들어가선 안됨. - 입력 데이터 "B" 주의 사항 1. 보드를 기울이면 파란 구슬과 빨간 구슬이 동시에 움직임 → 파란 구슬을 끝까지 이동시킨 후 빨간 구슬을 끝까지 이동시킨다 (X) → 파란 구슬과 빨간 구슬을 동시에..

https://www.acmicpc.net/problem/14503 문제 풀이 복잡한 설명이지만 굉장히 간단하게 생각해야한다. 후진의 경우도 방향을 그대로 살려서 각 방향에 따라 진행하는 방향의 반대로 가기 때문에 현재 좌표에서 빼줌으로써 해결하면 좋음 :) 문제에서 유일하게(?) 조심해야할 점은 일반적으로 "동,서,남,북" 이라고 말하고 쓰는데, "북, 동, 남, 서"를 기준으로 문제를 해석해나가야함 ! 시뮬레이션 부분에서 예전보다 많이 어려움을 느끼는 것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 ..

https://www.acmicpc.net/problem/2146 문제 풀이 초기에는 특정 섬에서 다른 섬까지 이동하는 경로를 dfs로 구현했음. 하지만 굉장히 바보같이 무식한 생각이라는 걸 뒤늦게 깨달은 후 좌표만으로 계산하여 문제를 해결함. 문제를 보면 최단거리를 찾는 문제로 착각하기 쉬운데, 이러한 트릭을 잘 해결하는 머리를 가지도록 해보자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 7..

백준 14890번 경사로https://www.acmicpc.net/problem/14890 문제 풀이- 경사로 조건 1. 경사로는 낮은 칸에 놓으며, L개의 연속된 칸의 높이가 동일해야함. 2. 낮은 칸과 높은 칸의 차이는 오직 1이어야 함. - 경사로를 놓는 2가지 경우 1. 이전 칸이 현재 칸보다 1 낮은 경우 (이전 칸 높이 현재 칸 높이) - 현재 칸에서 뒤의 칸까지 총 L개가 높이가 동일한지 확인해야함...

백준 15683번 감시https://www.acmicpc.net/problem/15683 총 5종류의 CCTV가 있는데, 각 CCTV 별로 지켜볼 수 있는 방향이 정해져 있음. - 1번 : 상, 하, 좌, 우 중 1방향 - 2번 : (상, 하) or (좌, 우) 중 하나 - 3번 : 상, 하, 좌, 우 중 2 방향 (대신, 선택된 두 방향은 인접해야함) - 4번 : 상, 하, 좌, 우 중 3방향 - 5번 : 상, 하, 좌, 우 모든 방향 그 외에 6번은 '벽'이고, cctv 영상은 벽까지만 볼 수 있으며 벽을 건너서는 볼 수 없음.이러한 CCTV 별 특성으로 인하여 각 별개로 처리를 해주어야 함. 문제 풀이1. 초기에 데이터를 입력 받음과 동시에 각 cctv를 배열에 저장함. 이때, 5번 cctv는 별도..