개발 창고

뭔가 이름이 멋있는 알고리즘이다. O(N + M)의 시간 복잡도 특정한 상황에서 KMP 알고리즘보다 매우 느리게 동작한다고 한다. 사실 그럴만도 한 것이 일단 hash함수를 써야하고, hash값이 같은 부분이 많으면 check하는 함수를 써야하니... 그래도 내 머리보단 빠르지 않을까? 설명은 이 분의 블로그가 좋겠다. blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221240679247&redirect=Dlog&widgetTypeCall=true&directAccess=false #include #include char * parent = "acabacdabac"; char * pattern = "abacdab"; // 같은 문장인지 확인하는 함수 void che..

O(N + M)의 시간복잡도의 알고리즘이다. matching 전에 접두사와 접미사가 일치하는 최대길이를 기록하는 table을 만들어 이용한다. 알고리즘이 다소 복잡하게 느껴질 수 있으니 설명을 찾아보는 게 좋을 듯하다. 그런데 알고리즘에 대한 설명은 나보다 이 사람이 더 잘하지 않을까? bowbowbow.tistory.com/6 #include #include #include char * parent = "acabacdabac"; char * pattern = "abacdab"; int * makeTable(char * pattern){ int patternSize = strlen(pattern); int * table = (int *)malloc(sizeof(int) * patternSize); for..

컴퓨터가 2의 보수를 이용하는 것을 이용할 것이다...? 2의 보수, 1의 보수에 관한 좋은 설명이 있는 블로그 링크 ndb796.tistory.com/tag/2%EC%9D%98%EB%B3%B4%EC%88%98 오타쳐서 런타임 에러가 났었고 찾아서 해결했다.. 아래는 예시 코드다. #include #define NUMBER 7 int tree[NUMBER]; int sum(int i){ int res = 0; while (i > 0){ res += tree[i]; i -= (i & -i); // i = (i & -i); // 오타쳤음. 이 경우 계속 i = 1이라서 영원히 안끝난다... 오버플로우까지 } return res; } void update(int i, int dif){ //i index에 di..

구간 합을 구하는데 좋은 알고리즘 중 하나이다. O(N)의 시간복잡도. 이마저도 비효율적이라 생각하는 알고리즘에 미친자들... 결국 트리를 이용해서 시간복잡도를 O(logN)으로 축소시킨다. #include #define NUMBER 7 // data의 개수 int a[] = {7,1,9,5,6,4,1}; int tree[4*NUMBER]; // 4를 곱해서 모든 범위를 커버한다...라고 하는데 그냥 높이를 곱한 것. // start : 시작하는 인덱스, end : 끝나는 인덱스 // node : 사실 그냥 1이 들어간다...만은 원래는 특정 노드에 특정 값이 들어가게 하기 위해 따로 파라미터로 내놓는다. 즉, 재귀함수로 사용하기 위해 존재하는 파라미터. main에서의 용도는 root node를 지정해주..

동작 원리가 프림 알고리즘과 흡사. 아래 설명 코드에선 main 함수에서 차이가 난다. 프림 알고리즘과의 차이점은 간선의 '가중치'가 아닌 간선의 '이동거리'를 중심으로 판단한다는 점이다. 즉 기존 이동했던 노드를 거쳐간다는 가정하에 '이동거리'를 계산하고 이를 통해 Table을 갱신한다. 기존의 테이블을 매번 새로 갱신하는 특징이 있다. 우선순위 큐를 이용해서 구현한다. 프림 알고리즘과 같이 시간복잡도 O(ElogV) #include #include #include #define NODE_MAX 1001 #define EDGE_MAX 600001 // 양방향 간선이므로 300000개를 고려 // Node가 Edge를 참조, priorityQueue가 Edge의 cost를 중심으로 최소값이 pop되게 구..

신장 트리 : 모든 정점을 포함하는 그래프 최소신장트리 : 스패닝 트리 중 간선 가중치 합이 가장 작은 트리 과정에 대해 간략히 설명하는 글을 인용하면... 1) 그래프에서 정점 하나를 선택하여 트리 T에 포함시킵니다. 2) T에 포함된 노드와 T에 포함되지 않은 노드 사이의 간선 중에서 가중치가 가장 작은 간선을 찾습니다. 3) 해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함시킵니다. 4) 모든 노드가 포함될 때까지 2)와 3) 과정을 반복합니다. 중요한 것은 간선을 중심으로 노드를 우선순위 큐에 담아 처리한다는 점이다. 그리고 이때 가중치를 Cost라고 표현한다. 프림 알고리즘은 시간복잡도가 O(ElogV)이다. #include #include #incldue #define NODE_M..

체이닝(chaning) 체이닝은 연결리스트를 통해 특정한 키를 가지는 항목들을 연결해서 저장한다. 같은 key에 대한 중복을 허용 체이닝을 이용한 해시맵 구현 코드 예시 #include #include #include #include #define TABLE_SIZE 10007 #define INPUT_SIZE 5000 typedef struct{ int id; char name[20]; } Student; //하나의 key에 여러 data가 들어갈 수 있게 해주는 구조체다. Student * 의 주소를 담는 구조체 typedef struct{ Student * data; struct Bucket * next; } Bucket; //해시테이블 초기화 void init(Student ** hashTable..

해시맵 특징 - 많은메모리 소모, 빠른 데이터 처리 특정값을 찾을 때에는 key로 접근한다. 그 key를 index라고 한다. key 중복을 collision이라고 한다. - hashing은 division method을 주로 이용. 나머지를 key로 이용한다는 것. 테이블의 크기(나누기 크기)는 prime number로 설정한다. 충돌 처리 1. 선형조사법,이차조사법 : 충돌 발생항목을 테이블의 다른 위치에 저장한다. 2. 체이닝 : 해시 테이블의 하나의 버킷에 여러개의 항목을 저장한다. 선형 조사법 예시 코드 // 선형조사법 #include #include #include #include #define TABLE_SIZE 10007 #define INPUT_SIZE 5000 typedef struct..

실제 데이터를 추상화하고 그것을 Modeling을 하는 데 있어서 그래프 형태로 표현하는 것이 유용하다. 여기서 말하는 그래프는 이런 그래프를 말하는 것이다. 행렬 배운 세대는 다 아는 그것.. C언어라면 그래프를 구현하기 위해서 이중배열을 사용하는 등 복잡한 과정을 거쳐야하지만 파이썬의 경우 Dictionary를 이용해서 간단하게 구현할 수 있다. 아래는 『모두의 파이썬x알고리즘』의 예제이다. 실제 모델링 대상인 미로와 '서로아는 친구'문제의 그래프는 해당 도서를 참고하길 바란다. maze = { 'a' : ['e'], 'b' : ['c','f'], 'c' : ['b','d'], 'd' : ['c'], 'e' : ['a','i'], 'f' : ['b','g','j'], 'g' : ['f', 'h'], ..

최대값 찾는 방법은 1. 정렬을 하거나 2. 하나하나 값을 비교해서 하면 되지만, 이번 알고리즘에는 제한이 있다. 알고리즘의 시간복잡도를 O(n)이 되도록 해야한다. 시간복잡도가 O(n)이 되기 위해선, 반복문이 이중으로 존재하면 안된다. 그러므로 다음과 같이 작성한다. price_tag = [10300,9600,9800,8200,7800,8300,9500,9800,10200,9500] def max_profit(prices): n = len(prices) maxprofit = 0 minprice = prices[0] for x in range(1,n): profit = prices[x] - minprice if profit > maxprofit: maxprofit = profit if prices[x]..