작성 - 2020.8.4
알고리즘 문제 중 인상깊었던 문제들.
코드 스테이츠 20주 과정 2주차 첫 날.
1.Pseudo Code 작성의 중요성
오늘은 지난주 금요일에 이어 페어로 알고리즘 베이직 문제들을 풀었다. 많은 문제들은 특히 for문을 응용하는 문제였다. 알고리즘 문제를 풀면서 특히 중요하다고 체감한 것은 바로 ‘Pseudo Code(의사코드)’를 작성하는 것. 아무리 익숙하지 않은 문제라도 문제의 요구점을 의사 코드로 정리해 낼 수 있다면 코드를 작성해 낼 수 있다. 특히나 이번 페어분은 의사코드를 작성하는데 매우 공을 들이는 분으로 작성하는 과정을 많이 배웠다.
현재 내가 의사코드를 작성하는 방법을 서술하자면 다음과 같다.
- 문제의 입출력, 예외처리를 파악한다.
1-1. 입력값의 형태를 파악한다.
1-2. 요구하는 출력 형태를 파악한다.
(String, Number, Array, Object, 혹은 Boolean)
1-3. 예외처리할 부분은? (ex. '문자열의 길이가 0이면...' || '빈 배열이면...' 등) - 해당 문제의 요구를 파악한다.
2-2. 해당 문제가 요구하는 답을 찾기 위한 적절한 구문은? (ex. for문 || while문 등)
2-2. 해당 문제를 풀기 위한 조건은 무엇인가? (if 조건 등...)
2-3. 해당 문제를 풀기 위한 메소드는 무엇인가? (메소드 검색 및 적용) - 테스트를 진행한다.
3-1.일부가 제대로 돌아가지 않았다면 돌아가지 않은 부분은 어디인가? => Debugger 확인
3-2.전체가 잘 못되어다면, 해당 문제를 제대로 파악한것이 맞는가? => 2번 돌아감
3-2.출력값이 true라면, 문제에서 원하는 포인트를 제대로 파악한것이 맞나? => 복기
복잡한 구조를 거치지만 의사코드를 작성하지 않을 때 보다 당황하는 정도는 많이 줄어들었다. 하지만 여전히 지나치게 구어체이고 문장이 길 때가 많다. 코드에 주석처리를 최소화 하더라도 협업하는 사람이 이해할 수 있는 의사코드 작성법을 더 찾아야 한다.
- 알고리즘
2–1. 제곱근 값을 구하는 방법
코플릿 문제 중 하나는 Math.sqrt를 사용하지 않고 제곱근 값을 구하는 방법에 대한 것이었다. 일반적으로 자바스크립트는 제곱근을 구하는 간편한 메소드가 존재한다.
제곱근을 구하는 메소드 : Math.sqrt(num);
해당 메소드는 Number를 매개변수로 가지며 해당 숫자에 루트를 씌워 제곱근 값을 출력한다. 만약 숫자가 음수이면 ‘NaN’ 을 반환한다.
단, 이번 문제는 Math의 메소드를 사용하지 않고 문제를 해결하는 방법과, 결과를 소수점 셋째 자리에서 반올림하여 둘째 자리까지 표기하는것을 요구했다. 문제에 대한 힌트였던 제곱근을 구하는 바빌로니아 법의 점화식을 검색해 공식을 찾았다.
Image for post
바빌로니아 점화식의 제곱근 구하는 방법. 나 참 바빌로니아 유적 발굴은 해봤어도 바빌론 수학은 처음이네
이를 적용해 작성한 function은 다음과 같다.
function computeSquareRoot(num) {
let result = 1;
for (i =0; i<num; i++){
result = (1/2) * (result + num/result);
//result =(result + num/result) /2
}
return Number(result.toFixed(2));
}
해당 문제를 통해 숫자의 소숫점 표기에 대한 메소드를 함께 숙지했다.
num.toFixed(n)
//n+1자릿수에서 반올림하며, 소숫점 n자리까지만 표기
2–2. 보기 문자열을 생성해 비교 기준 만들기.
코플릿 알고리즘 중 두 문제가 해당 포인트 개념을 이해하여 풀도록 설계가 되었다. 한 문제는 문자열을 입력받고, 문자열에 포함된 숫자를 더하고, 공백을 제외한 문자열의 길이로 숫자를 나누는 것이었다. 다른 한 문제는 카이사르 암호에 대한 문제로, 임의의 문자열이 입력되면 인자로 들어온 숫자만큼 알파벳 순서를 옮겨 암호화된 문자열을 푸는 내용이었다.
이 문제들을 해결하는데 포인트를 의사코드로 작성하면 다음과 같다.
1.기준으로 삼을 수 있는 문자열을 만든다.
2.for문을 작성하고 if 조건을 통해 기준열과 비교한다.
실제로는 문자열에 숫자가 포함되었는지를 파악하는데는 이런 코드가 쓰였다.
function numberSearch(str){
const num = '0123456789'; // 기준 상수를 만든다
for (let i = 0; i < str.length; i++){
if(num.includes(str[i])){
//str[i]가 숫자인지 num(기준상수)와 비교해 파악한다.
실행 조건;
}
}
}
해당 문제를 통해서 string의 포함관계 확인 메소드인 includes()에 대해 숙지했다.
str.includes(searchStr,num)
//searchStr이 str에 있는지 파악하며, num을 기록하면 해당 위치부터 검색한다.
includes() 메서드는 하나의 문자열이 다른 문자열에 포함되어 있는지 판별하고 결과를 boolean 으로 반환한다.
includes()는 대소문자를 구분한다.
익스플로러에서는 호환되지 않는다!
2–3. 끙끙대다 푼 문제. Isogram?
for문과 for문 내 if 조건의 관계에 대한 정확한 이해 없이 풀어가다가 Isogram을 확인하는 문제에서 턱 하고 막혀버렸다. for문 안에서 조건을 설정하는 것에 의해 어떻게 작동되는지를 한 시간 넘게 끙끙거리며 풀었다.
문제에서 요구한 내용
string 타입을 입력받아 Isogram 여부를 boolean 값으로 리턴할 것.
빈 문자열은 true로 리턴할 것
- 의사코드 작성
// 1. 입력은 str
// 2. str을 모두 소문자로 바꾸어준다(대소문자 구별하지 않기때문에)
// 3. str을 어레이로 바꾸어준다.
// 4. 새로운 어레이를 만든다.
// 5.for문에서, 어레이[i] 엘리멘트가 newArr에 없다면?
// 6.새로운 어레이에 추가한다.
// 7. 어레이 [i] 엘리멘트가 새로운 어레이에 있다면? => return false;
// 9. for문이 끝날때까지 false가 출력 안된다면? => return true;
-
실제 완성한 코드
function isIsogram(str) {
let lowerStr = str.toLowerCase();
let arr = lowerStr.split('');
let newArr = [];
if (str.length === 0 ){
return true;
}
for(i = 0; i<arr.length;i++){
if (newArr.includes(arr[i])){
return false;
} else newArr.push(arr[i]);
}
return true;
} -
시행착오와 배운 내용은?
for문 안에서 for in 문을 사용해 배열을 검색하려고 시도했다. for in은 obj 에서 사용하는 요소 확인방법임을 인지했다.
배열 안에 요소를 검사하는 방법에 대해서 다양한 시행착오를 거쳤다. 위에서 전술한 inclouds()의 활용방법에 대해서 다시 한번 인지했다.
여전히 괴롭다. 잘 풀리지 않는다. 그러나 풀다보면 결국에는 풀어낼 수 있다. 머리가 돌아가지 않을 때는 파인만의 알고리즘 해결법을 보자.
Image for post
파인만의 알고리즘 해결법. 출저는 갓무위키
페페 짤이 생각난다. 그 얼굴이 일그러져 물음표를 달고 있는 페페…
