csmoon1010의 SW 블로그

두 String의 패턴을 비교할 때 사용하는 알고리즘들을 정리해보자!! 1. Brute Force 알고리즘 : 처음부터 끝까지 차례대로 순회하면서 일일이 비교 - 문자가 일치한다면 : 두 String의 index를 한 칸씩 ++ - 문자가 일치하지 않는다면 : 비교 대상의 index를 다시 처음으로 public int BruteForce(String[] p, String[] t){ //p : 패턴, t : 전체 텍스트 int i = 0; int j = 0; while(i < t.length && j < p.length()){ if(t[i] != p[j]){ i = i - j; j = -1; } i++; j++; } if(j == p.length()) return i-p.length(); //패턴 찾음 -..

1. 완전탐색(Brute-force)? : 모든 경우의 수를 탐색하여 문제를 푸는 방식. 대표적인 예로 순열, 조합이 있음 2. 순열(Permutation, nPk) : n개의 요소들 중 k개를 뽑아 '정렬'할 수 있는 경우의 수 (1) 전통적인 순열 구하는 방법 - k개의 자리에 올 수 있는 요소의 개수를 세는 방식 - n x (n-1) x (n-2) x ... x (n-k+1) = n! / (n-k) ! - 단, 위의 수식은 단순히 "개수"를 구하는 방법일 뿐 완전탐색에 조건을 적용하기엔 부족함 (2) 순열 알고리즘 : 0~k번째에 수를 고정시킨다. [과정] ① depth번째 수 고정 - 방법1) 첫번째 수와의 swap을 통해 지정 - 방법2) 고정여부를 담은 visited배열(n과 같은 길이)에 표..

1. Dynamic Programming이란? : 복잡한 문제를 "작은 문제"로 나누어 푸는 방법 - "작은 문제"에서 최적의 결과 → 전체의 최적의 결과 - 앞에서 구한 결과를 다음 계산 때 이용하는 방향 (재사용) 2. 방식 1) 하향식 알고리즘(Top-Down) : 큰 문제에서 재귀함수를 호출하여 푸는 방식 → "작은 문제"가 중복되어 풀림 ex> 막대 자르기 문제 : 어떻게 잘라야 최대 이익으로 팔 수 있는가(길이에 따라 가격 책정이 다름) Function cutRod(p, n){ if(n = 0) return 0; q