Algorithm 문제 풀이/LeetCode

[Algorithm][KMP] 28. Find the Index of the First Occurrence in a String

KMP 알고리즘이란? 문자열을 한개씩 비교하는 것이 아니라 지금까지 비교한 문자열 중 접두사, 접미사가 같을 경우 중간 과정을 생략하고 비교하는 알고리즘 시간 복잡도 \( O(n + m) \) 문제 링크 https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/ 이번 문제는 주어진 문자열에서 sub 문자열이 몇번 째 index에 존재하는지를 답안으로 내야합니다. 단순하게 생각하면 단순 문자열 비교로 보일 수 있지만, 주어진 조건을 보면 문자열의 길이가 10000입니다. 그래서 단순 비교를 한다면 당연히 시간초과가 발생합니다. 단순 전체 비교 방법 우선 단순 비교로 문제를 푸는 방법을 소개하겠습니다. 전체 문자열의 시작..

[Algorithm] LeetCode 5 - Longest Palindromic Substring

시간 복잡도 \( O(N^2) \) 문제 링크 https://leetcode.com/problems/longest-palindromic-substring/ 이번 문제의 유형은 palindrome으로써 문자열 중 가장 긴 palindrome을 찾는 문제입니다. Palindrome이란 거꾸로 뒤집어도 똑같은 문자열을 뜻합니다. 가장 쉬운 방법으로는 모든 문자열에 대하여 palindrome 여부를 검사해 가장 길이가 긴 문자열을 답으로 제출하면 됩니다. 시간을 계산하면, 모든 문자열은 이중 for문을 이용해 \( O(N^2) \)의 시간, 문자열마다 palindrome 여부를 검사하는 \( O(N) \) 시간이 걸리므로 총 \( O(N^3) \)의 시간 복잡도를 가집니다. \( O(N^3) \)의 시간 복잡도..

[Algorithm][투 포인터] LeetCode 3 - Longest Substring Without Repeating Characters

알고리즘 분류 Two Pointer 시간 복잡도 \( O(N) \) 문제 링크 https://leetcode.com/problems/longest-substring-without-repeating-characters/ 관련 글 [Algorithm 문제 풀이/백준] - [Algorithm][투 포인터] 백준 1806 - 부분합 이번 문제의 알고리즘 종류는 투 포인터입니다. 투 포인터는 이전 글에서도 다른 문제로 한번 접했습니다. 개념도 단순하고 코드도 상당히 짧지만, 알고리즘을 모른다면 쉽게 풀지 못하는 문제이기도 합니다. 해당 문제는 서로 다른 부분 문자열 중 가장 길이가 긴 것을 찾아야 합니다. 만약 이것을 이중 for문을 이용한다면 당연스럽게도 시간 복잡도는 \( O(N^2) \) 이므로 상당히 비효..

[Algorithm][LCP] LeetCode 14 - Longest Common Prefix

알고리즘 분류 Longest Common Prefix 시간 복잡도 \( O(mn) \) 문제 링크 https://leetcode.com/problems/longest-common-prefix/ 이번 문제의 알고리즘 종류는 LCP(Longest Common Prefix)입니다. LeetCode에서 Easy 난이도의 문제로 등록되어 있지만, 여러가지 문제 풀이 방법들이 존재합니다. 저는 여러가지 방법 중 분할기법(Devide and Conquer)을 사용했습니다. String 리스트가 주어질 때 리스트 길이가 1이 될 때까지 index를 계속 두 그룹으로 나눠줍니다. 재귀 함수를 사용하여 쉽게 구현할 수 있습니다. 해당 재귀 함수는 String끼리 비교하며 LCP를 구하며 가장 처음의 함수까지 올라옵니다. ..