[자료구조와 알고리즘] 유데미 강의 "JavaScript 알고리즘 & 자료구조 마스터클래스" 정리(섹션 4: 문제 해결 접근법)

섹션 4: 문제 해결 접근법

📌 알고리즘

특정 작업을 달성하기 위한 과정이나 일련의 단계

 

📌 문제 해결법

1단계 문제의 이해

• 작업을 수행하면서 어떤 해결책을 마련할지, 애플리케이션이 어떻게 구동되도록 할지, 각 상황에서 어떤 식으로 작동되도록 할지에 대해 확실히 이해한다.
• 면접관에게 질문을 던져서 문제를 명확히 함으로써 확실히 이해할 수도 있다.
• 문제 이해는 구체적인 예시를 살펴보는 것과도 관련된다.

2단계 구체적 예시

• 이 두 가지 단계(문제의 이해, 구체적 예시)는 문제를 이해하고, 입력값과 출력값을 이해하고 경계 조건을 이해하는 것에 관한 것이다. 에러를 어떻게 처리할지, 그리고 사용자가 잘못된 값을 입력하면 어떻게 되는지와 같은 질문들은 처음부터 모든 것이 어떻게 작동해야 하는지를 이해하는 것과 관련이 있다.

🤔프로그래머스 사이트 문제의 "입출력 예"와 같은 것으로 생각된다.

3단계: 문제 세분화

• 구현해야 할 코드에 대한 계획의 틀을 잡기 위한 단계를 몇 가지로 세분화하는 것이 좋다.
• 이 단계는 특히 면접에서 큰 도움이 되는데, 그 이유는 시간이 제한된 상황에서 시간이 부족하리라는 것을 알고 있다면 계획을 작성하여 이런 방향을 갖고 있지만 40% 밖에 구현하지 못했다고 면접관에게 어필할 수 도 있을 것이기 때문이다.

🤔구현하기 전에 문제 해결을 위한 각 단계를 주석으로 작성(의사 코드 등)하는 방식을 권장하는 것으로 이해했다.

4단계: 문제 해결/단순화

• 문제를 당장 해결할 수 없다면 해결할 수 있는 문제부터 처리한다.
• 단순한 문제 같더라도 더 단순화하면 핵심적인 어려운 부분이 사라진다.
• 해결할 수 있는 부분을 먼저 처리하면 어려운 부분을 다시 통합할 수 있을 것이다.

5단계: 문제 복습/재구성(Refactor)

• 시간을 내어 코드를 살펴보고, 되돌아보고, 성찰하지 않는다면 좋은 기회를 놓치게 될 것이다.
• 각 구성요소를 한 줄씩 살펴보면서 마음에 들지 않는 부분이나, 코드의 형태, 해석 방법, 또 이해하기 얼마나 쉬운지에 대해 이야기를 하라는 의미이다.
• 효율성과 가독성이라는 두 기둥 사이에 균형을 맞춰야 할 필요가 있다.

 

📌 리팩토링 질문

1. 결과를 확인할 수 있는가?

2. 결과를 다른 방식으로 도출할 수 있는가?

• 해결한 이 방법 외에 생각나는 다른 접근 방식이 있는가? 앞서 생각하지 못한 다른 방법을 적용할 수 있는가?

3. 한눈에 보고 이해할 수 있는가?

• 코드 편집기의 내용을 종이나 화이트보드에서 보더라도 이해할 수 있을까?

4. 결과나 방법을 다른 문제에도 적용할 수 있는가?

• 문제를 해결함으로써 얻을 수 있는 큰 이점 중 하나는 직감을 발달시켜 다른 문제를 해결할 수 있는 직관력을 길러준다는 것이다.

5. 해결책의 성능을 향상할 수 있는가?

• 성능은 주로 시간 복잡도와 공간 복잡도로 분석한다.-예제의 경우-정규 표현식보다 문자 코드를 사용하는 것이 더 효율적이다.

 

📌 예제 코드

// 1. 의사 코드 작성 예
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, and one to count
  // if the char is a number/letter AND not in object, add it to object and set value to 1
  // if character is something else (space, period, etc.) don't do anything
  // return object at end
}

// 2. 해결 코드 구현
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 number/letter AND is a key in object, and one to count
    if (result[char] > 0) {
      result[char]++;
    }
    // if the char is a number/letter AND not in object, add it to object 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;
}

// 3. 리팩토링 - 정규식
function charCount(str) {
  var obj = {};
  for (var i = 0; i < str.length; i++) {
    var char = str[i].toLowerCase();
    if (/[a-z0-9]/.test(char)) {
      if (obj[char] > 0) {
        obj[char]++;
      } else {
        obj[char] = 1;
      }
    }
  }
  return obj;
}

// 4. 리팩토링 - for of
function charCount(str) {
  var obj = {};
  for (var char of str) {
    char = char.toLowerCase();
    if (/[a-z0-9]/.test(char)) {
      if (obj[char] > 0) {
        obj[char]++;
      } else {
        obj[char] = 1;
      }
    }
  }
  return obj;
}

// 5. 리팩토링 - 논리 연산자(||)
function charCount(str) {
  var obj = {};
  for (var char of str) {
    char = char.toLowerCase();
    if (/[a-z0-9]/.test(char)) {
      obj[char] = ++obj[char] || 1; // ++이 앞쪽에 위치함에 유의
    }
  }
  return obj;
}

// 6. 리팩토링 - 문자 코드
function charCount(str) {
  var obj = {};
  for (var char of str) {
    char = char.toLowerCase();
    if (isAlphaNumeric(char)) {
      obj[char] = ++obj[char] || 1; // ++이 앞쪽에 위치함에 유의
    }
  }
  return obj;
}

// 정규 표현식보다 문자 코드를 사용하는 것이-코드는 길어지지지만 성능에서-더 효율적
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;
}

console.log(charCount("hello")); // { h: 1, e: 1, l: 2, o: 1 }
console.log(charCount("Hi there!")); // { h: 2, i: 1, ' ': 1, t: 1, e: 2, r: 1, '!': 1 }