본문 바로가기

자료구조12

[자바, C++] 백준 2042 - 구간 합 구하기 (java cpp) 문제 : boj2042 필요 알고리즘 개념 펜윅 트리, 세그먼트 트리 등 펜윅 트리, 세그먼트 트리 등 구간 쿼리 알고리즘(자료구조)를 알고 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 펜윅 트리, 세그먼트 트리 등으로 풀 수 있는 기본형태의 문제이다. 펜윅 트리로 풀려면 작성해둔 펜윅 트리 글에서 '기본 : 펜윅 트리' 부분을 읽어보면 이 문제를 풀 수 있다. 코드(C++ 펜윅 트리) : github.. 2022. 8. 12.
[자료구조] C언어 - 이진 탐색 트리(BST , binary search tree) 구현 - 객체지향 - C언어로 구현한 이진 탐색 트리(BST, binary search tree) 코드이다. 완벽하진 않지만 c에서 객체지향 개념을 넣을 수 있는 기본 베이스는 마련해둔 코드이다. - 재귀를 사용한 버전과, 그렇지 않은 버전 두 가지 종류가 함께 들어있다.(각각 따로 빼내도 된다.) 사용예시처럼 구분해서 사용할 수 있다. 덕분에 코드가 좀 길다. binary_search_tree.c만 600줄정도.. - 글 말고 github으로 보려면 여기를 누르면 된다. - 영어를 잘 못하지만 주석을 영어로 작성했으므로 틀린 표현이 많을 수 있다. (댓글로 알려줘요 ㅠ) - 이하 코드에서 사용된 node.h, list.h, list.c, stack.h, stack.c, queue.h, queue.c는 '[자료구조] C언.. 2022. 4. 9.
[자료구조] C언어 - 우선순위 큐(priority queue) 구현 - 객체지향 - C언어로 구현한 우선순위 큐(priority queue) 코드이다. 완벽하진 않지만 c에서 객체지향 개념을 넣을 수 있는 기본 베이스는 마련해둔 코드이다. - 글 말고 github으로 보려면 여기를 누르면 된다. - 영어를 잘 못하지만 주석을 영어로 작성했으므로 틀린 표현이 많을 수 있다. (댓글로 알려줘요 ㅠ) 0. 사용 예시 #include #include"priority_queue.h" int main(int argc, char* argv[]) { priority_queue_t* q = create_priority_queue(); q->op->insert(q, 132); q->op->insert(q, 6929); q->op->insert(q, 232); q->op->insert(q, 5933);.. 2022. 4. 9.
[자료구조] C언어 - 큐(queue) 구현 - 객체지향 - C언어로 구현한 큐(queue) 코드이다. 완벽하진 않지만 c에서 객체지향 개념을 넣을 수 있는 기본 베이스는 마련해둔 코드이다. - 글 말고 github으로 보려면 여기를 누르면 된다. - 영어를 잘 못하지만 주석을 영어로 작성했으므로 틀린 표현이 많을 수 있다. (댓글로 알려줘요 ㅠ) - 이하 코드에서 사용된 node.h, list.h, list.c는 '[자료구조] C언어 - 이중 연결 리스트(doubly linked list) 구현 - 객체지향' 글에서 구현한 코드들이다. 위 github에서 보거나, 여기를 눌러 해당 글에서 확인하면 된다. 0. 사용예시 #include #include"queue.h" int main(int argc, char* argv[]) { queue_t* q = crea.. 2022. 4. 9.
[자료구조] C언어 - 스택(stack) 구현 - 객체지향 - C언어로 구현한 스택(stack) 코드이다. 완벽하진 않지만 c에서 객체지향 개념을 넣을 수 있는 기본 베이스는 마련해둔 코드이다. - 글 말고 github으로 보려면 여기를 누르면 된다. - 영어를 잘 못하지만 주석을 영어로 작성했으므로 틀린 표현이 많을 수 있다. (댓글로 알려줘요 ㅠ) - 이하 코드에서 사용된 node.h, list.h, list.c는 '[자료구조] C언어 - 이중 연결 리스트(doubly linked list) 구현 - 객체지향' 글에서 구현한 코드들이다. 위 github에서 보거나, 여기를 눌러 해당 글에서 확인하면 된다. 0. 사용예시 #include #include"stack.h" int main(int argc, char* argv[]) { stack_t* s = cre.. 2022. 4. 9.
[자료구조] C언어 - 다항식(polynomial) 구현 - 객체지향 - C언어로 구현한 다항식(polynomial) 코드이다. 완벽하진 않지만 c에서 객체지향 개념을 넣을 수 있는 기본 베이스는 마련해둔 코드이다. - 글 말고 github으로 보려면 여기를 누르면 된다. - 영어를 잘 못하지만 주석을 영어로 작성했으므로 틀린 표현이 많을 수 있다. (댓글로 알려줘요 ㅠ) - 이하 코드에서 사용된 node.h, list.h, list.c는 '[자료구조] C언어 - 이중 연결 리스트(doubly linked list) 구현 - 객체지향' 글에서 구현한 코드들이다. 위 github에서 보거나, 여기를 눌러 해당 글에서 확인하면 된다. 0. 사용예시 #include #include"polynomial.h" int main(int argc, char* argv[]) { polyn.. 2022. 4. 9.
[자료구조] C언어 - 이중 연결 리스트(doubly linked list) 구현 - 객체지향 - C언어로 구현한 리스트 (doubly linked list) 코드이다. 완벽하진 않지만 c에서 객체지향 개념을 넣을 수 있는 기본 베이스는 마련해둔 코드이다. - 글 말고 github으로 보려면 여기를 누르면 된다. - 영어를 잘 못하지만 주석을 영어로 작성했으므로 틀린 표현이 많을 수 있다. (댓글로 알려줘요 ㅠ) 0. 사용 예시 #include #include #include"list.h" int main(int argc, char* argv[]) { list_t* l = create_list(); printf("--- insert test ---\n"); l->op->insert_to_head(l, "aaa"); l->op->insert_to_tail(l, "bbbb"); l->op->inser.. 2022. 4. 9.
이분 그래프 (bipartite graph) 그래프의 정점의 집합을 둘로 나눴을 때, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프를 이분 그래프(bipartite graph)라고 한다. 즉, 정점을 어떠한 방법으로든 두 개의 집합으로 나눴을 때 각 집합의 정점끼리 간선이 존재하지 않게 나눌 수만 있다면 이분 그래프이다. 예를들어 위 이미지에서 1,2,3은 이분 그래프이고 4는 이분 그래프가 아니다(4번의 경우 동일한 집합끼리 간선이 연결되어 있다. 이와 같이 홀수 길이의 사이클이 있다면 이분 그래프가 될 수 없다.). 또 3과 같이 서로 연결된 부분이 없더라도 어쨌든 이분 그래프의 정의를 위반시키지 않으므로 이분 그래프이다. 이분 그래프 판별방법은 다음과 같다. 1. 모든 정점에 대해 각 정점에서 dfs 혹은 bfs를 진.. 2022. 3. 23.
백준 17162 자바 - 가희의 수열놀이 (Small) (BOJ 17162 JAVA) 문제 : boj17162 mod가 최대 10^2라서 뭐 복잡한 알고리즘 필요없이 풀 수 있다. 결국 나누었을 때 0, ..., mod-1인 수가 어느 idx 위치에 있냐가 중요하다. 이걸 빨리 알 수 있으면 되는건데, mod가 10^2이니깐 대충 O(Q * mod) 정도의 시간복잡도만 가져도 풀 수 있다. 그럼 해볼만한게 많이 있다. 내 경우엔 어차피 맨 뒤에서만 수가 추가되고 빠지니 스택을 사용했다. 그리고 mod개 만큼의 스택을 마련했다. 스택배열을 arr이라고 하고, 현재 넣을 위치를 idx라고 하겠다. 그럼 각 쿼리에 대해 다음과 같이 대응할 수 있다. --- [ 쿼리 : 1 num ] arr[num % mod]에 num을 추가하고 idx++ -> O(1) [ 쿼리 : 2 ] 최대 10^2개인 a.. 2022. 3. 18.
자료구조 큐, 스택, 덱 (Queue, Stack, Deque) Queue, Stack, Deque(=Double-ended Queue) 큐, 스택, 덱은 배열, 리스트와 함께 선형 자료구조에 속하는 자료구조들이다. 사실 큐, 스택, 덱의 모든 기능은 리스트(이하 '리스트'라는 단어는 모두 Linked List를 뜻함)만 사용해서도 시간복잡도 마저 동일하게 동작할 수 있다. 즉, 어찌보면 스택, 큐, 덱은 리스트에 포함되는 자료구조라고 볼 수 있다. 그럼에도 큐, 스택, 덱은 분명 리스트와는 별개의 자료구조로 정의되어 사용되고 있다. 이건 일종의 컨셉, 규칙에 해당한다고 생각한다. 술먹고 있는데 상대방이 갑자기 병따개를 준다. 병따달라는 의도를 바로 파악할 수 있다. 술먹다가 이번엔 상대방이 멀티툴을 갑자기 준다. 물론 멀티툴엔 병따개가 있다. 하지만 난 멀티툴을 받.. 2021. 10. 11.

티스토리툴바