[UJAD] 문제 해결 접근법

🚨 이 글은 'Colt Steele'의 'JavaScript 알고리즘 & 자료구조 마스터클래스' 강의를 듣고 정리한 글입니다.
https://www.udemy.com/course/best-javascript-data-structures/?couponCode=BFCPSALE24

---

문제 해결 접근법

What is an algorithm?

A process or set of steps to accomplish a certain task

Why do i need to know this?

Almost everything that you do in programming involves some kind of algorithm.
It is the foundation for being a succesful problem solving and developer.

How do we improve?

1. Devise a plan for solving problems
2. Master common problem solving patterns

Problem solving

• Understand the problem
• Explore Concrete Examples
• Break it down
• Solve/Simplify
• Look back and Refactor

The hardest thing is solving new problem

Step 1. Understand the Problem

1. Can I restate the problem in my own words?
2. What are the Inputs that go into the problem?
3. What are the outputs that should come from the solution to the problem?
4. Can the outpust be determined from the inputs? In other words, do I have enough information to solve the problem?
   (it may not be able to answer theis question until you set about solving the problem, but it is okay; still worth considering the question at the early stage.)
5. How should i label the important pieces of data that are a part of the problem?

• example question: Write a function which takes two numbers and returns their sum.

Step 2. Explore Concrete Examples.

Coming up with examples can help us eunderstand the problem better.
Examples also provide sanity checks that your eventual solution works how it should.

ex) user stories, unit tests

1. Start with simple examples
2. Progress to More COmplex Examples
3. Explore Examples with Empty Inputs
4. Explore Examples with Invalid Inputs

• example question: Write a function which takes in a string and returns counts of each character in the string.

Step 3. Break it Down

Explicitly write out the steps you need to take.

This forces us to think about the code we'll write before w e write it, and helps us catch any lingering conceptual issues or misunderstandings before we dive in and have to worry about details as well.

• example question: Write a function which takes in a string and returns counts of each character in the string.

first, think of the examples

charCount("aaaa");
// { a: 4 }

charCount("hello");
// {h:1, e:1, l:2, o:1}

charCount("Your PIN number is 1234!")
// {...}

next, break the problem down

// now write down the skeleton
function charCount(str) {
  // do something
  // return an object with keys that are lowercase alphanumeric characters in the string;
}

// Break it down
function charCount(str) {
  // make object to return at end
  // loop over string, for each character
    // if the char is a number/letter AND is a key in object, add one to count
    // if not, add it and set value to 1
    // if character is something else (space, period, etc) don't do anything.
  // return object at end
}

These can demonstrates to the interviewees that we at least know how to approach the problem

Step4. Solve or Sipmlify the problem.

Simplify

• Find the core difficulty in what you're trying to do
• Temporarliy ignore that difficulty
• Write a Simplified solution
• Then incorporate that difficulty back in

function charCount(str) {
  // make object to return at end
  let result = {};
  // loop over string, for each character
  for (let i = 0; i < str.length; i++) {
    let char = str[i].toLowerCase()
    // if the char is a number/letter AND is a key in object, add one to count
    if (result[char] > 0) {
      result[char]++;
    }
    // if not, add it and set value to 1
    else {
      result[char] = 1;
    };
  };
    // if character is something else (space, period, etc) don't do anything.
  // return object at end
  return result;
}

Step 5. Look back and Refactor

Refactoring Questions

1. Can you check the result?
2. Can you derive the result differently?
3. Can you understand it at a glance?
4. Can you use the result or method for some other problem?
5. Can you improve the performanc of your colution?
6. Can you think of other ways to refactor?
7. How have other people solved thie problem?

function charCount(str) {
  let obj = {};
  for (let i = 0; i < str.length; i++) {
    let char = str[i].toLowerCase();
    if (/[a-z0-9]/.test(char)) {
      if (obj[char] = 0) {
        obj[char]++;
      } else {
        obj[char] = 1;
      }
    }
  }
  return obj;
}

// make it into for..of
function charCount(str) {
  let obj = {};
  for (let char of str) {
    let char = char.toLowerCase();
    if (/[a-z0-9]/.test(char)) {
      if (obj[char] = 0) {
        obj[char]++;
      } else {
        obj[char] = 1;
      }
    }
  }
  return obj;
}

//shortening
function charCount(str) {
  let obj = {};
  for (let char of str) {
    let char = char.toLowerCase();
    if (/[a-z0-9]/.test(char)) {
      obj[char] = ++obj[char] || 1;
    }
  }
  return obj;
}

even more is to replace regular expressions into using charCodeAt()

To say "I'm not sure if the 'regular expression' is the best idea" is a key!