[알고리즘] 문제 해결 접근법 (자바스크립트)

문제를 해결하기 위한 일련의 단계. 정답이 없음. 해답만이 존재할 뿐

 

문제 해결 접근법

0. 톺아보기

• 문제 이해
• 구제척 예시 탐색
• 문제 세분화
• 문제 해결 및 단순화
• 복기 및 재구성

 

1. 문제 이해 (Understand Problem)

코드를 입력하거나 보드에 작성하기 전 한 걸음 물러서서 직면한 과제를 확실히 이해하는 것. 당연하다고 들릴 수 있겠지만 굉장히 중요하다.

1. 주어진 과제나 질문을 그대로 생각하는 게 아닌, 스스로의 방식으로 치환하여 이해하는 것
2. 문제의 입력과, 내가 도출해내야 할 출력값은 무엇인가?
3. 입력에 의해서만 출력값이 결정되는가?
4. 문제 내부의 중요 데이터는 어떻게 레이블링하는가?

 

2. 구체적 사례 탐색 (Explore Examples)

1. 앞선 문제 이해 과정을 마치고, 입력값과 출력값의 순서대로 예시를 두세 개 작성. 가장 쉬운 사용 예시부터 좀 더 복잡한 예시들까지
2. 사례들을 대입해보며 조건과 규칙을 설계

 

3. 문제 세분화 (Break it Down)

코드 작성 전 문제를 세분화 (Break down). 앞으로 밟아야 할 단계들을 명확하게 작성하는 과정.

면접관이나, 팀원들과의 소통에 있어서도 중요한 과정. 이해되지 않는 부분들을 파악하거나, 이해를 돕게 할 수 있다.

 

예를 들어, 입력받은 문자열의 갯수를 반환하는 함수를 만든다고 할 때의 문제를 세분화해보자.

대문자는 소문자로 카운트하고, 공백 혹은 마침표 등의 특수문자는 제외한다.

function charCount(str){
    // 1. 마지막에 반환할 객체 생성
    // 2. 문자열을 한 글자씩 순회***
        // 한 글자(char)가 문자 혹은 숫자이고 객체의 키에 있다면, 기존 값 +1
        // 한 글자가 객체의 키에 없다면, 그 글자를 키로 추가하고 값을 1로 설정
        // 한 글자가 공백, 마침표 등의 문자 혹은 숫자 이외의 형태라면 무시
    // 3. 객체 반환
}

끝까지 구현을 못했다 하더라도 작업에 대한 전반적인 틀을 이해할 수 있게 된다.

 

4. 문제 해결과 단순화 (Solve & Simplify)

단순화

이해나 구현 과정에서 어려운 부분과 맞닥뜨렸을 때 이를 잠깐 무시하고 단순한 해결책을 작성한 다음, 다시 어려운 부분에 접근하여 통합시키는 과정

 

앞선 문제 세분화 과정에서 본 charCount() 함수의 문제가 될 만한 부분을 살펴보자.

1. 입력받은 문자열의 가장 첫 항목을 어떻게 처리하는가 (루프 처리)
2. 객체의 키-값 조작
3. 대/소문자 변환 메서드 등

function charCount(str){
    // 마지막에 반환할 객체 생성
    var answer = {};
    // 문자열을 한 글자씩 순회***
    for (var i=0;i<str.length;i++){
        var char = str[i].toLowerCase()


        // 한 글자(char)가 문자 혹은 숫자이고 객체의 키에 있다면, 기존 값 +1
        if(answer[char] > 0){
            answer[char]++;
        }
        // 한 글자가 객체의 키에 없다면, 그 글자를 키로 추가하고 값을 1로 설정
        else {
            answer[char] = 1;
        }
        
    }
        // 한 글자가 공백, 마침표 등의 문자 혹은 숫자 이외의 형태라면 무시
            // 영문자, 숫자를 전부 포함한 배열을 만들어 특수문자를 필터링
            // 정규표현식을 사용할 수도 있고, ASCII 코드를 사용할 수도 있음
    
    // 객체 반환
    return answer
}

charCount("Hello")

charCount()의 세분화 단계를 따라 코드를 구성해 보았다. 그리고 마지막 특수문자를 필터링하는 과정에서 어느 방법이 최선의 방법인지, 어떻게 구현하는지 등의 문제에 직면할 수 있다. 만약 지금이 면접 상황이라면, 앞선 코드들을 전부 구성한 후 알고 있는 로직들에 대한 조언을 구해 문제를 해결하고 모듈식으로 붙혀 나가 코드를 완성할 수도 있을 것이다.

 

5. 복기 및 재구성 (Look Back & Refactor)

코드 작성을 끝낸 후 각 구성요소를 한 줄씩 살펴보며 마음에 들지 않는 부분이나 코드의 형태, 해석 방법, 얼마나 이해하기 쉬운지에 대해 생각해보는 단계

 

재구성을 위해 던져보기 좋은 질문 몇 가지

• 결과를 다른 방식으로 도출할 수 있는가?
• 해결한 방법 외에 생각나는 다른 접근 방식이 존재하는가?
• 해결책이 얼마나 직관적인가? 코드 내용을 종이나 보드에서 보더라도 이해할 수 있을만한 가독성을 가졌는가?
• 유사한 유형의 문제에 적용, 응용할 수 있는가?
• 해결책의 성능을 향상시킬 수 있는가? (시/공간 복잡도나, 루프의 중첩 등)
• 다른 사람들은 이 문제를 어떻게 해결하는가? 꼭 같은 언어일 필요는 없다. 해당 문제의 해법을 자바스크립트에서 찾을 수 없더라도 자바나 파이썬에서 작성한 코드를 찾아 내 코드와 비교해볼 수 있을 것이다.

 

정규식을 이용하여 charCount() 함수를 재구성해보았다.

function charCount(str){
    var answer = {};
    
    for (var i=0;i<str.length;i++){
        var char = str[i].toLowerCase();

        if(/[a-z0-9]/.test(char)){
            if(answer[char] > 0){
            answer[char]++;
            }
            else {
            answer[char] = 1;
            }
        }
    }
    return answer
}

charCount("Hello there!")

 

기본적인 For loop를 For..of로, If 조건문을 삼항연산 조건문으로 변환하여 보자.

기본 문법으로 문제를 접근하여 단계적으로 리팩터링해 나가는 방법이다.

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

    for (var char of str){
        char = char.toLowerCase();

        if(/[a-z0-9]/.test(char)){
            answer[char] = ++answer[char] || 1;
        }
    }
    return answer
}

charCount("Hello there!")

 

더 나아가 정규표현식을 charCodeAt() 혹은 isAlphaNemeric() 등의 메서드로 대체할 수도 있다. 최근에 발생한 크롬에서의 정규식 에러를 언급하면서 말이다.

---

Javascript 알고리즘 / 자료구조 마스터 (유데미) 강의 수강 후 복습하며 정리한 내용입니다. 원 강의는 이곳에서 수강할 수 있습니다.