하고싶은거하는 | 개발자

[Algorithm] Strings - Longest Common Substring Problem

문자열 LCS

Longest Common Substring? Longest Common Substring (LCS) 문제는 두 문자열 간에 가장 긴 공통 부분 문자열을 찾는 문제입니다. 이때, 부분 문자열은 문자열에서 연속된 문자들로 이루어진 부분을 말하며, 중간에 문자가 생략될 수는 없습니다. 어디에 사용되는지: 유전자 서열 비교: 유...

2024년 09월 27일 · lim.Chuck

[Algorithm] Strings - Rabin Karp Algorithm

문자열 라빈 카프

Rabin-Karp? Rabin-Karp 알고리즘은 문자열에서 특정 패턴을 찾는 데 사용되는 효율적인 해시 기반 문자열 검색 알고리즘입니다. 이 알고리즘의 핵심은 해시 함수를 이용해 텍스트와 패턴의 해시 값을 계산하고, 이를 비교하여 패턴을 찾는 방식입니다. 동작 방식: 패턴과 텍스트의 첫 번째 부분의 해시 값을 계산합니다...

2024년 09월 27일 · lim.Chuck

[Algorithm] Strings - Levenshtein Distance

문자열 레벤슈타인 거리

레벤슈타인 거리 (Levenshtein Distance)? 설명: 레벤슈타인 거리는 두 문자열 사이에서 하나의 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 횟수를 의미합니다. 여기서 편집 작업은 삽입(Insertion), 삭제(Deletion), 교체(Substitution) 세 가지로 이루어집니다. 이 거리는 문자열 유...

2024년 09월 27일 · lim.Chuck

[Algorithm] Strings - Z Algorithm

문자열 Z 알고리즘

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

2024년 09월 27일 · lim.Chuck

[Algorithm] Strings - Hamming Distance

문자열 해밍 거리

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

2024년 09월 26일 · lim.Chuck

[Algorithm] Sets - Combination Sum Problem

집합 최대 조합 합 문제

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

2024년 09월 26일 · lim.Chuck

[Algorithm] Sets - Maximum subarray problem

집합 최대 부분 배열 문제

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

2024년 09월 25일 · lim.Chuck

[Algorithm] Sets - Knapsack Problem

집합 배낭 문제

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

2024년 09월 24일 · lim.Chuck

[Algorithm] Sets - Shortest Common Supersequence

집합 최단 공통 슈퍼시퀀스

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

2024년 09월 23일 · lim.Chuck

[Algorithm] Sets - Longest Increasing Subsequence

집합 최장 공통 부분수열

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

2024년 09월 22일 · lim.Chuck

CHUCK CHUCK 박사

[Algorithm] Strings - Longest Common Substring Problem

문자열 LCS

[Algorithm] Strings - Rabin Karp Algorithm

문자열 라빈 카프

[Algorithm] Strings - Levenshtein Distance

문자열 레벤슈타인 거리

[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

집합 최장 공통 부분수열

인기 태그

ABOUT ME

FRIENDS