2023.03.29 [검색 알고리즘, 버블 정렬]

📖오늘 배운  것

검색 알고리즘

선형 검색

데이터를 담은 배열이 있고 사용자가 해당 배열에 해당하는 값을 입력했는지 확인할 때 맨 앞부터 순서대로 맞는 데이터인지 확인하는 것이 선형검색이다.

⇒첫 부분에서 시작해서 끝부분으로 이동하면서 한 번에 하나씩 항목을 확인하는 것(혹은 역순으로)

 

선형 검색을 사용하는 자바스크립트 내장함수

• indexOf
• includes
• find
• findIndex

선형검색은 배열의 길이가 길어질 수록 더 많은 검색을 실시해야되기 때문에 최악의 경우 O(n) 의 시간복잡도를 가지게 된다.

⇒ best는 O(1), 평균은 O(n), 최악은 O(n)이다.

❗선형 검색은 데이터가 정렬되어 있지 않을 때 적절한 방법이다.

 

이진검색

데이터가 정렬되어 있는 상태에서 절반씩 버리면서 확인하는 방법

⇒ 중간점을 기준으로 중간점의 앞에 위치하는지, 뒤에 존재하는지 확인하는 과정을 반복

이진겁색의 시간복잡도

최악의 경우, 평균 : O(log n)

베스트: O(1)

❗이진 검색은 데이터가 정렬되어 있을 때 적절한 방법이다.

 

나이브 문자열

긴문자열에서 짦은 문자열을 찾을 때 하나씩 대조해보면서 찾는 방법

function naiveSearch(long, short) {
  let count = 0;
  
  for(let i = 0; i<long.length; i++) {
    for(let j = 0; j<short.length; j++){
      if(short[j] !== long[i+j]) break;
      if(j === short.length - 1) count++;
    }
  }
  
  return count;
}

naiveSearch("lorie loled", "lo")

 

정렬 알고리즘이란?

: 컬렉션의 항목을 재베열하는 과정

 

왜 배워야 하는가?

• 프로그래밍에서 흔하게 사용하기 때문이다.
  • 자바스크립트에서 내장된 정렬 메소드 등을 이해할 필요가 있다.
• 거의 정렬된 데이터 목록에서 정렬되지 않은 데이터를 정렬하고자 할 때 어떤 정렬 알고리즘을 사용하느냐에 따라 속도차이가 나기 때문이다.

버블 정렬

배열을 오름차순으로 정렬 한다면 더 큰 숫자가 하나씩 뒤로 이동하는 것.

 

버블 정렬의 최적화를 위해서 우리가 확인해야 할 것은

루프가 마지막으로 실행됐을 때 교환을 했는가?

이다. 만약 교환을 하지 않았다면 이미 정렬이 종료된 상태이기 때문에 종료하면 된다.

function bubbleSort(arr) {
let noSwaps;
  for(let i = arr.length; i> 0; i--) {
		noSwaps = true;
    for(let j = 0; j< i-1; j++){
      if (arr[j] > arr[j+1]) {
        let temp = arr[i];
        arr[i] = arr[j+1];
        arr[j+1] = temp;
				noSwaps = false;
      }
    }
		if(noSwaps) break;
  }
  return arr;
}

시간 복잡도

일반적으로 O(n2)이다. 하지만 데이터가 거의 정렬되었거나 이미 정렬이 끝난 상태에서 noSwaps 변수를 사용하는 경우 선형 시간O(n)에 더 가깝다.

 

 

💭배운 점

어렴풋이 알고 있던 검색 알고리즘과 버블 정렬에 대한 이론을 다시 습득할 수 있었다. 알고리즘 배워야하는 건 알겠는데 잘 모르겠어! 라는 생각을 가지고 있었는데 강의를 통해서 시각화된 알고리즘 속도 비교, 정렬 과정 자료를 보니까 알고리즘에 따라 방법도 천차만별이고 속도고 확실히 다르다 라는 것을 다시 깨달았다. 그리고 신기했던 것은 정렬 알고리즘에서 아예 정렬되지 않은 데이터에서 사용할 땐 느렸던 알고리즘이 대부분 정렬된 데이터에서 사용하면 오히려 제일 빠를 수 있다는 점이었다. 

알고리즘의 이론을 알고 사용할 수 있는 것뿐만 아니라 어느 상황에서 사용해야하는지도 잘 알아야겠다고 생각했다.

이제 진짜 알고리즘 내용 시작인데... 앞으로의 목표는 그냥 강의만 냅다 듣는 게 아니라 많이 연습해보고 다른 코테 문제도 같이 풀어보면서 적용해보고 하면서 실력을 쌓아가고 싶다!! 조급해하지 말자!!