[코딩노트] S2 daily-coding review

💡 이 포스트에는 section2를 진행하는 동안 매일 풀었던 코딩 문제들을 풀고 몰랐던 점이나 부족했던 점을 정리했다!
(누군가에게는 너무 쉬워 하품이 나올 수 있습니다.🥲)

코딩노트 정리하기

지난 번 진행되었던 section2에서는 아침마다 코딩 문제를 풀었다. 그 중에서는 레퍼런스랑 비슷하게 금방 풀고 통과한 문제도 있었지만 간신히 풀었거나, 레퍼런스랑 완전 다르게 풀었던 경우도 있었다. 심지어 통과못하고 제출만 한 문제도 있었다. 그간의 우여곡절을 기록으로 남겨보았다.

저작권의 문제로 코딩문제를 변형하거나 코드를 변형하였다.
경우에 따라 어떤 문제는 코드도 적지 않았다.

1. 'a'로 시작하여 'b'로 끝나는 길이 5의 문자열 찾기

핵심 : 0번째부터 5개를 탐색하는 것보다, 4번째부터 0번째를 검사하며 탐색하는 것을 생각해본다.
핵심 : 'a'를 찾는 것과 'b'를 찾는 것을 따로 수행하는 것보다 'a'와 'b'를 찾는 동시에 찾는 방법이 더 효율적이다.
핵심 : 변수의 선언을 최소화하는 방향으로 생각해본다.
'a'로 시작해서 'b'로 끝나는 길이 5의 문자열을 찾아야 하는 문제였다.
0번째부터 시작해서 찾으면 첫번째가 'a'가 맞는지도 확인해야하고, +4번째도 'b'가 맞는지 확인해야 한다.
하지만 4번째부터 'b'가 맞는지 확인한 후 그 4개 전의 수가 'a'인지 확인하면 순회하는 횟수가 줄어들 수 있다.
그리고 나는 'a'와 'b'가 있는지 따로 탐색했는데, 'a'를 찾는 즉시 'b'를 찾거나 'b'를 찾는 즉시 'a'를 찾는 것이 좀 더 효율적이다.
그리고 모든 경우의 수를 따지기보다, 원하는 케이스를 제외하고 모두 false처리하는 것이 덜 복잡하다.

function find5lenAtoB(str){
  for(let i=4; i<str.length; i++){
    if(str[i]==='b' && str[i-4]==='a') return true;
  }
  return false;
}

2. 나눗셈, 나머지 연산 없이 두 수를 나눈 나머지 구하기

핵심 : 빼기, 더하기, 곱셈을 이용하여 반복한다.
n1/n2의 나머지를 구할 때 다음과 같은 방법이 있다.

1. n2에 자연수를 곱한 뒤 n1에서 빼는 것을 반복하는 방법이 있고,
2. n1에서 n2를 계속 빼는 방법이 있다.

처음에는 첫번째 방법만 생각했었는데, 변수를 할당해야 하고 코드가 길어지는 단점이 있었다. 따라서 직관적이고 효율적인 두 번째 방법이 더 낫겠다는 생각이 들었다.
아래는 각 방법을 나타낸 코드로 n1, n2가 각각 0보다 작은 경우는 없다고 가정했다.

• 첫번째 방법

function modulo1(n1, n2) {
  let i=0;
  let multiple=n2*i;
  while(n1-multiple>n2){ 
    multiple=n2*i;
    i++;
  }
  return n1-multiple;

}

• 두번째 방법

function modulo2(n1, n2) {
  while (n1 >= n2) {
    n1 = n1 - n2;
  }

  return n1;
}

3. 메서드 사용하지 않고 n의 제곱근 구하기

