알고리즘 & 자료구조 스터디 2주차 [Problem Solving]

April 12, 2023 🐰

☺︎ What is agorithm??

- 알고리즘을 간단하게 설명하면 특정 작업을 달성하기 위한 과정이나 일련의 단계를 의미 
→ 문제를 해결하기 위해 수행해야 하는 일련의 수학적 단계이다.

• 알고리즘 실력이 향상되는 법
  • Devise a plan for solving problems .. → 문제 해결을 위한 계획을 수립
  • Master common problem solving patterns → 일반적인 문제 해결 패턴을 파악

☺︎ Problem Solving

💪🏻 앞으로 많은 알고리즘 문제를 해결할 때 기존에 가지고 있던 안좋은 버릇들을 고쳐보자!

문제를 해결할 때에 5가지 방법으로 접근해보자.

🔑 understand the problem : 문제에 대해 이해하기
🔑 Explore concrete Examples : 각 예시들을 탐구하기.
🔑 Break it Down : 분석하기. (문제에 대한 단계들을 실제로 수행하면서 작성)
🔑 Solve/Simplify : 문제를 해결하고 단순화하기.
🔑 Look Back and Refactor : 회고와 리팩터링하기. (개발자들에게 있어서 가장 중요한 단계)

🔑 Understand the Problem : 문제에 대해 이해하기.

• 문제에 대해 이해할 때에는 아래와 같이 5가지 방법으로 진행된다.

Step by Step!
1. 문제를 우리 방식대로 다시 생각할 수 있을까?
2. 문제가 어떤 입력값을 담고 있는가?
3. 문제에 대한 해결책에서 나와야 할 결과는 무엇일까?
4. 입력값이 출력값을 결정할 수 있을까?(문제를 해결할 충분한 정보가 주어졌는가)
5. 문제의 일부인 데이터의 중요한 부분에 어떻게 라벨을 지정할 수 있을까?

👩🏻‍🌾 아래 예시를 통해 문제에 접근해보자!

• ex) Write a function which takes two numbers and returns thier sum.

/*
Problem solving - step 1 : Understand the Problem : 문제에 대해 이해하기

ex) Write a function which takes two numbers and returns thier sum.

1. Can I restate the the problems in my own words?
"implement addition";

2. what are the inputs that go into the problem?
 - ints?
 - floats?
 - what about string for large numbers?

3. what are the outputs that should come from the solution to the problem?
 - int? float? string?

4. Can the outputs be determined from the inputs?

5. How should I label the important pieces of data that are a part of the problem?
*/

🔑 Explore Examples :각 예시들을 탐구하기

Step by Step!

1. 간단한 예시로 시작
2. 더 복잡한 예시들로 진행
3. 빈 입력값이 있는 예제를 살펴보기
4. 사용자가 유효하지 않은 값을 입력하면 어떻게 될지 살펴보기

👩🏻‍🌾 아래 예시를 통해 문제에 접근해보자!

• ex) write a function which takes in a string and returns counts of each character in the string.

//ex) write a function which takes in a string and returns counts of each character in the string.

//Problem solving - step 2 :Explore Concrete Examples : 각 예시들을 탐구하기

//1. 간단한 예시로 시작 🛫
charCount("aaaa"); // {a:4}
charCount("hello"); // {h:1,e:1,l:2,o:1}

//2. 더 복잡한 예시들로 진행.
charCount("Your PIN number is 1234!");
/*
    1:1,   
    2:1,
    3:1,
    4:1,
    b:1,
    e:1,
    i:2,
    m:1,
    n:2,
    o:1,
    p:1,
    r:2,
    s:1,
    u:2,
    y:1
 */
charCount("Hello Hi");

//3. 빈 입력값이 있는 예제를 살펴보기
charCount("");
//4. 사용자가 유효하지 않은 값을 입력하면 어떻게 될지 살펴보기
charCount(123);

🔑 Break it Down! : 분석하기.

(취향저격 개그..! break Dance Time..)

Step by Step!

• 문제에 대한 단계들을 실제로 수행하면서 작성
• 여기서 나중에 기술면접의 Tip 은 문제를 해결하지 못해도 과정을 작성해서 문제를 전체적으로 풀 수 있음을 증명하는 것이 중요하다.
• " 나는 함수를 사용해서 for문을 통해 loop를 돌리고~ key를 입력받아 숫자를 늘려가며 문자가 있는 갯수를 셀꺼야~ 그리고value 값을 추가할꺼야" 와 같은 과정들
• 요소와 과정을 작성하는 단계

