Aif

웹 동영상 스트리밍 서비스를 프로젝트로 해보려고 한다.

https://yiyj1030.tistory.com/495 [알고리즘/ 파이썬] KMP 알고리즘 알아보기 KMP 알고리즘(Knuth-Morris-Pratt algorithm)이란 문자열 검색을 매우 빠르게 해주는 알고리즘이다. 특정 패턴이 주어졌을 때 전체 문자열을 빠르게 검색하여 그 패턴이 어디에 등장하는 지 찾아준다. KMP yiyj1030.tistory.com KMP 알고리즘을 구현하였는데 수정해야할 사항이 있었다. 사실 내가 구현한 코드는 KMP 알고리즘이라고 할 수 없다. 왜 그런지는 정확하게 설명할 수 없지만 KMP 알고리즘을 사용하지 않았다. KMP 알고리즘의 패턴 테이블을 참조하여 중복 건너뛰기만 한 느낌이다. 일단 KMP 알고리즘이 정확하게 이해되지 않는 부분이 접두부의 인덱스를 패턴 테..

// KMP.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다. // #include #include #include #include using namespace std; // 패턴의 접두부 접미부 겹치는 길이 확인 vector makepi(string pattern); // KMP 알고리즘 vector KMP(string p, string T); int main() { // 텍스트 및 패턴 string T = "AABABABAABABAABBABAABBAABAABABAABBBABBABAB"; string p = "ABAABABAABB"; // 길이 체크 cout > 다시 반복 KMP - 알고리즘 무식한 탐색과 같이 탐색하다가 일치하는 문자열 발생시 해당 패..

KMP 알고리즘 >> 무식한 탐색 알고리즘의 개선 버전 만든사람의 앞글자를 따서 KMP 알고리즘이라 불림 김명표 Knuth, Morris, Pratt 무식한 탐색 알고리즘은 시간복잡도가 O( 텍스트 길이*패턴 길이 ) 로 상당히 느린데 KMP 알고리즘은 O ( 텍스트 길이 + 패턴 길이 )로 굉장히 효율이 좋아짐 성능이 좋은 알고리즘에 속하지만 대부분의 프로그램은 보이어 무어 알고리즘을 채택하고 있다고 한다. 또한 살짝 다른 기능인 자동완성 기능에서는 트라이 자료구조를 사용하여 데이터를 관리하여 보다 빠르게 탐색을 완료한다고 함. 구현 방법 >> KMP 알고리즘은 무식한 탐색 알고리즘에서 중복된 부분을 건너 뛰어서 탐색하여 성능을 향상시킨다. 이미 탐색한 부분을 건너 뛰는 건 당연한 일이다. 하지만 여기..

카프라빈 알고리즘은 찾고 싶은 문자열과 비교할 타깃 문자열을 해쉬 하여 비교하는 알고리즘이다. 같은 문자를 해쉬하면 같은 값이 나오는 원리를 이용한 것이다. 여기서 중요한 것은 해쉬를 하면 연산이 늘어나서 결국 고지식한 알고리즘과 다를 게 없지 않을까 했는데 그렇지 않다. 그 이유는 카프 라빈은 천재이고, 이 사람들은 해쉬 연산을 최적화하여 속도를 더 올렸다고 한다. 그 방법은 타겟 문자열을 해쉬해 나갈 때, 첫 문자와 마지막 문자만 변하는 형식일 것이다. 여기서 중복되는 가운데 문자열의 해쉬 연산을 줄여서 속도를 올린다. 이러한 해쉬시 알고리즘을 롤링 해시라고 한다. 원리는 기존의 문자열을 패턴길이만큼 해시하여 비교할 때, 다음 해시해야하는 문자열이 이전의 해시값으로 나타내진다. 사실상 롤링 해시를 통..

