꿀팁 저장소

피보나치 수 문제를 풀어보았다

팩토리얼과 마찬가지로

기본적인 재귀함수 구현에 대한 문제였다.

피보나치 수는

F0 = 0;

F1 = 1;

Fn = F(n-1) + F(n-2) 라는 공식이 있다.

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().split(" ");
const value = parseInt(input[0]);

function fibonacci(m, n, arr) {
  const a = arr[0];
  const b = arr[1];

  if (m > n) {
    console.log(b);
  } else {
    const newArr = [b, a + b];
    const _m = m + 1;
    fibonacci(_m, n, newArr);
  }
}

if (value === 0) {
  console.log(0);
} else if (value === 1) {
  console.log(1);
} else {
  fibonacci(2, value, [0, 1]);
}

재귀의 가장 기본이라고 할수있는

팩토리얼 문제를 풀어보았다.

팩토리얼이란

주어진 수 까지의 차례곱을 의미한다.

예) 5! = 1 * 2 * 3 * 4 * 5 = 120

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().split(" ");
const value = parseInt(input[0]);

function factorial(n, sum) {
  if (n === 0) {
    console.log(sum);
  } else {
    const multi = sum * n;
    const m = n - 1;
    factorial(m, multi);
  }
}

factorial(value, 1);

https://github.com/jaekwangLee/algorithm

객체지향 공부에 이어

자료구조에 대해 간단히 짚어보았다.

공부했던 객체지향 개념을 적용해서

직접 스택을 구현해본 결과

interface Stack {
  readonly size: number;
  pop(): string;
  push(value: string): void;
}

  class StackTest1 implements Stack {
    private obj: any = {};
    private _size: number = 0;

    get size(): number {
      return this._size;
    }

    push = (value: string) => {
      this.obj[this.size.toString()] = value;
      this._size++;
    };

    pop = () => {
      this._size--;
      const value = this.obj[this._size.toString()];
      delete this.obj[this._size.toString()];
      return value;
    };
  }

  const stack = new StackTest1();
  stack.push("jk");
  stack.push("zl");
  stack.push("steve");
  while (stack.size !== 0) {
    console.log(stack.pop());
  }

type StackNode = {
    value: string;
    next?: StackNode;
  };

  class StackTest2 implements Stack {
    private _size: number = 0;
    private head?: StackNode;

    get size(): number {
      return this._size;
    }

    push = (value: string) => {
      const node = { value, next: this.head };
      this.head = node;
      this._size++;
    };

    pop = (): string => {
      if (this.head == null) {
        throw new Error("no more data");
      }

      const node = this.head;
      const value = this.head.value;
      this.head = node.next;
      this._size--;

      return value;
    };
  }

  const stack2 = new StackTest2();
  stack2.push("value1");
  stack2.push("value2");
  stack2.push("value3");
  while (stack2.size !== 0) {
    console.log(stack2.pop());
  }

위 두가지 방식으로 해보게됐다.

첫번쨰 방식은

올바른 방식이라기 보다는

이렇게도 할 수 있다 정도로만 봐야될것같다.

2번은 단일 연결 list라는 자료구조의 개념을 도입하여

스택을 구현한 예제이다.

완전탐색에 해당하는 문제이다.

function solution(answers) {
    var answer = [];
    const score = [
        { name: 1, count : 0 },
        { name: 2, count : 0 },
        { name: 3, count : 0 },
    ];
    const user1 = [1, 2, 3, 4, 5];
    const user2 = [2, 1, 2, 3, 2, 4, 2, 5];
    const user3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
    
    answers.forEach((answer, index) => {
        const value = index + 1;
        if (value < 5) {
            if (answer === user1[index]) score[0].count += 1;
        } else {
            if (answer === user1[index % 5]) score[0].count += 1;
        }
        
        if (value < 8) {
            if (answer === user2[index]) score[1].count += 1;
        } else {
            if (answer === user2[index % 8]) score[1].count += 1;
        }
        
        if (value < 10) {
            if (answer === user3[index]) score[2].count += 1;
        } else {
            if (answer === user3[index % 10]) score[2].count += 1;
        }
    });
    
    score.sort((a,b) => a.count > b.count ? -1 : 1)
    answer = score.filter((val) => val.count === score[0].count).map((val) => val.name);
    
    return answer;
}

위와 같이 문제를 해결해보았다.

1. score를 쉽게 정렬하기위해 배열을 이용했다.

2. 수포자들이 찍기 방식이 일정한 패턴을 가지고 있음을 활용한다. (사실, 랜덤이라면 답을 구하는것 자체가 불가능하지않을까?)

