하고싶은거하는 | 개발자

[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

[Algorithm] Sets - Power Set

집합 멱집합

멱집합(Power Set)이란? 멱집합은 주어진 집합 $ S $의 모든 부분 집합으로 구성된 집합입니다. 여기에는 공집합과 집합 $ S $ 자체도 포함됩니다. 만약 집합 $ S $가 $ n $개의 원소를 가지고 있다면, $ S $의 멱집합은 $ 2^n $개의 부분 집합을 가집니다. 이는 각 원소가 부분 집합에 포함되거나 제외될 수 ...

Posted by lim.Chuck on September 21, 2024

[Algorithm] Sets - Fisher–Yates shuffle

집합 Fisher–Yates 셔플

Fisher–Yates 셔플? Fisher–Yates 셔플(또는 Knuth 셔플)은 유한한 배열이나 리스트의 무작위 순열을 생성하는 알고리즘입니다. 이 알고리즘은 리스트를 역순으로 반복하며 각 요소를 자신 또는 앞에 있는 임의의 요소와 교환하는 방식으로 작동합니다. 이 알고리즘은 편향되지 않은 무작위 셔플을 보장하는데, 이는 배열...

Posted by lim.Chuck on September 21, 2024

[Algorithm] Sets - Cartesian Product

집합 카테시안 곱

카테시안 곱? 카테시안 곱은 두 집합 $ A $와 $ B $의 곱으로, 각각의 집합에서 선택한 원소를 조합하여 만든 모든 순서쌍으로 구성된 집합입니다. 이를 수식으로 나타내면 $ A \times B $로 표기하며, 결과는 각 집합 $ A $의 원소 $ a $와 집합 $ B $의 원소 $ b $로 구성된 순서쌍 $ (a, b) $들로...

Posted by lim.Chuck on September 21, 2024

CHUCK CHUCK 박사

[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

집합 순열

[Algorithm] Sets - Power Set

집합 멱집합

[Algorithm] Sets - Fisher–Yates shuffle

집합 Fisher–Yates 셔플

[Algorithm] Sets - Cartesian Product

집합 카테시안 곱

FEATURED TAGS

ABOUT ME

FRIENDS