핵심 :
메서드를 사용하지 않고 제곱근을 구하려면 여러 방법이 있다.
바빌로니아 법, 뉴턴 랩슨 법, 조선시대 숙수념 등등...
처음에는 바빌로니아 방법을 선택하여 풀었다.
일단 너무 어렵고 복잡하여 통과를 못했었고, 레퍼런스를 봐도 이해가 잘 가지않았다.ㅠㅠ😫
레퍼런스를 계속 이해할 때까지 차근차근 따라해보고, 바빌로니아 방법을 고쳐본 결과 결국 오차범위를 줄이기 위해서는 여러번 패턴을 반복해야 한다는 점이 같았다.
그래서 어차피 패턴을 반복해야 한다면 간단한 방법으로 도전하는 게 좋아보여서 코드를 고치게 되었다.
의사코드는 다음과 같다.

• n은 제곱근을 구할 수, x는 n의 제곱근으로 근사값이다.
• 아래는 제곱근을 구하는 방법이다:
  1. x에 1씩 더해가며 제곱하고, n보다 작은지 확인한다. 크면 멈춘다.
  2. 1의 자리의 x를 구했으면 다음 단계로 가기 전 x에 -1을 한다. 그렇지 않으면 다음단계에서 더할 때 n보다 큰 값이 되버린다.
  3. x에 0.1씩 더해가며 제곱하고, n보다 작은지 확인한다. 크면 멈춘다.
  4. 0.1의 자리의 x를 구했으면 다음 단계로 가기 전 x에 -0.1을 한다. 그렇지 않으면 다음단계에서 더할 때 n보다 큰 값이 되버린다.
  5. ...
• 위 과정을 보면 1,2번과 3,4번은 비슷하다. 즉 비슷한 패턴으로 반복할 수 있으며 정리하면 아래와 같다.
  • x에 i씩 더해가며 제곱하고, n보다 작은지 확인한다. 크면 멈춘다.
  • i의 자리의 x를 구했으면 다음 단계로 가기 전 x에 -i을 한다.

• 이 과정을 소수점 둘째자리까지 반복할 예정이므로 0.001까지 반복한다.

이 기나긴 의사코드를 코드로 정리해보면 아래와 같다.

function findSqrt(num) {
  let x = 1;
  //각 자리수만큼 반복하기 위해 각 자리수를 배열에 담았다.
  let errorRangeArr = [1, 0.1, 0.01, 0.001];
  //위 의사코드처럼 각 자리수만큼 반복한다.
  for (let i = 0; i < rangeArr.length; i++) {
    while (x * x < num) {
      x = x + rangeArr[i];
    }
    //딱 맞아떨어지는 경우 더 이상 반복할 필요가 없으므로 x를 리턴한다.
    if ((x * x) === num) {
      return x;
    } else {
      //최종 결과에 각 자리 수를 빼야 다음 단계를 반복할 수 있다.
      x = x - rangeArr[i]; 
    }
  }
  //소수점 셋째자리까지 구했으므로 둘째자리까지 구해준다.
  return Number(parseFloat(x).toFixed(2));
}

4. 문자열에서 숫자를 찾아 합 구하기

핵심 : 때로는 문제가 곧 의사코드이다.
핵심 : 숫자나 문자열 전체를 비교하거나 찾아야 할 때, 숫자나 문자열 혹은 이런 요소들이 담긴 배열을 생성한다.
이번 문제는 문제 자체가 의사코드나 다름없었기에 먼저 문제를 찬찬히 읽으며 분석해 보았다.
1. 입력받은 문자열에서 숫자를 모두 찾는다.
2. 찾은 숫자를 모두 더한다.
문제가 좀 길었지만 저렇게 정리하니 알고리즘 자체는 어렵지 않았다.
여기서 중요한 건 숫자를 찾는 방법이다.
여러 가지 방법이 있지만 쉬운 방법은 아래와 같다.

• 방법1: 한 문자를 Number를 사용해 숫자로 변환했을 때 NaN이 아닌 경우 숫자이다.
• 방법2: 숫자로 된 문자열 nums를 만들고 각 문자가 nums에 있는 경우 숫자이다.

