📝 오늘 한 것

1. 배열 / 집합 / 선형 검색 / 이진 검색

📖 학습 자료

1. 책 '누구나 자료 구조와 알고리즘'

📚 배운 것

1. 자료 구조가 중요한 까닭

자료 구조의 연산 : 읽기 / 검색 / 삽입 / 삭제

자료 구조의 시간 복잡도 : 주어진 연산에 걸리는 단계 수

1) 배열

• 읽기 : 항상 1단계

  컴퓨터는 배열의 첫 번째 인덱스의 메모리 주소를 알고 있기 때문이다

• 검색 : 최대(맨 뒤 검색) N단계

• 삽입

  최소(맨 뒤 삽입) 1단계
  최대(맨 앞 삽입) N + 1 단계

• 삭제 : 최대(맨 앞 삭제) N 단계

2) 집합

중복 값을 허용하지 않는 자료 구조
종류가 다양하지만, 예제로는 '배열 기반 집합'을 다룸

• 읽기, 검색, 삭제 : 배열과 동일한 단계를 거쳐야 한다

• 삽입

  최소(맨 뒤 삽입) N + 1 단계

  먼저, 기존 집합에 중복 값이 없는지 검색한다. (N단계)
  중복 값이 없으면, 맨 뒤에 넣고자 하는 값을 삽입한다. (1단계)

  최대(맨 앞 삽입) 2N + 1 단계

  먼저, 기존 집합에 중복 값이 없는지 검색한다. (N단계)
  중복 값이 없으면, 기존 값들을 오른쪽으로 한 칸씩 옮긴다. (N단계)
  맨 앞에 넣고자 하는 값을 삽입한다. (1단계)

💡 배열? 집합?

속도 면에서는 집합보다 배열이 효율적이다.
그러나, 중복 데이터가 없어야 할 때는 집합을 사용해야 한다.
애플리케이션의 요구사항을 먼저 분석한 후, 어떤 자료 구조가 더 적합한지 결정해야 한다.

2. 알고리즘이 중요한 까닭

알고리즘 : 특정 연산을 풀어나가는 절차

1) 정렬된 배열 선형 검색

p.46
Ruby로 구현된 코드 → JavaScript로 수정

function linearSearch (arr, value) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > value) {
      return null;
    } else if (arr[i] === value) {
      return value;
    }
  }
  return null;
}

const arr1 = [2, 4, 6, 8, 10];
console.log(linearSearch(arr1, 6)); // 6

2) 정렬된 배열 이진 검색

p.51
Ruby로 구현된 코드 → JavaScript로 수정
했는데 이렇게 하는 게 맞는 걸까

function binarySearch (arr, value) {
  // 상한선(처음 인덱스)과 하한선(마지막 인덱스)
  let lowerBound = 0;
  let upperBound = arr.length - 1;

  while(lowerBound <= upperBound) {
    // 중간 지점 인덱스
    const midpoint = (function searchMidpoint () {
      if ((lowerBound + upperBound) % 2 === 0) {
        return (lowerBound + upperBound) / 2;
      } else {
        return Math.floor((lowerBound + upperBound) / 2);
      }
    })();

    // 중간 지점 값
    const valueAtMidpoint = arr[midpoint];

    // 찾으려는 값과 중간 지점 값 비교
    if (value < valueAtMidpoint) {
      upperBound = midpoint - 1;
    } else if (value > valueAtMidpoint) {
      lowerBound = midpoint + 1;
    } else {
      return midpoint;
    }
  }

  // 찾으려는 값을 결국 배열에서 찾지 못하면 null 반환
  return null;
}

// 적용 예시
const arr1 = [1, 2, 3, 4, 5, 6, 7];
console.log(binarySearch(arr1, 6)); // 5

✨ 내일 할 것

1. 책 계속 읽기