Sangmun

https://leetcode.com/problems/repeated-substring-pattern/ Repeated Substring Pattern - LeetCode Can you solve this real interview question? Repeated Substring Pattern - Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. Example 1: Input: s = "abab" Output: true Expl leetcode.com 문자열의 길이가 최대 10000까지 주어져서 일일이 substr..

17976번: Thread Knots (acmicpc.net) 17976번: Thread Knots Your program is to read from standard input. The input starts with a line containing one integer, n (2 ≤ n ≤ 100,000), where n is the number of threads. In the following n lines, the i-th line contains two integers xi (0 ≤ xi ≤ 109) and li (1 ≤ www.acmicpc.net * 이분 탐색으로 풀이하는 문제 import sys input = sys.stdin.readline n = int(input()) lines = ..

https://leetcode.com/problems/move-zeroes/submissions/944108528/ Move Zeroes - LeetCode Can you solve this real interview question? Move Zeroes - Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. Note that you must do this in-place without making a copy of the array. E leetcode.com class Solution: def moveZeroes(self, nums: ..

https://www.youtube.com/watch?v=UcjK_k5PLHI # Python3 program for KMP Algorithm def KMPSearch(pat, txt): M = len(pat) N = len(txt) # create lps[] that will hold the longest prefix suffix # values for pattern lps = [0] * M j = 0 # index for pat[] # Preprocess the pattern (calculate lps[] array) computeLPSArray(pat, M, lps) i = 0 # index for txt[] while (N - i) >= (M - j): if pat[j] == txt[i]: i +..

Rabin Karp 알고리즘은 문자열 매칭 알고리즘이며 문자열 매칭을 O(n)의 시간안에 수행하게 해주는 알고리즘이다. 문자열 매칭은 다음과 같은 사례가 있다. 우리가 찾고자 하는 문자열을 target이라고 하고 대상이 되는 문자열을 S라고 했을때 아래 그림처럼 문자열을 하나씩 옮겨가면서 BruteForce 방식으로 찾게되면 len(target)*len(S)의 time complexity가 소요되게 된다. 즉 O(n**2)이라고 봐도 무방한것이다. Rabin karp 알고리즘은 이러한 brute force방식의 문제점을 해결하여 O(n) time complexity로 문자열을 찾는 알고리즘이다. 핵심아이디어는 다음과 같다. * brute force방식으로 문자열의 자리를 하나씩 옮겨가며 비교하지 말고 해..

https://www.youtube.com/watch?v=Yjgmw3rMof4&t=3s https://leetcode.com/problems/valid-palindrome/ Valid Palindrome - LeetCode Can you solve this real interview question? Valid Palindrome - A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric cha leetcode.com cla..

https://leetcode.com/problems/longest-palindromic-subsequence/ Longest Palindromic Subsequence - LeetCode Can you solve this real interview question? Longest Palindromic Subsequence - Given a string s, find the longest palindromic subsequence's length in s. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements wi leetcode.com class Solution: def lo..

https://leetcode.com/problems/maximum-width-of-binary-tree/ Maximum Width of Binary Tree - LeetCode Can you solve this real interview question? Maximum Width of Binary Tree - Given the root of a binary tree, return the maximum width of the given tree. The maximum width of a tree is the maximum width among all levels. The width of one level is defined as leetcode.com 트리를 이용한 문제이며 트리의 전위순회, 후위순외같은..