위의 방법들을 활용하여 찾은 숫자를 합에 추가한다.

//방법1
function findNumber(str) {
  let sum=0;
  for(let i=0; i<str.length; i++){
    if(!isNaN(Number(str[i]))) sum+=Number(str[i]);
  }
  return sum;
}

//방법2
function findNumber(str) {
  let nums = '0123456789';
  let sum = 0;
  for (let i = 0; i < str.length; i += 1) {
    if (nums.includes(str[i])) {
      sum = sum + Number(str[i]);
    }
  }
  return sum;
}

엄청 어렵지는 않지만 찾아야할 값을 사전에 선언하고 찾는 방법이 인상깊어 기록해보았다.

5. 카이사르 암호 문제

핵심 : 카이사르 암호는 평문의 각 알파벳에 임의의 숫자 n씩을 더해 암호화하는 것을 의미한다.
카이사르 암호는 핵심에 언급한 것처럼 각 문자에 숫자 n씩을 더한 차례의 알파벳으로 암호화하는 것을 의미한다.
예를 들어 평문 'cake'와 숫자 2가 주어졌다면
c의 2번째 후의 알파벳은 e,
a의 2번째 후의 알파벳은 c,
k의 2번째 후의 알파벳은 m,
e의 2번째 후의 알파벳은 g로
암호화하면 'ecmg'가 된다.
그럼 이 과정을 의사코드로 정리하자면 아래와 같다.

1. 주어진 문자열의 첫번째 알파벳의 순서를 찾는다.
2. 그 알파벳 순서에 n만큼 더한 알파벳을 찾는다.
   (cf. 응용문제로 복호화해야하는 경우 n만큼 빼면 된다.)
3. 이 과정을 문자열의 각 알파벳마다 반복한다.

여기서 중요한 것은 의사코드 1번의 알파벳의 순서찾기로 제일 쉬운 방법은 아래와 같다.

• 이전 4번 코딩문제에서 변수에 모든 숫자를 문자열로 할당한 것처럼, 변수에 모든 알파벳을 한 문자열로 할당하는 방법이다.
• 다만 주의할 점은 마지막 문자열에서 n을 더할 경우 전체길이 만큼 빼줘야 한다.
  그리고 이 문자열의 인덱스를 기준으로 문제를 해결하면 된다.
  아래는 암호화 과정을 코드로 나타냈다.

function makeCaesarCipher(str, n) {
  let alphabet='abcdefghijklmnopqrstuvwxyz';
  let result='';
  for(let i=0; i<str.length; i++){
    if(str[i]===' '){//공백처리
      result+=' ';
    }else{
      let newIndex=alphabet.indexOf(str[i])+secret;
      //조건문을 사용하지 않고 아래처럼 처리할 수도 있다.
      //newIndex=newIndex%alphabet.length;
      /* cf) 복호화인 경우:
        let newIndex=alphabet.indexOf(str[i])-secret;
        newIndex=(newIndex+alphabet.length)%alphabet.length;
      */
      if(newIndex>=alphabet.length){
        newIndex=newIndex-alphabet.length;
      }
      result+=alphabet[newIndex];
    }
  }
  return result;
}

6. 반복되는 문자 압축하기

핵심 : 반복하려는 문자열.repeat(반복하려는 횟수)를 사용하면 문자열을 반복해서 출력할 수 있다.
문제 자체의 알고리즘은 어렵지 않았지만, 문자열을 반복하는 repeat 메서드를 몰라서 이 문제를 적어두었다.문자열 첫시간부터 열심히 공부했는데 가끔 가물가물하거나 미처 몰랐던 메서드들이 있는 것 같다. 복습을 잊지말자!!
문제는 주어진 문자열에 3회 이상 반복된 문자열이 있다면, 반복횟수를 넣어 압축하는 것이다. 만약 'abcccddggg'라는 문자열이 있다면 'ab3cdd3g' 이렇게 압축한다.
문제 자체의 의사코드는 어렵지 않았으나 조건이 있어서 분기처리를 잘 했어야 했다. 그리고 repeat 메서드를 모른다면 좀 더 복잡하게 풀어야 했다.
의사코드는 다음과 같다.