3. 각자의 패턴의 길이만큼은 단순비교를

4. 패턴의 길이 이상에서는 나머지 값을 이용해서 답안과 비교한다.

5. forEach를 이용해 답안의 수 만큼 반복한다.

6. 마지막으로 배열을 정렬하고, 가장 큰 수와 같은 수만큼 답안을 획득한 수포자들만 필터한다.

7. map으로 수포자들의 이름(1,2,3)만 뽑아낸다.

간단하지만,

패턴을 이용한다. 나머지를 이용한다. 와 같은 발상을 못한다면

맞출수없는 문제같다.

마지막으로, 완전탐색의 개념을 살짝 짚어본다.

완전 탐색이란? 가능한 모든 경우의 수를 탐색하고, 확인하는 방법입니다.

function solution(genres, plays) {
    var answer = [];
    let genreArr = [];
    
    genres.forEach((gen, idx) => {
        const currentCnt = plays[idx];
        const hasIdx = genreArr.findIndex(g => g.name === gen);
        if (hasIdx >= 0) {
            genreArr[hasIdx].total += currentCnt;
            genreArr[hasIdx].cntList.push({ order: idx, cnt: currentCnt });
        } else {
            genreArr.push({
                name: gen,
                total: currentCnt,
                cntList: [{ order: idx, cnt: currentCnt }]
            });  
        };
    });
        
    genreArr.sort((a,b) => a.total > b.total ? -1 : 1);
    genreArr.forEach((gen) => {
        gen.cntList.sort((a,b) => a.cnt > b.cnt ? -1 : a.cnt === b.cnt ? 1 : a.cnt < b.cnt ? 1 : -1);
        gen.cntList.slice(0, 2).forEach(({ order }) => answer.push(order));
    });
    
    return answer;
}

1. 장르를  순회하며 새 배열에 필요한 객체 형태로 push해준다.

2. 우리가 알아야 할 값은, 장르별 총합과 index별 플레이 횟수이다.

3. 따라서, name, total, list<{order, cnt}> 구조로 객체를 정의해주었다.

4. 장르 total에 따라서 정렬

5. 장르 내 재생횟수 높은순 -> 고유번호 낮은순으로 정렬

6. 장르별로 두개씩 모아서 앨범을 출시한다고 했으므로, slice(0, 2)하여 출력

경우의 수와 관련된

수학문제

function solution(clothes) {
  let answer = 1;
  let obj = {};
  
  for(var i=0; i < clothes.length; i++) { 
    if(obj[clothes[i][1]] >= 1) { 
      obj[clothes[i][1]] += 1;
    } else { 
      obj[clothes[i][1]] = 1;
    } 
  }
    
  for (let key in obj) { 
    answer *= (obj[key]+1);
  }

  return answer - 1;
}

1. 객체에 해당 옷의 종류가 없으면 1

2. 객체에 해당 옷의 종류가 있으면 기존값 + 1

3. 경우의 수 계산을 위해 종류별로 곱해나가는데 (곱의 법칙), 해당 종류의 옷을 안입는 경우의 수도 존재하니 +1하여 곱한다.

4. 3번에 옥의티로 저렇게하면 모든 옷을 안입은 경우의 수가 발생하게 되는데 문제에서 아무것도 안입는 경우는 없다고 했으므로 마지막에 -1을 해준다.

* 한걸음 더 나아가 생각해보기

만약에, 문제에 모든 종류의 옷을 반드시 한가지씩 입어야한다는 조건이 붙는다면?

function solution(clothes) {
  let answer = 1;
  let obj = {};
  
  for(var i=0; i < clothes.length; i++) { 
    if(obj[clothes[i][1]] >= 1) { 
      obj[clothes[i][1]] += 1;
    } else { 
      obj[clothes[i][1]] = 1;
    } 
  }
    
  for (let key in obj) { 
    answer *= obj[key];
  }

  return answer;
}

1. 해당 종류의 옷을 안입는 경우를 제외

2. 위의 코드에서 모든 종류의 옷을 안입는 경우는 발생하지 않으므로 마지막에 -1도 제외

* 떠올려본 방법

1. completion을 포문으로 돌린다 + participant에서 해당 index를 찾아 + splice(index, 1) [시간초과]

2. 2중포문으로 비교해나간다. [시간초과]

3. sort를 이용해 각 배열을 정렬 + 순서대로 비교해가며 다를때 리턴 [성공]

function solution(participant, completion) {
  participant.sort();
  completion.sort();
    
  for (let i=0; i<participant.length; i++) {
    if (participant[i] !== completion[i]) {
      return participant[i];
    }
  }
}