알고리즘의 정의
-
정의 : 특정 작업을 달성하기 위한 과정이나 일련의 단계를 의미, 문제를 해결하기 위한 일련의 수학적 단계 (ex. 유튜브 알고리즘)
-
필요성 :
- 프로그래밍에서 수행하는 거의 모든 작업에는 일종의 알고리즘이 포함됨
- 성공적인 문제 해결 및 개발자가 되기 위한 기반
- 면접에 필요함
어떻게 해야 알고리즘을 더 잘 이해할 수 있을까?
→ 타고난 문제 해결 능력도 있겠지만, 노력하면서 향상될 수 있음.
- 문제 해결을 위한 계획을 수립한다.
- 일반적인 문제 해결 패턴을 파악한다. → 카테고리화
문제 해결 접근법
- 문제를 이해한다. (Understand the Problem)
- 코드를 바로 작성하기 전에 한 걸음 물러서서 직면한 과제를 확실히 이해하는 것이 중요함.
- Check List
- 문제를 나만의 방식으로 다시 생각할 수 있습니까?
- 문제는 어떤 형태의 입출력값을 가집니까?
- 문제를 해결하기에 충분한 정보를 가지고 있습니까?
- 데이터의 중요한 부분에 라벨을 지정할 수 있습니까?
- 구체적인 예시를 알아본다. (Explore Concrete Examples)
- 예시를 생각하면 문제를 더 잘 이해하는 데 도움이 되며, 최종 솔루션이 정상적으로 작동하는지 확인하는 기능을 제공한다.
- Check List
- 간단한 예시부터 시작
- 더 복잡한 예시로 나아가기
- 빈 입력이 있는 예시 및 유효하지 않은 입력값이 주어진 예시 탐색 (엣지 케이스)
- 문제를 세분화한다. (Break It Down)
- 필요한 단계들을 명확하게 의사 코드로 작성하기 (가이드라인 작성) → 면접에서 문제를 모두 풀지 못하더라도 문제 접근 방법은 알고 있다는 것을 보여줄 수 있음.
- 문제를 해결하고 단순화한다. (Solve / Simplify)
- 문제를 해결할 수 있다면 해결하고, 당장 해결할 수 없다면 해결 가능한 단순한 문제부터 해결하기 → 분할 정복
- 어려운 부분에 막혔을 때
- 문제의 핵심적인 어려움을 찾기
- 잠시 어려운 부분을 무시하기
- 단순화 된 솔루션 작성하기
- 다시 어려운 부분을 통합시키기
- 문제를 복습하고 재구성(리팩토링)한다. (Look Back and Refactor)
- 문제를 풀고나면 끝? ㄴㄴ 일어나…리팩토링 해야지…
- 그냥 작동만 하도록 작성한 코드로 끝나지 않고 코드를 분석, 성찰하며 되돌아보는 것이 중요함.
- Check List
- 결과를 확인할 수 있습니까?
- 결과를 다르게 도출할 수 있습니까?
- 한눈에 이해가 되시나요? → 직관력
- 결과나 방법을 다른 문제에 사용할 수 있습니까?
- 솔루션의 성능을 향상시킬 수 있습니까? → 시간 복잡도, 공간 복잡도로 평가
- 리팩토링할 다른 방법을 생각할 수 있습니까? → 가독성, 성능 등을 위해 리팩토링
- 다른 사람들은 이 문제를 어떻게 해결했습니까?
Q. 문자열을 입력받아 각 문자의 개수를 반환하는 함수를 작성하시오.
- 1단계 : 의사코드를 보고 가장 단순한 문법으로 구현한다.
function charCount(str) {
let result = {};
for(let i = 0; i < str.length; i++) {
let char = str[i].toLowerCase();
if(result[char] > 0) { // value가 0보다 크면 이미 해당 문자가 존재한다
result[char]++; // 1 증가
}
else {
result[char] = 1; // 1로 설정
}
}
return result;
}- 2단계 : 1차 리팩토링
function charCount(str) {
let obj = {};
for(let char of str) {
char = char.toLowerCase();
if(/[a-z0-9]/.test(char)){ // 문자가 영숫자인지 test하는 정규 표현식 (특수문자 제외)
obj[char] = ++obj[char] || 1; // ||을 기준으로 truthy면 값 증가, falsy면 1로 설정
}
}
return obj;
}- 3단계 : 2차 리팩토링 (정규 표현식보다 빠른 방법)
function charCount(str) {
let obj = {};
for(let char of str) {
if(isAlphaNumeric(char)) {
char = char.toLowerCase();
obj[char] = ++obj[char] || 1;
}
}
return obj;
}
function isAlphaNumeric(char){
let code = char.charCodeAt(0); // 첫번째 문자를 할당
if(!(code > 47 && code < 58) && // 숫자 (0-9)
!(code > 64 && code < 91) && // 대문자 (A-Z)
!(code > 96 && code < 123)) { // 소문자 (a-z)
return false;
}
return false;
}
charCodeAt(0)문제 해결 패턴
- 문제 해결 패턴은 프로그래밍 매커니즘이자 청사진이다.
- 문제 해결 패턴
- Frequency Counter
- Multiple Pointers
- Sliding Window
- Divide and Conquer
- Dynamic Programming
- Greedy Algorithms
- Backtracking
빈도 카운터 (Frequency Counter)
- 이 패턴은 객체 또는 집합을 사용하여 값의 빈도를 수집하는 패턴이다.
- 배열과 문자열을 사용하여 중첩 루프 또는 O(n^2) 작업의 필요성을 피할 수 있다.
Q. 배열 2개를 입력받아 첫번째 배열의 모든 값의 제곱이 두번째 배열에 포함되면 참을 반환하는 same 함수를 작성해라. (순서 상관없음)
- example
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)- naive solution - 시간 복잡도 : O(n²)
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]) // true- Frequency Counter solution - 시간 복잡도 : O(n)
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);
console.log(frequencyCounter2);
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]) // falseQ. 두 개의 문자열이 주어지면 두 번째 문자열이 첫 번째 문자열의 애너그램인지 확인하는 함수를 작성해라. 애너그램은 단어의 문자를 재배열해 다른 뜻을 가진 단어로 바꾸는 것을 말한다. (ex. iceman → cinema)
- example
validAnagram('', '') // true
validAnagram('aaz', 'zza') // false
validAnagram('anagram', 'nagaram') // true
validAnagram("rat","car") // false) // false
validAnagram('awesome', 'awesom') // false
validAnagram('amanaplanacanalpanama', 'acanalmanplanpamana') // false
validAnagram('qwerty', 'qeywrt') // true
validAnagram('texttwisttime', 'timetwisttext') // true- Frequency Counter solution - 시간 복잡도 : O(n)
function validAnagram(first, second) {
if(first.length !== second.length) {
return false;
}
const lookup = {};
for(let i = 0; i < first.length; i++) {
let letter = first[i];
lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
}
for(let i = 0; i < second.length; i++) {
let letter = second[i];
if(!lookup[letter]) {
return false;
} else {
lookup[letter] -= 1;
}
}
return true;
}- 내가 쓴 답
function validAnagram(str1, str2){
// add whatever parameters you deem necessary - good luck!
let obj1 = {};
let obj2 = {};
if(str1.length !== str2.length) {
return false;
}
for(let val of str1) {
obj1[val] = (obj1[val] || 0) + 1;
}
for(let val of str2) {
obj2[val] = (obj2[val] || 0) + 1;
}
for(let key in obj1) {
if(obj1[key] !== obj2[key]) {
return false;
}
}
return true;
}다중 포인터 (Multiple Pointers)
- 인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 시작, 끝 또는 중간으로 이동하는 포인터 또는 값을 생성하는 패턴. 두 개 또는 그 이상의 포인터를 두고 값들을 비교한다.
- 최소한의 공간 복잡성으로 문제를 해결하는 데 매우 효율적.
Q. 정렬된 배열을 받는 sumZero 함수를 작성해라. 함수는 합계가 0인 첫 번째 쌍을 찾아야 하며, 합계가 0이거나 쌍이 존재하지 않는 경우 정의되지 않은 두 값을 모두 포함하는 배열을 반환한다. (양 끝에서 시작하여 중간으로 이동하는 경우)
- example
sumZero([-3,-2,-1,0,1,2,3]) // [-3, 3]
sumZero([-2,0,1,3]) // undefined
sumZero([1,2,3]) // undefined- naive solution - 시간 복잡도 : O(n²)
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])- Multiple Pointers solution - 시간 복잡도 : O(n)
function sumZero(arr){
let left = 0;
let right = arr.length - 1;
while(left < right){
let sum = arr[left] + arr[right];
if(sum === 0){
return [arr[left], arr[right]];
} else if(sum > 0){
right--;
} else {
left++;
}
}
}
sumZero([-4,-3,-2,-1,0,1,2,5]) // [-2, 2]Q. 정렬된 배열을 받아 배열의 고유한 값을 계산하는 countUniqueValues라는 함수를 구현해라. 배열에 음수가 있을 수 있지만 항상 정렬된다.
- example
countUniqueValues([1,1,1,1,1,2]) // 2개
countUniqueValues([1,2,3,4,4,4,7,7,12,12,13]) // 7개
countUniqueValues([]) // 0개
countUniqueValues([-2,-1,-1,0,1]) // 4개- Multiple Pointers solution - 시간 복잡도 : O(n)
function countUniqueValues(arr){
if(arr.length === 0) return 0;
var i = 0;
for(var j = 1; j < arr.length; j++){
if(arr[i] !== arr[j]){
i++;
arr[i] = arr[j]
}
}
return i + 1;
}
countUniqueValues([1,2,2,5,7,7,99])- 내가 쓴 답
function countUniqueValues(arr){
let i = 0;
let j = 1;
if(arr.length === 0) return 0;
while(arr.length > j) {
if(arr[i] === arr[j]) {
j++;
} else {
i++;
arr[i] = arr[j];
}
}
return i + 1;
}슬라이딩 윈도우 (Sliding Window)
- 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘.
- 배열이나 문자열 등의 일련의 데이터를 입력하거나 특정 방식으로 해당 데이터의 하위 집합을 찾는 경우에 유용.
Q. 정수 배열과 n이라는 숫자를 받아들이는 maxSubarraySum이라는 함수를 작성해라. 함수는 배열에서 n개의 연속된 요소의 최대 합을 계산해야 한다.
- example
maxSubarraySum([1,2,5,2,8,1,5],2) // 2 + 8 = 10
maxSubarraySum([1,2,5,2,8,1,5],4) // 2 + 5 + 2 + 8 = 17
maxSubarraySum([4,2,1,6],1) // 6
maxSubarraySum([4,2,1,6,2],4) // 4 + 2 + 1 + 6 = 13
maxSubarraySum([],4) // null- naive solution - 시간 복잡도 : O(n²)
function maxSubarraySum(arr, num) {
if (num > arr.length){ // 주어진 수가 배열의 길이보다 크면 null 반환
return null;
}
var max = -Infinity; // 배열이 모두 음수일 경우 가장 큰 합은 여전히 음수이므로 음수로 최댓값 지정
for (let i = 0; i < arr.length - num + 1; i ++){
temp = 0; // 각 루프의 합계가 저장되는 변수
for (let j = 0; j < num; j++){ // i를 기준으로 num개씩 더함
temp += arr[i + j];
}
if (temp > max) {
max = temp;
}
}
return max;
}
maxSubarraySum([2,6,9,2,1,8,5,6,3],3)- Sliding Window solution - 시간 복잡도 : O(n)
function maxSubarraySum(arr, num){
let maxSum = 0;
let tempSum = 0;
if (arr.length < num) return null; // 주어진 수가 배열의 길이보다 크면 null 반환
for (let i = 0; i < num; i++) { // num 개수 만큼 합산
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)분할 정복 (Divide and Conquer)
- 분할 정복 알고리즘은 주로 배열이나 문자열 같은 큰 규모의 데이터 세트를 더 작은 조각으로 나눈 다음 데이터 하위 집합으로 프로세스를 반복하는 것을 포함한다.
- 이 패턴은 시간 복잡성을 크게 줄일 수 있다.
Q. 정렬된 정수 배열이 주어지면 값을 받아 함수에 전달된 값이 있는 인덱스를 반환하는 search라는 함수를 작성해라. 값을 찾을 수 없으면 -1을 반환한다.
- example
search([1,2,3,4,5,6],4) // 3
search([1,2,3,4,5,6],6) // 5
search([1,2,3,4,5,6],11) // -1- naive solution - 시간 복잡도 : O(n)
function search(arr, val){
for(let i = 0; i < arr.length; i++){
if(arr[i] === val){
return i;
}
}
return -1;
}- Divide and Conquer solution (이진 탐색) - 시간 복잡도 : O(log n)
function search(array, val) {
let min = 0;
let max = array.length - 1;
while (min <= max) {
let middle = Math.floor((min + max) / 2); // 반복적으로 절반을 나누어 중간 지점을 찾는다
let currentElement = array[middle];
if (array[middle] < val) {
min = middle + 1;
}
else if (array[middle] > val) {
max = middle - 1;
}
else {
return middle;
}
}
return -1;
}Udemy의 JavaScript 알고리즘 & 자료구조 마스터클래스를 학습하고 정리한 내용입니다.
잘못된 부분이 있다면 댓글로 피드백 부탁드립니다!
FE developer