오름차순 정렬을 가정했을 때, 피봇이라는 기준값으로 왼쪽에는 기준값보다 작은 부분집합을 형성시키고 오른쪽에는 기준값보다 큰 부분집합을 형성시킨다. 분할정복을 이용하기 때문에 lgN의 깊이만큼 재귀호출을 하고, 깊이마다 배열의 길이인 N만큼 비교하기 때문에 총 평균 시간복잡도는 NlgN만에 정렬시킬 수 있다 피봇을 잡는 기준은 다양하며 특정 피봇 위치를 잡았을 때 엄청 좋다라는 것은 없다. 다만 합병 정렬과 달리, 피봇에 따라 비균등하게 부분집합들이 나눠질 수 있기 때문에 unstable-sort로 분류를 한다. 만일 정렬된 배열에 대해서 퀵 소트를 한다고 하면, 퀵 정렬 알고리즘에 따라서 lgN의 깊이가 아닌 N의 깊이만큼 내려가게 된다. 따라서 최악의 시간복잡도 O(N^2)이 나오게 된다 1) 리스트 ..

N의 길이의 텍스트에서 M의 길이를 가진 패턴을 찾으려고 할 때(N>=M) 일반적인 문자열 탐색 알고리즘. 즉 브루트포스로 모든 문자를 검색한다고 하면 시간복잡도는 O(NM)이 된다. 즉 NM이 1억이 넘어가면 1초 안에 해결할 수 없을뿐더러 텍스트의 길이가 헤아릴 수 없다는 점에서 NM은 매우 비효율적이다. 따라서 해결할 수 있는 방법인 KMP다. KMP는 시간복잡도 O(N)에 해결할 수 있다 1. KMP를 구현하기 위해선 패턴의 접두사, 접미사가 같은 최대 길이를 알아야 한다. 이는 KMP에서 점프를 할 때 유용하게 쓰이는 데이터 중 하나다. 보통 이를 실패 배열이라고 부른다. 2. 문자열 탐색 중 어긋나는 경우, 그 전까지는 다 맞다고 할 수 있다. 따라서 맞은 부분 문자열에서 실패 배열을 통해 맞..

map에 정보를 담은 후 vector로 옮긴 뒤 정렬을 한다 map m; vector tmp; for (map::iterator it = m.begin(); it != m.end(); ++it) { tmp.push_back(make_pair(it->first, it->second)); } sort(tmp.begin(), tmp.end(), cmp1);

[출처] http://www.cplusplus.com/reference/algorithm/sort/ cpp 레퍼런스의 사용자 정의 sort 함수를 참조하면, 다음과 같이 정의되어 있다 template void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); comp 함수는 bool 타입을 반환하는 함수를 의미한다. 만일 true를 반환하면 들어오는 두 매개변수에 대해서 이미 정렬된 상태이고, false를 반환하면 두 매개변수는 로직에 맞지 않게 정렬된 상태이므로 자동적으로 바꿔주게 된다 따라서 comp 함수를 작성할 때는 원하는 로직으로 부등호를 정한다면 내부적으로 false를 return 하면 두 매개변수를 바꾸게 ..

getline에 세번째 있는 delimeter를 이용해서 token할 수 있다 vector solution(vector record) { vector ans; for (int i = 0; i < record.size(); i++) { vector tokens; istringstream f(record[i]); string s; while (getline(f, s, ' ')) { tokens.push_back(s); cout

문자열 알고리즘은 파이썬으로 해결하는 것이 편리하다. 이번 기회에 필요한 기능을 정리해보려고 한다 1. find와 index 둘 모두 문자열의 인덱스를 알려주지만, 만일 해당 문자가 없을 때 find는 -1을 반환하고 index는 인터프리터 오류를 발생시킨다 2. 문자열 삽입 join a = "," b = a.join("abcd") print(b) >> a, b, c, d 3. 문자열 바꾸기 a = "Life is too short" b = a.replace("Life", "Your leg") print(b) >> "Your leg is too short" 4. 문자열 나누기 a = "Life is too short" b = a.split() print(b) a = "a:b:c:d" b = a.split..