728x90

10주 1일차 - 휴가 사용(알고리즘 보충학습)

1. 배운 것

해시 테이블 - 별도 문서로 정리. https://github.com/ryan-kim-dev/data-structures-and-algorithms/blob/master/dataStructures/hash.md
버블 정렬
백준 1920번
프로그래머스 완주하지 못한 선수

2. 내용 정리

데일리 코딩 3번 - 버블 정렬

// 외부 for문: 배열 전체 순회
// 내부 for문: 요소 2개끼리 비교 & 정렬 완료된 뒷부분 반복에서 제외시키기 위해 -1 -i
// noSwap: 정렬이 일어나지 않으면 break시켜 불필요한 연산 스킵

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

BOJ 1920번 이분 탐색 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs')
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\\n');

// N개의 숫자를 가진 A 배열에서 M개의 숫자를 가진 B 배열의 요소가 있으면 1, 없으면 0 리턴
const N = Number(input[0]);
const M = Number(input[2]);
let A = input[1].split(' ').map(el => +el);
A = A.sort((a, b) => a - b);
let B = input[3].split(' ').map(el => +el);

function binerySearch(arr, target) {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (arr[mid] === target) return 1;
    if (arr[mid] > target) {
      end = mid - 1;
    }
    if (arr[mid] < target) {
      start = mid + 1;
    }
  }
  return 0; // 찾는 요소가 없으면 0 리턴.
}

const result = B.map(el => binerySearch(A, el));
console.log(result.join('\\n'));

겨우 겨우 풀긴 풀었는데 너무 어렵다.. 공부 진짜 많이 해야되겠다.
좋은 레퍼런스 코드 → https://gurtn.tistory.com/93

프로그래머스 - 완주하지 못한 선수

continue는 반복문의 다음 회차로 넘어가고, break는 반복문을 완전히 종료시킨다.
참가자와 완주자들은 배열의 길이가 1 차이나는 걸 제외한다면 요소들의 이름 자체는 같기 때문에 둘 다 sort 해서 같은 인덱스끼리 비교하면 없는 사람을 찾을 수 있음.
참조 타입 데이터의 원본 값을 건드리지 않는 코드 작성 습관을 들여야 한다.
sort 내장 메서드 대신 merge sort를 사용하여 정렬하는 게 훨씬 더 효율적이나 아직 안배워서 일단 스킵..!

function solution(participant, completion) {
   
    // 참가자와 완주자를 동일 인덱스로 비교하기 위해 sort.
    let sortedParticipants = [...participant].sort();
    let sortedCompletion = [...completion].sort();
    for (let i = 0; i < participant.length; i++) {
        if (sortedParticipants[i] === sortedCompletion[i]) continue;
        if (sortedParticipants[i] !== sortedCompletion[i]) {
            return sortedParticipants[i];
        }
    }
}

참고 자료

3. 리뷰

3.1 좋았던 점

모자란 공부를 일부 보충할 수 있었다.

3.2 아쉬웠던 점

난관을 만날 때마다 너무 오래 손 떼고 시간이 낭비된다.

3.3 notes

욕심을 버리고 싶어도 팀프로젝트 걱정에 조바심이 절로 나는데 어찌 할지 고민..
조금 어이없는 이유인데 결국 못해서 온 슬럼프는 그만큼 배운걸 체화하는 시간이 없었기 때문에 그렇다고 느꼈다.
그래서 스터디도 하나 내려놓았고 이제 mern과 알고리즘에만 집중하기로 했고, 잘하는 분들에 비하면 당연히 내 기본기가 부족했기 때문에, 그나마 나름의 최선으로 해와서 지금 정도로 온 것에 만족하고 한순간에 확 바뀌길 헛된 기대 말고 꾸준히만 하자:)