1.3Problem Solving Approach

What is an Algorithm?

A process or set of steps to accomplish a certain task.
어떤 작업을 수행하기 위한 절차 또는 일련의 단계를 의미한다.

알고리즘 작성 실력을 늘리는 방법

1. 문제 해결을 위한 계획을 세운다.
2. 자주 등장하는 문제 해결 패턴을 마스터한다.

이번 포스팅에선 1번, 즉 문제 해결을 위한 계획 수립에 대해 알아보자.

Plan for solving problems

문제 해결 계획의 큰 그림은 아래와 같다.(강의에선 George Polya의 『How to Solve It』에서 영감을 받았다고 밝힌다):

1. Understand the Problem(문제를 이해하라)
2. Explore Concrete Examples(구체적인 예시를 탐색하라)
3. Break It Down(문제를 분해하라)
4. Solve/Simplify(문제를 해결하거나 단순화하라)
5. Look Back and Refactor(돌아보고 리팩터링하라)

1. Understand the Problem

실전이나 코딩 테스트나 연습이나 언제나 시간 제약이 있기 때문에, 문제를 맞이했을 때 바로 코드를 쓰려는 유혹이 있다. 하지만 잠시, 그 전에 다음 질문들을 스스로에게 던져 문제를 충분히 이해했는지 확인하자.

1. 문제를 내 말로 바꿔 설명할 수 있는가?
2. 입력값은 어떤 형태인가?
3. 출력값은 어떤 모습이어야 하는가?
4. 입력값 만으로 출력값을 유도할 수 있는가?(즉, 필요한 정보가 충분한가?)
5. 문제의 핵심 데이터를 어떻게 이름 지을 것인가?

2. Explore Concrete Examples

보다 구체적인 예시를 생각해보면 문제를 더 잘 이해할 수 있다. 또 유효성 검사, 예외 처리, 로직 설계 등을 미리 점검하는데 도움이 된다.

• 단순한 예시로 시작하기
• 점점 복잡한 예시로 확장하기
• 빈 인풋을 받았을 때의 예시 생각해보기
• 유효하지 않은 인풋을 받았을 때의 예시 생각해보기

예를 들어, 문자열을 받아 문자열의 각 문자들이 얼마나 많이 쓰였는지 반환하는 함수를 쓴다고 생각해보자.

javascript
// 단순한 예시
charCount("aaaa") // {a:4}
charCount("hello") // {h:1, e:1, l:2, o:1}
// 복잡한 예시
charCount("my phone number is 123456") // 숫자도 따로 표현해야 하나??
charCount("Hello") // {H: 1...} 대문자 구분이 필요했던가??
// 빈 인풋
charCount("") // 이런 경우에는 에러를 반환해야하는지, 빈 객체를 반환해야하는지?

문제를 해결하는 상황에 따라 숫자가 포함되어야 하거나, 대소문자 구분이 필요없다거나, 빈 입력값이 들어올 수 없을 수 있다. 무작정 코딩을 시작했다간 중간에 요구사항을 재확인하면서 전체 코드를 다시 작성하게 될 수도 있다.

처음부터 다양한 예시를 충분히 고려하고 대응 방식을 정해두는 것이 중요하다.

3. Break It Down

코드를 본격적으로 쓰기 전에, 문제 해결을 위해 거쳐야 하는 단계들을 명시적으로 적어보자. 이는 사고의 공백을 메워주고, 본격적인 구현 시 시행착오를 줄여준다.

예를 들어, 위의 charCount 함수를 쓴다고 해보자.(숫자는 없고, 대소문자 구분도 필요 없는 상황)

javascript
function charCount(str){
  // 마지막에 반환할 객체 만들기
  // 문자열 안에서 루프 돌리기
    // 문자가 알파벳이라면...
      // 문자가 객체의 키에 있으면 카운트에 1 더하기
      // 문자가 객체의 키에 없다면 키 만들고 카운트를 1로 설정하기
    // 문자가 알파벳이 아니라면(공백, 점 등) 넘어가기
  // 객체 반환하기
}

이처럼 pseudo-code 또는 그 이하 수준의 단계 정리만으로도 문제 해결 흐름을 명확히 잡을 수 있다.

4. Solve Or Simplify

준비가 되었으면, 문제를 해결하자!...

다만 문제를 해결하는 것은 말처럼 쉽지 않을 것이다. 만약 위의 절차를 따랐는데도 해결이 어렵다면, 쉬운 문제부터 풀자.

• 하려는 일의 핵심 어려움(core difficulty)이 무엇인지 찾자.
• 잠시동안 해당 문제를 무시하고, 해당 문제를 제외한 부분들부터 푼 후 돌아가자.

복잡한 문제는 단순한 부분부터 공략하는 것이 효과적이다.

5. Look Back and Refactor

리팩토링 시에는 아래의 질문들을 스스로에게 던져보자:

• 결과를 확인할 수 있는가?
• 다른 방식으로 결과를 얻을 수 있는가?
• 딱 보면 코드를 이해할 수 있는가?
• 다른 문제에도 이 방법을 쓸 수 있는가?
• 해결책의 성능을 향상시킬 수 있는가?
• 리팩토링할 수 있는 다른 방법을 생각할 수 있는가?
• 다른 사람들은 어떻게 풀었는가?