넘치게 채우기

설명Knuth, Morris, Pertt이 만든 문자열 패턴 검색 알고리즘인 KMP 알고리즘은O(n+m)에 문자열 패턴을 검색해낼 수 있다. 이 알고리즘의 핵심은 lps 배열이다.lps = Longest Prefix Suffix.각 위치까지의 부분 문자열에서 자기 자신의 접두사이면서 접미사인 가장 긴 길이를 저장한 배열이다.패턴 내에서 일치하지 않는 문자가 발견되면, 이전에 계산한 lps를 이용하여 패턴을 적절히 이동한다.lps[i]는 0부터 i-1까지는   LPS 배열의 생성방법은 다음과 같다:lps[0]와 len을 0으로 초기화한다. len은 가장 긴 접두사와 접미사 값의 길이이다.pat[len]과 pat[i]가 일치하면, len을 1 증가하고, 증가된 값을 lps[i]에 할당한다.일치하지 않고 le..

설명Naive 패턴 검색에서는, 우리는 모든 pattern의 길이와 같은 부분문자열들을 원본 문자열에서 추출해서 각각 한 글자씩 비교했다. Rabin-Karp 알고리즘에서도, 모든 부분문자열을 검사하지만, 대신 패턴의 해시 값와 현재 부분문자열의 해시 값을 비교한다.그리고 해시 값이 매칭되면, 패턴이 맞는 것이다.Rabin-Karp 알고리즘은 다음의 해시 값들을 계산할 필요가 있다:패턴의 해시 값더미 문자열(haystack)에서의 길이가 m인 모든 부분문자열해시 값은 문자열에서 패턴을 찾는 데 효율적으로 사용된다.해시 값은 rolling hash function으로 계산되는데, 기존의 글자를 하나 버리고 새 글자를 가져오면서 해시 값을 업데이트하면 된다.롤링 해시 함수의 과정은 다음과 같다:기저 수 b와..

설명Naive 패턴 검색 알고리즘은, 문자열에서 패턴을 찾는 가장 단순한 방법이다.패턴을 텍스트 위로 하나씩 밀어서 일치하는지 확인하고, 일치하는 것이 발견되면, 1개씩 다시 밀어서 다음에 일치하는 항목을 확인한다. 코드(C++)#include #include using namespace std;void search(string &pat, string &txt) { int M = pat.size(); int N = txt.size(); for (int i = 0; i   Example 1: pattern found at: 0pattern found at: 9pattern found at: 12Example 2: pattern found at: 1  복잡도 분석시간 복잡도: O(n * m)..

https://www.acmicpc.net/problem/11183BOJ - Coast Length문제 유형 : BFS, DFS, 행렬, 구현문제 난이도 : Silver I 문제The island municipality of Soteholm is required to write a plan of action for their work with emission of greenhouse gases. They realize that a natural first step is to decide whether they are for or against global warming. For this purpose they have read the IPCC report on climate change and found..

https://leetcode.com/problems/different-ways-to-add-parentheses/description/?envType=daily-question&envId=2024-09-19leetcode - Different Ways to Add Parentheses문제 유형 : 문자열 처리, 재귀, 다이나믹 프로그래밍, 카탈란 수문제 난이도 : Medium 문제Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answe..

https://leetcode.com/problems/largest-number/description/?envType=daily-question&envId=2024-09-18leetcode - Largest Number문제 유형 : 문자열 처리, 정렬문제 난이도 : Medium 문제Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.Since the result may be very large, so you need to return a string instead of an integer. 음이 아닌 정수 nums를 받는다. 이 수들을 나열하여 만들 수 있는 가..

https://leetcode.com/problems/uncommon-words-from-two-sentences/description/?envType=daily-question&envId=2024-09-17leetcode - Uncommon Words from Two Sentences문제 유형 : 문자열 처리, 해시문제 난이도 : Easy 문제A sentence is a string of single-space separated words where each word consists only of lowercase letters.A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the ..

https://leetcode.com/problems/minimum-time-difference/description/?envType=daily-question&envId=2024-09-16leetcode - Minimum Time DIfference문제 유형 : 정렬, 문자열 처리문제 난이도 : Medium 문제Given a list of 24-hour clock time points in "HH:MM" format, return the minimum minutes difference between any two time-points in the list. "HH:MM"의 형식으로 24시간기준의 시간이 배열로 주어진다.두 시간의 최소 시간차를 분단위의 정수로 구하시오. 풀이우선, 모든 시간을 분단위로 ..

https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/description/?envType=daily-question&envId=2024-09-15leetcode - Fine the Longest Substring Containing Vowels in Even Counts문제 유형 : 비트마스크, 비트 연산, 슬라이딩 윈도우문제 난이도 : Medium 문제Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, 'a', 'e', 'i', 'o', a..

https://leetcode.com/problems/longest-subarray-with-maximum-bitwise-and/description/?envType=daily-question&envId=2024-09-14leetcode - Longest Subarray With Maximum Bitwise AND문제 유형 : 비트 연산, 비트마스킹, 슬라이딩 윈도우문제 난이도 : Medium 문제You are given an integer array nums of size n.Consider a non-empty subarray from nums that has the maximum possible bitwise AND.In other words, let k be the maximum value of ..