SW Academy 2기 프론트엔드 과정

6 minute read

Day15

동적계획법

코딩테스트 준비방법

동적계획법

  • 해결한 작은 문제로 큰 문제를 해결하는 풀이 방식
  • 특정 알고리즘이 아닌 문제 해결 방식이다.
  • 메모리를 많이 사용하는 대신 빠른 성능을 자랑한다.
  • 메모이제이션(Memoization)
    • 하향식 접근법
    • 작은 문제들의 결과를 저장해뒀다 필요할 때 꺼내쓰는 방식
    • Lazy evaluation
  • 태뷸레이션(Tabulation)
    • 상향식 접근법
    • 필요한 값들을 미리 계산해두는 것
    • Eager evaluation
  • 가장 작은 문제를 정의할 수 있는가?
  • 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙이 있는가?
  • 문제 : 단어퍼즐
  • 정답코드 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

    function solution(strs, t) {
  // 편의를 위해 t의 길이 + 1만큼 배열을 만든다.
  const dp = Array.from({ length: t.length + 1 }, () => 0);
  // 문자열 검사를 빠르게 하기 위해서 문자열 리스트를 set으로 만든다.
  const strsSet = new Set(strs);
    
  // 1부터 문자열 길이 + 1까지 루프를 돈다.
  for (let i = 1; i < t.length + 1; i += 1) {
      // 일단 해당 문자열의 최솟값은 무한으로 설정한다.
      dp[i] = Infinity;
      // 문자열을 자르면서 단어 조각을 찾기 위해 루프를 돈다.
      // 단어 조각은 5 이하기 때문에 마지막까지 자를 필요는 없다.
      for (let j = 1; j < Math.min(i + 1, 6); j += 1) {
          const start = i - j;
          const end = i;
          // 단어 조각이 있다면
          if (strsSet.has(t.slice(start, end))) {
              // 이전 조합과 더해서 최솟값인지 체크 후 대입한다.
              dp[i] = Math.min(dp[i], dp[i - j] + 1);
          }
      }
  }

  // 결과적으로 단어의 최솟값을 구할 수 있다. 만약 무한이라면 불가능한 조합이기 때문에 -1을 리턴한다.
  return dp[dp.length - 1] === Infinity ? -1 : dp[dp.length - 1];
}

