📖 문제 해결 접근법(Problem Solving Strategies)

우리가 흔히 일상에서도 사용하는 단어 '알고리즘'은 '특정 작업을 달성하기 위한 과정이나 일련의 단계'를 의미한다.

코딩테스트 문제를 풀때도 알고리즘 능력이 필요한데, 알고리즘 능력은 분명 타고난 것도 있을 것이라 생각하지만, 이를 향상시킬 수 있는 방법도 분명 존재한다.

강의에서는 알고리즘 능력을 키울 방법으로 두가지를 제시한다.
1. 문제해결을 위한 계획을 수립하기
2. 일반적인 문제 해결 패턴을 파악하기

이번 포스팅에서는 첫번째 방법인 문제해결을 위한 계획 수립, 즉 문제 해결 접근법에 대해 알아보자.

📌 문제 해결 접근법 5단계

문제 해결 접근법은 다음과 같이 5단계로 나뉘어져 있다.

1. Understand the problem : 문제를 이해하기
2. Explore Concrete Examples : 구체적 예시 탐색하기
3. Break it Down : 세분화하기
4. Solve/Simplify : 문제를 해결하고 단순화하기
5. Look Back and Refactor : 문제를 회고하고 리팩토링하기

📌 Understand the problem : 문제를 이해하기

문제 이해 단계에서 우리는 다음과 같은 물음을 던질 수 있겠다.

1. 질문을 내 방식으로 이해 가능한가?
2. 문제가 어떤 입력값을 담고 있는가?
3. 문제에서 아웃풋은 어떤 형태인가?
4. 입력값이 출력값을 결정할 수 있는가? / 문제를 해결할 충분한 정보가 있는가?
5. 문제의 일부인 데이터의 중요한 부분에 어떻게 라벨지정을 할 수 있는가?

다음 예시를 보면서 물음에 답해보자.

/*
Write a function which takes two numbers and returns their sum.

1. Can I restate the the problems in my own words?
"implement addition"

2. what are the inputs that go into the problem?
 - ints?
 - floats?
 - what about string for large numbers?
 
3. what are the outputs that should come from the solution to the problem?
 - int? float? string?
 
4. Can the outputs be determined from the inputs? In other words, do I have enough information to solve the problem?

5. How should I label the important pieces of data that are a part of the problem?
*/

📌 Explore Concrete Examples : 구체적 예시 탐색하기

예시를 탐색하는 것으로, 우리는 문제를 더 잘 이해할 수 있을 뿐만 아니라, 온전성 검사를 제공하므로 솔루션이 제대로 작동하는지 확인할 수 있을 것이다.

=> 그러므로, 예시를 알고 있다면 구현한 작업을 확인할 수 있을 뿐만 아니라 예시를 적용하면서 더 많은 정보를 습득할 수 있다. (실무에서는 유저스토리나 유닛테스트등을 이용)

구체적인 예시를 살펴보는 단계는 다음과 같다.

1. 가장 쉬운 예시로 시작해서 복잡한 예시로 진행한다.
2. 빈 입력값이 있는 예제를 살펴본다.
3. 유효하지 않은 입력값의 예제를 살펴본다.

다음 예시를 보자.

/*
Write a function which takes in a string and returns counts of each character in the string.

1. 가장 쉬운 예시로 시작하기
charCount("aaaa"); // 출력: {a:4}
charCount("hello"); // 출력: {h:1,e:1,l:2,o:1}

2. 더 복잡한 예시들로 진행하기
charCount("Your PIN number is 1234!");
charCount("Hello Hi");

3. 빈 입력값이 있는 예제를 살펴보기
charCount("");
4. 유효하지 않은 입력값의 예제 살펴보기
charCount(123);
*/

📌 Break it Down : 세분화하기

코드를 작성하기 전에 세분화해보자. 이는 단계의 틀을 잡고 이해되지 않은 것의 이해를 돕는다.

function charCount(str) {
  //do something
  //return an object with keys that are lowercase alphanumeric characters in the string; values should be the counts for those characters
}

//세분화
function charCount(str) {
  //make object to return at end
  
  //loop over string, for each character...
  //if the char is a number/letter AND is a key in object, add one to count
  	//if the char is a number/letter AND not in object, add it to object and set value to 1
  	//if character is something else (space, period, etc..) don't do anything
  //return object at end

}

📌 Solve/Simplify : 문제를 해결하고 단순화하기

문제를 해결하는데 만약 해결할 수 없다면 더 단순한 문제를 해결하자. 이는 문제를 쉬운 문제로 바꾸라는 것이 아니라, 다른 것에 집중하기 위해 시간이 많이 소요되는 부분을 무시하라는 것이다.

