본문 바로가기

CS24

[자료구조] 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.
분할 정복을 이용한 거듭제곱 최적화 아마 다음은 이미 알고 있을 것이다. 예를들어 거듭제곱되는 수치가 짝수일 때와 홀수일 때를 예로들면 다음과 같다. A^4 = (A^2)^2 (짝수일때) A^5 = A * A^4 = A * (A^2)^2 (홀수일때) 만약 A^8이 있다면 원래는 A*A*A*A*A*A*A*A 으로 곱셈 연산을 7번 해야 하지만, A^8을 ((A^2)^2)^2 으로 변경하면 A*A=A', A'^2=A'' 이라 할 시 최종적으로 A'을 구하는데에 A*A로 곱셉 한번, A''=A'*A'을 구하는데도 마찬가지로 곱셈 한번, 최종적으로 A''*A''을 구하는데 곱셈 한 번이 들어간다. 즉 7번의 연산이 3번의 연산으로 줄어든다! 즉, 거듭제곱을 위와 같이 계산한다면 원래 N번의 연산이 O(logN)으로 줄어든다. 여기서 분할정복을 활.. 2022. 4. 5.
이분 그래프 (bipartite graph) 그래프의 정점의 집합을 둘로 나눴을 때, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프를 이분 그래프(bipartite graph)라고 한다. 즉, 정점을 어떠한 방법으로든 두 개의 집합으로 나눴을 때 각 집합의 정점끼리 간선이 존재하지 않게 나눌 수만 있다면 이분 그래프이다. 예를들어 위 이미지에서 1,2,3은 이분 그래프이고 4는 이분 그래프가 아니다(4번의 경우 동일한 집합끼리 간선이 연결되어 있다. 이와 같이 홀수 길이의 사이클이 있다면 이분 그래프가 될 수 없다.). 또 3과 같이 서로 연결된 부분이 없더라도 어쨌든 이분 그래프의 정의를 위반시키지 않으므로 이분 그래프이다. 이분 그래프 판별방법은 다음과 같다. 1. 모든 정점에 대해 각 정점에서 dfs 혹은 bfs를 진.. 2022. 3. 23.
에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유 흔히 에라토스테네스의 체를 사용해 n 이하의 모든 소수를 구하려고 할 때, 효율적으로 구하기 위해 n의 제곱근( sqrt(n) ) 까지만 확인하곤 한다. 1년전쯤엔 n까지 다 확인하거나, 좀 머리 쓴다고 n/2까지 확인했었다. 그런데 당시에 sqrt(n)까지만 본다는 획기적인 말을 들었고, 증명을 찾아봤었다. 증명을 어디서 봤는진 정확히 모르겠다. 아무튼 자주 쓰이다보니 현재까지도 기억하고 있고, 중간중간 블로그에 해설을 적을 때 에라토스테네스가 나올때 마다 작성하기 귀찮아서 따로 글을 쓰게 되었다. 최대한 쉽게 작성해보겠다. n 이하의 모든 소수를 구한다고 해보자. 이 때 해당 수 n은 자연수 a, b에 대해 n = a * b 라고 표현할 수 있다. -> 예를들어 12는 2*6 혹은 3*4 등으로 나타.. 2022. 2. 12.
자료구조 큐, 스택, 덱 (Queue, Stack, Deque) Queue, Stack, Deque(=Double-ended Queue) 큐, 스택, 덱은 배열, 리스트와 함께 선형 자료구조에 속하는 자료구조들이다. 사실 큐, 스택, 덱의 모든 기능은 리스트(이하 '리스트'라는 단어는 모두 Linked List를 뜻함)만 사용해서도 시간복잡도 마저 동일하게 동작할 수 있다. 즉, 어찌보면 스택, 큐, 덱은 리스트에 포함되는 자료구조라고 볼 수 있다. 그럼에도 큐, 스택, 덱은 분명 리스트와는 별개의 자료구조로 정의되어 사용되고 있다. 이건 일종의 컨셉, 규칙에 해당한다고 생각한다. 술먹고 있는데 상대방이 갑자기 병따개를 준다. 병따달라는 의도를 바로 파악할 수 있다. 술먹다가 이번엔 상대방이 멀티툴을 갑자기 준다. 물론 멀티툴엔 병따개가 있다. 하지만 난 멀티툴을 받.. 2021. 10. 11.
백트래킹 알고리즘 (Back Tracking) 다음과 같은 그래프가 있다. 여기서 1부터 시작해서 숫자 순서대로 얼마나 멀리 갈 수 있는지 찾고싶다. 즉 1->2->3->4->5->... 이런식의 루트를 찾으려 한다. 우선 생각해볼 수 있는 방법은, 그냥 모든 루트에 대해 DFS 등을 사용해 전부 탐색해 보는 것이다. 이 방식이 이전에 작성한 Brute Force 방식이다. 그냥 컴퓨터의 빠른 연산력에 기대어 모든 경우를 확인하는 것이다. 위는 모든 경우를 살펴보는 DFS 과정의 순서를 표시한 것이다. 모든 경우를 확인해보니 결국 1->2->3->4를 찾긴했다. 그런데 우린 직관적으로, 중간과정에서 이미 순서가 안맞다면 해당 루트로는 아예 안가봐도 될 것임을 알 수 있다. 그럼 다음 이미지를 보자. 위와 같이 답이 될 가능성이 없는 경로라면 더이상 .. 2021. 10. 3.

티스토리툴바