0708_TIL

 

---

🎄오늘 한 일

✔️ 1.  2021 kakao 채용연계형 인턴십 코딩테스트 문제 풀이

• 프로그래머스에 새로 올라온 카카오 인턴쉽 코딩기출 문제를 풀어보았다.
• 현재 수준을 감안하여 lv1.숫자문자열과 영단어  lv2. 거리두기확인하기 만 풀어보았고, 총 3시간을 소요하여 2문제 풀이를 성공하였다. 
  카카오 문제를 풀면 정말 딱 내 코딩테스트 실력을 파악할 수 있는 것 같다. 
  현재 나의 실력은 lv1, lv2 를 풀 수 있지만, 구현과정에서 시간소요가 상당히 요구되어 어려움을 겪는 것을 파악하였다.

✔️ 2. 이코테 DP 학습

• 이것이 코딩테스트다의 DP(다이나믹프로그래밍) 챕터를 학습하였다.
• DP는 점화식으로 해결할 수 있는 문제이며,
  1. 큰 문제를 작은 문제로 쪼개어 생각해볼 수 있을 때
  2. 작은 문제가 큰 문제의 해결에 반복하여 동일하게 사용될 때 
  DP방식을 고려해볼 수 있다.

• DP의 점화식 부분을 코드로 옮길 때에는
  1. bottom-up 방식으로 for문을 사용하여 첫번째 값부터 n번째 값을 찾으며 구현하는 방법
  2. top-down 방식으로 재귀식을 사용하여 n번째 부터 첫번째 값까지 찾는 방법이 존재한다. 

 

가장 간단한 DP 구현 문제
 :총 4가지의 연산 (2로나누는 연산 / 3으로 나누는 연산 / 5로나누는 연산 / 1을 빼는 연산 ) 만이 가능할 때, n을 입력값으로 넣어서 1을 만드는 최소의 연산횟수를 구하는 문제

 

# 1. for문을 이용하여 bottom up 방식으로 점화식 구현하기

// by for문 바텁업
let memo = [0, 0];
function makeOneByFor(n) {
  for (let i = 2; i <= n; i++) {
    memo[i] = memo[i - 1] + 1; // 2
    if (i % 2 === 0) {
      memo[i] = Math.min(memo[i], memo[i / 2] + 1); //3
    }
    if (i % 3 === 0) {
      memo[i] = Math.min(memo[i], memo[i / 3] + 1);
    }
    if (i % 5 === 0) {
      memo[i] = Math.min(memo[i], memo[i / 5] + 1);
    }
  }
  return memo[n];
}

# 2. for문을 이용하여 bottom up 방식으로 점화식 구현하기

let memo = [];
function makeOne(n) {
  if (n === 1) return 0;
  if (memo[n]) return memo[n];

  // 1빼는 경우
  memo[n] = makeOne(n - 1) + 1;
  if (n % 5 === 0) {
    let temp = makeOne(n / 5) + 1;
    memo[n] = Math.min(memo[n], temp);
  }
  if (n % 3 === 0) {
    let temp = makeOne(n / 3) + 1;
    memo[n] = Math.min(memo[n], temp);
  }
  if (n % 2 === 0) {
    let temp = makeOne(n / 2) + 1;
    memo[n] = Math.min(memo[n], temp);
  }
  return memo[n];
}