1. 첫번째 문자열을 다음 문자열과 비교한다.
2. 같다면 반복횟수에 1회 추가한다.
3. 다르다면 두번째 문자열을 다음 문자열과 비교한다.
4. 이 과정을 문자열을 하나하나 순회하며 진행한다.
5. 다만 현재 문자열과 다음 문자열이 다르면 반복횟수를 확인한다.
6. 이 반복횟수가 3이상인 경우는 '반복횟수''문자열' 이렇게 압축하고, 아닐 경우 문자열을 압축하지 않고 그대로 입력한다.
7. 그렇게 압축한 문자열을 리턴한다.

복잡해 보이지만 의사코드를 차근차근 반영하여 풀면 문제를 해결할 수 있다.
아래는 의사코드를 바탕으로 작성한 코드이다.

function stringZip(str) {
  //반복하는 문자열은 repeat로 일단 첫번째 문자열을 할당한다.
  //반복하는 횟수는 count로 일단 1을 할당한다.
  let repeat=str[0];
  let count=1;
  let result='';
  
  for(let i=0; i<str.length; i++){
    //다음 문자열이 현재 문자열과 같다면 반복횟수를 1씩 추가한다.
    if(str[i+1]===repeat){
      count+=1;
    }
    //다음 문자열이 현재 문자열과 다르다면, 다음단계로 넘어가기 전 반복횟수를 확인해야 한다.
    else{
      //반복횟수가 3이상인 경우만 압축한다.
      if(count>=3){
        result+=`${count}${repeat}`;
      }
      //반복횟수가 2이하인 경우, 만약 2인 경우를 대비해 해당 문자를 반복해 줘야 한다.
      else{
        result+=repeat.repeat(count);
      }
      //다음 단계로 넘어가기 위해 반복횟수를 초기화하고, 반복될 문자열을 다음문자열로 바꿔준다.
      count=1;
      repeat=str[i+1];
    }
    
  }
  return result;
}

노트 정리 후 느낀점

section2를 진행하는 동안 매일 한 문제씩 코딩문제를 풀면서 그냥 넘기면 안될 것 같아 인상깊었거나 기록해야할 문제를 적어두었었다.
다만, 섹션이 끝나고 한 번에 정리하려니 시간이 꽤 오래걸렸고 할 일이 쌓이는 느낌이라 불편했다. 반드시 다음 번엔 바로바로 한 문제씩 정리해야 함을 강하게 느꼈다.
확실히 예전보다는 나아진 것 같긴한데, 아직까지는 공부하거나 기억해야할 게 많다. 알고리즘 실력이 나아지는 그날까지 코딩노트를 멈추지 않길 바랄 뿐이다.
뭣보다 오랜시간 정리한 이 포스트를 드디어 끝내게 되어 정말 다행이다.😮‍💨

• 이번의 부족한 점
  • 문제를 한 번에 정리하려고 하면 시간도 오래걸리고 부담이 크다.
  • 문제를 풀긴 했는데 리팩토링이 필요하다.

다음 번에는 부족한 점을 보완하기 위해 아래와 같이 공부할 예정이다.

• 부족한 점 보완하기
  • 다음 섹션부터는 한 문제씩 미리미리 정리하고 기록하자.
  • 문제를 다 풀었다면 리팩토링 시간을 꼭 가지고, 혹시 관련된 메서드는 없는지 꼭 검색해본다.

그냥 포기할 수도 있었지만, 이렇게 정리를 하니 뿌듯하다. 다음 섹션의 데일리 코딩도 힘내자!🤓