브루트 포스 방식을 이용한 알고리즘.
Problem
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
정수 배열들이 주어지고, 더해져서 특정 타겟에 해당하는 정수로 만드는 두개의 숫자 인덱스들을 반환한다.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
각각의 입력이 정확히 하나의 해를 가질 수 있다고 가정한다. 같은 요소를 두 번 사용할 수 없다.
Example
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].JSDoc
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/전략
배열내의 숫자가 이미 주어져 있으므로, brute force를 사용해 볼 수 있다. N을 nums의 크기라고 하고, i 와 j 를 통해 nums[i]와 nums[j]의 요소를 하나하나씩 더해보면서 target 과 값이 일치하는지 알아낸다.
다만, 덧셈연산의 경우 교환법칙이 성립하므로, nums[i] + nums[j] 와 nums[j] + nums[i] 는 동일하다. 따라서, j는 항상 i보다 크거나 같게 만들어주면, 불필요한 연산과정이 생략될 수 있다.
구현
var twoSum = function(nums, target) {
for(let i = 0; i < nums.length; i++) {
for(
let j = (i == nums.length-1) ? 0 : i+1 ;
j < nums.length;
j++
) {
if(nums[i] + nums[j] == target)
return [i,j];
}
}
};최악의 경우 시간복잡도
비교연산을 기준으로 시간복잡도를 생각해 볼 수 있다. 결과가 nums[N-2] + nums[N-1] 인경우에는 다음과 같다.
최선의 경우 시간 복잡도
결과가 nums[0] + nums[1] 인경우에는 O(1)의 시간 복잡도를 가진다.
공간복잡도
반복(Iteration)을 사용하였기 때문에 다른 함수 stack을 사용하지 않는다.
다른 배열에 복사하는 과정이 없으며, 오직 i와 j지역변수를 사용하기 때문에 O(1)의 복잡도이다.
반환하는 과정에서 배열로 반환해야 하므로, 추가적인 공간의 사용이 필요하지만, 결국 O(1) + O(1) = O(1) 이므로, 상관이 없다.
결과와 보충
LeetCode 시스템 상, 120ms의 런타임이 나왔다.
48ms의 실행속도를 가진 굇수(!)도 있어서 한번 그 코드를 보았다.
var twoSum = function(nums, target) {
let numsObj = {};
for (let i = 0; i < nums.length; i++) {
let current = nums[i];
let match = target - current;
if (match in numsObj) {
return [i, numsObj[match]];
} else {
numsObj[current] = i;
}
}
};원리는 target 값에 nums[i]의 값을 뺀 match값을 numsObj에 저장한다. 각각의 요소의 match 를 구한다음, 특정요소가 numsObj 내의 match 값을 만족한다면, 해당 인덱스 배열을 반환한다.
만일 nums가 [1,2,3,4]이고 target이 7일때, 메모리 구조도를 보게 되면…
정말 경이롭다….
이와 같은 경우 numsObj 객체를 사용한 Memoization을 사용하였다. ES6의 key-value 접근을 사용하여 효율적이다. 객체내 탐색 복잡도를 O(1)이라고 한다면, 최악의 경우의 시간복잡도는 O(n)에 불과하다.
한번의 반복구문 내에, 대입 연산 O(1), 객체 key 탐색 연산 O(1) 이 일어난다. 반복은 총 N회 일어나므로…. N×(O(1)+O(1)) 이고, 따라서 O(n)의 시간 복잡도가 발생한다. 내가 사용한 방식은 O(n²)이였으므로, 매우 효율적이다.
다만 공간복잡도의 경우에는 또하나의 객체를 만들기 때문에 O(n)이다.
결론
객체를 사용하는 방법에 대해서 더 공부를 해보아야 할것 같다… 1번 문제만 풀었는데도 불구하고, 다른 사람의 코드를 보니 공부할 점이 많은 것은 사실이다…
JS의 도사가 되기 위한 길이 멀고도 험하다.
2018.7.5.
