❓알고리즘이란 무엇일까?
➡ 특정 작업을 달성하기 위한 과정 혹은 일련의 단계
❓알고리즘은 왜 중요할까?
➡ 프로그래밍을 사용하는 거의 모든 작업에는 일종의 알고리즘들이 포함된다. 알고리즘은 문제를 성공적으로 해결하고 좋은 개발자가 되는 기초이다.
그렇다면,
❓어떻게 해야 알고리즘을 더 잘 이해할 수 있을까?
1️⃣ 문제 해결 계획 수립
2️⃣ 일반적 상황에서의 문제 해결 패턴을 마스터한다.
문제 해결 계획 수립
1️⃣ 문제를 이해하기
2️⃣ 구체적인 예시를 파악하기
3️⃣ 문제를 세분화하기
4️⃣ 해결 혹은 단순화하기
5️⃣ 복습(회고) 하고 리팩터링(재구성)하기
문제를 이해하기
"중요한 것은 문제를 이해하는 것이다. 면접에서는 마음이 급해서 당장 무언가를 보여주려고 하지만, 문제가 무엇인지 이해하는 것이 가장 중요하다."
문제를 이해하는데에 도움이 되는 질문들은 다음과 같다.
1️⃣ 문제를 내 방식으로 다시 정의할 수 있나?
2️⃣ 문제에서 입력값은 무엇인가?
3️⃣ 그렇다면, 출력값은 무엇이어야 하나?
4️⃣ 입력값만이 출력값을 결정하나? (=문제해결을 위한 정보가 충분한가?)
5️⃣ 문제의 일부인 데이터의 중요부분에 어떻게 라벨링을 할까? (= 이 문제에서 정말 중요한 것은 무엇인가?)
예시) 숫자 두개를 받아 그 합계를 리턴하는 함수를 만든다면?
1️⃣ 문제를 내 방식으로 다시 정의할 수 있나?
: "implement addition"
2️⃣ 문제에서 입력값은 무엇인가?
: 정수인가? 아니면 자연수만 들어오나? 문자열이나 엄청나게 큰 숫자가 들어온다면?
3️⃣ 그렇다면, 출력값은 무엇이어야 하나?
: 2️⃣와 같은 질문을 할 수 있다. 즉, 정수인가? 아니면 자연수만 들어오나? 문자열이나 엄청나게 큰 숫자가 들어온다면?
4️⃣ 입력값만이 출력값을 결정하나?
: 대부분은 그렇겠지만... 만약 숫자를 하나만 입력하면? 거기에
0을 더해줘야하나 undefined를 리턴해야하나 null을 리턴해야하나
5️⃣ 문제의 일부인 데이터의 중요부분에 어떻게 라벨링을 할까?
: 이 경우에는, 인수로 num1, num2를 전달하고, 리턴값을 sum이 되도록 이름을 지어줄 수 있다.
구체적인 예시를 파악하기
"예시를 드는 것은 문제를 이해하는데에 도움이 된다."
쉬운 예시로 시작한다.
: 가장 쉬운 예시 >>>> 더 복잡한 예시들로 나아간다.
대표적 복잡한 예시들
- 입력값이 유효하지 않은 경우에는?
- 입력값이 비어있는 경우에는?
예시) 문자열을 입력받아 각 문자의 수를 반환하는 함수를 작성한다면?
1️⃣ 가장 쉬운 예시부터 시작 (입력값 : 'aaaa') //{a: 4}
: 의문이 생김. "그렇다면 b~z까지 언급되지 않은 수들은 어떡하지? b:0 , c:0 으로 두면 안되나?"
2️⃣ 더 복잡한 예시 (입력값: 'mu number is 93697712', 혹은 'HelLo')
: "숫자와 띄어쓰기는 어떡하지? 대문자는 어떻게 처리해야하지?"
3️⃣ 빈 입력값이 주어진 경우 (입력값 : '')
4️⃣ 입력값이 유효하지 않은 경우에는? (입력값 : null)
세분화하기
"문제에 대한 단계들을 실제로 수행하면서 작성해본다."
(이 때, 반드시 정확한 의사코드나 구문이 필요한 것은 아니다. 이는 면접관들에게 내가 생각한 접근 방식을 알려주기 위한 의사소통 수단일 뿐이다.)
이는 곧 작성하기 전에 코드를 다시 생각하게끔 만들어주고, 디테일에 걱정하거나 몰두하기 전에 잘못 이해하고 있는 부분들을 알 수 있게 해준다.
예시) 위와 같은 예시 - 문자열을 입력받아 각 문자의 수를 반환하는 함수를 작성한다면?
함수의 구조를 잡고, 주석을 입력한다.
fucntion charCounter(str) { // 리턴할 객체를 먼저 만들어줌 // 문자열에 반복문을 적용하고 // 각 문자가 숫자 혹은 문자이고 객체에 들어있다면 1을 더하고 // 없다면 키로 만들고 값을 1로 설정한다. // 만약 이외의 경우라면 아무것도 하지 않는다. // 객체를 리턴한다. }이렇게 작성하는 것은, 비록 문제를 해결하진 못하더라도 이러한 접근방식을 가지고 있다는 것을 면접관에게 보여주는 것이다.
해결하거나, 단순화하거나
"만약, 작업이 순조롭고 가능하다면 그 즉시 코드를 작성해 해결하는것이 베스트다. 하지만 그렇지 않다면? 만약 한두 문제가 해결이 되지 않았다면?"
➡ "문제를 해결하거나, 해결이 불가능하면 단순한 문제부터 해결하거나"
단순화란
- 작업에서 핵심적인 어려운 부분을 찾는 것
- 잠시 어려운 부분을 무시하는 것
- 단순한 해결책을 먼저 작성하는 것
- 이를 어려운 부분과 합치는 것
예시) 위와 같은 예시 - 문자열을 입력받아 각 문자의 수를 반환하는 함수를 작성한다면?
fucntion charCounter(str) { // 리턴할 객체를 먼저 만들어줌 var result = {}; // 문자열에 반복문을 적용하고 for(let i = 0 ; i < str.length ; i ++) { var char = str[i] // 각 문자가 숫자 혹은 문자이고 객체에 들어있다면 1을 더하고 if(/[a-z0-9/.test(char)) { if(result[char] > 0) { result[char]++ } // 없다면 키로 만들고 값을 1로 설정한다. else { result[char] = 1 } } // 만약 이외의 경우라면 아무것도 하지 않는다. // 객체를 리턴한다. return result; }객체의 키는 소문자 혹은 숫자만 들어올 수 있으므로 이를 작성한다.
var char = str[i].toLowerCase();정규 표현식을 사용해 영, 숫자가 아닐 경우를 쳐낸다.
if(/[a-z0-9/.test(char)) { if(result[char] > 0) { result[char]++ } // 없다면 키로 만들고 값을 1로 설정한다. else { result[char] = 1 } }
복습(회고) 하고 리팩터링(재구성)하기
"해결은 축하하지만, 아직 끝나지 않았다."
리팩터링을 위한 질문들
- 결과는 정확한가?
- 결과를 다른 방식으로 이끌어낼 수 있는가?
- 한눈에 봐도 이해하기 쉬운가?
- 이 해결책을 다른 문제에도 사용할 수 있나?
- 이 해결책의 성능을 향상시킬 수 있나?
- 리팩터링할 다른 방법을 알고있나?
- 다른사람들은 이걸 어떻게 풀었나?
예시) 위와 같은 예시 - 문자열을 입력받아 각 문자의 수를 반환하는 함수를 작성한다면?
fucntion charCounter(str) { var result = {}; for(let i = 0 ; i < str.length ; i ++) { var char = str[i].toLowerCase(); if(/[a-z0-9/.test(char)) { if(result[char] > 0) { result[char]++ } else { result[char] = 1 } } return result; }여기서 for..of 문을 사용할 수 있다.
for(let char of str)밑의 변수도 맞춰서 바꿔준다.
char = char.toLowerCase();if문도 조금 더 간단하게 변형해본다.
f(/[a-z0-9/.test(char)) { result[char] = ++result[char] || 1; }
정규 표현식을 사용하지 못할 경우도 고려해 charCodeAt() 또한 고려한다.
function charCount(str) {
var result = {};
for(let char of str) {
char = char.toLowerCase();
if(isAlphaNumeric(char)) {
result[char] = ++result[char] || 1;
}
}
}
function isAlphaNumeric(char){
var code = char.charCodeAt(0);
if(!(code > 47 && code < 58) &&
!(code > 64 && code < 91) &&
!(code > 96 && code < 123)
) {return false}
return true
}