본문 바로가기

old/알고리즘
22

재귀 알고리즘 재귀란? 어떤 사건이 자기 자신을 포함하고, 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다. 대표적인 재귀 알고리즘 1 : 팩토리얼 구하기 package recursive; import java.util.Scanner; public class Factorial { //양의 정수 n의 팩토리얼을 반환합니다. static int factorial(int n) { if(n>0) { return n*factorial(n-1); } else { return 1; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("팩토리얼을 구하고 싶은 양의 정수를 입력하세요 .. 2020. 11. 17.
BM 검색 알고리즘 BM 검색 알고리즘이란? 문자열을 데이터에서 검색할 때, 검색할 문자열의 끝에서부터 비교하다가 일치하지 않는 문자를 만나면 검색할 문자열만큼 이동하여 검색을 수행하는 알고리즘. 고안자인 Boyer-Moore 법이라고도 한다. - 찾고자 하는 문자열이 중복되지 않을 경우 예를 들어 다음과 같은 데이터에서 'MYBK' 처럼 중복되지 않는 문자열을 찾을 경우. M Y B B A G M Y B K 찾고자 하는 문자열인 'MYBK'의 마지막 문자 'K'와 배열의 4번째 데이터, 배열[3] 데이터인 'B'를 비교한다. 서로 다르므로 4칸을 건너뛰고 검색한다. - 찾고자 하는 문자열이 중복되는 경우 예를 들어 다음과 같은 데이터에서 'MBMBC' 처럼 중복되는 문자열을 찾을 경우. M B M B M B C K A B.. 2020. 11. 17.
KMP 검색 알고리즘 KMP 검색 알고리즘이란? 문자열 안에서 부분 문자열을 검색할 때, 검색에 실패한 위치를 기반으로 비교할 필요가 없는 문자열은 건너뛰고, 다음 번 검색 위치를 결정하는 알고리즘. - 찾고자 하는 문자열이 중복되지 않을 경우 예를 들어 다음과 같은 데이터에서 'MYBK' 처럼 중복되지 않는 문자열을 찾을 경우. M Y B B A G M Y B K 'MYB'까지는 일치하지만 4번째 K가 일치하지 않는다. 이럴 경우 'MYB' 다음 위치부터 검색을 다시 시작한다. - 찾고자 하는 문자열이 중복되는 경우 예를 들어 다음과 같은 데이터에서 'MBMBC' 처럼 중복되는 문자열을 찾을 경우. M B M B M B C K A B M B M C M B A B C A 'MBMB' 까지는 일치하지만 5번째 C가 일치하지 않.. 2020. 11. 17.
문자열 검색(String Search) 알고리즘 1. 브루트-포스법 문자열 검색(String Search) 알고리즘 주어진 문자열에서 찾고자 하는 문자열이 있을 때, 해당 문자열의 위치를 찾는 알고리즘. 브루트-포스법이란? 텍스트의 맨 앞부터 한 문자씩 살펴보며 패턴의 첫 자와 일치하는 문자를 찾고, 일치한다면 그 문자부터 패턴의 나머지와 일치하는지 검사한다. 불일치한다면 텍스트의 다음 문자부터 다시 검사한다. 선형검색을 확장한 알고리즘으로, 단순법, 소박법이라고도 한다. 자바로 구현하기 package algorithm; public class BFMatch { //브루트-포스법으로 문자열을 검색하는 메서드 static int bfMatch(String txt, String pat) { int pt = 0;//txt 커서 int pp = 0;//pat 커서 //텍스트 커.. 2020. 11. 17.

최근댓글

최근글

skin by © 2024 ttuttak

티스토리툴바