알고리즘 문제 해결 패턴
ALGORITHM ·해당 내용은 UDEMY의 알고리즘 ∙ 자료구조 강의를 수강 후 정리한 내용입니다.
빈도수 세기 패턴
자바스크립트 객체를 사용해 다양한 값과 빈도를 수집하는 것으로, 값이 다른 값에 포함되는지 또는 데이터를 입력값이나 두 개 이상의 빈도 또는 특정한 빈도와 비교할 때 사용합니다.
빈도수 세기 패턴 예시 : 두 개의 배열을 받았을 때 두 번째 배열이 첫 번째 배열의 제곱값들을 가지는 지 확인하기
same([1, 2, 3], [4, 1, 9]); // true
same([1, 2, 3], [1, 9]); // false
same([1, 2, 1], [4, 4, 1]); // false (must be same frequency)
function same(arr1, arr2) {
if (arr1.length !== arr2.length) {
return false;
}
for (let i = 0; i < arr1.length; i++) {
let correctIndex = arr2.indexOf(arr1[i] ** 2);
if (correctIndex === -1) {
return false;
}
console.log(arr2);
arr2.splice(correctIndex, 1);
}
return true;
}
same([1, 2, 3, 2], [9, 1, 4, 4]);
위와 같은 방법을 쓸 시, 좋지 않은 방법으로서 시간 복잡도가 O(n^2)이 됩니다. 원하는 결과를 얻기 위해 있는 그대로의 해결법을 제시하는 형태이기 때문에 생기는 문제로 아래와 같은 방식으로 문제를 다시 해결할 수 있습니다.
function same(arr1, arr2) {
if (arr1.length !== arr2.length) {
return false;
}
let frequencyCounter1 = {};
let frequencyCounter2 = {};
for (let val of arr1) {
frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
}
for (let val of arr2) {
frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
}
console.log(frequencyCounter1);
// { '1': 1, '2': 2, '3': 1, '5': 1 }
console.log(frequencyCounter2);
// { '1': 1, '4': 2, '9': 1, '11': 1 }
for (let key in frequencyCounter1) {
if (!(key ** 2 in frequencyCounter2)) {
return false;
}
if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
return false;
}
}
return true;
}
same([1, 2, 3, 2, 5], [9, 1, 4, 4, 11]);
현재의 코드는 이전 코드와 다른 점으로서, 두 개의 다른 루프를 사용하기 때문에, 이전의 중첩된 루프를 쓰는 것보다 훨씬 효율적으로 해결할 수 있습니다. 개수와 관련된 두 개의 객체를 만들고 하나의 객체에서 확인을 위해 순회하면 되기 때문에 계산 횟수가 훨씬 줄어들게 됩니다.
위 함수를 통한 계산을 진행할 시 아까의 O(n^2)와 달리 O(3n)이라는 결과가 나와 훨씬 효율적이게 됩니다. 이와 같은 빈도 카운터의 개념은 보통 객체를 사용하게 됩니다. 이러한 객체를 사용해 배열, 문자열과 같은 선형 구조를 재구성하고, 순회를 통해 문제를 해결하는 방법을 ‘빈도수 세기 패턴’ 이라고 볼 수 있습니다.
빈도수 세기 패턴 예시 : ANAGRAMS (애너그램)
두 개의 문자가 주어진 상황에서, 주어진 문자의 횟수, 빈도가 같은 상황을 애너그램이라고 합니다. 아래와 같은 예시가 나올 수 있습니다. 이러한 경우에도 빈도 카운터를 통해서 해결이 가능합니다.
validAnagram(" ", " "); //true
validAnagram("aaz", "zza"); //false
validAnagram("anagram", "nagaram"); //true
function validAnagram(first, second) {
if (first.length !== second.length) {
return false;
}
// 같은 길이가 아닐 시, 횟수가 다르므로 false가 됨
const lookup = {};
for (let i = 0; i < first.length; i++) {
let letter = first[i];
// 문자가 존재할 시 1을 더하고, 아닐 시 1로 설정함
lookup[letter] ? (lookup[letter] += 1) : (lookup[letter] = 1);
}
for (let i = 0; i < second.length; i++) {
let letter = second[i];
// 문자가 존재하지 않거나, 0일 경우 애너그램이 아니므로 false가 됨
if (!lookup[letter]) {
return false;
} else {
// 문자가 존재할 경우 1을 빼줌
lookup[letter] -= 1;
}
}
return true;
}
// {a: 0, n: 0, g: 0, r: 0, m: 0,s:1}
validAnagram("anagrams", "nagaramm");
이전 예시와 같이 중첩된 루프가 아니라, 두 개의 개별적인 루프(for문)를 돌아서 문제를 해결하는 것을 볼 수 있습니다. 이러한 접근법을 활용 가능한 사례로는 아래와 같습니다.
- 여러 데이터가 같은 개별 데이터 조각으로 구성되었는지 확인 시
- 한 배열이 각 개별 데이터 조각을 제곱한 것과 같을 시
- 숫자가 같은 숫자로만 구성되고 순서가 다른 것인지 확인 시
다중 포인터 패턴
인덱스나 위치에 해당하는 포인터, 값을 만들고 특정 조건에 따라 중간 지점에서부터 시작 지점이나 끝 지점, 양쪽 지점으로 이동하는 것을 말합니다. 선형 구조, 다중 연결 리스트 등에 사용하며, 한 쌍의 값이나 조건을 충족하는 무언가를 찾는 데에 사용합니다.
다중 포인터 패턴 예시 : 정렬된 배열(오름차순)을 취하는 함수 작성하기
배열 내의 합이 0이 되는 두 요소를 모두 찾아야 하는 문제입니다. 여기서는 배열이 정렬되어 있다는 점을 인지해야 하는데, 두 개의 포인터를 사용해 위 아래로 이동하도록 설정하면 됩니다.
function sumZero(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] === 0) {
return [arr[i], arr[j]];
}
}
}
}
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]);
위 코드는 부적절한 코드 예시로서, 배열이 중첨되어 돌아가, 시간 복잡도가 O(n^)의 형태로 되는 것을 볼 수 있습니다. 하나의 값에 대한 음수를 찾기 위해서 계속 찾아가는 과정이 필요하게 되고, 만약 10000개가 넘는 배열이 있다면 반복이 너무나 많이 이루어지게 됩니다.
function sumZero(array) {
let left = 0;
// 가장 왼쪽의 인덱스
let right = arr.length - 1;
// 가장 오른쪽의 인덱스
while (left < right) {
// 서로 만나는 지점에 가기 전까지 반복
let sum = array[left] + array[right];
if (sum === 0) {
return [array[left], array[right]];
} else if (sum > 0) {
right -= 1;
} else {
left += 1;
}
}
}
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]);
위 코드는 적절한 예시의 코드로서, 시간 복잡도가 O(n)이 됩니다. 좌우의 합을 0과 비교해가며, 좌우가 만나기 전까지 점점 좁혀가며 계산을 계속하게 됩니다. 다음과 같은 순서로 계산이 이루어지게 됩니다.
-4와 5가 만남 → 양수가 되므로 5가 2로 이동 → 음수가 됨 → -4가 -3으로 이동 → 음수가 되므로 -3이 -2로 이동 → 0이 됨 → [-2, 2] 리턴
다중 포인터 패턴 예시 : 주어진 배열의 고유값의 개수를 구하기
처음과 끝에서 이동하는 것이 아닌 같은 포인터에서 서로 다른 방향으로 이동해야 하는 예시입니다. 두 개의 포인터가 왼쪽 ∙ 오른쪽 중 한 방향에서 같이 시작해 하나가 더 앞서가는 방식으로 진행합니다.
function countUniqueValues(arr) {
if (arr.length === 0) return 0;
// 값이 없는 경우에 대한 처리
var i = 0;
for (var j = 1; j < arr.length; j++) {
// 서로 다른 비교값일 경우, i가 늘어나면서 배열 내에 표기
if (arr[i] !== arr[j]) {
i += 1;
arr[i] = arr[j];
}
}
return i + 1;
}
countUniqueValues([1, 2, 2, 5, 7, 7, 99]);
i[(1, 2, 3, 3, 3, 5, 6, 7, 7, 8)];
j;
위와 같은 형식으로 i와 j의 비교가 계속 되면서, 일치하지 않는 경우 i에 위치한 값을 j의 값으로 변경하며 앞으로 나아가게 됩니다.
기준점 간 이동 배열 패턴
sliding window라고도 불리는 패턴으로, 배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용합니다. 사용되는 예시로는 다음과 같습니다.
- 규모가 큰 데이터셋에서 데이터의 하위 집합을 추적할 때
- 연속된 고유 문자를 가지는 문자열을 찾을 때
(“hellothere”와 같은 문자열이 주어질 경우 “hel”까지는 이어지지만 “lo”부분에서 “l”이 연속되어 끊어지게 됨)
기준점 간 이동 배열 패턴 예시 : 배열 내의 연속적인 n개의 요소의 합 중 가장 큰 것 구하기
maxSubarraySum([2, 6, 9, 2, 1, 8, 5, 6, 3], 3);
function maxSubarraySum(arr, num) {
if (num > arr.length) {
return null;
}
var max = -Infinity;
// 양수로만 작업을 할 경우에는 0으로 할 수 있으나, 음수를 더하고 비교할 수도 있기 때문에 -Infinity
for (let i = 0; i < arr.length - num + 1; i++) {
// 0부터 시작하는 시작점
temp = 0;
for (let j = 0; j < num; j++) {
// i가 바뀔 때마다 합을 구하기 위한 루프
temp += arr[i + j];
}
if (temp > max) {
max = temp;
}
}
return max;
}
maxSubarraySum([2, 6, 9, 2, 1, 8, 5, 6, 3], 3);
위 예시는 단순하게 푸는 방법으로서, ‘2 - 2 사이의 요소를 더한 것을 비교 → 6 - 1 사이의 요소를 더한 것을 비교’의 순서로 풀어 나가게 되고, 하나의 지점에 방문할 때마다 모든 합을 구하고, 그 합을 이전의 값과 비교하는 과정을 가집니다. 이렇게 진행할 시, 주어진 배열이 상당히 긴 경우에 비효율적으로 이루어지게 됩니다.
function maxSubarraySum(arr, num) {
let maxSum = 0;
let tempSum = 0;
if (arr.length < num) return null;
// 처음에 0부터 num까지의 합 구하기
for (let i = 0; i < num; i++) {
maxSum += arr[i];
}
tempSum = maxSum;
// 기존의 값에서 가장 처음 값을 빼고, 새로 들어오는 마지막 값을 더함
for (let i = num; i < arr.length; i++) {
tempSum = tempSum - arr[i - num] + arr[i];
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}
maxSubarraySum([2, 6, 9, 2, 1, 8, 5, 6, 3], 3);
위 예시는 O(N)의 시간 복잡도, 즉 선형 복잡도를 가지는 풀이입니다. 처음에 0부터 주어진 값의 인덱스까지의 값을 더한 뒤, 이후 루프를 돌면서 가장 처음 값을 빼고, 새로 들어오는 마지막 값을 더하는 방식으로 진행하여 문제를 해결할 수 있습니다.
분할과 정복 패턴
주로 배열이나 문자열, 연결리스트와 같은 큰 규모의 데이터셋을 처리할 때 사용합니다.
분할과 정복 패턴 예시 : 배열 내 문자 인덱스 찾기
search([1, 2, 3, 4, 5, 6], 4); // 3
search([1, 2, 3, 4, 5, 6], 11); // -1
단순한 방법으로 찾는 것은 배열을 하나씩 다 돌면서 정해진 숫자를 찾는 것으로 코드로는 아래와 같습니다.
function serach(arr, val) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === val) return i;
}
return -1;
}
위와 같이 진행할 경우, O(N)의 시간복잡도가 나오게 되어 상당히 비효율적입니다. 대신에, 주어지는 배열이 이미 오름차순과 같이 정렬된 배열일 경우, 배열의 중간에서 바로 시작하는 방법을 사용할 수 있습니다.
function serach(arr, val) {
let min = 0;
let max = arr.length - 1;
while (min <= max) {
let middle = Math.floor((min + max) / 2);
let currentElement = arr[middle];
if (currentElement < val) {
min = middle + 1;
} else if (currentElement > val) {
max = middle - 1;
} else {
return middle;
}
return -1;
}
}
위 코드에서 가장 중요한 것은 중간 지점으로 간 뒤 필요 없는 부분을 모두 없애고 남는 부분에 집중한다는 것입니다. 위와 같은 방법을 통해서 시간 복잡도를 상당히 낮출 수 있습니다.