버블정렬은 가장 큰 값 또는 가장 작은 값이 계속 버블되며(자리를 이동하며) 정렬이 되는 알고리즘이다. 만약 [1, 2, 7, 4, 6, 5, 3, 8] 이란 배열이 있을 경우에 쭉 오름차순으로 정렬할 수 있고, ex) [1, 2, 3, 4, 5, 6, 7, 8] 내림차순으로 정렬할 수 도 있다. ex) [8, 7, 6, 5, 4, 3, 2, 1] 단순한 정렬 알고리즘인 만큼 직관적이지만 비효율적으로 구현 해볼 수 있다. 아래 코드는 굉장히 naive한 버블정렬 구현이다. 원시적인 버블정렬 (Naive) function naiveBubbleSort(arr) { for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length; j++) { if ..
배열 내 문자열을 탐색하는 무식한 방법이다. 알고리즘이 기억이 안날 경우, Naive한 방법으로도 해결이 가능해야하므로 해당 글을 포스팅한다. 문제는 아래와 같다. /* 인수로 문자열 2개를 가지는 naivestring이라는 함수를 작성해라. 첫번째 인수로 들어가는 문자열 내부에 두번째 인수로 들어가는 문자열이 총 몇개가 있는지 카운트해서 리턴한다. */ naivestring('멋쟁이사자처럼', '이사자') // 1 naivestring('안녕하세요감사해요잘있어요다시만나요', '요') // 4 naivestring('디아블로', '메피스토') // 0 풀이 전 생각) for문을 사용해서 해결한다. 일단 count 변수를 하나 생성해서 for문이 다 끝나면 리턴한다. 외부 for문을 첫번째 인수 문자열을,..
이진 탐색 이진탐색은 정렬된 배열에서 사용하기 좋은 탐색 알고리즘으로써, 배열 내 모든 엘리먼트를 전부 찾아가는 선형 탐색과는 달리 배열을 절반씩 잘라 탐색하여 필요한 부분을 효과적으로 찾아낼 수 있는 알고리즘이다. 즉, 정렬된 배열이 아니면 사용할 수 없는 알고리즘이다. 이진탐색에는 인덱스를 표시할 변수가 3개 필요하다. 여기서는 편의상 start, point, end라고 부르겠다. start : 탐색 범위를 지정해주는 시작 지점이 되며, 루프를 돌때마다 동적으로 바뀐다. point : 탐색 범위의 가운데를 짚어주는 인덱스이며, 언제나 (start + end) / 2 의 값을 가진다. end : 탐색 범위를 지정해주는 끝 지점이 되며, 루프를 돌 때마다 동적으로 바뀐다. 이 때 point가 굉장히 중요..
선형 탐색 배열 내에서 특정한 값을 찾기 위해 사용할 수 있는 가장 심플한 방법은 배열 내의 모든 엘리먼트를 A부터 Z까지 쭉 훑어서 찾는 것이다. 이 방법이 선형 탐색이다. 우리는 선형 탐색을 이미 사용중이다. 우리는 이미 자바스크립트에서 선형 탐색을 사용하고 있었을 것이다. 자바스크립트에는 몇 종류의 선형 탐색 메서드가 내장되어 있다. Array.indexOf Array.includes Array.find Array.findIndex 네개의 메서드는 리턴하는 값은 다르지만 동작하는 로직은 크게 다를바가 없다. 배열 내 모든 엘리먼트를 순환하는 로직이라는 것이다. (선형 탐색) 단어를 너무 어렵게만 생각하지 말자 배열을 A부터 Z까지 모두 순회하며 값을 찾아낸다면 그것은 선형 탐색이다. 아래의 코드처럼..
재귀문제로 피보나치 수열을 접한 사람은 어마어마하게 많을 것이다. 그러나, 피보나치 수열을 재귀적으로 이해하지 못하는 사람이 너무나도 많음을 느낀다. 피보나치 수열은 어렵다. 이 문제를 쉬운 문제라고 말하는 것은 옳지 못하다고 생각한다. 다만 쉽게 풀어서 설명해보고자 한다. 피보나치 수열 피보나치 수열이란 뭘까? 피보나치라는 사람이 발견한 수열이며, 수열로써 특정 식을 가지고 쭉 뻗어 나간다. 피보나치 수열은 아래의 점화식으로 표현이 가능하다. F0 = 0, F1 = 1, F(n + 2) = F(n + 1) + Fn 그러나 여기에서는 굳이 점화식이라는 단어를 써가며 재귀함수를 공부하지 말자. 위를 직관적으로 표현하면 아래와 같다. 15번째 항까지 나열된 피보나치 수열을 보자. 1, 1, 2, 3, 5, ..
pure recursive는 그냥 순수한 재귀함수로 문제를 해결하는 방식이다. 코드는 짧아질 지 몰라도 매우 직관적이지 못하다. 아래 함수는 바로 밑 게시글에 있는 helper function recursive와 같은 문제풀이이다. 다만, 헬퍼 함수없이 순수히 재귀적으로만 문제를 해결한 것이다. function collectOddValues(arr) { let newArr = [] if (arr.length === 0) return if (arr[0] % 2 !== 0) newArr.push(arr[0]) newArr = newArr.concat(collectOddValues(arr.slice(1))) return newArr } collectOddValues([1,2,3,4,5,6,7,8,9])
재귀함수를 쓰는 방법에는 여러가지가 있는데 헬퍼 함수처럼 재귀함수를 사용하는 방법이 있다. 아래는 주어진 배열 내 엘리멘트 중 홀수의 값만 배열에 담아 리턴하는 함수이다. function collectiveOddValues(arr) { let result = [] function helper(input) { if (input.length === 0) return if (input[0] % 2 !== 0) result.push(input[0]) return helper(input.slice(1)) } helper(arr) return result } 함수 내 재귀함수로 사용할 함수를 따로 생성하여 문제 해결에 도움을 주는 패턴이다. 만약 collectiveOddValues를 재귀한다면 result값은 계속..
이번 글에서 재귀함수란 무엇인지 간단히 정의해보고, 다음 게시물부터는 재귀함수에 관한 문제를 쭉 풀어보고자 한다. 재귀란 무엇일까? - 재귀(Recursion)는 스스로를 부른다는 의미이다. - 프로그래밍 언어에서는 함수가 자기 자신을 호출한다는 의미가 될 것이다. 재귀는 재귀함수의 형태로 실제로 프로그래밍의 많은 부분을 차지하고있는데, JSON.parse, JSON.stringify, DOM 순회 등에서 사용이 되며 본인도 재귀함수로 배열 고차함수인 reduce, map, filter, find를 만들어 본 적이 있다. 사용해본 바, 재귀함수는 기능을 작성할 때 편리하고 가독성이 좋아질 수 있는 장점이 있다. 다만 크나 큰 단점도 존재하며, 그 단점은 마지막에 후술한다. 스택 자료구조(콜 스택) 함수가..
슬라이딩 윈도우 슬라이딩 윈도우 패턴은 배열을 탐색하는 윈도우(Window, 창)을 만들어 배열 내를 순환하는 패턴이다. 윈도우는 필요한 만큼의 칸 만큼씩 전진하며 필요한 값을 찾을때까지 동작하게 된다. 이 방법은 배열이나 문자열을 순환하며 부분집합(subset)을 찾아낼 때 아주 유용한 문제 해결 방법이다. 문제를 풀면서 확인해보자. /* Write a function called maxSubarraySum which accepts an array of integers and a number called n. The function should calculated the maximum sum of n consecutive elements in the array */ /* 해설: 정수로 구성된 어레이와 ..
어레이 내 정렬된 엘리먼트와 관련된 문제를 해결할 때 멀티플 포인터 패턴이 해답을 줄 수 있다. 이게 무슨말인가? 글로써 보면 조금 어렵다. 문제 예시를 보자. /* Write a function called sumZero which accepts a sorted array of integers. The function should find the first pair where the sum is 0. Return an array that includes both values that sum to zero or undefined if a pair does not exist */ /* 해설: 정렬된 정수값을 가진 어레이를 인수로 받는 sumZero라는 함수를 작성해라. 함수는 어레이 내 정수의 합계가 0인..