코딩테스트 준비방법

  • 알고리즘을 잘 공부하는 법

    1. 항상 여러가지 풀이 방법이 있을 수 있다는 것을 기억하자
    2. 항상 예외가 있을 수 있다는 것을 기억하자
    3. 내가 풀어낸 답이 베스트인지 의심하자
    4. 문제를 풀었다면 시행착오를 모두 기록하자
    5. 다른 사람의 코드를 많이보자, 생각하지 못한 방법을 발견할 수 있다.
    6. 쉽게 포기하지 말자. 하지만 도저히 모르겠다면 답을 보는 것도 좋은 방법이다.
    7. 시각적인 사이트의 도움을 받자

  • 코딩테스트를 잘 보는 법

    1. 자신의 성향을 파악하자.
      • 미리 생각하고 의사 코드를 작성해야 더 잘 풀리는 사람
      • 일단 코드를 작성하면서 생각해야 더 잘 풀리는 사람 ✅
    2. 메모하기
      • 코드에 주석을 달고나 노트에 메모하면서 풀기
      • 헷갈리면 순서도를 그리면서 정리
      • 데이터가 변하는 과정을 기록하면서 정리
    3. 디버깅은 필수
    4. 익숙해지기
      • 문제를 잘 읽는 것에 익숙해지기
      • 시간복잡도를 계산하는 것에 익숙해지기
      • 엣지 케이스를 생각하는 것에 익숙해지기

  • 좋은 코드를 만드는 법

    1. 간결하고 가독성이 좋은 코드
      • 변수, 함수 이름은 잘 정했는가?
      • 중복 코드를 제거했는가?
      • 함수형 프로그래밍도 좋은 방법(map, filter, reduce)와 같은 고차함수 이용하기
    2. 가지치기를 했는가?
    3. 자바스크립트를 잘 활용했는가?
      • 구조 분해 할당
      • …오퍼레이터
    4. 일관성을 잘 유지했는가?
      • var와 let 혼용
      • snake_case와 camelCase 혼용
      • 변수명, 함수명 규칙의 통일

  • 코딩테스트 문제 유형 파악하기

    • 문제를 읽기전에 무조건 입출력 제한을 보자!

      • 입력이 100 이하인 경우
        • 완전 탐색
        • 백트래킹
      • 입력이 10,000 이하인 경우 → 최소 O(n^2), 최대 O(n^2 log n) 이내로 끝내야하는 문제
        • n*n 2차원 리스트를 모두 순회해야하는 문제가 많음
      • 입력이 1,000,000 이하인 경우 → 최대 O(n log n)으로 끝내야하는 문제
        • 힙, 우선순위 큐
        • 정렬
        • 동적 계획법
        • 위상 정렬
        • 다익스트라 알고리즘
      • 입력이 100,000,000 이하인 경우 → 최대 O(n)으로 끝내야하는 문제
        • 동적 계획법
        • 그리디
      • 그 이상인 경우 → 최대 O(log n)으로 끝내야하는 문제가 많음
        • 거의 안나오는 문제 유형
        • 이진탐색

    • 문제 유형

      • 입력값이 작은 문제
        • 백트래킹
      • 지도가 주어지고 채워진 영역을 찾아야하는 경우
        • BFS, DFS
      • 그래프 그림이 있는 경우
        • 최단 거리 찾기
        • 최소 신장 트리
        • 위상 정렬
      • X라는 조건을 만족하는 가장 최대/최소값을 찾아라
        • 이진 탐색
      • 실시간으로 정렬이 이루어져야 하는 경우
        • 우선순위 큐(heap)
      • DP 문제
        • 특징이 없음
      • 문자열이 주어지는 경우
        • 구현력
      • 현재 상황에서 가장 최적인 선택을 해야하는 경우
        • 그리디

  • 엣지 케이스 유형

    • 입력 값의 크기가 굉장히 작은 케이스 (대부분의 입력 값이 최대값 언저리인 경우)
    • 입력 값의 크기가 굉장히 큰 케이스 (대부분의 입력 값이 최소값 언저리인 경우)
    • 입력 값의 범위가 넒은 케이스 (A는 최소값이고 B가 최대값인 경우)
    • 음수 입력이 허용된 경우 음수만 입력받는 케이스
    • 리스트를 입력 받을 때 값이 없거나 하나만 있는 케이스
    • 그래프에서 사이클(cycle)이 발생하는 경우
    • 길찾기 문제에서 지그재그로 움직일 경우
    • 부동소수점 오차

  • JavaScript 의 10가지 코드 트릭

    • 1. 구조 분해 할당을 이용한 변수 swap

      ES6의 구조 분해 할당 문법을 사용하여 두 변수를 swap 할 수 있습니다.

      1
2
3

      let a = 5, b = 10;
[a, b] = [b, a];
console.log(a, b); // 10 5

    • 2. 배열 생성으로 루프 제거하기

      보통 단순히 범위 루프를 돌고 싶다면 다음과 같이 코드를 작성합니다.

      1
2
3
4

      let sum = 0;
for (let i = 5; i < 10; i += 1) {
sum += i;
}

      만약 범위 루프를 함수형 프로그래밍 방식으로 사용하고 싶다면 배열을 생성해서 사용할 수 있습니다.

      1
2
3

      const sum = Array
.from(new Array(5), (_, k) => k + 5)
.reduce((acc, cur) => acc + cur, 0);

    • 3. 배열 내 같은 요소 제거하기

      Set을 이용할 수 있습니다.

      1
2
3

      const names = ['Lee', 'Kim', 'Park', 'Lee', 'Kim'];
