알고리즘 문제 접근 방법

출처: https://unsplash.com/ko/%EC%82%AC%EC%A7%84/DK1qF7wIxX8

해당 글은 Udemy "JavaScript 알고리즘 & 자료구조 마스터 클래스" 수업을 기반으로 작성한 내용입니다.

 

 

알고리즘을 처음 접했을 때, 마주했던 상황들은 다음과 같다.

• 문제 자체에 대한 이해를 하지 못함
• 문제를 이해했다고 하더라도 결과값을 얻기 위해 구체적인 방법을 모름

제일 처음 풀었던 문제는 결국 return 한 단어만 적어서 제출했던 기억이 떠오른다.

당시 필요했던건 알고리즘 문제를 단계별로 접근하는 방법이었다.

 

그 방법에 대해 알아보자!

 

---

문제에 대해 이해하기 Understand the Problem

구체적 예제 떠올리기 Explore Concrete Examples

세부적으로 분석하기 Break It Down

문제 해결하기 및 단순화 하기 Solve / Simplify

되짚어 보기 및 리팩토링 Look Back and Refactor

 

 

문제에 대해 이해하기

이 순서에서는 다음과 같은 질문을 통해 문제에 대해 보다 깊이 있는 이해를 할 수 있다

• 문제를 나만의 방식으로 재정의 할 수 있는가?(문제에 대한 이해)
• 해당 문제의 input 값은 어떤 것인가? (인자로 들어오는 값의 형태)
• 해당 문제의 결과로 어떤 output 값이 나와야 하는가? (해답의 형태)
• input 값에 의해 output 값이 결정 될 수 있는가? 문제를 해결할 충분한 정보가 주어졌는가?
• 해당 문제에서 정말 중요한 핵심 요소는 무엇인가?

 

예시를 통해 살펴보자

1. 문제에 대해 이해하기

// Problem : Write a function which takes two numbers and returns their sum.

  1) 내가 문제를 나의 언어로 재정의 할 수 있는가? Can I restate the problem in my own words?
   -> 합계를 구하라 "implement addition"

  2) 입력값으로 들어오는 것은 무엇인가? What are the inputs that go into the problem?
   - 정수? ints? 
   - 부동소수점? float?
   - 문자열? 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? 
  In other words, do I have enough information to solve the problem?

  5) 문제에서 중요한 핵심요소는 무엇인가?
  How should I label the important pieces of data that are a part of the problem?

 

구체적 예제 떠올리기 Explore Concrete Examples

• 구체적인 case 에서 시작하기 (구체적 case 2~3개 작성하기 또는 해당 case로 해결책 접근하기)
• 조금 더 복잡한 case 생각해보기
• 빈 값(null)과 같은 유효하지 않은 값을 입력하는 edge case에 대해서 생각해보기

2. 구체적 예제 떠올리기

// Problem: Write a function which takes in a string and returns counts of each character in the string

  1) 구체적 case
	charCount("aaaa"); // {a:4}
    
  2) 조금더 복잡한 case
	charCount("hello"); // {h:1, e:1, l:2, o:1}

  3) edge case 생각해보기
	"my phone number is 182763" // 공백과 숫자를 고려해야하는가?
	"Hello hi"// 대문자 및 소문자를 고려해야하는가?
	charCount(""); // 빈 값을 입력한 경우 null, false, undefined 또는 error를 반환해야 하는가?

 

세부적으로 분석하기 Break It Down

• 문제 해결을 위한 단계들을 명확하게 작성해보기

3. 세부 단계 분석

// Problem: Write a function which takes in a string and returns counts of each character in the string

// 구체적 예시
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,
  m: 1,
  n: 2,
  o: 1,
  p: 1,
  r: 2,
  s: 1,
  u: 2,
  y: 1
}

function charCount(str) {
/*
 1) 문제 푸는데 필요한 변수 선언 make object to return at end
 2) 문제를 해결하는데 필요한 핵심 로직 loop over string, for each character...
  2-1) 조건별 분기처리 if the char is a number/letter And is a key in object, add one to count
  2-2) if the char is not a number/letter And is not in object, add it to object and set value to 1
  2-3) 엣지케이스 if character is something else (space, period, etc.) don't do anyting
 3) 결과값 반환 return object at end
 */
}

 

문제 해결 및 단순화 하기 Solve / Simplify

• 이전 단계에서 이미 문제를 해결했을 수도 있고 아직 한 두가지 정도 해결하지 못한 부분이 남아 있을 수 있으므로 이때 단순화 단계를 거침
• 문제를 해결하는데 시간이 많이 소요되는 부분은 우선은 건너뛰기
• 문제를 단순화 하는 과정에서 복잡한 부분을 해결하는데 필요한 실마리를 얻을 가능성이 있음

 

다시 요약하자면 해단 단계에서는

1. 시도하면서 어려운 부분을 찾는다
2. 일시적으로 그 어려운 부분은 넘어간다
3. 단순화된 해결 방법을 적는다
4. 추후 어려웠던 부분을 해결방법에 합친다

 

구체적으로 살펴보자

4. 문제 해결 및 단순화 하기(90% 달성)

/*
1) 정답으로 반환할 객체를 선언 make object to return at end
2) 인자로 들어온 문자열을 반복문을 통해 순회 loop over string, for each character...
3) 변수 char가 숫자 또는 문자이고 result 객체에 해당 키가 존재하면 해당 키의 값을 1 증가 if the char is a number/letter And is a key in object, add one to count
4) 객체에 해당 키가 존재하지 않으면 result 객체에 해당 숫자 또는 문자를 키로 하고 값으로 1을 할당 if the char is not a number/letter And is not in object, add it to object and set value to 1
5) 입력값이 숫자와 문자 외의 공백, 특수문자 등이면 아무것도 하지않음 if character is something else (space, period, etc.) don't do anyting 
6) result 객체를 결과값으로 반환 return object at end
*/

function charCount(str) {
  const result = {};
  
  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;
}

 

되짚어 보기 및 리팩토링 Look Back and Refactor

최종적으로 작성한 코드를 보며 다음과 같이 질문해보자

• 올바른 결과값이 도출되었는가?
• 작성한 방법 외에 다른 방식으로 결과를 도출해내는 방법은 무엇인가?
• 가독성이 좋은 코드인가? 직관적인가?
• 작성한 코드를 다른 문제에도 적용할 수 있을까?
• 작성한 해결책의 성능을 향상시킬 수 있을까? 어떻게 하면 성능을 더 개선시킬 수 있을까? → 시간복잡도 & 공간복잡도 관점에서
• 조금 더 리팩토링 할 수 있지 않을까?
• 다른 사람들은 이러한 문제를 어떻게 해결했을까? → 다른 사람 코드 리뷰해보기

5.되짚어보기 및 리팩토링

// #1 초기 해결코드
function charCount(str) {
  let result = {};
  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;
}

// #2 문자, 공백 등의 조건 고려하여 정규표현식 추가
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;
}

// #3 반복문, 조건문 리팩토링
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;
}

// #4 정규표현식의 성능 고려 charCodeAt 메서드로 변경
function charCount(str) {
  let obj = {};
  for (let char of str) {
    if (isAlphaNumeric(char)) {
      char = char.toLowerCase();
      obj[char] = ++obj[char] || 1;
    }
  }
  return obj;
}

function isAlphaNumeric(char) {
  const 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;
}

 

해당 내용들을 종합하여 아래와 같은 양식을 만들어서 사용하고 있다.