[CodingTest]Algorithm 예제(Brute Force)

Algorithm 구현 Brute-Force

---

• 더 효율적인 알고리즘이 없을 때
• 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때

---

Brute Force Algorithm 사용처

---

순차 검색 알고리즘 (Sequential Search)

---

배열 특정 값이 검색할 시, 인덱스 0부터 차례대로 검색

function SequentialSearch2(arr, k) {
  // 검색 키 K를 사용하여 순차 검색을 구현
  // 입력: n개의 요소를 갖는 배열 arr와 검색 키 K
  // 출력: K값과 같은 요소 인덱스 또는 요소가 없을 때 -1
  let n = arr.length; // 배열 개수를 n에 할당
  arr[n] = k; // 검색 키 arr n인덱스에 할당(맨뒤)
  let i = 0; // while문 초기 값 지정
  while (arr[i] !== k) {
    // 배열의 값이 k와 같지 않다면 while문 들어감
    i = i + 1; // k와 같지않을 때 i를 +1
  }
  if (i < n) {
    // i가 k를 할당하기전의 배열개수보다 적다면(배열안에 k값이 있다면)
    return i; // i 반환
  } else {
    return -1; // -1 반환
  }
}

---

문자열 매칭 알고리즘 (Brute-Force String Matching)

---

길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색

function BruteForceStringMatch(arr, patternArr) {
  // 입력: n개의 문자 텍스트 배열 arr, m개의 문자 패턴 배열 patternArr
  // 출력: 일치하는 문자열이 있으면 첫번째 인덱스를, 검색에 실패한 경우 -1을 반환
  let n = arr.length;
  let m = patternArr.length;
  for (let i = 0; i <= n - m; i++) {
    // 전체 요소개수에서 패턴개수를 뺀 만큼만 반복. 그 수가 마지막 비교요소이기 때문
    // arr의 길이가 12, patternArr 4일 때, arr의 뒤에서 4번째의 텍스트가 patterArr의 첫번째 텍스트와 같지 않다면 더 할 필요가 없기 때문

    // i 반복문은 패턴과 비교의 위치를 잡는 반복문
    let j = 0;
    // j는 전체와 패턴의 요소 하나하나를 비교하는 반복문
    while (j < m && patternArr[j] === arr[i + j]) {
      // j가 패턴의 개수보다 커지면 안되기때문에 개수만큼만 반복
      // 패턴에서는 j인덱스와 전체에서는 i + j 인덱스의 값이 같은지 판단
      // 같을때 j에 +1 합니다.
      j = j + 1;
    }
    if (j === m) {
      // j와 패턴 수가 같다는 것은 패턴의 문자열과 완전히 같은 부분 존재
      // 이 때의 비교했던 위치 반환
      return i;
    }
  }
  return -1;
}

선택 정렬 알고리즘 (Selection Sort)

---

전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 또는 내림차순에 따라)를 교환하는 정렬 알고리즘

function SelectionSort(arr) {
  // 배열을 오름차순 정렬하는 함수
  // 입력: 정렬 가능한 요소의 배열 arr
  // 출력: 오름차순으로 정렬된 배열
  for (let i = 0; i < arr.length - 1; i++) {
    // 배열의 0번째 인덱스부터 마지막인덱스까지
    // 현재 값 위치에 가장 작은 값 넣기
    let min = i;
    // 현재 인덱스를 최소값의 인덱스를 나타내는 변수에 할당합니다.
    for (let j = i + 1; j < arr.length; j++) {
      // 현재 i에 +1을 j로 반복문을 초기화하고 i 이후의 배열요소과 비교하는 반복문
      if (arr[j] < arr[min]) {
        // j인덱스의 배열 값이 현재 인덱스의 배열 값보다 작다면
        min = j;
        // j 인덱스를 최소를 나타내는 인덱스로 할당
      }
    }
    // 반복문이 끝났을 때(모든 비교가 끝났을때)
    // min에는 최소값의 인덱스
    // i값과 최소값을 바꿔서 할당
    let temp = arr[i];
    arr[i] = arr[min];
    arr[min] = temp;
  }

  return arr;
}

그 밖의 알고리즘

• 버블 정렬 알고리즘 - Bubble Sort
• Tree 자료 구조의 완전탐색 알고리즘 - Exhausive Search (BFS, DFS)

• 동적 프로그래밍 - DP(Dynamic Programing)

• Brute Force vs Dynamic Programing
• Closet-Pair Problems by Brute Force
• Convex-Hull Problems by Brute Force