하고싶은거하는 | 개발자

[Algorithm] Strings - Z Algorithm

문자열 Z 알고리즘

Z 알고리즘? Z 알고리즘은 문자열에서 특정 패턴을 찾거나 문자열 내에서 일치하는 부분을 빠르게 계산하는 효율적인 방법입니다. 주어진 문자열에서 각 접두사와 원래 문자열의 접두사와의 일치하는 길이를 저장하는 Z 배열을 기반으로 동작합니다. Z 배열이란? Z 배열의 각 요소는 해당 인덱스에서 시작하는 부분 문자열이 원래 문자...

Posted by lim.Chuck on September 27, 2024

[Algorithm] Strings - Hamming Distance

문자열 해밍 거리

해밍 거리 (Hamming Distance)? 설명: 해밍 거리는 두 이진 문자열 간에 서로 다른 비트의 개수를 의미합니다. 즉, 두 개의 동일한 길이의 문자열에서 각 위치에서 다른 값을 가진 비트의 수를 측정하는 데 사용됩니다. 이는 주로 오류 검출 및 교정, 데이터 전송에서 사용됩니다. 사용 사례: 오류 검출 및 교정:...

Posted by lim.Chuck on September 26, 2024

[Algorithm] Sets - Combination Sum Problem

집합 최대 조합 합 문제

조합 합 문제 (Combination Sum Problem)? 설명: 조합 합 문제는 주어진 배열 내의 숫자들을 사용하여 특정 목표값을 만들 수 있는 모든 조합을 찾는 문제입니다. 이 문제에서 각 숫자는 여러 번 사용할 수 있으며, 숫자의 순서는 중요하지 않습니다. 주로 백트래킹(Backtracking)을 통해 효율적으로 해결할 수...

Posted by lim.Chuck on September 26, 2024

[Algorithm] Sets - Maximum subarray problem

집합 최대 부분 배열 문제

최대 부분 배열 문제 (Maximum Subarray Problem)? 설명: 최대 부분 배열 문제는 배열 내에서 연속된 부분 배열 중 합이 가장 큰 부분 배열을 찾는 문제입니다. 이 문제는 Kadane’s Algorithm이라는 알고리즘을 사용해 효율적으로 해결할 수 있습니다. 이 알고리즘의 시간 복잡도는 O(n)으로 매우 효율적...

Posted by lim.Chuck on September 25, 2024

[Algorithm] Sets - Knapsack Problem

집합 배낭 문제

배낭 문제 (Knapsack Problem)? 배낭 문제는 제한된 용량의 배낭에 다양한 무게와 가치가 있는 물건들을 넣어 최대 가치를 얻는 문제입니다. 배낭 문제는 최적화 문제 중 하나로, 다양한 변형들이 존재하며 실제로 여러 가지 분야에 응용될 수 있습니다. 대표적으로 세 가지 배낭 문제가 있습니다: 0/1 배낭 문제 (0...

Posted by lim.Chuck on September 24, 2024

[Algorithm] Sets - Shortest Common Supersequence

집합 최단 공통 슈퍼시퀀스

최단 공통 슈퍼시퀀스 (SCS)? 최단 공통 슈퍼시퀀스 (SCS)는 컴퓨터 과학 문제로, 두 개의 시퀀스가 주어졌을 때, 이 두 시퀀스를 모두 부분 시퀀스로 포함하는 가장 짧은 시퀀스를 찾는 문제입니다. 이 시퀀스는 두 입력 시퀀스의 모든 문자를 원래 순서대로 포함해야 합니다. 문제 정의: 두 문자열 X와 Y가 주어졌을 때, 두...

Posted by lim.Chuck on September 23, 2024

[Algorithm] Sets - Longest Increasing Subsequence

집합 최장 공통 부분수열

가장 긴 증가하는 부분 수열 (LIS)? 가장 긴 증가하는 부분 수열 (LIS)은 고전적인 컴퓨터 과학 문제입니다. 숫자 시퀀스가 주어졌을 때, 이 시퀀스에서 모든 요소가 엄격하게 증가하는 가장 긴 부분 수열을 찾는 것이 목표입니다. 부분 수열은 일부 또는 아무 요소도 삭제하지 않고, 나머지 요소들의 순서를 유지하여 다른 시퀀스로...

Posted by lim.Chuck on September 22, 2024

[Algorithm] Sets - Longest common subsequence problem

집합 최장 공통 부분수열

최장 공통 부분 수열 문제(Longest Common Subsequence Problem)? 최장 공통 부분 수열 (LCS) 문제는 두 개의 수열에서 같은 순서로 나타나는 가장 긴 부분 수열을 찾는 문제입니다. 여기서 부분 수열은 다른 수열에서 일부 또는 아무 요소도 삭제하여 나머지 요소의 순서를 변경하지 않고 얻은 수열입니다. ...

Posted by lim.Chuck on September 21, 2024

[Algorithm] Sets - Combinations

집합 조합

조합(Combinations)? 조합은 더 큰 집합에서 항목을 선택할 때 선택의 순서가 중요하지 않은 경우를 말합니다. $ n $개의 항목 중 $ r $개의 항목을 선택할 때 가능한 조합의 수는 $ C(n, r) $로 표시되며, 다음과 같은 공식을 사용하여 계산됩니다: $ C(n, r) = \frac{n!}{r!(n - r)!} ...

Posted by lim.Chuck on September 21, 2024

[Algorithm] Sets - Permutations

집합 순열

순열(Permutations)? 순열은 순서가 중요한 원소의 다양한 배열을 말합니다. $ n $개의 원소로 이루어진 집합이 주어질 때, 가능한 순열의 수는 $ n! $ (n 팩토리얼)로 표현되며, 이는 1부터 $ n $까지의 모든 양의 정수의 곱을 나타냅니다. 예를 들어, 집합 $ S = {1, 2, 3} $의 순열은 다음과 같습...

Posted by lim.Chuck on September 21, 2024

CHUCK CHUCK 박사

[Algorithm] Strings - Z Algorithm

문자열 Z 알고리즘

[Algorithm] Strings - Hamming Distance

문자열 해밍 거리

[Algorithm] Sets - Combination Sum Problem

집합 최대 조합 합 문제

[Algorithm] Sets - Maximum subarray problem

집합 최대 부분 배열 문제

[Algorithm] Sets - Knapsack Problem

집합 배낭 문제

[Algorithm] Sets - Shortest Common Supersequence

집합 최단 공통 슈퍼시퀀스

[Algorithm] Sets - Longest Increasing Subsequence

집합 최장 공통 부분수열

[Algorithm] Sets - Longest common subsequence problem

집합 최장 공통 부분수열

[Algorithm] Sets - Combinations

집합 조합

[Algorithm] Sets - Permutations

집합 순열

FEATURED TAGS

ABOUT ME

FRIENDS