알고리즘
[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][투 포인터] 백준 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) \)의 시간 복잡도에서는 당연히 시간 초..
[Algorithm][위상 정렬] 백준 2252 - 줄 세우기
알고리즘 분류 위상 정렬 시간 복잡도 \( O(V + E) \) 문제 링크 https://www.acmicpc.net/problem/2252 선행되어야 할 인덱스들이 주어지면서 가능한 순서를 답으로 제출하는 위상 정렬의 문제입니다. 입력으로써 특정 인덱스 2개가 주어지면 첫 번째 숫자와 두 번째 숫자는 꼭 지켜야 할 순서입니다. 테스트 케이스 2번을 예시로 든다면 아래 그림처럼 4가 2를 가리키고 3이 1을 기리 키는 구조가 됩니다. 이 두 관계를 제외하고는 각 숫자들은 서로 연관되지 않습니다. 위상 정렬의 핵심은 "간선이 없는 노드를 처리하자" 입니다. 여기서 간선이 없는 노드의 뜻은 "가리킴을 당하지 않는 노드"입니다. 그래서 저의 풀이는 Queue를 사용했고 처리하는 과정에서 간선이 없는 노드가 생..