본문 바로가기

Computer Science304

백준 2042 구간 합 구하기 / 세그먼트 트리 - 세그먼트 트리- 로그엔 로그엔으로 계산함- 이닛, 업데이트, 섬 이렇게 3개의 함수로 구성됨- 모두 재귀로 구성됨- 어떤 개념인지는 명확히 앎 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include #include #include using namespace std; long long init(vector &a, vector &tree, int node, int start, int end) { if (start == end) { return tree[node] = a[start]; } else { return tree[node] .. 2018. 12. 12.
1780 종이의 개수 / 분할 정복 1. 문제2. 재귀형식3. 체크 사항4. 인덱스 주의5. 같은 지 확인 하는 함수, 풀이 함수 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include using namespace std;#define MAX_N 2188int N;int paper[MAX_N][MAX_N];int cnt[3]; // cnt[0] : -1로만 채워진 종이의 개수, cnt[1] : 0으로만 채워진 종이의 개수, cnt[2] : 1로만 채워진 종이의 개수bool same(int x, int y, int n){ for (int i = x; i 2018. 12. 11.
1766 문제집 / indgree 위상정렬 1. 벡터2. 큐3. 벡터, 벡터 vt4. pq 우선순위 큐 vt 를 만들어서, 패런트와 차일드 관계를 만듬그리고 pq 우선순위 큐를 사용함in을 사용함 그래서 이어져 있는 것을 찾음 1234567891011121314151617181920212223242526272829303132333435#include #include #include #include #define MAX_N 32000using namespace std;int n, m, a, b, in[MAX_N + 1];vector vt;priority_queue pq;int main() { freopen("input.txt", "r", stdin); scanf("%d%d", &n, &m); vt.resize(n + 1); for (int i = .. 2018. 12. 7.
백준 2252 줄 세우기 / 위상 정렬 1. 알고리즘2. 벡터3. 스택4. 백터 백터5. 오토 키워드6. 먼저 1부터 넣어서, dfs를 돌려서 연결이 안되는 지점까지 가면순서대로 스택에 넣습니다그리고 마지막에 스택에서 빼면 됨그리고 비지트의 경우, 방문했는지 안했는지를 체크하기 위해서 사용합니다순서 확실히 하면 됨 1234567891011121314151617181920212223242526272829303132333435363738#include #include #include #include #include #define MAX_N 32000using namespace std;vector vt;stack st;int n, m, x, y, visited[MAX_N + 1];void dfs(int v) { visited[v] = true; f.. 2018. 12. 7.
공통 조상 찾기 트리 1. 벡터와2. 큐를 사용함3. 벡터 를 사용하여 트리 구조를 나타냄 1. 높이를 찾고2. 공통 조상을 찾고3. 아래 들어 있는 서브트리의 개수를 셈 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697#include#include#includeusing namespace std; int get_depth(vector& parent, int v){ int ret = 0; int cur = v; while (cur != 1) { r.. 2018. 12. 7.
expert / 블록 부품 문제풀이연산과정순서해설답지구현 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163.. 2018. 12. 6.
쿠리 / 더블 링크드 리스트 더블 링크드 리스트배열을 사용해서 링크드 리스트배열의 크기를 어떻게 설정해야 하는가구조체를 만들어서 노드를 만들어도 될 것 같음그리고 삽입, 삭제 그리고 탐색이 가능함포인터가 가르키는 것을 반복함 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132.. 2018. 12. 6.
쿠리 프로 시험 유용 그래프 사용법 1. 배열 이용하는 방법2. 리스트 이용하는 방법각각 맵에 저장하고 검색하는 방법을 나타내고 있음아래 코드는 리스트 이용하는 방법 연결된 노드 정보를 single linked list 배열에 저장한느 방식parent 정보가 없는 Tree 생각 초기화시 myalloc 사용하는 heap_cnt 와 Single linked list 저장되는 table[]을 초기화 주면 됨가중치가 있는 그래프의 경우 node 구조체에 value를 추가하고, n->value에 가중치를 저장하면 됨 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include usi.. 2018. 12. 6.
박트리 - Pro 공부법 해싱 : 비형 해싱, 응용링크드리스트 : 링크드리스트 트리 구현 : 자식 수 비고정 트리 구현 메모이제이션 : 한 번 계산한 값 저장비트마스킹 : 변수 쪼개서 공간복잡도 아끼면서 저장, 비트 연산 통해 코드 최적화 문제 트라이 문자열 관련된 문제. 트라이 해싱 정해인 정도 트라이 해싱LCA 디렉토리 구조 가계도 유형BST : 바이너리 서치 트리Segment Tree : 2018. 12. 4.

티스토리툴바