:: ADVANCE ::

[List] List 구현 연습 입력 0 -> init 1 # -> front 추가 + num 2 # -> tail 추가 + num 3 -> front delete 4 -> tail delete 5 # -> # number list 에서 삭제 6 -> print 더보기

[문자열] 접미어 배열 & LCP 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108// 접미어 배열 suffix array #include #define Size 100 char string[Size] = "banana";int suffixArray[Size];int lcp[Size];int strsize; void init(){ int i; for (i = 0; i

[문자열 검사] Boyer_moore 알고리즘 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include char string[] = "a pattern matching algorithm";char input[10] = "rithm";int size, stringsize;int skip[10]; int _strlen(char *str) { int size = 0; while (*(str + size) != '\0') size++; return size;} void makeskip(){ int i; for (i = 0; i

[문자열 검사] 카프-라빈 알고리즘 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899// 해시 값 함수를 이용#include char string[] = "hello my name is ksj";char input[10];int size;int strhash[30];int inputhash; int _strlen(char *str) { int size = 0; while (*(str + size) != '\0') siz..

[문자열 검사] KMP 알고리즘 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include char string[] = "naabcdabcdefmeaabcdabcefksj";char input[10] = "abcdabcef";int next[50];int size, stringsize; int _strlen(char *str) { int size = 0; while (*(str + size) != '\0') size++; return size;} void makenext(){ int i; next[0] = 0; ..

가장 긴 증가하는 부분수열 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #define N 6 int number[N] = { 10, 20, 10, 30, 40, 50 };int count[N];int index[N]; void init(){ for (int i = 0; i

순열 Permutation 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #define N 4#define R 3 int number[10]; int data[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; void swap(int *first, int *second) { int temp = *first; *first = *second; *second = temp;} void print(int n){ for (int i = n - 1; i >= 0; i--) { printf("%d ", number[i]); } printf("\n");} void permutation(int ..

[MST] 크루스칼 알고리즘 Kruskal Algorithm최소 스패닝 트리 구하는 알고리즘 중 하나다른 알고리즘으로는 Prim (프림) 알고리즘이 있다 최소 스패닝 트리는사이클을 형성하지 않고 가장 적은 가중치로 이루어진 트리이다 크루스칼은 간선을 기준으로 트리를 형성해 나가는 알고리즘이다.자세한 설명은 [참고] 이 곳이 설명이 자세하고 그림이 있어 이해하기 좋다 크루스칼은 dfs 또는 Union-find을 이용하여 구현할 수 있다 코드를 간단하게 하고 싶어서 Union-find을 이용하여 구현해 보았다. 간선을 오름차순으로 정렬하여야 하는데 입력받을 때 priority_queue에 넣어서 따로 정렬을 해주지 않았다.만약 C로 구현할 필요가 있다면 구조체를 선언하고, 정렬알고리즘을 따로 구현하기만 하면..

bit 중 1의 개수를 세어 저장해두는 함수 12345678void countbit(int n){ int bc[1

[BitMask] 에라토스테네스의 체 비트마스크를 이용한 에라토스테네스의 체 구현 에라토스테네스의 체는 빠르게 동작하기 때문에 수행 범위를 늘릴 때 부담이 되는 것은 시간보다는 메모리이다.체를 구현 할 때 범위 내의 각 정수들의 소수 여부를 저장하기 위해 범위 만큼의 배열 크기를 선언해 두었어야 했는데 비트마스크를 이용하여 이를 줄일 수 있다. 이는 예를 들어 unsigned char로 배열을 잡을 경우 8bit를 사용하여 8개의 정수의 소수 여부를 1 or 0으로 표현, 이를 담은 하나의 정수로 저장하면 된다.또한 type의 크기 이후 정수를 저장하려면 다음 배열에 다시 그 이후 8개의 정수 소수 여부를 한번에 저장한다. prime[0] -> 0부터 7까지의 소수 여부 저장 : 10101100 (7 :..