여기서 말하는 단순화는, 수행하려는 작업에서 가장 어려운 부분을 찾았다면 어려운 부분은 무시하고 단순한 해결책을 작성 후, 다시 어려운 부분들을 가능하면 통합하는 것이다. -> 이 과정에서 보통 어려운 문제를 이해할 수 있게 될 것이다.

function charCount(str) {
  //make object to return at end
  var result = {};
  //loop over string, for each character...
  for (var i = 0; i < str.length; i++) {
  	var char = str[i].toLowerCase();
  //if the char is a number/letter AND is a key in object, add one to count
  	if (result[char] > 0) {
  		result[char]++;
  	} else {
  	//if the char is a number/letter AND not in object, add it to object and set value to 1
    	result[char] = 1;
  }
}
  	//if character is something else (space, period, etc..) don't do anything
  //return object at end
  return result;
}

📌 Look Back and Refactor : 문제를 회고하고 리팩토링하기

이제 문제를 해결했으니 다음과 같은 질문을 해볼 수 있을 것이다.

1. 결과를 확인 할 수 있는가?
2. 결과를 다른 방식으로 도출할 수 있는가?
3. 한눈에 이해 가능한가?
4. 결과나 방법을 다른 문제에도 적용할 수 있는가?(이전에 접한 문제와의 유사성)
5. 해결책의 성능 향상이 가능한가?(시간, 공간 복잡도의 평가를 통해)
6. 코드를 향상 시킬 수 있는 다른 방법을 떠올릴 수 있는가?
7. 다른 사람은 어떻게 해결했는가?

💪 문제 해결 접근법을 통해 문제 해결해보기

프로그래머스 0레벨 7의 개수
문제를 문제 해결 접근법을 통해 해결해보자.

문제 설명
머쓱이는 행운의 숫자 7을 가장 좋아합니다. 정수 배열 array가 매개변수로 주어질 때, 7이 총 몇 개 있는지 return 하도록 solution 함수를 완성해보세요.

제한사항
1 ≤ array의 길이 ≤ 100
0 ≤ array의 원소 ≤ 100,000

입출력 예
array result
[7, 77, 17] 4
[10, 29] 0

✏️ Understand the problem : 문제를 이해하기

/*

1. Can I restate the the problems in my own words?
정수 배열 array에서 7의 개수 찾아 return하기

2. what are the inputs that go into the problem?
1 ≤ array의 길이 ≤ 100
0 ≤ array의 원소 ≤ 100,000
 
3. what are the outputs that should come from the solution to the problem?
array에서의 7의 개수 > 정수형 데이터
 
4. Can the outputs be determined from the inputs? In other words, do I have enough information to solve the problem?
ㅇㅇ

5. How should I label the important pieces of data that are a part of the problem?
7의 개수 -> sevenCount
*/

✏️ Explore Concrete Examples : 구체적 예시 탐색하기

/*
solution([7, 77, 17]); // 출력: 4
solution([10, 29]); // 출력: 0

2. 더 복잡한 예시들로 진행하기
solution([7,23,476,43,54, 77]); //출력 : 4

3. 빈 입력값이 있는 예제를 살펴보기
solution(""); //출력 : 0

4. 유효하지 않은 입력값의 예제 살펴보기
solution(1de); //Caught SyntaxError: Invalid or unexpected token (
*/

✏️ Break it Down : 세분화하기

function solution(array) {
  //7의 개수를 세기 위한 sevenCount변수를 0으로 초기화한다.
  
  //for문을 array의 길이만큼 돌면서 각 요소를 순회한다.
  //각 요소를 String으로 변환해 temp변수에 담는다.
  //temp의 각 자리가 7인지 아닌지를 확인하고 만약 7이 있으면 sevenCount에 1을 더해준다.
  //sevenCount를 반환한다.

}

✏️ Solve/Simplify : 문제를 해결하고 단순화하기

function solution(array) {
  //7의 개수를 세기 위한 sevenCount변수를 0으로 초기화한다.
  let sevenCount = 0;
  //for문을 array의 길이만큼 돌면서 각 요소를 순회한다.
  for(let i=0; i<array.length; i++){
  //각 요소를 String으로 변환해 temp변수에 담는다.
  	const temp = array[i].toString();	
  //temp의 각 자리가 7인지 아닌지를 확인하고 만약 7이 있으면 sevenCount에 1을 더해준다.
  	temp.split('').map(x=> x === '7' ? sevenCount++ : sevenCount 
   }
  //sevenCount를 반환한다.
  return sevenCount;
}

✏️ Look Back and Refactor : 문제를 회고하고 리팩토링하기

아쉬운 점을 생각해보자면 for문에 map()과 split()이 들어있어 O(n^2)의 시간 복잡도를 가진다는 것이었다.

이렇게 리팩토링하면 O(n)으로 해결할 수 있었다.

function solution(array) {
    return array.join('').split('7').length-1;
}

📘 참고 자료
https://www.udemy.com/course/best-javascript-data-structures/