본문 바로가기

분류 전체보기85

MVC(Model, View, Controller) MVC(모델-뷰-컨트롤러)는 사용자 인터페이스, 데이터 및 논리 제어를 구현하는데 널리 사용되는 소프트웨어 디자인 패턴이다. 모델은 데이터와 비즈니스 로직을 관리하고, 뷰는 레이아웃과 화면을 처리한다. 컨트롤러는 명령을 모델과 뷰 부분으로 라우팅한다. 즉 사용자가 컨트롤러를 조작하면 컨트롤러는 모델을 통해 데이터를 가져오고, 해당 데이터를 바탕으로 뷰를 통해 시각적 표현을 처리하고 이를 사용자에게 제공한다. MVC 패턴은 비즈니스 로직과 UI로직을 분리하여 유지 보수를 독립적으로 수행 가능케하고, 모델과 뷰가 다른 컴포넌트에 종속되지 않아 변경에 유리하다. 이런 관심사 분리는 개발자들에게 효율적인 업무와 관리 환경을 제공하게 된다. 모델은 앱이 포함해야할 데이터가 무엇인지 정의한다. 모델의 상태가 변화할.. 2023. 4. 20.
Rabin-Karp 알고리즘 KMP 알고리즘과 더불어 문자열을 탐색하는 알고리즘 중 하나이다. Rabin-Karp 알고리즘은 해싱을 이용해서 문자열을 비교하는 알고리즘으로, 최악의 경우 O(MN)이지만 평균적으로는 선형에 가까운 빠른 속도를 가진다. Rabin-Karp 알고리즘은 다음과 같이 진행된다. - 패턴의 해시값을 계산한다. - 비교하려는 문자열에서 패턴의 길이만큼 잘라서 해시값을 계산한다. - 해시값을 비교한다. (해시값이 같다면 정확히 일치하는 것이고, 다르다면 첫글자를 빼주고 다음 글자를 추가한다.) - (문자열 - 패턴)의 길이만큼 반복하고 종료한다. 예를 들어 패턴은 ABAC 문자열은 CABABACD라고 하면 패턴의 해시값을 다음과 같이 구한다. static int cal(String pattern){ int sum.. 2023. 4. 14.
KMP 알고리즘(2) 지난 번에는 KMP 알고리즘의 패턴에 관해 알아보았다. 그럼 이번에는 그 패턴에서 구한 이동 위치 저장 배열을 가지고 어떻게 비교 문자열에 적용하는지 확인해보자. 패턴은 다음과 같다. ABCDABA 비교할 문자열은 다음과 같다. ABCDABCDABABCDCD 이 두 문자열을 비교할 것이다. 우선 코드로 살펴보자. static void KMP(String str, String pattern){ int []arr = getTable(pattern); char[] text = str.toCharArray(); char[] pt = pattern.toCharArray(); int j=0; for(int i=0;i0&& text[i]!=pt[j]) j=arr[j-1]; if(text[i]==pt[j]){ if(j.. 2023. 4. 14.
KMP 알고리즘(1) KMP 알고리즘은 패턴 매칭에 사용되는 알고리즘으로 Knuth, Morris, Pratt이라는 천재 세명이 만든 알고리즘이다. 기본적인 개념은 패턴을 매칭하는 과정에서 불일치가 발생한 텍스트 문자열의 앞 부분에 어떤 문자가 있는지를 미리 알고, 이를 통해 불일치가 발생한 앞 부분에 대해 다시 비교하지 않고 매칭을 수행할 수 있다. 라는 개념이다. 브루트 포스로다가 때려 박아서 비교하는 거는 시간 복잡도가 O(MN)이되는데 반해, KMP 알고리즘의 시간 복잡도는 O(N+M)이 된다. 여기서 N은 문자열 길이이고, M은 패턴의 길이다. 이런 개념을 가지고 KMP 알고리즘을 알아보자. 일단 KMP알고리즘은 접두사와 접미사를 차례대로 이용한다. ABCABCABC 라는 문자가 있다면 한개를 비교할 때의 접두사와 .. 2023. 4. 14.

티스토리툴바