문제 해결 접근법

알고리즘(Algorithm): 특정 작업을 달성하기 위한 과정이나 일련의 단계

 

문제를 해결하기 위해 수행해야 하는 일련의 수학적 단계, 특정 광고를 사용자에게 제안하는 페이스북이나 구글의 알고리즘이라고 할 수 있다. 

 

우리는 왜 알고리즘을 필요로 할까?

프로그래밍에서 수행하는 거의 모든 작업에는 일종의 알고리즘이 포함되므로 문제를 해결할 방법을 마련할 수 있도록 결정을 해야 한다. 

 

어떻게 발전해나가야 할까?

1. Devise a plan for solving problems. 문제 해결을 위한 계획을 수립하라.

문제에 접근하는 방법, 문제를 세분화하기 위한 전략, 방향을 잡기 위한 몇 가지 단계

2. Master common problem solving patterns.  일반적인 문제 해결 패턴을 파악하라.

많은 알고리즘들, 문제들을 몇 가지 범주로 나눌 수 있는데 범주를 식별할 수 있는 경우에는 코드에 수행할 수 있는 몇 가지 단계를 통하여 얻을 수 있는 알고리즘이나 과제를 해결하는 데 도움이 될 몇 가지 조합법을 확보할 수 있다.

 

Problem solving strategies

• Understand the Problem (문제 이해하기)
• Explore Concrete Examples (구체적인 예시 살펴보기)
• Break It Down (문제 세분화하기)
• Solve/Simplify (문제 해결하고 단순화 하기)
• Look Back and Refactor (문제를 복습하고 재구성하기)

 

Understand the Problem

문제를 해결하기 전에 한 발짝 물러서서 문제를 확실하게 이해하는 것이 중요하다.

문제를 확실하게 이해하기 위한 스스로에 대한 몇 가지 질문들을 정의해보고

두 숫자를 가지고 합계를 반환하는 함수를 예시로 들어 이를 통해 문제를 이해하는 방법을 살펴보자.

 

1. Can I restate the problem in my own words?

     -문제를 자신의 방식대로 다시 말하고 생각할 수 있나요?

"implement addtion" - 덧셈 구현하기

 

2. what are the inputs that go into the problem?

     -문제에 들어가는 입력 값은 무엇인가요?

아주 간단한 질문처럼 여겨진다. 그저 두 숫자를 더하는 것으로 두 숫자가 필요하다. 

하지만 숫자가 정수인지 부동 소수점인지 확실하지 않고, 숫자의 범위, 숫자가 아닌 문자열과의 덧셈 등

그저 두 숫자를 더하기만 하는 건 현명하지 않다. 그리고 항상 두 입력값만 있지 않을 경우도 있을 것이다.

 

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?

     -입력에서 출력을 결정할 수 있습니까?

이 질문들은 문제를 해결할 충분한 정보가 주어졌는가 하는 것이다. 

예를 들어, 누군가가 한 숫자만 입력한다면 어떻게 될 것인가? 이때 덧셈을 수행할 충분한 정보가 없다.

0을 더해야 할까? undefined나 null을 반환해야 할까? 이것은 상황에 따라 다를 것이다. 

 

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

     -문제의 일부인 데이터의 중요한 부분에 어떻게 라벨을 지정할 수 있을까?

이 문제에 중요한 것은 입력값과 출력 값이다. 간단하게 add함수에 인수 num1과 num2를 입력하여 sum을 리턴하는 것이다. 간단하지만 더 복잡한 문제가 생기기 시작하면 단계별로 생각하는 것이 차이를 만들 수 있다. 유용한 몇 가지 예를 보자.

 

 

Explore Concrete Examples

면접관이나 스스로에게 던진 질문을 이해하면서 입력값과 출력 값 등 모든 사항들을 확실히 이해하고자 애쓴다.

예제를 떠올리는 것은 문제를 더 잘 이해하는 데에 도움이 된다. 

예제는 온전성 검사(sanity checks)를 제공하므로 최종 해결책을 입력했다면 제대로 동작하는지 검사를 수행할 수 있다.

*sanity checks: 새로운 기능, 수정된 버그를 중점으로 테스트함.

 

1. Start with Simple Examples

   - 간단한 예제로 시작하라.

 

2. Progress to More Complex Examples

   - 더 복잡한 예제로 진행하라.

 

3. Explore Examples with Empty Inputs

   - 빈 입력이 있는 예제를 탐색하라.

 

4. Explore Examples with Invalid Inputs

   - 유효하지 않은 입력값이 주어진 예제를 살펴봐라.

 

문제: 문자열을 취하고 각 문자의 수를 반환하는 함수를 작성하라.

