javascript error

자료구조와 알고리즘1 (Data Structure & Algorithm)

Posted by Seongkyun Yu on 2020-03-12
Estimated Reading Time 4 Minutes
Words 753 In Total
Viewed Times

연습문제

1. 선형 검색

선형 검색을 통해 주어진 배열(array)에 주어진 값(target)이 요소로 존재하는지 확인하여 존재하는 경우 해당 인덱스를 반환하고 존재하지 않는 경우 -1을 반환하는 함수를 구현하라. 단, 어떠한 빌트인 함수도 사용하지 않고 for 문을 사용하여 구현하여야 한다.

linearSearch.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i;
    }
  }
  return -1;
}

console.log(linearSearch([1, 2, 3, 4, 5, 6], 1)); // 0
console.log(linearSearch([1, 2, 3, 4, 5, 6], 3)); // 2
console.log(linearSearch([1, 2, 3, 4, 5, 6], 5)); // 4
console.log(linearSearch([1, 2, 3, 4, 5, 6], 6)); // 5
console.log(linearSearch([1, 2, 3, 4, 5, 6], -1)); // -1
console.log(linearSearch([1, 2, 3, 4, 5, 6], 0)); // -1
console.log(linearSearch([1, 2, 3, 4, 5, 6], 7)); // -1

2. 이진 검색

이진 검색을 통해 주어진 배열(array)에 주어진 값(target)이 요소로 존재하는지 확인하여 존재하는 경우 해당 인덱스를 반환하고 존재하지 않는 경우 -1을 반환하는 함수를 구현하라. 단, 아래의 빌트인 함수 이외에는 어떤 빌트인 함수도 사용하지 않아야 하며, while 문을 사용하여 구현하여야 한다.

1차

binarySearch.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function binarySearch(array, target) {
  let midIndex = Math.floor(array.length / 2);
  let maxIndex = array.length - 1;
  let minIndex = 0;

  while (maxIndex !== midIndex) {
    if (array[midIndex] > target) {
      maxIndex = --midIndex;
    } else if (array[midIndex] < target) {
      minIndex = ++midIndex;
    } else {
      return midIndex;
    }
    midIndex = Math.floor((maxIndex + minIndex) / 2);
  }

  return array[midIndex] === target ? midIndex : -1;
}

console.log(binarySearch([1, 2, 3, 4, 5, 6], 1)); // 0
console.log(binarySearch([1, 2, 3, 4, 5, 6], 3)); // 2
console.log(binarySearch([1, 2, 3, 4, 5, 6], 5)); // 4
console.log(binarySearch([1, 2, 3, 4, 5, 6], 6)); // 5
console.log(binarySearch([1, 2, 3, 4, 5, 6], -1)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6], 0)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6], 7)); // -1

문제점:

  • while문이 끝나도 찾는 값이 마지막에 있거나 없는 경우를 한번 더 가려야함
  • 변수 이름이 전부 m으로 시작해서 가독성이 떨어짐
  • while문 첫줄에 Math.floor를 쓰면 while문 안에만 Math.floor 사용 가능

2차

binarySearch.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function binarySearch(array, target) {
  let startIndex = 0;
  let endIndex = array.length - 1;
  let midIndex;

  while (startIndex <= endIndex) {
    midIndex = Math.floor((startIndex + endIndex) / 2);
    if (array[midIndex] < target) {
      startIndex = ++midIndex;
    } else if (array[midIndex] > target) {
      endIndex = --midIndex;
    } else {
      return midIndex;
    }
  }
  return -1;
}
console.log(binarySearch([1, 2, 3, 4, 5, 6], 1)); // 0
console.log(binarySearch([1, 2, 3, 4, 5, 6], 3)); // 2
console.log(binarySearch([1, 2, 3, 4, 5, 6], 5)); // 4
console.log(binarySearch([1, 2, 3, 4, 5, 6], 6)); // 5
console.log(binarySearch([1, 2, 3, 4, 5, 6], -1)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6], 0)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6], 7)); // -1

개선점:

  • while문의 조건식 개선
  • 변수 이름 변경
  • Math.floor 중복 사용 개선



3. 버블 정렬

버블 정렬을 통해 주어진 배열(array)을 정렬하는 함수를 구현하라. 단, 어떠한 빌트인 함수도 사용하지 않고 for 문을 사용하여 구현하여야 한다.

1차

bubbleSort.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function bubbleSort(array) {
  let replace;
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - 1; j++) {
      if (array[j] > array[j + 1]) {
        replace = array[j];
        array[j] = array[j + 1];
        array[j + 1] = replace;
      }
    }
  }
  return array;
}

console.log(bubbleSort([2, 4, 5, 1, 3])); // [1, 2, 3, 4, 5]
console.log(bubbleSort([5, 2, 1, 3, 4, 6])); // [1, 2, 3, 4, 5, 6]
console.log(bubbleSort([3, 1, 0, -1, 4, 2])); // [-1, 0, 1, 2, 3, 4]

문제점:

  • while문을 한번 돌 때마다 배열의 최대값 순으로 오른쪽 정렬이 되어가는데 루프문을 쓸 데 없이 많이 돈다.

2차

bubbleSort.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function bubbleSort(array) {
  let replace;
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        replace = array[j];
        array[j] = array[j + 1];
        array[j + 1] = replace;
      }
    }
  }
  return array;
}

console.log(bubbleSort([2, 4, 5, 1, 3])); // [1, 2, 3, 4, 5]
console.log(bubbleSort([5, 2, 1, 3, 4, 6])); // [1, 2, 3, 4, 5, 6]
console.log(bubbleSort([3, 1, 0, 11, 4, 2, 9, -1])); // [-1, 0, 1, 2, 3, 4]

개선점:

  • 루프 반복마다 최대값 순으로 하나씩 정렬이 완성되므로 -i를 추가하여 루프 회수를 줄임

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

FEATURED TAGS
javascript error
FRIENDS
ESC