Hash

• 해시함수로부터 얻어지는 값을 해시라 한다.
• 해시함수에서 임의의 고정된 value를 가진 데이터에 Key를 부여하고 value를 저장한다.
• 기본 연산으로 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다. - 시간복잡도: O(1)을 가진다.
• 빠른 데이터 검색에 널리 사용된다.

예제로 알아보기

문제 - Two Sum

문제 출처 - LeetCode - Two Sum
임의의 정수들을 가진 배열과 타겟값이 주어진다.
배열안의 두 정수의 합이 타겟이 되는 값을 호출하라.

Ex)
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

풀이 1

var twoSum = function (nums, target) {
  const answer = [];

  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        answer.push(i);
        answer.push(j);
      }
    }
  }

  return answer;
};

처음에는 해시가 아닌 배열과 반복문으로 단순하게 풀었다.

문제는 해결되지만, 많은 시간을 소요하고 있다.
2중 for문의 경우 모든 경우의 수를 검토하기에 O(n^2)의 시간복잡도가 필요하다.

풀이 2

var twoSum = function (nums, target) {
    let map = {}; // key, value를 위한 객체
    for (let i = 0; i < nums.length; i++) {
      let n = nums[i]; 
  
      if (map[target - n] !== undefined) { 
        return [map[target - n], i];
      } else {
        map[n] = i; // key(nums[i])에 value i 부여
        // map = { key:2 value:0 , key:7 value:1 ... , key:15 value:3}
      }
    }
  };

객체의 key와 value를 이용하여 풀면 시간을 많이 단축 할 수 있다.
nums를 한번만 탐색하여 해결 (시간복잡도 O(n))

문제 - Linked List Cycle

문제 출처 - LeetCode - Linked List Cycle
링크드 리스트의 헤드들이 주어진다.
링크드 리스트에 사이클이 존재하는지 확인하라.

Ex)

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

풀이 1

var hasCycle = function (head) {
  const set = new Set();

  function checkNodes(node) { // 각 노드 탐색
    if (set.has(node)) return true; // 존재하는 노드를 만나면 true
    if (!node) return false; // 존재하는 노드를 만나지 않으면 false
    set.add(node); 
    return checkNodes(node.next);
  }
  return checkNodes(head); // 재귀함수 
};

전체 헤드(노드)를 한 번 탐색하여 해시 데이블을 만든 후,
다시 해당 헤드를 만난다면 사이클이 존재함을 이용한다.

풀이 2

해시가 아닌 두개의 포인터로 사이클을 확인하는 좋은 솔루션이 있기에 함께 공부하자.
slow & fast pointers

var hasCycle = function (head) {
  let fast = head; // 빠른 포인트

  while (fast && fast.next) { 
  // check the fast and fast.next both are not undefined ot null
    
    head = head.next; // 기존 헤드는 하나씩
    fast = fast.next.next; // 빠른 헤드는 두개씩
    if (fast === head) return true; // 만나면 true
  }
  return false; // 만나지 않고 루프가 끝나면 false
};

요점

사이클 트랙에서 친구와 내가 달린다고 가정하자.
친구는 나보다 2배 빠르게 달린다. (군대 오래달리기를 떠올리자 🤮)
트랙은 사이클이기에 계속 달리다 보면 친구는 나를 따라잡게(?) 된다.

위와 같은 맥락으로 링크드 리스트에 두개의 포인트를 만들어서
하나의 포인트는 한 단계씩, 다른 포인트는 두 단계식 이동한다고 가정한다면,
사이클이 존재하면 만나게 되고, 존재하지 않는다면 만나지 않는다.