먼저 문제를 이해했는지 살펴보자. 제대로 이해한 건지 확실히 하기 위해 몇 가지 간단한 예시를 떠올려보자.

charCount라는 함수를 직접 작성해보자

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

배열이나 다른 데이터 구조가 아닌 객체가 반환되어야 한다는 것을 알 수 있다. 

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

이렇게 간단한 예시로 문제를 쉽게 이해할 수 있다. 좀 더 복잡한 예시로 넘어가 보자.

 

"my phone numbe is 0101234" 이것이 입력값이라면 어떻게 반환되도록 해야 할까? 

공백을 고려해야 할까? 달러 기호, 밑줄, 중요한 숫자는 어떻게 해야 할까? 숫자를 포함해야 할까? 

대소문자를 구분해야 할까? 이처럼 복잡한 입력값과 예시를 알아봄으로써 문제를 이해하고 단순화하며 이러한 질문을 통해 보다 잘 이해할 수 있을 것이다. 이러한 질문과 예시들은 우리가 문제를 해결하기 전에 문제를 더 잘 이해하기 위한 방식일 뿐이다. 

 

빈 입력값이 주어진 예시를 살펴보자. 

누군가가 charCount를 입력하고 아무것도 전달하지 않거나 빈 문자열을 전달하는 경우 무엇을 반환할 수 있을까?

null, false나 undefined나 에러를 반환하도록 할 수 있을까? 이는 유효하지 않은 입력값이 주어진 예제를 살펴보는 것과 관련 있다. 누군가가 문자열이 아닌 숫자나 객체나 unll을 반환한다면 어떻게 될까?

면접 상황에서 이런 사례들을 이해하는 건 중요하지 않지만 실제 환경에서 보다 강력하고 문제가 없을 해결책을 갖추는 데 도움이 될 테니 염두에 두는 게 좋다.

 

Break It Down

문제에 대한 단계들을 실제로 수행하면서 작성한다. 

문제를 세분화하는 예로 위와 동일한 문자열을 취하고 문자열의 각 문자 수를 반환하는 함수를 만드는 상황을 가정해보자.

charCount("aaaa") // {a:4}
charCount("hello")  // {h:1, e:1, L:2, o:1}
charCount("Your PIN number is 1234!")
/* {
  1: 1,
  2: 1,
  3: 1,
  4: 1,
  b: 1,
  e: 1,
  i: 2, ...
  } */

위처럼 예시를 작성하며 함수의 구조를 잡아 나간다. 

// #1
function charCount(str) {
  // 뭔가를 함.
  // return 소문자 영숫자 문자인 키를 지닌 객체를 반환. 
}

// #2
function charCount(str) {
  // 마지막에 반환할 객체를 생성
  // 문자열에 loop를 적용함. 
  // 객체를 반환함.
}

// #3
function charCount(str) {
  // 마지막에 반환할 객체를 생성
  // 각 문자에 대해 문자열 loop
    // 객체에 해당 문자가 number/letter이고 키로 존재하면 +1
    // 문자가 number/letter이고 키로 존재하지 않으면 추가하고 값을 1로 설정
    // 문자가 공백이나, 마침표 등 과 같이 다른 것이라면 아무것도 하지 않음.
  // 객체를 반환함.
}

면접에서 단계를 작성한다는 것을 달성하는 방법을 확신하지 못하더라도 수행해야 할 작업을 알고 있다는 의미를 가질 수 있다. 접근 방법을 공식화하여 문제 해결 접근법에 긍정적인 효과를 가져온다.

 

 

Solve/Simplify

앞의 과정을 통하여 문제를 해결할 수 있다면 해결하고 해결할 수 없다면 더욱 단순한 문제를 해결하라.

해결해야할 대상을 바꿔 1 + 1 같은 문제를 고르라는 것이 아니다. 

 

하려는 작업에서 핵심적인 어려움을 찾고, 잠깐 그 어려움을 무시하고 좀 더 단순화된 해결책을 적은 다음,

다시 어려운 부분으로 돌아가서 통합시키는 것이다. 단순화된 해결책을 찾고 작성하는 과정에서 핵심적인 어려운 부분이 어떻게 동작하는지 이해하게 된다. 예시로 돌아가보자.

// #4
function charCount(str) {
  // 마지막에 반환할 객체를 생성
  let result = {}
  // 각 문자에 대해 문자열 loop
  for(let i = 0; i < str.length; i++) {
    let char = str[i]
    
    // 객체에 해당 문자가 number/letter이고 키로 존재하면 +1
    if(result[char] > 0) {
      result[char]++;
    } 
    // 문자가 number/letter이고 키로 존재하지 않으면 추가하고 값을 1로 설정
    else {
      result[char] = 1;
    };
  }
    // 문자가 공백이나, 마침표 등 과 같이 다른 것이라면 아무것도 하지 않음.
  // 객체를 반환함.
  return result;
}

