알고리즘 문제 해결 접근법

ALGORITHM · 11 Nov 2022

해당 내용은 UDEMY의 알고리즘 ∙ 자료구조 강의를 수강 후 정리한 내용입니다.

알고리즘이란?

특정 작업을 달성하기 위한 과정이나 일련의 단계. 즉, ‘일련의 단계’의 의미를 가리킵니다. 프로그래밍 수행 시 하는 모든 작업에 일종의 알고리즘이 들어가게 되므로, 알고리즘을 알아야 두어야합니다.

알고리즘을 잘 이해하기 위해서 문제 해결 과정을 수립하고, 일반적인 문제 패턴들을 파악해야 합니다. 그리고 문제 해결 과정으로는 아래와 같은 순서들이 존재합니다.

문제 이해하기
구체적인 예시 알아보기
문제 세분화 하기
문제 해결 및 단순화하기
문제 복습 및 재구성하기

문제의 이해

문제의 해결에 있어서 새로움을 맞닥뜨리고 이를 해결하는 것이 가장 어렵습니다. 그래서 단게별 지침을 통해 계획을 수립할 필요가 있습니다.

문제를 풀기 시작하기에 앞서 이를 이해하는 과정이 훨씬 중요한데, 이는 문제의 해결을 정의하는 데에 큰 도움이 됩니다. 문제 이해의 과정에서 중요한 것은 아래와 같은 사항들이 있습니다.

문제를 그대로 생각하는 것이 아니라 나만의 방식으로 바꿔서 질문이 무엇인지 실제로 이해하기
문제의 입력값과 그에 따른 올바른 출력값을 파악하기
주어진 입력값만으로 출력값을 가져올 수 있는 지 확인하기
데이터의 중요한 부분에 라벨링을 하기

예를 들어, ‘두 개의 숫자를 더해 결과를 만드는 함수를 설정’하는 경우, 아래와 같은 사항들을 고려해서 문제를 이해해볼 수 있습니다.

두 개의 큰 숫자를 더하려는 경우, 자바스크립트는 Infinity라는 값을 보여주고 계산을 포기하게 됨
하나는 String, 하나는 Number로 설정된 두 값의 합에 대해서는 제대로 된 결과를 보여주지 못함
두 개의 값이 들어와야 하는 상황에서 하나의 값만 입력될 경우, 어떻게 처리할 지에 대한 문제가 발생함
라벨링을 위해서 add, num1, num2와 같은 값들을 설정하게 됨

구체적인 예시 알아보기

예시를 통해 온전한 검사를 수행해볼 수 있고, 예시를 적용해 많은 정보를 얻을 수도 있습니다.

예시를 알아보는 순서로는 ‘쉬운 예시로부터 복잡한 예시의 방향으로 진행’하는 것과 ‘빈 입력값 또는 유효하지 않은 입력값이 주어진 상황 살펴보기’가 있습니다.

예시로 ‘문자열에서 각 문자의 수를 반환하기’를 하는 상황이 주어졌을 때 아래와 같은 것들을 살펴볼 수 있습니다.

문자 수 객체가 미리 주어지는 상황인지, 직접 찾아가며 객체에 넣어주어야 하는지 여부 확인

'aaaa' {a: 4} or {a: 4, b: 0 ... }
"hello" {h: 1, e: 1, l: 2, o: 1}

대소문자에 대한 구분 여부 확인

"Hello" {H: 1} or {h: 1}

빈 입력값 또는 부적절한 값이 들어오는 경우 → null, false, error 등이 나오게 하기

위와 같은 예시들은 실무를 할 때에도 확실하게 상황을 분리하는 데에 도움이 됩니다. 복잡한 입력값과 예시를 입력해 문제에 대해 더 잘 이해할 수 있습니다.

세분화하기

문제에 대한 단계를 실제 작성하면서 나누는 단계입니다. 이 단계를 통해 아래와 같은 이점들을 얻을 수 있습니다. 실제 면접의 경우에도 제 시간 내에 풀 수 없는 문제가 출제되고, 흐름을 보는 경우가 존재하기 때문에 세분화를 통해 먼저 단계를 나눠보는 것이 좋은 습관이 될 수 있습니다.

