2023-09-18 알고리즘 공부 정리

이 게시글은 데일리 알고리즘 공부 후 강의 내용을 정리한 글 입니다.
저작권 때문에 문제 내용은 올리지 못하는 점 양해바랍니다.

1.1,2 차 탐색 알고리즘 문제입니다.
인덱스에서 순서대로 탐색 하면서 높은 숫자가 이전 높은 숫자보다 높을때마다 값이 증가하는 알고리즘 입니다.

function solution(arr) {
  let answer = 1;
  let max = arr[0];

  for (let i = 1; i < arr.length; i++) {
    if (max < arr[i]) {
      max = arr[i];
      answer++;
    }
  }
  return answer;
}
let arr = [130, 135, 148, 140, 145, 150, 150, 153];
console.log(solution(arr 

풀이: 이중 for 문을 사용해서 i 까지 돌때 148 을 돌때 그 앞에 있는 인덱스들을 다 탐색해서 i 가 j 보다 작으면 카운팅 하지 않게끔 풀 수 있지만 이중 for문을 사용하게 되면 시간 복잡도가 n 제곱이 된다 . 그래서 Olog(n) 이 될수있게 1차 탐색만 하는 식으로 작성해봤습니다.
먼저 저는 max 라는 변수를 만들어 처음에 arr[0] 인덱스의 값을 할당 시켰습니다. 그리고 for문을 통해서 max 가 arr[i] 보다 클때만 answer 을 카운팅 시켜주고 max를 arr[i] 값으로 재 할당 시켜주는 방식으로 풀었습니다. for문에 let i=1 인 이유는 answer 을 처음에 arr[0] 째를 카운팅 시켜줬기 때문에 0을 탐색할 필요가 없기 때문입니다.

2.가위 바위 보 알고리즘 입니다.

function solution(a, b) {
  let answer = [];
  for (let i = 0; i < a.length; i++) {
    if (a[i] === 1 && b[i] === 3) {
      answer.push('A');
    } else if (a[i] === 2 && b[i] === 1) {
      answer.push('A');
    } else if (a[i] === 3 && b[i] === 2) {
      answer.push('A');
    } else if (a[i] === b[i]) {
      answer.push('D');
    } else {
      answer.push('B');
    }
  }

  return answer;
}
let A = [2, 3, 3, 1, 3];
let B = [1, 1, 2, 2, 3];
console.log(solution(A, B));

풀이: 해당 알고리즘은 a가 이겼을때 조건이 어떻게 되는지를 먼저 파악 하고 난 후 a가 이기는 조건이였을때만 answer 에 'A'를 push 시켜줬습니다. 그리고 특수한 조건 (서로 비겼을때)일 때에는 'D'를 push 시켜주고 나머지 지는 경우에는 'B'를 push 시켜줌에 따라 가위,바위,보에 관한 알고리즘을 작성했습니다.

3.점수 계산 알고리즘

function solution(a) {
  let answer = 0;
  let max = 0;

  for (let x of a) {
    if (x === 1) {
      max = max + x;
      answer = answer + max;
    } else {
      max = 0;
      answer = answer + max;
    }
  }
  return answer;
}
console.log(solution([1, 0, 1, 1, 1, 0, 0, 1, 1, 0]));

풀이: 연속적으로 답을 맞으면 1점,2점,3점 ,N점 이 되고 도중에 한문제라도 틀리게 되면 다시 0점부터 1점씩 올라가는 알고리즘 입니다.
먼저 max라는 변수를 선언하여 카운팅 초기값인 0으로 할당 시켜 주고,
for of 문을 이용해 x=== 1 (답을 맞췄을때)일 때에는 max 값에다가 max +x를 해주어 1씩 지속적으로 더하게끔 하고 answer에다가 +max 를 더해줬습니다. x=== 1 이 아닐때 (답을 틀렸을때 ) 에는 max를 다시 0으로 초기화 시켜주고 answer 값에 초기화된 max값을 더해주었습니다.
이렇게 되면 1씩 증가하다가 틀리면 값을 0으로 초기화 시키고 다시 카운팅 하는 알고리즘이 작성 됩니다.