[알고리즘] 문제 해결 방법

카테고리 : 컴퓨터 공학
태그: cs · 컴퓨터 공학 · algorithm · 문제 이해하기 · 리팩토링하기

1. 알고리즘의 정의와 필요성

1) 알고리즘

  • 특정 작업을 수행하기 위한 프로세스 또는 일련의 단계
  • 프로그래밍과 관련된 대부분의 것들은 항상 일종의 알고리즘을 포함함 , 좋은 개발자가 되기 위해서 기초적인 것

2. 알고리즘 방법

1) 문제 이해하기

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

function addTwoNumbers(number1, number2) {
  return number1 + number2;
}

// 함수 호출 예제
var number1 = 5;
var number2 = 3;
var result = addTwoNumbers(number1, number2);

console.log(result);

// 1. 더하기를 실행하라
// 2. 정수인지 실수인지 수? 숫자의 크기는?
// 3. 정수? 실수? 문자열?
// 4. 만약 숫자 하나만 입력된다면?

2) 구체적인 예시 찾아보기

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

3) 설명해본다

  • 코드를 작성하기 전에 작성할 코드에 대해 생각해야 하며, 개념적 문제나 오해가 남아 있는 부분을 파악하고 세부 사항에 대해 다시 살펴보게된다.

4) 문제를 해결하고 단순화하는 과정

  1. 핵심적인 어려운 점을 찾는다.
  2. 어려운 부분을 일단 넘긴다.
  3. 단순화된 솔루션부터 작성한다.
  4. 어려운 부분에 대하여 생각하고 결과물을 통합한다.

예제: 문자열을 받아서 문자열의 각 문자의 개수를 반환하는 함수를 작성하라.

function charCount(str) {
  var result = {};

  for (var i = 0; i < str.length; i++) {
    var char = str[i].toLowerCase();
    if (result[char] > 0) {
      result[char]++;
    } else {
      result[char] = 1;
    }
  }
  return result;
}
console.log(charCount("안녕하세요 Abel입니다."));

[Running] node "/workspaces/codespaces-blank/SolvingPatterns.js"
{
  '안': 1,
  '녕': 1,
  '하': 1,
  '세': 1,
  '요': 1,
  ' ': 1,
  a: 1,
  b: 1,
  e: 1,
  l: 1,
  '입': 1,
  '니': 1,
  '다': 1,
  '.': 1
}

[Done] exited with code=0 in 0.043 seconds

5) 리팩토링

  • 리팩토링 체크 리스트
    • 결과를 확인할 수 있는지?
    • 다른 방법으로 결과를 유도할 수 있는지?
    • 한눈에 결과를 이해할 수 있는지?
    • 해당 결과나 방법을 다른 문제에 활용할 수 있을지? (다른 문제나 상황에 활용할 수 있는가?)
    • 솔루션의 성능을 향상시킬 수 있는지? (실행 시간,메모리)
    • 다른 방법으로 리팩토링할 수 있는 방법을 생각할 수 있는지?
    • 다른 사람들은 이 문제를 어떻게 해결했는지?

예제: 영문자와 숫자인 경우만 처리하도록 조건 추가

function charCount(str) {
  var result = {};

  for (var i = 0; i < str.length; i++) {
    var 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("안녕하세요 Abel입니다."));

(1) 리팩토링

function charCount(str) {
  const result = {};
  for (let char of str) {
    char = char.toLowerCase();
    // 영문자와 숫자인 경우만 처리하도록 조건 추가
    if (/[a-z0-9]/.test(char)) {
      result[char] = ++result[char] || 1;
    }
  }
  return result;
}
console.log(charCount("안녕하세요 Abel입니다."));

(2) 리팩토링 : 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("안녕하세요 Abel입니다."));