프로그래밍나무

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 접근방법 최빈값 같은 경우 정수의 절댓값이 4000을 넘지 않으므로 8001개의 원소를 가지는 배열을 생성 각 숫자가 나올때 +1을 해주었다. 나중에 배열을 검사하면서 제일 큰 원소를 찾고, 지금 있는 최댓값과 같은 원소가 있다면 두 번째까지만 인덱스를 저장한다. 정렬을 직접 구현하였는데 퀵소트로 구현할 경우 제출 시 46~50% 정도에서 많은 시간이 걸리는 것을 확인할 수 있다. 그래서 합병 정렬을 사용해 풀었다.

합병 정렬 알고리즘 개념 과정 설명 배열을 길이가 0 또는 1이 될 때까지 두 개의 배열로 나눈다. 각 나눠진 두개의 배열을 정렬하면서 합병 하나의 배열이 될 때까지 계속 합병 과정 상세 설명 정렬되지 않은 배열을 다른 배열에 정렬하면서 합병 4 3 7 1 5 6 2 3 4 1 7 5 6 2 두 개의 원소를 하나의 배열로 묶으면서 정렬한다. ex) (4,3)->(3,4) 3 4 1 7 5 6 2 1 3 4 7 2 5 6 두 개의 원소로 이루어진 배열 두 개를 하나의 배열로 묶으면서 정렬한다. ex) (3,4,1,7)->(1,3,4,7) 1 3 4 7 2 5 6 1 2 3 4 5 6 7 하나의 배열로 묶어서 정리 퀵 정렬 알고리즘 시간복잡도 Best: nlogn Avg: nlogn Worst: nlogn ..

https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 퀵 정렬 사용 이 문제의 경우 n^2이면 시간 초과가 나므로 퀵 정렬을 사용할때 최악의 경우를 피해야한다. 가운데 원소를 피벗으로 사용한다. 그리고 입출력 할때 시간을 줄여야 한다. #include #include using namespace std; void print_vec(vector v, int num); vector init(vector v, int num); void Qso..

퀵 정렬 알고리즘 개념 과정 설명 배열의 한 원소를 피벗으로 선택 피벗을 기준으로 왼쪽에는 피벗보다 작은 원소를 오른쪽에는 피벗보다 큰 원소를 배치 피벗을 제외한 양쪽의 두 배열을 각각 정렬 배열이 더 이상 나누어지지 않을 때까지 실행 과정 상세 설명 피벗을 제외한 배열의 왼쪽과 오른쪽을 같이 검사한다. 배열의 왼쪽에는 피벗보다 작은 수가 있어야 하므로 왼쪽에서 검사할 때는 피벗보다 큰 수를 찾으면 멈추고 배열의 오른쪽에는 피벗보다 큰 수가 있어야 하므로 오른쪽에서 검사할 때는 피벗보다 작은 수를 찾으면 멈춘다. 양쪽의 검사가 멈추게 되면 그 두 수의 위치를 바꾼다. 4 3 7 1 5 6 2 4를 피벗으로 설정한다. 4 3 7 1 5 6 2 3과 2를 검사한다. 3

KMP(Knuth–Morris–Pratt) 알고리즘은 문자열에서 특정 패턴을 찾아내는 문자열 검색 알고리즘 중 하나입니다. 이 알고리즘은 패턴과 문자열을 비교해나가다가 틀렸을 때 틀렸다는 사실보다는 틀리기 전에 일치하는 부분이 있었다는 사실에 집중하는 것이 특징입니다. 그러기 위해서 패턴을 통해서 pi배열을 만들고 패턴과 문자열을 비교해나가면서 pi배열을 통해 다시 비교하는 횟수를 줄이는 과정을 거치게 됩니다. 이제 과정을 하나씩 설명해 보도록 하겠습니다. 이 설명은 백준1786번 : 찾기 문제를 풀면서 작성하였습니다. https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가..