프로그래밍나무

합병 정렬 알고리즘 개념 과정 설명 배열을 길이가 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 ..

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