파일 내용이 10GB가 되는 것은 어떻게 정렬할까? 메모리에 올릴 수 있는 크기가 한정되어 있기 때문에, 10GB 짜리의 큰 파일을 한번에 읽어서 quick sort 같은 인메모리(in-memory) 정렬을 할 수 없다. Linux/Mac에는 sort 라는 명령어가 있고, Windows에서는 git bash를 깔면 사용할 수 있다. 이미 있는 커맨드인지 모르고 python으로 직접 구현했다. 더보기 과정 메모리에 올릴 수 있는 만큼만 쪼개어서 올린 후, 각각을 정렬하고 다시 합친다. 여기서 "메모리에 올릴 수 있는 만큼"은 적당히 128MB로 설정했다. 이를 자세히 각 단계별로 쪼개면 이렇다. 준비 - 나눠 담을 크기를 계산 분리 - 큰 세그먼트 단위로 나누어 쪼개어 담는다. 정렬 - 쪼개진 각 파일을 ..

저는 quick sort를 기반으로 구현했고, 그 중에서도 중간값이 아닌 (위치가) 중앙에 있는 값을 사용했습니다.이 정도만 구현해도 많은 문제는 생기지 않았습니다. 다만 실제 std::sort 는 구조가 조금 다른 것으로 알고 있습니다. 크기가 100개 이하인 케이스는 insertion sort를 사용하는 등 최적화를 위해서 수정했다고 하네요. template 함수로 작성했기 때문에, 타입은 별도로 명시하지 않아도 됩니다.int형 배열 a[100]에 대해서도, std::sort 함수 쓰듯이 sort(a, a+100) 이라고 호출해도 동작합니다. 이전 게시글에서 구현한 vector를 파라미터로 넘겨도 동작합니다. 즉, sort(vec.begin(), vec.end()) 가능합니다.코드

링크: https://www.acmicpc.net/problem/5052문제한 문자열이 다른 문자열의 접두어(prefix)이면 NO, 그런 경우가 없으면 YES를 출력하는 문제이다.풀이 1 (정렬)모든 문자열을 사전순으로 정렬하면, 접두어가 겹치는 문자열끼리 붙어있다.어떤 문자열이 직전 문자열의 부분 문자열인지 확인하면 된다.시간 복잡도는 정렬 + 부분 문자열 확인 시간만큼이므로, \(O(nlogn + n|s_{max}|)\)코드 1 (정렬) 풀이 2 (트라이; Trie)분류에 트라이가 있기도 하고, 트라이를 한번도 구현해본 적 없어서 트라이로 풀어봤다.문자열을 하나씩 확인하며 트라이를 만들어간다.어떤 문자열이 끊긴 지점에 "이 곳이 하나의 단어였다"로 리프 표시를 해두고 넘어간다.다음에 트라이를 만드는..