알고리즘 문제 해결 접근법

호떡집사·2024년 8월 27일

JavaScript algorithm 알고리즘

알고리즘

목록 보기

3/8

알고리즘 (algorithm)

문제 해결 방법을 정의한 '일련의 단계적 절차'이자 어떠한 문제를 해결하기 위한 '동작들의 모임'이다
출처 : wiki

즉, 문제 해결 위해 수행해야 하는 일련의 과정 및 단계

🧐 어떻게 접근해야 할까?

문제 해결을 위한 계획 수립
일반적 문제 해결 패턴 파악

🔎 문제 해결 단계

EX)
문자열을 받아 각각의 문자의 갯수를 출력하는 charCount 함수를 작성하시오
(단, 대소문자 구분 없음)

1️⃣STEP 01 - 문제 이해

자신만의 방식으로 바꿔서 이해 가능한가?
그 문제의 입력값(input)이 무엇인가?
->입력값의 형태 등등
문제 해결을 위한 결과(output)는 무엇인가?
-> 출력 값의 형태 등등
입력값이 출력값을 결정할 수 있는가?
->문제 해결을 위한 충분한 정보를 알고,갖고 있는가?
문제의 중요한 부분이 무엇인지 아는가? 해당 부분을 어떻게 명칭하는가?

2️⃣STEP 02 - 구체적인 예시

간단한 예제로 시작 해서 복잡한 예제로
빈 입력값
-> 유효하지 않는 입력값이 주어진 상황 유용
유효하지 않은 입력값

charCount('aaaA'); // {a:4}
charCount('Hi~ Hello World! 1223');
/*
{
  h: 2,
  i: 1,
  e: 1,
  l: 3,
  o: 2,
  w: 1,
  r: 1,
  d: 1,
  1: 1,
  2: 2,
  3: 1
}
*/

3️⃣STEP 03 - 문제의 세분화

기본적 구성요소 작성
➡️ 감이 잘 잡히지 않거나 이해되지 않는 부분들을 파악하는 데 도움이 된다

const charCount = (str) => { // 기본적 구성 요소
  // 실행 과정
  // 리턴 : 객체, 각각의 키는 소문자, 값은 숫자, 특수문자 공백 제외
}

function charCount (str)  { // 세분화
   [시작] => 객체 생성
   [과정] => 
       string 문자열 순회하며 각각의 문자 처리
       문자가 숫자/문자 && 객체 안에 없을 경우 => object의 key로 설정 후 +1
       문자가 숫자/문자 && 객체 안에 있을 경우 => 해당 숫자/문자의 key로 값을 찾아 +1
       문자나 숫자가 아닌 공백,마침표 등등 일 경우 카운팅 하지 않는다
   [끝] => 객체를 반환한다
};

4️⃣STEP 04 - 해결 / 단순화

이전 일련의 과정을 통해 문제 해결
당장 해결하지 못한다면 단순화 부터
➡️ 다른 문제 해결을 위해 시간이 많이 소요되는 부분을 배제하여 단순화 시킴
➡️ 문제를 단순화 하는 과정(동작 방식의 이해)에서 문제의 어려운 부분을 파악하면서 다시 통합



function charCount(str) {
  // 시작 => 객체 생성
  const result = {};
  // 과정 => string 문자열 순회하며 각각의 문자 처리
  for (let i = 0; i < str.length; i++) {
    // 영대문자 -> 영소문자
    const char = str[i].toLowerCase();

    // 문자나 숫자가 아닌 공백,마침표 등등 일 경우 카운팅 하지 않고 다음 문자열 체크
    if (/[`~!@#$%^&*()_|+\-=?;:'",.<>\{\}\[\]\\\/ ]/gim.test(char)) continue;

    if (result[char] > 0) { // 문자가 숫자/문자 && 객체 안에 없을 경우 => object의 key로 설정 후 +1
      result[char]++;
    } else { //문자가 숫자/문자 && 객체 안에 있을 경우 => 해당 숫자/문자의 key로 값을 찾아 +1

      result[char] = 1;
    }
  }
  // 끝 => 객체를 반환한다
  return result;
}


console.log(charCount('aaaaa~~~~bbb**(@@ccccccccccc!!!!&&&    dddddd'));  //{ a: 5, b: 3, c: 11, d: 6 }

5️⃣STEP 05 - 검증 및 재구성(리팩토링)

결과 확인했는가?
결과를 다른 방식으로 도출 할 수 있는가?
한눈에 알아보고 이해할 수 있는가?
해결책을 다른 문제에 적용할 수 있는가?
해결책의 성능을 향상할 수 있는가?
➡️ 해결책을 도출하면서 가장 먼저 고려할 부분
다른방식으로 리팩토링 할 방법을 고려할 수 있는 가?
다른 사람들은 어떻게 해결했는가?
➡️ 새로운 접근 방식과 다른 해결책을 알 수 있음

💡 예제 풀이에서 선택했던 정규표현식은 일반적으로 백트래킹으로 일치 여부 판단 , 최악의 경우 O(2^n)의 복잡도를 가짐 (n=정규식 크기) -> 어디까지나 최악의 경우, 까다로운 조건이 아니라면 큰 문제는 없으나 성능 향상을 위해 아래와 같이 시간복잡도 O(1)방식으로 변경 가능

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

function charCount(str) {
  // 시작 => 객체 생성
  const result = {};
  // 과정 => string 문자열 순회하며 각각의 문자 처리
  for (const char of str.toLowerCase()) {
    // 문자나 숫자가 아닌 공백,마침표 등등 일 경우 카운팅 하지 않고 다음 문자열 체크
    if (!isCharNumeric(char)) continue;

    // 문자가 숫자/문자 && 객체 안에 없을 경우 => object의 key로 설정 후 +1
    //문자가 숫자/문자 && 객체 안에 있을 경우 => 해당 숫자/문자의 key로 값을 찾아 +1
    result[char] = ++result[char] || 1;
  }
  // 끝 => 객체를 반환한다
  return result;
}

console.log(charCount('aaaaa~~~~bbb**(@@ccccccccccc!!!!&&&    dddddd')); //{ a: 5, b: 3, c: 11, d: 6 }