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][투 포인터] 백준 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) \)의 시간 복잡도에서는 당연히 시간 초..

[C++] 2차원 배열 특정 값 초기화

2차원 배열 값 할당 2차원으로 선언된 배열을 fill 함수를 사용하여 특정 값을 할당시킬 수 있습니다. fill( 시작 주소, 끝 주소, 값 ) fill() 함수를 적용시켰을 때 배열의 값이 바뀌는 범위는 [시작주소, 끝 주소) 입니다. C++에서 배열 값을 특정 값으로 설정하는 함수들이 존재합니다. 대표적으로 memset(), fill() 함수가 있습니다. 하지만 memset()의 경우 초기화시킬 수 있는 값은 0과 -1로 제한이 됩니다. 알고리즘 문제를 풀 때 보통 0으로 초기화시키는 경우가 많아서 memset()을 흔히 사용하긴 하지만, 가끔씩 0과 -1이 아닌 값으로 초기화시키고 싶을 때가 있습니다. 이럴 때 memset() 함수를 사용하지 못하는 점이 아쉽긴 합니다. 하지만 memset()을 ..