Algorithm 문제 풀이

[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를 구하며 가장 처음의 함수까지 올라옵니다. ..

[Algorithm][Union Find] 백준 1717 - 집합의 표현

알고리즘 분류 Union Find 시간 복잡도 \( O(N) \) 문제 링크 https://www.acmicpc.net/problem/1717 이번 문제의 알고리즘 종류는 Union Find입니다. 많은 수가 있을 때 특정 수들이 같은 집합인가?라는 물음에 대해 효율적으로 사용할 수 있는 알고리즘입니다. Union Find의 핵심은 "같은 집합이면 같은 루트"입니다. 처음에는 모든 수들이 자기 자신을 루트로 가지고 있도록 초기화를 시켜놓습니다. 하지만 두 수를 merge 한다면 각 수의 루트 값들이 부모, 자식의 관계를 가지게 됩니다. ( 아래 예시를 보면 이해가 가능합니다. ) 그리고 서로 같은 집합임을 알고싶다면 각 숫자들의 최상단 부모, 즉 루트 값을 비교할 수 있습니다. 하지만 이렇게 계속 진행하..

[Algorithm][투 포인터] 백준 1806 - 부분합

알고리즘 분류 투 포인터 시간 복잡도 \( O(N) \) 문제 링크 https://www.acmicpc.net/problem/1806 이번 문제의 알고리즘 종류는 투 포인터입니다. 주어진 배열에서 조건을 만족하는 연속된 수들 중 가장 짧은 길이를 알아야 합니다. 문제의 제목은 부분합이지만 실제로 이 문제를 푸는데 지난번에 다뤘던 부분합 알고리즘이 사용되진 않습니다. 왜냐하면 부분합 알고리즘은 각 지점마다 누적된 합을 구해놓고 특정 구간의 합만 구하면 되지만 이번 문제는 조건을 만족하는 모든 구간을 알아봐야하기 때문입니다. 투 포인터의 핵심은 "배열이 끝날 때까지 크면 줄이고 작으면 늘린다"입니다. 투 포인터는 배열을 처음부터 탐색하게 되는데 특정 구간의 시작점을 나타내는 S와 끝 지점을 나타내는 E가 있..

[Algorithm][BFS] 백준 13549 - 숨바꼭질 3

알고리즘 분류 BFS (너비 우선 탐색) 시간 복잡도 \( O(V + E) \) 문제 링크 https://www.acmicpc.net/problem/13549 해당 문제는 대표적인 BFS 문제입니다. 현재 위치 N에서 목적지 K까지 가는데 가장 최소 시간을 구해야 합니다. 이처럼 탐색을 하는 데 있어 최소 시간을 구하는 문제는 DFS보다는 BFS를 이용해야 시간 초과가 나지 않습니다. BFS의 핵심은 "해당 지점에서 갈 수 있는 곳을 다시 Queue에 넣는다" 입니다. 이때 중복되는 지점을 계속해서 탐색을 한다면 시간 초과가 발생하기 때문에 꼭 잘 체크해서 Queue에 넣어줘야 합니다. BFS 문제는 많이 풀다 보면 비슷한 템플릿이 있다는 것을 알게 됩니다. 템플릿은 보통 아래와 같습니다. 입력 변수들 ..

[Algorithm][부분 합] 백준 11659 - 구간 합 구하기 4

알고리즘 분류 부분 합 시간 복잡도 \( O(n) \) 문제 링크 https://www.acmicpc.net/problem/11659 해당 문제는 부분 합 알고리즘의 가장 기본적인 문제입니다. 부분 합 알고리즘의 핵심은 "처음부터 \( i \)번째까지 원소의 합을 미리 구해놓자"입니다. 그래서 특정 구간의 합을 \( O(1) \)의 시간으로 알아낼 수 있습니다. 단순하게 for문을 이용하여 특정 구간의 합을 구하는 시간은 \( O(n) \)이지만 구간의 합들 중 가장 크거나 작은 값을 알려면 모든 구간의 합을 알아야 합니다. 그래서 결국 시간 복잡도는 \( O(n^2) \)가 됩니다. 이런 문제의 경우 \( N \)의 값은 10만 이상의 값이므로 \( O(n^2) \)의 시간 복잡도에서는 당연히 시간 초..