[1주차] 5월 16일~5월 22일

• 빅오 표기법 (#)
• 배열과 오브젝트의 성능 평가 (#)
• 문제 해결 접근법 / 패턴 (*)
• 재귀 (#)

---

5월 18일

문제 해결 접근법

• 문제를 이해하기
• 구체적인 예시를 알아보기
• 문제를 세분화하기
• 문제를 해결하고 단순화하기
• 문제를 복습하고 재구성하기

모든 작업들은 기본적으로 너무 간단하거나 순조롭게 바로 해결할 수 있다면 생략할 수도 있다.

문제를 이해하기

예시 : 두 숫자를 가지고 합계를 반환하는 함수를 작성하라.

• 자신만의 방식으로 문제가 무엇인지 실제로 이해하기
  두 숫자를 입력 받으면 해당 값을 더해서 출력해주는 함수를 작성하기
• 입력값이 어떤 형태일지
  두 숫자의 종류는 무엇일지 (정수, 실수), 범위는 얼마까지일지, 입력 값이 몇개가 들어올지
• 출력값은 어떤 형태일지
  위와 동일 + 문자열이라면 문자열을 합쳐서 반환할지 등
• 입력값이 출력값을 정할 수 있을지(문제를 해결할 충분한 정보가 주어졌는지)
  한 숫자만 입력 받았을 때 어떨지?
• 데이터에 어떻게 라벨(용어)을 지정할 수 있을지 (이 문제에서 제일 중요한 것이 무엇인지)
  num1, num2, sum(result)

구체적인 예시를 알아보기

유저 스토리, 유닛테스트 등

예시 : 문자열을 전달받아 각 문자가 몇개 있는지 출력하는 함수를 작성하라.

• 간단한 예시
  "hello" = {h:1, e:1, l:2, o:1} or {a:0, b:0, ... e:1, ... z:0}
• 복잡한 예시
  "he low 839 _ Hi" = 숫자도 포함할지, 특수 문자는 어쩔지, 대소문자를 따로 셀지
• 빈 입력 값
  {}, null, false, undefined
• 유효하지 않은 값
  숫자나 객체, null을 입력 받는다면 어떨지

문제를 세분화하기

밟아야 할 단계들을 명확하게 작성하기. 해결책의 기본적인 구성 요소 (pseudocode, 주석 etc.)

예시 : 문자열을 전달받아 각 문자가 몇개 있는지 출력하는 함수를 작성하라.

숫자나 소문자만을 받는다고 한다면,

• 관리하고 리턴 할 객체 만들기
• 입력받은 값을 소문자로 변환하기
• input.forEach
  숫자나 문자라면, 이미 존재 하는지 검사
  존재한다면 1 추가, 존재하지 않다면 객체에 추가
  숫자나 문자가 아니라면 아무 처리도 안하기
• 객체 리턴하기

문제를 해결하거나 단순화하기

문제를 모두 해결할 수 있다면 해결하고 해결하지 못한다면 단순한 부분 먼저 해결하기

짧은 시간 내로 해결하기 어려운 부분을 찾게 되면 잠깐 뒤로 미루고 단순한 부분을 먼저 해결한 다음 다시 어려운 부분으로 넘어가 통합하기

예시: 문자열을 전달받아 각 문자가 몇개 있는지 출력하는 함수를 작성하라. 에서
문자열이나 숫자가 아닌 경우를 찾는 메서드(정규표현식)이 기억나지 않는다면 // 혹은 모른다면,
기본 로직부터 시작해 대소문자를 그대로 둔 뒤에 나중에 (마지막에) 처리하기

function charCount(input) {
  let result = {};
  input.toLowerCase();
  input.forEach( (e) => {
    //if(문자나 숫자라면)
    if(result[e] > 0) result[e]++;
    else result[e] = 1;
  });

  return result;
}

문제를 복습하고 재구성하기

해결에서 끝내지 않고 리팩토링을 위해 무엇이 필요할지 생각해보기

• 더 나은 해결 방법이 있을지
  효율성, 가독성 등, 이 방법 외에 생각나는 다른 접근 방식이 있는지
• 한눈에 보고 이해할 수 있는지
• 결과나 방법을 다른 문제에도 적용할 수 있을지
• 성능을 어떻게 더 향상시킬 수 있을지
  시간 복잡도, 공간 복잡도
• 스타일 지침에 따라 작성했는지 / 일관성 있게 작성했는지
  시간이 없었지만 깔끔하게 만들 의향이 있다는 것을 어필하기.

function charCount(input) {
  let result = {};
  input.toLowerCase();
  input.forEach( (e) => {
    if(result[e] > 0) result[e]++;
    else if (e.match("/[a-z0-9]/" !== null)	//문제 해결, 로직 위치를 옮겨 시간 복잡도 향상
      result[e] = 1;
    }
  });

  return result;
}

여기서 성능을 더 향상시키겠다면 정규표현식 대신 charCodeAt을 이용해 유니코드로 직접 비교 등
코드를 더 간결하게 만들겠다면 if else 대신 삼항연산자 사용 등
많은 리팩토링 방법이 존재

면접 전략

• 질문을 던져가며 문제를 명확히, 확실히 이해하기
  작업을 수행하며 어떤 해결책을 마련할지, 앱이 어떻게 구동되도록 할지
• 입력값과 출력값을 이해하며 경계 조건을 이해하기, 에러를 어떻게 처리할지, 어떻게 동작할지
• 의사코드를 작성해가기, 구현해야 할 코드를 계획하기 위해 단계로 세분화 하기 (이런 방향을 갖고 문제를 해결하려 했으나 나머지를 구현하지 못했을 시 +)
  코드를 작성하기 전 방향을 계획하기 (어디서부터 시작할지) 한가지 접근법에 치우쳐있지 않기
• 해결할 수 있는 문제부터 처리하기
• 분석하고 리팩토링해보기

---

5월 19~20일

문제 해결 패턴

• Frequency Counter (빈도 카운터)
• Multiple Pointers
• Sliding Window
• Divide and Conquer (분할 정복)
• Dynamic Programming
• Greedy Algorithms
• Backtracking
  등등 이미 알려진 문제 해결 패턴들이 존재함

Multiple Pointers

예시 : 교유값이 몇개 있는지 찾는 알고리즘 ([1, 1, 2, 3, 3, 4, 5, 6, 6, 7] = 7)

function countUniqueValues(str1, str2) {
  if(arr.length === 0) return 0;
  let i = 0;
  for(let j = 1; j < arr.length; j++) {
    if(arr[i] !== arr[j]) {
    	i++;
    	arr[i] = arr[j]
    }
  }
}
  return i + 1;
}
 i					   								 i ([6])
[1, 1, 2, 3, 3, 4, 5, 6, 6, 7] -> [1, 2, 3, 4, 5, 6, 7, 6, 6, 7]
    j				      									  j

Sliding Window

예시 : 배열 내에 n개의 이어진 요소를 더한 값의 최댓값 찾기 ([2, 6, 9, 4, 1, 8, 5, 6, 3], 3) = 19

function maxSubarraySum(arr, num) {
  let max = 0;
  let temp = 0;
  
  if (arr.length < num) return null;
  
  for (let i = 0; i < num; i++) {
    max =+ arr[i];
  }
  
  temp = max;
  
  for (let i = num; i < arr.length; i++) {
    temp = temp - arr[i - num] + arr[i];
    max = Math.max(max, temp);
  }
  return max;
}

[2, 6, 9], 4 => 2, [6, 9, 4], 1 => ...
    17		17 - 2(뒤의 값) + 4(앞의 값) = 19 (max < 19; max = 19)