Skip to main content

07. 정렬과 그리디, 결정알고리즘(이분검색)

정렬​

버블 정렬 (Bubble Sort)​

선택정렬과 비슷한 정렬로써 2중 for문을 돌면서 바로 다음 값과 비교해 가장 큰 값을 끝으로 밀어내면서 진핸되는 방식이다.

Bubble Sort.gif

시간 및 공간 복잡도​

  • 시간복잡도 - O(n^2)
  • 공간복잡도 - O(1)

선택 정렬 (Seletion Sort)​

버블정렬과 비슷한 정렬로써 2중 for문을 돌면서 가장 큰 값을 기억해 마지막 값과 위치를 바꾸는 방식이다.

Seletion Sort.gif

시간 및 공간 복잡도​

  • 시간복잡도 - O(n^2)
  • 공간복잡도 - O(1)

삽입 정렬 (Insertion Sort)​

현재 위치보다 아래쪽으로 순회 하면서 자기 자신보다 작은 값을 만났을 때 그 뒤에 위치 시켜준다. 정렬이 되어 있는 경우에는 한번만 순회하며 체크해도 되기 때문에 그 때는 시간복잡도가 O(n)으로 떨어진다.

Insertion Sort.gif

시간 및 공간 복잡도​

  • 정렬 된 배열 → 시간복잡도 - O(n^2)
  • 정렬 안 된 배열 → 시간복잡도 - O(n^2)
  • 공간복잡도 - O(1)

그리디​

  • 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
  • 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다.
  • 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

결정 알고리즘(이분 검색)​

  • 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
  • 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
  • 변수 3개(start, mid, end)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.

문제 풀이​

Ch.07 - 01. 선택정렬​

function solution(arr: Array<number>): Array<number> {
  for (let i: number = 0; i < arr.length; i++) {
    let minNumIdx = i;

    for (let j: number = i + 1; j < arr.length; j++)
      if (arr[j] < arr[minNumIdx]) minNumIdx = j;

    [arr[i], arr[minNumIdx]] = [arr[minNumIdx], arr[i]];
  }

  return arr;
}

Ch.07 - 02. 버블정렬​

