알고리즘 기말

퀵 정렬

솔직히 이건 외우자

int pl = left;
int pr = right;
int x = a[(pl + pr) / 2];
 
while (pl <= pr) { // pl 항상 ++ pr은 항상--
	while (a[pl] < x) {
		pl++;
	}
	while (a[pr] > x) {
		pr--;
	}
	if (pl <= pr) {
		swap(a, pl++, pr--);
	}
}
 
if (left < pr) {
	quickSort(a, left, pr);
}
if (pl < right) {
	quickSort(a, pl, right);
}

퀵 정렬 (피벗 선택)

// x[a], x[b], x[c]을 정렬(중앙값의 인덱스를 반환 )
static int sort3elem(int[] x, int a, int b, int c) {
	if (x[b] < x[a])
		swap(x, b, a);
	if (x[c] < x[b])
		swap(x, c, b);
	if (x[b] < x[a])
		swap(x, b, a);
	return b;
}
 
int m = sort3elem(a, pl, (pl + pr) / 2, pr);
int x = a[m];
swap(a, m, right - 1);
pl++;
pr -= 2;

• 알고리즘을 이해하자면

  • 첫 값, 중앙값, 마지막 값을 정렬하고
  • 중앙 인덱스 반환 하기

  병합 정렬

static int[] buff; //작업용 배열
static void __mergeSort(int[] a, int left, int right) {
	if(left<right) {
		// 쓰인변수 i, center, p, j, k
		int i;
		int center = (left+right) / 2;
		int p =0;
		int j =0;
		int k = left;
		
		__mergeSort(a, left, center);
		__mergeSort(a, center+1, right);
	
		// for문은 buferr 복사
		for(i=left; i<=center; i++)
			buff[p++] = a[i];
		// while은 원래배열에 뭔짓거리
		while(i<=right && j<p)
			a[k++] = (buff[j]<= a[i]) ? buff[j++] : a[i++];
		while(j<p)
			a[k++] = buff[j++];
	}
}
static void mergeSort(int[] a, int n) {
        buff = new int[n];
        __mergeSort(a, 0, n-1);
        buff = null;
}

부르트-포스법

• 무식하게 하나 하나 다 대조해보는

static int bfMatch(String txt, String pat) {
	int pt = 0; 	// 택스트 담당
	int pp = 0;	// 패턴 담당
	
	while (pt != txt.length() && pp != pat.length()) {
		if (txt.charAt(pt) == pat.charAt(pp)) {
			pt++;
			pp++;
		} else {
			pt = pt-pp+1; //+1 인거 기억
			pp = 0;
		}
	}
	
	// 검색 성공
	if (pp == pat.length()) {
		return pt-pp; // 이것도 기억
	} else {
		return -1;
	}
}

KMP 법

static int kmpMatch(String txt, String pat) {
	int pt = 1; // kmpMatch 는 1부터 시작
	int pp = 0;
 
	int[] skip = new int[pat.length()+1];
 
	skip[pt] = 0; // 0 넣고
	while(pt != pat.length()) {
		if(pat.charAt(pt) == pat.charAt(pp)) //pat 으로만 분석
			skip[++pt] = ++pp; //앞 pt 뒤 pp
		else if(pp == 0) 
			skip[++pt] = pp;
		else
			pp = skip[pp]; // 여긴 모두 pp
	}
	pt = pp = 0; // 모든게 끝나면 초기화
 
//  이후 로직은 부르트 포스와 비슷
else if(pp == 0)
	pt++;
else 
	pp= skip[pp];
}

보이어 무어 법

• 처음 시행 시 주어진 패턴의 전체가 맞지 않는다면 해당 영역만큼 건너 뛰는게 가능하다

static int bmMatch(String txt, String pat) {
	int pt;
	int pp;
 
	// 보이어는 길이 필요
	int txtLen = txt.length();
	int patLen = pat.length();
 
	// Character.MAX_VALUE +1 
	int[] skip = new int[Character.MAX_VALUE +1];
 
	// 첫 for 문은 Character.MAX_VALUE 까지
	for(pt = 0; pt<=Character.MAX_VALUE; pt++)
		skip[pt] = patLen;
	for(pt = 0; pt<patLen-1; pt++)
		// 스킵 배열 참조 = patlen - pt -1;
		skip[pat.charAt(pt)] = patLen-pt-1;
	while(pt < txtLen) {
		pp = patLen -1;
 
		while(txt.charAt(pt) == pat.charAt(pp)) {
			if(pp == 0)
				return pt; 
			pp--;
			pt--;
		}
		//여기선 두 번째 for 처럼 첨조 근데 -가 pp 맞으면 첫번째꺼 틀리면 뒤에꺼
		pt += (skip[txt.charAt(pt)] > patLen-pp) ? skip[txt.charAt(pt)] : patLen-pp;
	}
	return -1;
}