const uniqueNamesWithArrayFrom = Array.from(new Set(names));
const uniqueNamesWithSpread = [...new Set(names)];

    • 4. Spread 연산자를 이용한 객체 병합

      두 객체를 별도 변수에 합쳐줄 수 있습니다. ```javascript const person = { name: ‘Lee Sun-Hyoup’, familyName: ‘Lee’, givenName: ‘Sun-Hyoup’ };

    const company = { name: ‘Cobalt. Inc.’, address: ‘Seoul’ };

    const leeSunHyoup = { …person, …company }; console.log(leeSunHyoup); // { // address: “Seoul” // familyName: “Lee” // givenName: “Sun-Hyoup” // name: “Cobalt. Inc.” // 같은 키는 우선 순위에 따라 정해진다. // }

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

    - #### 5. &&와 || 활용
***
&&와 ||는 조건문 외에서도 활용될 수 있습니다.
```javascript
/// ||
// 기본값을 넣어주고 싶을 때 사용할 수 있습니다.
// participantName이 0, undefined, 빈 문자열, null일 경우 'Guest'로 할당됩니다.
const name = participantName || 'Guest';
  
/// &&
// flag가 true일 경우에만 실행됩니다.
flag && func();
  
// 객체 병합에도 이용할 수 있습니다.
const makeCompany = (showAddress) => {
return {
name: 'Cobalt. Inc.',
...showAddress && { address: 'Seoul' }
}
};
console.log(makeCompany(false));
// { name: 'Cobalt. Inc.' }
console.log(makeCompany(true));
// { name: 'Cobalt. Inc.', address: 'Seoul' }

    • 6. 구조 분해 할당 사용하기

      객체에서 필요한 것만 꺼내 쓰는 것이 좋습니다.

      1

      const { familyName, givenName } = person;

    • 7. 객체 생성시 키 생략하기

      객체를 생성할 때 프로퍼티 키를 변수 이름으로 생략할 수 있습니다.

      1
2
3
4
5
6
7
8
9
10
11

      const name = 'Lee Sun-Hyoup';
const company = 'Cobalt';
const person = {
name,
company
}
console.log(person);
// {
//   name: 'Lee Sun-Hyoup'
//   company: 'Cobalt',
// }

    • 8. 비구조화 할당 사용하기

      함수에 객체를 넘길 경우 필요한 것만 꺼내 쓸 수 있습니다.

      1
2
3
4
5
6
7
8

      const makeCompany = ({ name, address, serviceName }) => {
return {
name,
address,
serviceName
}
};
const cobalt = makeCompany({ name: 'Cobalt. Inc.', address: 'Seoul', serviceName: 'Present' });

    • 9. 동적 속성 이름

      ES6에 추가된 기능으로 객체의 키를 동적으로 생성 할 수 있습니다.

      1
2
3
4
5
6
7
8
9
10
11

      const nameKey = 'name';
const emailKey = 'email';
const person = {
[nameKey]: 'Lee Sun-Hyoup',
[emailKey]: 'kciter@naver.com'
};
console.log(person);
// {
//   name: 'Lee Sun-Hyoup',
//   email: 'kciter@naver.com'
// }

    • 10. !! 연산자를 사용하여 Boolean 값으로 바꾸기

      !! 연산자를 이용하여 0, null, 빈 문자열, undefined, NaN을 false로 그 외에는 true로 변경할 수 있습니다.

      1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

      function check(variable) {
if (!!variable) {
console.log(variable);
} else {
console.log('잘못된 값');
}
}
check(null); // 잘못된 값
check(3.14); // 3.14
check(undefined); // 잘못된 값
check(0); // 잘못된 값
check('Good'); // Good
check(''); // 잘못된 값
check(NaN); // 잘못된 값
check(5); // 5

Categories:

Updated:

You may also enjoy

Nextjs

less than 1 minute read

* 본 강의는 Udemy의 Next.js & React - 완벽 정복 가이드 (incl. Two Paths!)를 바탕으로 제작된 내용입니다. *

Ds06

less than 1 minute read

DS06

Dl06

2 minute read

DL06