function solution(arr: Array<number>): Array<number> {
  for (let i: number = 0; i < arr.length - 1; i++) {
    for (let j: number = 0; j < arr.length - i - 1; j++) {
      if (arr[j + 1] < arr[j]) [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
    }
  }
  return arr;
}

Ch.07 - 03. Special Sort(버블정렬응용)​

function solution(arr: Array<number>): Array<number> {
  let cacheIdx: number = 0;
  for (let i: number = 0; i < arr.length - 1 - cacheIdx; i++) {
    for (let j: number = 0 + cacheIdx; j < arr.length - 1; j++) {
      if (0 < arr[j]) [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      else cacheIdx++;
    }
  }
  return arr;
}

Ch.07 - 04. 삽입정렬​

function solution(arr: Array<number>): Array<number> {
  for (let i = 0; i < arr.length; i++) {
    let tempNum: number = arr[i];
    let j: number;

    for (j = i - 1; 0 <= j; j--) {
      if (tempNum < arr[j]) arr[j + 1] = arr[j];
      else break;
    }

    arr[j + 1] = tempNum;
  }

  return arr;
}

Ch.07 - 05. LRU(카카오 캐시 변형 : 삽입정렬응용)​

// Ver.1 → 삽입 정렬
function solution(arr: Array<number>): Array<number> {
  const cacheQueue: Array<number> = Array.from({ length: 5 }, () => 0);
  const n = cacheQueue.length;

  arr.forEach((data) => {
    let saved: boolean = false;

    for (let i = 0; i < n; i++) {
      if (data === cacheQueue[i]) {
        for (let j = i; 0 <= j; j--) {
          cacheQueue[j] = cacheQueue[j - 1];
        }
        saved = true;
      }
    }

    if (!saved) {
      for (let k = n - 1; 0 <= k; k--) {
        cacheQueue[k] = cacheQueue[k - 1];
      }
    }

    cacheQueue[0] = data;
  });

  return cacheQueue;
}

//  Ver.2 → 내장 함수
function solution(arr: Array<number>): Array<number> {
  const cacheQueue: Array<number> = Array.from({ length: 5 }, () => 0);
  const n = cacheQueue.length;

  arr.forEach((data) => {
    for (let i = 0; i < n; i++) {
      if (data === cacheQueue[i]) cacheQueue.splice(i, 1);
    }

    if (cacheQueue.length === n) cacheQueue.pop();

    cacheQueue.unshift(data);
  });

  return cacheQueue;
}

Ch.07 - 06. 장난꾸러기 현수 (정렬)​

function solution(statureList: Array<number>): Array<number> {
  const answer: Array<number> = [];

  const sortedStatureList: Array<number> = [...statureList].sort(
    (a, b) => a - b
  );

  sortedStatureList.forEach((data, idx) => {
    if (data !== statureList[idx]) answer.push(idx + 1);
  });

  return answer;
}

Ch.07 - 07. 좌표 정렬 (정렬)​

function solution(arr: Array<Array<number>>): Array<Array<number>> {
  arr.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  return arr;
}

Ch.07 - 08. 회의실 배정 (그리디)​

function solution(meetingList: Array<Array<number>>): number {
  let answer: number = 0;

  meetingList.sort((a, b) => a[1] - b[1] || a[0] - b[0]);

  let endTime: number = 0;
  for (const meeting of meetingList) {
    if (endTime <= meeting[0]) {
      answer++;
      endTime = meeting[1];
    }
  }

  return answer;
}

Ch.07 - 09. 결혼식 (그리디)​

function solution(guestList: Array<Array<number>>): number {
  let answer: number = 0;

  const timeTable = [];
  for (const [arrive, departe] of guestList) {
    timeTable.push([arrive, "a"]);
    timeTable.push([departe, "d"]);
  }
  timeTable.sort(
    (a, b) => a[0] - b[0] || b[1].charCodeAt() - a[1].charCodeAt()
  );

  let cnt = 0;
  timeTable.forEach(([_, action]) => {
    if (action === "a") cnt++;
    else cnt--;

    answer = Math.max(answer, cnt);
  });

  return answer;
}

Ch.07 - 10. 이분검색​

function solution(inputNum: number, arr: Array<number>): number {
  let answer = 0;

  arr.sort((a, b) => a - b);

  let lt: number = 0;
  let rt: number = arr.length - 1;
  while (lt <= rt) {
    let mid: number = Math.floor((lt + rt) / 2);

    if (arr[mid] === inputNum) {
      answer = mid + 1;
      break;
    } else if (arr[mid] > inputNum) rt = mid - 1;
    else if (arr[mid] < inputNum) lt = mid + 1;
  }

  return answer;
}

Ch.07 - 11. 뮤직비디오(결정알고리즘)​

function solution(m: number, songList: Array<number>): number {
  let answer = 0;

  let lt = Math.max(...songList);
  let rt = songList.reduce((acc, cur) => acc + cur, 0);

  while (lt <= rt) {
    const mid = Math.floor((lt + rt) / 2);

    let count = 1;
    let sumPlayTime = 0;
    for (const song of songList) {
      const tempPlayTim = sumPlayTime + song;

      if (mid < tempPlayTim) {
        count++;
        sumPlayTime = song;
      } else sumPlayTime = tempPlayTim;
    }

    if (count <= m) {
      answer = mid;
      rt = mid - 1;
    } else lt = mid + 1;
  }

  return answer;
}

Ch.07 - 12. 마구간 정하기(결정알고리즘)​

function solution(m: number, stalls: Array<number>): number {
  let answer: number = 0;

  stalls.sort((a, b) => a - b);

  let lt: number = 1;
  let rt: number = stalls.at(-1) - stalls.at(0);
  while (lt <= rt) {
    const mid: number = Math.floor((lt + rt) / 2);

    let count: number = 1;
    let tmp = stalls[0];
    for (let i = 1; i < stalls.length - 1; i++) {
      let distance = stalls[i] - tmp;
      if (mid <= distance) {
        count++;
        tmp = stalls[i];
      }
    }
    if (m === count) {
      answer = mid;
      lt = mid + 1;
    } else rt = mid - 1;
  }

  return answer;
}

참고​