[JS 알고리즘] 문제 해결 방식

알고리즘의 정의와 필요성, 그리고 방법

• 알고리즘이란 무엇인가?
  • 특정 작업을 수행하기 위한 프로세스 또는 일련의 단계를 의미한다.
    
• 왜 알아야 하는가?
  • 프로그래밍과 관련된 대부분의 것들은 항상 일종의 알고리즘을 포함한다. 문제 해결을 잘하고 좋은 개발자가 되기 위해서 기초적인 것이며, 면접에서도 항상 나온다.
• 그러면 어떻게 잘 할 수 있는가?
  1. 문제 해결을 위한 계획을 고안한다.
     1. 문제를 이해한다
     2. 구체적인 예시들을 살펴본다
     3. 설명해본다(break it down)
     4. 풀어보고 단순화한다
     5. 다시 보고 리팩토링한다
  2. 일반적인 문제 해결 패턴을 마스터한다.

1단계: 문제 이해하기

• 면접에서 문제를 풀기 위한 단계
  1. 문제를 자신의 말로 다시 설명할 수 있는가?
  2. 문제에 들어가는 입력은 무엇인가?
  3. 문제에 대한 솔루션에서 나오는 결과는 무엇인가?
  4. 입력에서 출력을 결정할 수 있는가? 다시 말하자면, 문제를 풀기 위한 충분한 정보를 갖고 있는가?
  5. 문제의 일부인 중요한 데이터 조각에 어떻게 레이블을 지정해야 하는가?
• 예시 : 두 개의 숫자를 받아 합계를 반환하는 함수를 작성하라
  1. 더하기를 실행하라
  2. 정수인지 실수인지 수? 숫자의 크기는?(대부분 언어에는 상한선이 있다),
  3. 정수? 실수? 문자열?
  4. 만약 숫자 하나만 입력된다면?

2단계: 구체적인 예시들을 살펴본다.

• 과정
  1. 단순한 예시부터 시작한다.
  2. 복잡한 예시로 진전한다
  3. 빈 입력값과 관련된 예시를 살펴본다
  4. 잘못된 입력값과 관련된 예시를 살펴본다.

3단계: 분해한다. 설명한다(break it down)

• 진행해야 할 단계들을 명시적으로 써본다.
  • 이렇게 하면 코드를 작성하기 전에 작성할 코드에 대해 생각해야 하며, 자세히 알아보기 전에 개념적 문제나 오해가 남아 있는 부분을 파악하고 세부 사항(예: 언어 구문)에 대해서도 살펴보게 된다.

4단계: 문제를 풀고 단순화하기

• 과정
  • 하려는 일의 핵심적인 어려운 점을 찾고
  • 그 어려운 부분을 일단 일시적으로 무시하여
  • 우선 단순화된 솔루션부터 작성한다
  • 그런 다음 그 어려운 부분에 대하여 고민하고 결과물을 통합한다
• 예시 : 문자열을 받아서 문자열의 각 문자의 개수를 반환하는 함수를 작성하라.

function charCount(str) {
	// 마지막에 반환할 빈 객체를 만든다
	const result = {};
	// 문자열의 각 문자를 돌면서
	for(let i=0; i<str.length; i++) {
		const char = str[i];
		// 만약 객체에 해당 문자가 이미 들어갔으면, 문자의 개수에 1을 더한다
		if(result[char] > 0) {
			result[char]++;
		}
		// 만약 객체에 해당 문자가 없다면, 객체에 더해주고 값을 0으로 지정한다
		else {
			result[char] = 1;
		};
	// 객체를 반환한다
	return result;
}

5단계 : 되돌아보고 리팩토링하라.

• 리팩토링 체크 리스트
  • 결과를 확인할 수 있습니까?
  • 결과를 다르게 도출할 수 있습니까?
  • 한눈에 이해가 되시나요?
  • 결과나 방법을 다른 문제에 사용할 수 있습니까?
  • 솔루션의 성능을 향상시킬 수 있습니까?
  • 리팩토링할 다른 방법을 생각할 수 있습니까?
  • 다른 사람들은 이 문제를 어떻게 해결했습니까?

function charCount(str) {
  const result = {};
  for (let i = 0; i < str.length; i++) {
    // 모두 소문자로 통일한다
    const char = str[i].toLowerCase();
    // 영문자와 숫자인 경우만 처리하도록 조건 추가
    if (/[a-z0-9]/.test(char)) {
      if (result[char] > 0) {
        result[char]++;
      } else {
        result[char] = 1;
      }
    }
  }
  return result;
}
console.log(charCount('helloㄴㅇㄹ123'));

• 위 예시를 아래와 같이 리팩토링

function charCount(str) {
  const result = {};
  for (let char of str) {
    // 모두 소문자로 통일한다
    char = char.toLowerCase();
    // 영문자와 숫자인 경우만 처리하도록 조건 추가
    if (/[a-z0-9]/.test(char)) {
      // 값이 이미 있는(truthy) 경우 좌측 실행, 없는 경우(falsey) 우측 실행
      result[char] = ++result[char] || 1;
    }
  }
  return result;
}
console.log(charCount('helloㄴㅇㄹ123'));

• charCodeAt을 사용하여 함수 분리하는 방법으로 또 리팩토링
  • 정규표현식으로 인한 혹시모를 문제를 방지하고, 가독성이 좋다

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

function isAlphaNumeric(char) {
  const code = char.charCodeAt(0);
  if (
    !(code > 47 && code < 58) && // numeric(0-9)
    !(code > 64 && code < 91) && // upper alphabet(A-Z)
    !(code > 96 && code < 123) // lower alphabet(a-z)
  ) {
    return false;
  }
  return true;
}

console.log(charCount('helloㄴㅇㄹ123'));

• 이런 식으로 리팩토링할 수 있고 이러한 과정이 실력 향상에 중요하다.