실행 결과

 

이상적이진 않아도 거의 근접한 결과를 얻었다. 

function charCount(str) {
  let result = {}
  // 각 문자에 대해 문자열 loop
  for(let i = 0; i < str.length; i++) {
    let char = str[i].toLowerCase()
    if(result[char] > 0) {
      result[char]++;
    } else {
      result[char] = 1;
    };
  }
  return result;
}

toLowerCase를 이용해 모두 소문자로 변환해주었다.

공백 혹은 다른 문자를 처리해야하는 문제를 해결해야하는데 모든 유효한 문자를 포함하는 배열을 정의하는 방법은 아주 성가시다. 그러므로 알파벳 순서의 대문자와 소문자, 그리고 모든 영숫자 문자를 지닌 방대한 배열을 만드는게 좋다.

 

작성한 코드에 만족하거나 바꾸고 싶지 않을 수 있지만 생각해 볼 가치가 있는 몇가지를 정리해보자.

 

Look Back and Refactor

1. 결과를 다르게 도출할 수 있나요?

2. 해당 코드를 한눈에 이해할 수 있나요?

3. 해당 문제를 해결한 결과와 방법을 다른 문제에서 사용할 수 있나요?

4. 해결책의 성능을 향상시킬 수 있나요?

5. 리펙토링 할 수 있는 다른 방법들을 생각해 볼 수 있나요?

6. 다른 사람들은 어떻게 이 문제를 해결했을까요? 

 

코드를 분석하고 성찰하고 되돌아보는 것이 그저 작동하도록 코드를 작성하고 하루를 마감하는 것보다 가치있는 일이다.

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;
}

정규표현식을 사용하여 문자가 소문자 a에서z, 혹은 0부터 9에 해당하는지 검사한다. 문제에 대한 해결책이 완성된 모습이다. 여기서 몇가지 개선시킬 수 있는 부분들이 있다. 

코드를 단순화하는데 for-of루프를 사용해볼 수 있다. 이 작업은 성능 개선이 아닌 가독성을 개선 시킨 것이다.

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

또 개선 해보자.

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

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

위 두 코드는 같은 결과를 낸다. 여기서 생각해볼 수 있는 부분이 있다. 정규표현식이 아닌 다른 해결책이 있을까?

정규 표현식이 특정 패턴을 빠르게 확인할 수 있는 비교적 짧은 방법이라서 이 경우 조건에 부합하기 위해 사용할 수 있지만 실제로 얼마나 효율적인지는 모르겠다. 정규표현식은 사용 중인 브라우저에 따라 성능이 달라질 수 있다는 말을 들은 적 있다. 이 방법이 아닌 다른 방법으로 해당 문제를 해결할 charCodeAt을 사용해보자. 

 

charCodeAt을 구글링 해보면 이를 사용하는 방법이 자세히 나와있다. charCodeAt의 결과값이 47 - 58 사이에 해당하면 숫자 문자 코드이며 64 - 91 사이라면 대문자 알파벳임을 알 수 있고 96 - 123 사이라면 소문자 알파벳이라는 것도 알 수 있다. 게다가 charCodeAt을 사용하는 것이 정규표현식을 사용하는 것보다 55%가 더 빠르다는 결과가 나와있는 것 또한 알 수 있다.

function charCount(str) {
  let obj = {}
  for(let char of str) {
    if(isAlphaNumberic(char)) {
        char = char.toLowerCase();
        obj[char] = ++obj[char] || 1;
    }   
  }
  return obj;
}

function isAlphaNumberic(char) {
 let 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;
}

정규표현식을 사용한 것보다 성능이 좋은 유효한 문자를 검사하는 isAlphaNumberic 함수를 charCount함수에서 사용해주었다. 소문자로 변환하는 부분을 유효한 문자일때로 범위를 좁혀서 사용해주었다.

위와 같이 어떻게 개선시킬지, 어디서 스타일에 변화를 줄 수 있는지를 스스로에게 질문을 던지며 진행하는 것이 좋다. 

 

이렇게 의사 코드를 적어내려가면서 알고리즘 문제를 푸는 것은 위와 같은 예시에서는 그리 중요하게 다가오지 않을 수 있지만, 보다 복잡한 문제의 경우에는 이러한 행위가 구세주가 될지도 모른다. 특히 단계를 작성한다는 것은 방법을 확신하지 못하더라도 수행해야 할 작업을 알고 있다는 의미이다. 이는 면접관에게도 좋은 인상을 남길 수 있다.