ALGORITHM/알고리즘 이론

조합(Combination)이란?조합은 주어진 집합에서 특정 개수의 원소를 선택하는 방법을 의미한다. 순서에 상관없이 선택된 원소들로 구성된 집합을 조합이라고 한다. 예를 들어, 집합 {A, B, C, D, E}에서 3개의 원소를 선택하는 경우, 가능한 조합은 {A, B, C}, {A, B, D}, {A, B, E}, {A, C, D}, {A, C, E}, {A, D, E}, {B, C, D}, {B, C, E}, {B, D, E}, {C, D, E}이다.쉽게 말해 순서가 바뀌어도 연산(혹은 값)이 동일하고 선택해야 하는 개수가 고정되어 있으면(위의 예시로 들자면 개수는 3으로 고정되어 있다.) 조합을 고려해 볼 수 있겠다.  시간 복잡도조합 생성의 시간 복잡도는 O(C(C, R) 또는 O(N! / (R..

부분집합(Subset)이란?부분집합은 주어진 집합의 원소들 중 일부를 선택하여 형성된 집합을 말한다. 주어진 집합 S의 모든 가능한 부분집합을 구하는 것이 부분집합 문제이다. 예를 들어, 집합 S = {A, B, C}의 부분집합은 0(공집합), {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, {A, B, C}와 같다.쉽게 말해 순서가 바뀌어도 연산(혹은 값)이 동일하고 선택해야 하는 개수가 따로 고정되어 있지 않은 모든 경우라면 부분집합을 고려해 볼 수 있겠다.  시간 복잡도부분집합을 생성하는 시간 복잡도는 O(2^N)이다. 이는 각 원소에 대해 두 가지 선택(포함 또는 미포함)이 가능하므로, 모든 가능한 부분집합을 생성하기 위해 2^N개의 경우를 탐색해야 함을 의미한다. 이로 인해..

순열이란?순열(Permutation)은 집합에서 일부 원소를 선택하여 순서를 고려해 나열하는 방법을 말한다. 선택된 원소들의 순서가 다르면 다른 순열이 된다. 예를 들어, 주어진 집합 {A, B, C}에서 2개를 선택하여 나열할 수 있는 순열은 AB, AC, BA, BC, CA, CB 등이 있다.쉽게 말해 순서가 바뀌면 연산(혹은 값)이 달라지고 선택해야 하는 개수가 고정되어 있으면(위의 예시로 들자면 개수는 2로 고정되어 있다.) 순열을 고려해 볼 수 있겠다. 사용 사례문제 해결 : 원소들을 모든 가능한 방법을 나열해야 할 때 사용된다. 예를 들어, 순열을 이용하면 문제의 가능한 모든 경우의 수를 탐색하거나, 정렬된 순서대로 원소들을 나열하는 경우에 활용된다.암호 해독 : 암호 해독 문제에서 가능한 모..

Arrays.sort()와 Collections.sort()알고리즘 정렬 문제를 풀던 중 Arrays.sort()와 Collections.sort()의 시간복잡도에 차이가 있다는 점을 깨닫게 되었다. 같은 sort() 메서드지만 내부에서는 다른 정렬법을 사용한다. 정렬 방식시간 복잡도Arrays.sort()Dual-Pivot QuickSort평균 : O(n log n) / 최악 : O(n^2)Collections.sort()TimSort (삽입정렬과 합볍정렬을 결합한 정렬)평균, 최악 : O(n log n) Arrays.sort()의 경우 Dual-Pivot QuickSort 알고리즘을 사용한다. 평균 시간복잡도가 O(n log n)이고 매우 빠른 알고리즘인 것은 맞다. 하지만 최악의 경우 시간복잡도는 ..

카운팅 정렬(Counting Sort)이란?정수나 정수로 표현할 수 있는 자료에 대해 유효한 알고리즘으로, 시간 복잡도가 O(n + k)인 정렬 알고리즘이다. 여기서 n은 배열의 크기이고 k는 배열의 요소 중 최댓값이다. 카운팅 정렬은 주로 범위가 제한된 작은 정수들로 구성된 배열을 정렬하는 데 적합하다. 정렬 과정가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 리스트를 생성데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가증가된 리스트에서 0인 값을 제외하고, 인덱스를 인덱스 값만큼 출력  카운팅 정렬을 사용하면 안되는 상황카운팅 정렬은 수많은 정렬 알고리즘 중 시간복잡도가 O(n)으로 좋은 성능을 보여주는 알고리즘이다.다만, 카운팅 정렬의 단점은 count..

투 포인터 알고리즘 (Two Pointer Algorithm)배열이나 리스트에서 '두 개의 포인터'를 사용하여 '특정 조건을 만족하는 부분 구간'을 효율적으로 탐색하는 알고리즘이다. 일반적으로 배열이나 리스트가 '정렬되어 있을 때' 사용한다.투 포인터 알고리즘은 보통은 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킨다.또는 동일한 시점을 기점으로 왼쪽 포인터를 고정한 상태에서 오른쪽 포인터를 이동하고, 조건에 따라 왼쪽 포인터도 이동하며 탐색하는 방식을 가진다.해당 알고리즘은 탐색 범위 내에서 특정 조건을 만족하는 요소를 찾거나, 조건을 만족하는 부분 배열의 길이 등을 계산하는 데 사용될 수 있다. 투 포인터 수행 단계배열 또는 리스트의 시작 위치에 첫 번째 포인터와..