Algorithms
현재 위코드 사전 스터디를 진행 중에 있습니다. 저를 포함한 여섯 명이 각자의 스토리를 지니고 있어서 요즘 그 이야기를 듣는 맛에 매주 스터디를 기다리고 있답니다.
이렇게 모든 분들이 열정적으로 공부하고 코딩을 하는 모습을 보면, 자동적으로 동기부여가 되고 있습니다. 이러한 일환으로 Udemy라는 강의를 통해 현재 알고리즘을 공부하고 있고, 단일 연결 리스트 강의를 듣고 있습니다만 아직 저의 코딩 실력이 이를 이해하기엔 다소 부족하다는 결론을 내리게 되었습니다.
그리고 스터디 중에도 관련하여 다른 분들에게 여쭤봤고 어려운 자료 구조에 대해 물론 알면 좋지만, 대기업을 목적으로 하는 경우가 아니라면 천천히 진행해도 된다고 하셨기에 현재 시점에서 '포기'가 아닌 '유보'를 진행하려 합니다.
그래서 내린 결론은 검색과 정렬까지 배운 현재의 실력으로 다시 한번 Leetcode의 알고리즘을 풀이하려고 생각합니다. Big O Notation에 대한 개념도 어느 정도 잡혔기 때문에, 새롭게 알고리즘을 풀이를 진행해보면 저의 실력 점검을 다시금 할 수 있는 기회가 될 것 같습니다.
하루 하나씩 풀이하는 것은 어려울 수도 있지만, 이번에는 시간 복잡도를 고려하여 코드를 짜보고 풀이를 하는 방식으로 진행하겠습니다.
그럼 시작해볼까요? 😎
출처
문제
한 눈에 보셔도 아시겠지만, 크게 어려운 알고리즘은 아닙니다. 인수로 배열과 타겟 숫자가 주어집니다. 배열 중 두 값의 합이 타겟 숫자와 일치하면, 배열의 인덱스 넘버를 반환하는 알고리즘입니다.
가장 쉬운 풀이는 아시다시피 시간 복잡도가 O(n²)인 중첩 루프로 가능합니다. 하지만, 문제의 가장 아래에 적혀진 Follow-up: 시간 복잡도가 O(n²)보다 낮은 알고리즘을 생각해볼 수 있겠니?에서 저의 도전 의식을 불러일으켰고, 이를 생각해보려 애썼습니다. 그리고 아래와 같은 코드를 짜보았습니다.
풀이 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | /** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { let i = 0; let j = nums.length - 1; while (nums[i] + nums[j] !== target) { if (i < j - 1) { j--; } else { i++; j = nums.length - 1; } } return new Array(i, j) }; | cs |
두 배열의 값의 합이 target 숫자와 일치하면 반복문을 벗어날 수 있도록 while문으로 작성하였습니다.
그리고 각각 변수 i와 j를 0, nums.length - 1으로 지정하고, i와 j 값이 각각의 조건문에 맞게 변화되도록 풀이를 작성하였습니다.
if (i < j - 1) {
j--;
} else {
i++;
j = nums.length - 1;
}위 코드는 아래처럼 진행되도록 만든 코드입니다. 이를 통해, 시간 복잡도가 O(n²)보다 낮은 알고리즘을 작성할 수 있었습니다. 물론, 아직 부족한 코드지만 이전보다 실력이 다소 향상했다는 생각을 하게 된 문제였습니다.
혹시 다른 좋은 풀이 방법도 있으시다면 자유롭게 남겨주시기 바랍니다! 😁
[0, 3] ➡️ [0, 2] ➡️ [0, 1] ➡️ [1, 3] ➡️ [1, 2] ➡️ [2, 3]
실행 결과