코드를 실제 작성하기 전에 상상을 해 볼 수 있음
이해되지 않는 부분에 대한 이해를 도움
확신이 들지 않는 부분에 대해 확신을 위한 작업을 할 수도 있음
의사코드, 유사코드를 작성하여 전체적인 흐름을 확인하고, 접근 방식을 명확히 할 수 있음

문제 해결하기 ∙ 단순화하기

실제로 문제를 해결하는 부분입니다.

단순화란 해결하기 어려운 부분을 맞닥뜨렸을 때, 단순한 해결책을 작성하고 다시 어려운 부분에 통합하는 과정을 의미합니다. 단순화를 하는 과정이 어려운 부분을 해결하는 데에 도움을 줄 수 있습니다. 문제 해결 시 단순한 부분을 처리하고, 이후 어려운 부분과 통합할 것임을 염두에 두어야 합니다. 보통 어려운 문제의 해결 시 문제 단순화 과정을 통해 실제 해결책을 깊이 이해하고 어려운 부분에 대한 해결도 이루어지게 되기 때문입니다.

이전 예시(문자열의 각 문자 구하기)를 현재 단계에서 다시 살펴보면, 아래와 같은 코드가 나오게 됩니다. 우선 의사 코드(주석처리된 부분들)에 맞춘 코드를 작성하고, 예외처리가 제대로 되지 않을 수 있는 부분(대 ∙ 소문자, 특수문자 등)에 대해 처리하여 코드 작성이 이루어졌습니다.

이 때, 코드의 성급한 작성보다는 페이지에 작성해서 되길 바라되, 어려운 부분들을 파악하고 올바른 부분들에 바로 연결할 수 있도록 하는 것이 좋습니다.

const charCount = (str) => {
  // 마지막에 리턴할 객체 생성
  const result = {};
  const checkRegex =
  // 문자열을 순회
  for (let i = 0; i < str.result; i++) {
    const char = str[i].toLowerCase();
    // 문자열이 객체에 있는 경우, 1추가 없을 시 1로 생성
    if (result[char] > 0) {
      result[char] += 1;
    } else {
      result[char] = 1;
    }
  }

  return result;
};

되돌아보기와 리펙터

해결책이 좋은 지에 대한 유무와 상관없이 정리 작업은 개발자의 발전을 위해 항상 이루어져야 합니다. 작동하는 것에 그치지 않고 코드를 향상시키고자 노력하는 것은 항상 중요하기 때문입니다.

리펙터링을 할 때 고려할 사항으로는 아래와 같은 것들이 있습니다.

코드를 한 줄씩 살펴보면서 효율성, 가독성 등을 확인
해결책의 성능을 향상시킬 수 있는 지 고려하기 → 시간 복잡도, 공간 복잡도
다른 사람이 해결한 방식에 대해서 알아보기
작동만 하는 코드보다, 그 코드를 다시 분석해보기

문제를 해결함으로써 직감을 발달시켜 다른 문제를 해결할 수 있는 직관성을 기를 수 있습니다. 이를 위해서 해결책을 작성한 뒤 다른 문제와의 유사점을 찾아야합니다.

const charCount = (str) => {
  const result = {};
  const regexChecker = /[a-z0-9]/;
  // 문자, 숫자를 체크하는 정규표현식을 추가
  for (let i = 0; i < str.result; i++) {
    const char = str[i].toLowerCase();
    if (regexChecker.test(char)) {
      if (result[char] > 0) {
        result[char] += 1;
      } else {
        result[char] = 1;
      }
    }
  }

  return result;
};

for (const char of str) {
  // 리펙토링 작업을 위해 for문을 for of문으로 바꿈
  if (regexChecker.test(char)) {
    if (result[char] > 0) {
      result[char] += 1;
    } else {
      result[char] = 1;
    }
    z;
  }
}

obj[char] = ++obj[char] || 1;
// if else 문에 대한 리펙토링
// obj[char]가 없는 경우 1로 바꾸도록 설정