서론
알고리즘(algorithm)
특정 작업을 달성하거나 문제를 해결하기 위한 과정이나 일련의 단계
본론에 들어가기 전에 먼저 알고리즘이란 무엇인지 설명하기 위해 알고리즘이 무엇인지 간단하게 한 줄로 정리해 보았다. 알고리즘의 복잡성을 다 설명한 뒤에 이제와서 알고리즘에 대해 무엇인지 정리하는게 좀 늦은감이 있긴 한데... 오늘은 알고리즘 구현을 할 때의 효율적인 다섯가지 단계에 대해서 이야기 해 보려고 하기 때문에 먼저 이렇게 짚고 넘어간다.
본론
어떻게 해야 알고리즘을 더 잘 이해할 수 있는가?
어떤 문제를 보자마자 해결책이 떠오를 수도 있지만, 대부분은 그렇지 않는 경우가 많다. 어려운 문제의 경우에는 문제를 이해하는 것 부터가 난관일 때도 있다. 오늘은 이런 모든 상황에서 알고리즘을 더 잘 이해할 수 있는 방법들에 대해서 이야기 해 보려고 한다. 큰 바위도 조각을 내서 운반하면 쉽게 움직일 수 있다. 이와같이 알고리즘을 더 잘 이해하기 위해서는 단계별로 차근차근 문제를 분해하고 재조립하면서 진행할 필요가 있다.
내가 듣는 강의에서는 문제해결의 다섯가지 접근법을 다음과 같이 소개했다.
- 문제를 이해하기
- 경계조건들을 생각하며 구체화하기
- 문제를 세분화하기
- 문제 해결/단순화
- 되돌아보기와 리팩토링
이 다섯가지 접근법을 사용해서 이전에 풀었던 문제를 다시 한 번 풀어보기로 하겠다.
완주하지 못한 선수
validarity : 100%
language : javascript
link : 코딩 테스트 고득점 kit > 해시 > 완주하지 못한 선수
1단계 문제를 이해한다.
기본적으로 이 문제를 읽고 나의 방식으로 생각해 보는 단계이다.
이 문제는 참가한 선수(participant)와 완주한 선수(completion)의 이름이 배열로 주어질 때 완주하지 못한 선수의 이름을 출력하도록 요구하고 있다.
문제의 입력값을 보고 출력값을 확인해 보자. 위의 프로그래머스의 코딩 테스트 문제에서는 입력값과 출력값에 대한 정보가 잘 나와있다.
그럼 이 데이터를 가지고 우리는 두 배열을 데이터로 받아 서로 비교하고 그 중 맞지 않는 것을 문자 데이터로 출력해야 한다는 사실을 파악할 수 있다. 이렇게 문제를 이해하게 되는 것 만으로 벌써 몇 가지의 해결방법들이 머리에 떠올랐을 것이다. 일단 그 해결방법들을 저장해 두고 다음 단계로 넘어가 보자.
2단계 경계조건들을 생각하며 구체화한다.
이 단계는 한마디로 예외들을 생각해보는 단계이다. 다양한 입력값이 들어올 수 있다. 예를 들어, 위의 문제에서는 동명이인의 데이터가 들어왔을때 어떻게 처리해야하는지 고려해 봐야한다. 그 외에 이 문제가 아니더라도 현실에서는 문자를 입력받아 데이터를 출력해내는 기능에서 숫자데이터나 특수문자가 들어오는 상황이 생기기도 한다. 그럴때에는 어떻게 처리해야하는가? 또 null이나 undefined 데이터가 들어오면 어떻게 처리해야하는가? 이런 식의 예외상황을 상정하며 그것들을 어떻게 해결할 것인지를 이 단계에서 실행한다.
3단계 문제 세분화
아직 코드를 작성할 때가 아니다. 방금 문제를 이해하는 단계를 거치면서 어떤식으로 문제를 해결할지 해결방법들이 떠올랐을 것이다. for루프를 이용하거나 hashmap을 이용하거나 등등 이와같이 머릿속에 떠오른 과정들을 주석으로 작성한다.
function solution(participant, completion) {
//답을 담을 변수 생성
//두 배열을 체크하기위해 map 생성
//checkmap에 participant데이터가 존재하면 +1
//checkmap에 participant데이터가 존재하지 않으면 새롭게 set
//checkmap에 compeltion의 데이터가 존재하면 -1
//checkmap의 데이터가 1이상인 것을 return
}이렇게 말이다! 나는 이런식으로 map을 생성해 참가자의 이름을 모두 넣고 count를 증가시켰으며, 완주자의 이름과 비교해 완주했다면 count를 감소시켰다. 마지막으로 그렇게해서 1이상인 사람의 이름을 체크해 반환했다.
4단계 문제해결 혹은 단순화
이제 여기까지와서 문제 해결방법을 알았다면 코드를 작성해도 된다. 만약 아직도 모르겠다면 문제를 단순화하여 쉬운 문제부터 해결하고 통합 할 수도 있다. 나는 다음과 같이 문제를 해결했다.
function solution(participant, completion) {
var answer = '';
var checkMap = new Map();
participant.forEach(data=>{
if(checkMap.get(data)!=null){
checkMap.set(data, checkMap.get(data)+1);
}else{
checkMap.set(data, 1);
}
});
completion.forEach(data=>{
checkMap.set(data, checkMap.get(data)-1);
});
participant.forEach(data=>{
if(checkMap.get(data) >= 1){
answer = data;
}
});
console.log(checkMap);
return answer;
}이렇게 작성해도 문제없이 잘 실행이 된다. 하지만 여기서 끝이 아니다. 5단계 되돌아보기와 리팩토링이 있다. 5단계는 내일 게시글에 이어서 해 보려고 한다.
참고