👩🏻‍🌾 아래 예시를 통해 문제에 접근해보자! (Explore Examples의 예시의 다음 단계!)

//Problem solving - step 3 :break it Down : 분석하기 🤔
function charCount(str) {
  //do something
  //return an object with keys that are lowercase alphanumeric characters in the string;
  //values should be the counts for those characters
}
//위와 같이 작성 후 아래와 같이 세분화 시키기 😼
function charCount(str) {
  //make object to return at end

  //loop over string, for each character...
    //if the char is a num/letter And is a key  in object, add one to count
    //if the char is a number/letter And not in object, add it to object and set value t o 1
    //if character is something else (space, period, etc..) don't do anything
  //return object at end

}

🔑 Solving / Simplify : 문제를 해결하고 단순화하기

Step by Step!

• 단계별로 문제를 푸는 방법을 정했으면 문제를 해결
• 문제를 해결했다면 적재적소에 코드를 단순화 시키기
• 단계별로 요소와 과정을 작성했던 것에 코드를 추가한다!
  👩🏻‍🌾 아래 예시를 통해 문제에 접근해보자! (Explore Examples의 예시의 다음 단계!)

  //Problem solving - step 4 :Solving & simplify : 문제를 해결하고 단순화하기
  // 세분화 시켰던 과정에 코드를 추가한다.
  function charCount(str) {
  //make object to return at end
  var result = {};
  //loop over string, for each character...
  for (var i = 0; i < str.length; i++) {
    var char = str[i].toLowerCase();
    //if the char is a num/letter And is a key  in object, add one to count
    if (result[char] > 0) {
      result[char]++;
    } else {
      //if the char is a number/letter And not in object, add it to object and set value t o 1
      result[char] = 1;
    }
  }
  //if character is something else (space, period, etc..) don't do anything
  //return object at end
  return result;
  }

• to Lower Case() : 소문자로 변환시키기

🔑 Look Back & Refactor : 회고와 리팩터링하기

• 강의에서는 개발자들에게 가장 중요한 단계라고 한다.
• 사실 여기까지 왔다는 것은 "하지만 문제는 풀었죠?"로 안주하지 않기.
  ("하지만 행복했죠?") -> 발전하는 개발자가 되기위해 중요한 단계를 꼭 지켜보자!
• 마지막으로 refactor를 위해 정리

Step by Step! + Refactor

• 결과 확인! : yeah~👏
• 결과를 다른 방식으로 도출하기 😪
• 한눈에 보고 이해 가능한지 확인 (가독성)
• 결과나 방법을 다른 문제에 적용 가능한지 확인
• 해결책의 성능을 향상시킬 수 있는지 확인
• 코드를 향상시킬수 있는 다른 방법은 없을지 고민하기
• 다른 사람들은 이 문제를 어떻게 해결하는지 참고하기

👩🏻‍🌾 아래 예시를 통해 문제에 접근해보자! (refactor 하는 과정 2개의 version)

• 정규 표현식 version
  • 정규 표현식을 사용해 az , 09 등 얻고 싶은 값만 얻을수 있게 설정.

    function charCount(str) {
    var obj = {};
    for (var i = 0; i < str.length; i++) {
    var char = str[i].toLowerCase();
    //a~z , 0~9 , 밑줄,대시,마침표, 쉼표 등을 제거하고 문자와 숫자만
    if (/[a-z0-9]/.test(char)) {
    if (obj[char] > 0) {
      obj[char]++;
    } else {
      obj[char] = 1;
      1;
    }
    }
    }
    return obj;
    }

• charCodeAt version
  • 아스키 코드를 이용하면 정규식으로 접근하는 것보다 실행속도가 빠르다는 것을 배우게된다.

function charCount(str) {
  var obj = {};
  for (var char of str) {
    //a~z , 0~9 , 밑줄,대시,마침표, 쉼표 등을 제거하고 문자와 숫자만
    if (isAlphaNumeric(char)) {
      char = char.toLowerCase();
      obj[char] = ++obj[char] || 1;
    }
  }
  return obj;
}

//정규식보다 아래와 같이 charCodeAt을 하면 코드 실행이 더 빠르다.
function isAlphaNumeric(char) {
  var code = char.charCodeAt(0);
  if (
    !(code > 47 && code < 58) && //numeric (0-9)
    !(code > 64 && code < 91) && //upper alpha (A-Z)
    !(code > 96 && code < 123) //lower alpha (a-z)
  ) {
    return false;
  }
  return true;
}

💻 Source

• ✏️ Best JavaScript Data Structures & Algorithms Course by Udemy, last updated January 2022, accessed April 5, 2023 - https://www.udemy.com/