가장 먼저 떠오르는 문자열 탐색 알고리즘 탐색할 문자열을 타겟 문자열에 하나하나 대입하여 모두 일치할때 까지 돌린다. vector forceSearch(string p, string T) { vector find; for (int i = 0; i < T.size() - p.size(); i++) { for (int j = 0; j < p.size(); j++) { if (p[j] != T[i+j]) { break; } if (j+1 == p.size()) { find.push_back(i); } } } return find; }

다익스트라 알고리즘 최단 경로를 구하는 알고리즘 임의의 시작 정점에서 각각의 정점으로의 최단 경로를 구해낸다. 프림 알고리즘과 유사하다. 프림 알고리즘과 같이 그리디 알고리즘 기반이다. 전체적인 흐름은 시작 정점을 지정하고 해당 정점으로 가는 간선을 우선순위 큐에 넣는다. 이 간선은 시작을 나타내는 간선으로 가중치는 0이고 출발지는 -1로 한다. 우선순위 큐가 빌때까지 반복 { 우큐에서 하나 뺌 우큐에서 하나 삭제 해당 간선이 방문했을 경우 다음 반복 해당 간선 방문으로 표시 그래프를 모두 확인하여 시작 정점에 붙은 간선을 확인하여 거리가 현재 가중치보다 높게 저장된 간선을 현재 가중치로 계산하여 저장 후 우큐에 삽입 } 말로 보면 좀 힘들고 코드로 보는게 편할듯 하다.. int calDistance(i..

php 를 통해 개발을 할 시 프레임워크를 사용하게 된다. 프레임워크에는 팔콘, 라라벨, 코드이그나이터 등 여러가지 있는데 현재까지 3개를 설치하고 예제만 깔짝거려 봤다. 초반에는 iso관련 오류에 많은 시간을 허비했는데, 대충 가닥이잡히고 마지막으로 코드이그나이터를 할땐 금방 해결했다. 일단 확장자는 php.ini 파일에서 설정하며 vi 찾기 기능이나 VScode를 연동하면 쉽게 수정가능하다. 그럼 ini파일이 어디 있느냐... 가 중요한데 그건 패키지 설치 버전등에 따라 다르다 즉 서버설정마다 다르다. 하지만 확장자를 쉽게 설치하는 방법으로 간단하게 apt install 을 사용하는 것이다 이렇게 패키지를 설치하게되면 자동으로 ini파일에 추가된다 !! 굿

알고리즘을 하면서 포인터는 많이 익숙해졌는데 다익스트라 알고리즘을 공부하면서 버그를 수정하다 다른 예제 코드에서 다음과 같은 부분을 확인했다. void dijkstra(vector& graph, int start) void dijkstra(vector* graph, int start) 일반적으로 나는 포인터를 사용하고있었는데 & 를 사용하고있었다. 포인터는 해당 변수의 주소를 또 다른 변수에 저장하는거고 참조는 해당 변수의 또 다른 변수를 복제하는 느낌인거같다. alias 처럼 참고 - https://dayday-kim.tistory.com/5 참조변수와 포인터변수의 차이 [1] 레퍼런스와 포인터 : 이 둘은 분명 다른 개념이다. ⓐ : 포인터 포인터 변수를 설명하기 위해서, C의 이 예제를 가지고 와 ..

최소신장트리를 만드는 알고리즘으로 크루스칼 알고리즘이 있다. 개념자체는 단순하다. 그래프의 모든 간선을 가중치의 순서대로 이어 붙인다. 그렇다면 중복되는 간선은 어떻게 걸러내야 할지 고민하게 된다. 이 방법은 집합 개념을 도입하여 해결한다. 만약 최소 가중치의 간선을 최소신장트리에 포함하려 할 경우를 생각해 본다. 처음에는 아무도 집합을 이루지 않기에 바로 최소신장트리에 포함된다. 하지만 계속 반복되면 같은 집합 내에서 간선이 선택될 경우가 발생한다. 이는 순환을 발생시키므로 위와 같은 상황을 제외하면 최소신장트리가 완성된다. vector set; int findParent(vector set, int child) { int parent = set[child]; while (parent != child)..