[알고리즘] 문제 해결 접근법
알고리즘이란?
특정 작업을 수행하기 위한 프로세스 또는 일련의 단계. 즉, 우리가 알고리즘 문제를 푼다는 것은 특정 작업을 위한 프로세스를 수립하는 일이 된다. 예를 들자면, 두 수를 덧셈하라는 문제(작업) 를 받았다고 가정해보자. 그렇다면 두 자리를 덧셈하는 함수를 만들고, 결과값을 반환하는 과정이 프로세스일 것이다.
알고리즘 문제를 해결하기 위해서는 어떻게 해야할까?
1. 문제 해결을 위한 계획을 수립
문제에 접근하는 방법, 문제를 세분화하기 위한 전략
2. 일반적인 문제 해결 패턴을 파악
많은 알고리즘들, 특히 면접에서의 많은 문제들을 여러 범주로 나눌 수 있는데, 일부 범주를 식별할 수 있는 경우에는, 도움이 될 몇 가지 조합법을 확보하여 문제 해결을 용이하게 할 수 있다.
이 글에서는 우선 문제 해결 계획을 다룬다.
문제 해결법
- 문제를 이해하기
- 구체적인 예시를 탐색하기
- 세분화하기
- 해결/단순화 하기
- 복습/리팩터링 하기
크게 다섯 단계로 나눌 수 있다. 차례대로 적용해보자.
예시로 사용할 문제는 다음과 같다. 이 문제에 후술할 접근법들을 적용하며 글을 진행해 보겠다.
문자열을 받고, 포함된 문자의 갯수를 구하는 함수를 작성하시오. 이 때 공백은 무시한다.
문제를 이해하기
1. 나의 말로 다시 문제를 정의할 수 있는가?
이미 문제를 읽었지만, 다시 내가 직관적으로 이해할 수 있는 말로 표현해보자. 질문을 받으면 그대로 생각하는게 아니라, 나만의 방식으로 바꿔서 질문이 무엇인지를 실제로 이해하는 것이다.
나는 '문자열에 포함된 각 문자 갯수 세기' 정도로 정의해보았다.
2. 문제에 들어가는 입력값은 무엇인가?
문자열, 또는 문자 (str, char)
3. 문제 해결에서 도출되어야 할 출력값은 무엇인가?
단순히 숫자라고 생각하면 어떤 문자가 몇 개인지 알 수 없으므로 객체를 사용하겠다.
4. 입력을 통해 출력을 결정할 수 있는가? 다시 말해, 문제를 해결하기에 충분한 정보가 있나? (문제 해결을 시작하기 전까지는 이 질문에 답할 수 없을 수도 있다. 하지만 이 초기 단계에서 이 질문을 고려할 가치가 있다.)
문자열 또는 문자(str, char형)가 입력값으로 들어온다고 했지만, 그렇다면 #$@등의 특수문자, 공백을 받았을 경우 어떻게 처리될 것인가? null을 반환할 것인가? 이에 대해 충분한 정보가 없다고 볼 수 있다. 코딩테스트나 면접의 경우 구체적인 조건에 따라 다르기 때문에 상황에 따라 한 번 점검해보자. 여기서는 공백을 포함하지 않는다고 했기 때문에, 공백의 경우 객체에 추가하지 않는 로직이 필요할 것이다.
5. 문제의 핵심인 중요한 데이터들을 어떻게 라벨링할 것인가?
무엇이 중요한 지 생각부터 해보자. 우리에게 필요 한 것은 입력문자열과 출력값 이 두 가지이다. 예를 들어, charCount 함수에 인수인 str 문자열 변수를 받는다. 그리고 {문자 : 갯수} 형태의 객체 result를 반환할 것이다.
구체적 예시 살펴보기
- 쉬운 예시부터 시작하기
- 더 복잡한 예시로 발전시키기
- 빈 입력값의 예시를 살펴보기
- 잘못된 입력값의 예시를 살펴보기
charCount("hi") // { h:1, i:1}
charCount("hi I'm yujin") // {h:1, i:1, I:1, ':1, y:'1', ...}
// 복잡한 예시를 통해, 공백을 무시하고 대소문자를 적용할 것임을 알게 됨
charCount("") // {}
이처럼 복잡한 입력값과 예시를 알아봄으로써 문제를 이해하고 단순화하며 질문을 보다 잘 이해할 수 있을 것이다.
이러한 예시들은 우리가 문제를 해결하기 전에 문제를 더 이해하는 다른 방식일 뿐이다.
단계 세분화 하기
아주 세세하게 작성할 필요도 모든 라인마다 작성할 필요도 없다. 그저 해결책의 기본적인 구성 요소만 작성함으로써 코드를 실제로 입력하기 전에 한 번 생각해볼 수 있게 해준다. 이로써 감이 잡히지 않거나 이해되지 않는 부분들을 파악하거나 이해할 수 있게 해준다. 메모장에 쓰면서 해도 될 것이고, 주석으로 써도 되고 편한대로 하면 된다.
예시를 쓴 뒤 간단하게 단계를 나눠본다.
charCount("aaaa");
// {a : 4}
charCount("졸졸시냇물");
/*{
졸:2,
시:1,
냇:1,
물:1,}
*/
charCount("Hi I'm yujin");
/*{
H: 1,
i: 2,
I: 1,
':1,
m:1,
y:1,
u:1,
j:1,
n:1
}*/
function charCount(str) {
//나중에 반환한 객체 result 선언
//str를 순회하며 result에 문자 담음
//return 객체
}코드를 쓸 수 있도록 더 구체적으로 써본다.
function charCount(str) {
//나중에 반환할 객체 result 선언
// str을 for-of로 순회하면서 키를 검사, result에 문자 담음
// 문자가 객체의 키에 없다면
// 문자가 공백이 아닌 모든 글자일 시 값을 1로 지정 result[char] = 1;
// 문자가 객체의 키에 있다면
// 값에 1 더하기 result[char]++;
//return 객체
}해결 / 단순화 하기
function charCount(str) {
//나중에 반환할 객체 result 선언
let result = {};
// str을 for-of로 순회하면서 키를 검사, result에 문자 담음
for (let char of str) {
console.log(char);
// 공백이면 담지 않기
if (char !== " ")
if (char in result) {
// 문자가 객체의 키에 있다면
// 값에 1 더하기 result[chat]++;
result[char]++;
} else {
// 문자가 객체의 키에 없다면
// 문자가 공백이 아닌 모든 글자일 시 값을 1로 지정 result[char] = 1;
result[char] = 1;
}
}해결한다 하더라도 아직 한 단계가 남아있다. 때로 전체 문제를 해결할 준비가 되지 않은 경우이다. .아직 어떻게 해야 할지 확신이 들지 않거나 정말 어려운 문제가 한 두 가지 정도 남아있을 때, 단순화를 떠올리는 것이다.
즉, 문제를 해결할 수 있다면 해결하고 해결할 수 없다면 더 단순한 문제를 해결하라는 뜻이다. 모든 문제를 해결하려 하면 문제의 어려운 부분에 가로막혀 진도를 나가지 못할 것이다.
예를 들어, 대소문자를 구별하지 않고 소문자만 출력값으로 내보내야한다는 조건이 추가 되었을 때, 대문자를 소문자로 바꾸는 메서드나 방법이 떠오르지 않을 지도 모른다. (*) 그 때는 그냥 무시하고, 기본 로직부터 시작하여 해당 조건을 나중에 처리할 수 있다. 또한 컴퓨터를 사용할 수 있다면 이런 작은 문제 - 대문자 소문자로 바꾸기 - 를 검색해보면 그만일 것이다.
function charCount(str) {
//나중에 반환할 객체 result 선언
let result = {};
//str을 소문자 문자열로 변경..? (*)
// str을 for-of로 순회하면서 키를 검사, result에 문자 담음
for (let char of str) {
console.log(char);
// 공백이면 담지 않기
if (char !== " ")
if (char in result) {
// 문자가 객체의 키에 있다면
// 값에 1 더하기 result[chat]++;
result[char]++;
} else {
// 문자가 객체의 키에 없다면
// 문자가 공백이 아닌 모든 글자일 시 값을 1로 지정 result[char] = 1;
result[char] = 1;
}
}
return result;
}설령 가로막는 어려운 부분이 있더라도 해당 부분을 다시 통합해야 한다는 것을 염두에 두고 가능한 작업을 수행하기 위해 코드를 작성하는 편이 낫다.
보통 문제를 단순화하는 과정에서 실제 해결책을 깊이 이해하고 문제의 어려운 부분을 파악하면서 점차 해결되기 시작한다.
수행하려는 작업에서 혼란에 빠트리는 가장 어려운 부분을 찾게 된다면 잠깐 동안 어려운 부분을 무시하고 단순한 해결책을 작성한 다음, 어려운 부분을 가능하다면 다시 통합시킨다. 그리고 그 과정 중 보통 이 단계에서 이 부분이 어떻게 작동하는지 이해하게 된다.
만일 이를 통해 몇 퍼센트를 달성한 후에 해결책을 보거나 질문을 한다면, 시작하기도 전에 문제에 가로막히는 것보다는 훨씬 도움이 될 것이다.
복습/ 리팩토링 하기
이때 얻은 해결책이 좋든 형편없든 되돌아보고 미비한 부분을 다시 정리해야 한다. 필요한 작업을 수행할 만큼 작동이 잘 되는 해결책을 얻었다면 놀고 싶은 충동이 들 것이다. 제대로 작동하는 해결책만으로도 처리를 할 수 있는데 왜 해야하나 싶을 수 있다. 그러나, 코드를 향상시키고자 노력하는 것은 정말 중요하다.
시간을 내어 코드를 살펴보고, 되돌아보고, 성찰하지 않는다면 성장할 수 있는 기회와, 학습의 능률을 높힐 적절한 때를 놓치게 될 것이다. (일주일 전에 먹었던 점심 메뉴를 기억하는가?)
각 구성요소를 한 줄씩 살펴 보면서 마음에 들지 않는 부분이나, 코드의 형태, 해석 방법, 또 이해하기 얼마나 쉬운지에 대해 스스로 자문해보자. 대체로 효율성과 가독성이라는 두 기둥 사이에 균형을 맞춰야 할 필요가 있다.
해결책을 완성했다면 제대로 작동한다는 데에 자부심을 가져도 좋다. 이상적이지 않은 부분에 더 나은 방법을 적용할 수 있는 방법들을 검색해보자.
리팩토링 질문리스트
결과를 확인할 수 있는가?
- 코드가 제대로 작동하는 지 확인한다.
결과를 다른 방식으로 도출할 수 있는가?
- 해결한 방식 외에 다른 접근 방식이 있는가?
- 앞서 생각하지 못한 다른 방법을 적용할 수 있는가?
한 눈에 보고 이해할 수 있나?
- 해결책이 얼마나 직관적인가?
- 코드의 내용을 화이트보드나 글로 봤을 때도 바로 이해 가능한가?
결과나 방법을 다른 문제에도 적용할 수 있을까?
- 문제를 해결함으로써 얻을 수 있는 큰 이점 중 하나는 직감을 발달시켜 다른 문제를 해결할 수 있는 직관력을 길러준다는 것이다. 따라서 해결책을 작성할 때 잠시 이 해결책이나 이 문제가 이전 접했던 다른 문제와의 유사점이 있는지 생각해보자.
해결책의 성능을 향상 시킬 수 있는가?
- 시간 복잡도와 공간 복잡도를 고려해보자.
- 루프문을 검사하는 것으로 쉽게 고려할 수 있다. 과하게 중첩된 루프는 오랜 시간을 소요하게 한다.
코드를 향상시킬 수 있는 다른 방법을 떠올릴 수 있는가?
- 스타일 지침을 따라 코드를 작성했는가
- 언어의 규칙에 맞게 작성하였는가
다른 사람들은 이 문제를 어떻게 해결하였는가?
- 다른 사람들이 같은 문제를 어떻게 해결했는지를 보면 많은 것을 배울 수 있다. 새로운 개념과 다른 접근법을 탐색함으로써 실력을 높일 수 있다.
리팩토링 예시
function charCount(str) {
//나중에 반환할 객체 result 선언
let result = {};
//str을 소문자 문자열로 변경 (1)
lowerStr = str.toLowerCase();
// str을 for-of로 순회하면서 키를 검사, result에 문자 담음
for (let char of lowerStr) {
// 공백이면 담지 않기
if (char !== " ") result[char] = ++result[char] || 1;
// 키가 있으면 1을 더하고, 키가 없으면 값을 1로 지정하기 (2)
}
return result;
}1. 소문자 문자열로 변경하는 메서드를 통해 영문 소문자와 다른 문자들을 포함하게 하였다. 이 때 함수형 프로그래밍 관점에서 원본 문자열은 훼손하지 않았다.
2. 첫번째 truthy를 반환하는 || 연산자를 통해 코드의 길이를 줄였다.
이 때까지 문제 해결 접근법에 대해 알아보았다. 다음 시간에는 문제 해결 패턴을 다루어 보겠다.