📝 오늘 한 것

1. 프로그래머스 문제 풀이 - 문자열 내 p와 y의 개수 / 핸드폰 번호 가리기 / 문자열 내림차순으로 배치하기 / 자릿수 더하기 / 두 개 뽑아서 더하기

2. 재귀 함수 / 기저 조건 / 분할 / 퀵 정렬 알고리즘

📖 학습 자료

1. 책 '누구나 자료 구조와 알고리즘'

📚 배운 것

1. 프로그래머스 문제 풀이

1) Level 1 문제 풀이

(1) 문자열 내 p와 y의 개수

🔎 내가 작성한 풀이

function solution(s){
  let pCount = 0;
  let yCount = 0;

  for (let i = 0; i < s.length; i++) {
    if (s[i] === 'p' || s[i] === 'P') {
      pCount++;
    }
    if (s[i] === 'y' || s[i] === 'Y') {
      yCount++;
    }
  }

  if (pCount === yCount) {
    return true;
  } else if (pCount !== yCount) {
    return false;
  }
}

(2) 핸드폰 번호 가리기

🔎 내가 작성한 풀이

function solution(phone_number) {
  const arr = phone_number.split('');
  let arr_length = arr.length - 1;

  const hide = arr.map(num => num = '*');

  for (let i = hide.length - 1; i >= hide.length - 4; i--) {
    hide[i] = phone_number[arr_length];
    arr_length--;
  }

  return hide.join('');
}

🔎 다른 사람의 풀이

• repeat()와 slice() 활용

function solution(num) {
  return '*'.repeat(num.length - 4) + num.slice(-4);
}

(3) 문자열 내림차순으로 배치하기

🔎 내가 작성한 풀이

• 문자로 이루어진 배열에 sort()를 실행하면, 기본적으로 (대문자 오름차순 + 소문자 오름차순) 순으로 정렬된다.

// 예제
const string = 'cAdaCbfB';
console.log(string.split('').sort()); // ABCabcdf

• 리턴해야 할 값은 (소문자 내림차순 + 대문자 내림차순) 이다.

• sort()에 따라 기본적인 순서로 정렬된 배열을 slice()를 이용해 대문자와 소문자로 나누어 각각의 배열에 reverse()를 실행해 내림차순으로 정렬했다. 그 후 concat()을 이용해 합친 배열을 최종적으로 문자열로 변환했다.

function solution(s) {
  const arr = s.split('').sort();

  let lowercases;
  let uppercases;

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== arr[i].toUpperCase()) {
      lowercases = arr.slice(i);
      uppercases = arr.slice(0, i);
      break;
    }
  }

  const lowerReverse = lowercases.reverse();
  const upperReverse = uppercases.reverse();

  return lowerReverse.concat(upperReverse).join('');
}

🔎 다른 사람의 풀이

• 아니 나 뭐한 거지?...

function solution(s) {
  return s
    .split("")
    .sort()
    .reverse()
    .join("");
}

(4) 자릿수 더하기

🔎 내가 작성한 풀이

function solution(n) {
  return (n + '').split('')
    .map(item => parseInt(item))
    .reduce((prev, curr) => prev + curr);
}

🔎 다른 사람의 풀이

• do while 문 이용

function solution(n) {
  let sum = 0;
  
  do {
    sum += n % 10;
    n = Math.floor(n / 10);
  } while (n > 0);
  
  return sum;
}

(5) 두 개 뽑아서 더하기

🔎 내가 작성한 풀이

function solution(numbers) {
  const arr = [];
  for (let i = 0; i < numbers.length - 1; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      const sum = numbers[i] + numbers[j];
      if (arr[sum] === undefined) {
        arr[sum] = sum;
      }
    }
  }
  return arr.flat();
}

---

9장. 재귀를 사용한 재귀적 반복

📌 재귀 함수란, 자기 자신을 호출하는 함수를 말한다

1) 루프 대신 재귀

(1) 10에서 0까지 숫자를 표시하는 방법

p.173

• 방법 1

for 루프 이용

function count(num) {
  for (let i = num; i >= 0; i--) {
    console.log(i);
  }
}

count(10);

• 방법 2

재귀 함수 이용 (답 아님)

function count(num) {
  console.log(num);
  count(num - 1);
}

count(10); // 10부터 1씩 작아진 숫자가 무한으로 console 창에 출력되는 문제 발생

(2) 기저 조건

• 재귀가 일어나지 않는(메서드가 반복되지 않는) 경우를 기저 조건(중단 조건)이라고 한다.

• 위 예제의 경우, 카운트를 0에서 끝내고 재귀가 영원히 지속되는 것을 막아야 한다

• 따라서, if 문을 추가해 num 0이 되면 함수를 끝내도록 한다. 이때 0이 기저 조건에 해당한다.

function count(num) {
  console.log(num);
  if (num === 0) { // 추가!
    return;
  } else {
    count(num - 1);
  }
}

count(10);

2) 재귀 코드 읽기

[예제]

주어진 수의 계승을 반환하는 함수를 만들어라.
cf. 계승이란? 그 수보다 작거나 같은 모든 양의 정수의 곱을 말한다.

p.176
Ruby로 구현된 코드 → JavaScript로 변환

function factorial(num) {
  if (num === 1) { // 재귀가 일어나지 않는 경우이다 → 기저 조건
    return 1;
  } else { // 재귀가 일어나는 경우이다
    return num * factorial(num - 1);
  }
}

console.log(factorial(3)); // 6 (3*2*1)

(1) 재귀 코드 추론 순서 (by 사람)

1. 기저 조건(재귀가 일어나지 않는 경우)이 무엇인지 찾는다.

num이 1일 경우가 기저 조건이다.

if (num === 1) {
  return 1;
}

2. 기저 조건을 다룬다는 가정 하에 함수를 살펴본다.

factorical(1)을 살펴본다. factorial(1)을 호출하면 1을 반환한다.
일단 이 사실을 기억해라.

3. 기저 조건의 바로 '전' 조건을 다룬다는 가정 하에 함수를 살펴본다.

num은 1이 되기 '전'에 2였을 것이므로 factorial(2)를 살펴본다.
factorial(2)를 호출하면 2 * factorial(1)을 반환한다.
2.에 따르면 factorial(1)은 곧 1이므로 결국 factorial(2)는 2를 반환한다.
마찬가지로 이 사실을 기억해라.

4. 같은 방법으로 한 번에 한 조건씩 올라가면서 계속 분석한다.

(2) 재귀 함수 동작 원리 (by 컴퓨터)

컴퓨터는 호출 스택(Call Stack)을 사용하여 어떤 함수를 호출 중인지 기록한다.

1. factorial(3)이 호출된다.
   호출 스택에 factorial(3)을 push한다.

2. factorial(3)의 실행이 완료되기 전에,
   factorial(3) 실행 중, factorial(2)가 호출된다.
   호출 스택에 factorial(2)를 push한다.

3. factorial(2)의 실행이 완료되기 전에,
   factorial(2) 실행 중, factorial(1)이 호출된다.
   호출 스택에 factorial(1)을 push한다.

4. 1이 기저 조건이므로 factorial(1)은 factorial() 메서드를 실행하지 않고 1을 리턴하며 실행이 완료된다.
   호출 스택에서 factorial(1)을 pop한다.

5. 호출 스택에는 아직 채 실행이 완료되지 않은 factorial(2)와 factorial(3)이 들어 있다.
   이 중에서 호출 스택에 가장 마지막에 push된 것은 factorial(2)이다.
   따라서, factorial(2)가 (factorial(1)의 결과를 토대로) 실행이 완료된다.
   호출 스택에서 factorial(2)을 pop한다.

6. 이어서 factorial(3)가 (factorial(2)의 결과를 토대로) 실행이 완료된다.
   호출 스택에서 factorial(3)을 pop한다.

7. 이제 호출 스택은 비어 있으므로 컴퓨터는 메서드를 모두 실행했음을 알게 되고, 재귀는 끝나게 된다.

3) 재귀 다뤄보기

• 재귀 함수는 한 알고리즘 내에서 같은 알고리즘을 반복해야 할 때 사용한다.

[예제]

주어진 디렉터리의 모든 하위 디렉터리명을 출력하는 함수를 만들어라.

pp.182 ~ 184
Ruby로 구현된 코드 → JavaScript로 변환

🙋‍♀️ Q1. Ruby를 전혀 모르기 때문에 한글로 된 설명만 보고 구현해야 하는데 한글을 읽어도 코드로 못 바꾸겠다. node.js를 알아야 하는 건지 그냥 내가 이해를 못하는 건지.

10장. 속도를 높이는 재귀 알고리즘

📌 퀵 정렬의 동작 방식을 공부함으로써 어떻게 재귀를 사용해 알고리즘의 속도를 향상시킬 수 있는지 배우고자 한다

📌 많은 컴퓨터 언어에는 이미 퀵 정렬이 내장되어 있다

📌 퀵 정렬은 최악의 시나리오에서는 삽입 정렬, 선택 정렬과 성능이 유사하지만, 평균 시나리오에서는 훨씬 빠르다.

📌 퀵 정렬은 분할이라는 개념을 기반으로 한다.

1) 분할

(1) 설명

• 배열을 분할한다는 것은,

  배열로부터 임의의 수(피벗)을 가져와
  피벗보다 작은 모든 수는 피벗의 왼쪽에
  피벗보다 큰 모든 수는 피벗의 오른쪽에 두는 것을 말한다.

• 처음 분할이 성공적으로 끝나면, 배열은 완전히 정렬되지 않더라도 적어도 피벗만은 배열 내에서 올바른 위치에 있게 된다.

(2) 코드 구현

배열 분할 메서드를 포함하는 class 구현하기

• 배열 분할 메서드는 '왼쪽 포인터와 오른쪽 포인터의 시작점'을 매개변수로 전달받는다.

• 퀵 정렬 메서드에서 사용하기 위해, 배열 분할 메서드는, 최종적으로 '왼쪽 포인터가 이동을 멈췄을 때의 위치(즉, 피벗이 들어간 최종 위치)'를 리턴하도록 한다.

p.193
Ruby로 구현된 코드 → JavaScript로 변환

class SortableArray {
  constructor(arr) {
    this.arr = arr;
  }

  partition(left_pointer, right_pointer) {
    // 항상 가장 오른쪽에 있는 값을 피벗으로 설정한다 (이 예제의 조건일 뿐, 실제로 다른 위치를 고를 수도 있다)
    const pivot = this.arr[right_pointer];
    const pivot_position = right_pointer;

    let left = left_pointer;
    let right = right_pointer - 1;

    while (true) {
      while (this.arr[left] < pivot) {
        left += 1;
      }
      while (left < right && this.arr[right] > pivot) {
        right -= 1;
      }

      if (left >= right) {
        // 왼쪽 포인터와 오른쪽 포인터의 위치가 같거나
        // 왼쪽 포인터가 오른쪽 포인터보다 오른쪽에 있게 되면
        // 바깥 while 루프를 빠져나간 후
        break;
      } else {
        this.swap(left, right);
        left += 1;
      }
    }

    // 현재 왼쪽 포인터와 현재 피벗 위치를 교환한다
    this.swap(left, pivot_position);

    return left;
  }

  swap(pointer_1, pointer_2) {
    const temp = this.arr[pointer_1];
    this.arr[pointer_1] = this.arr[pointer_2];
    this.arr[pointer_2] = temp;
  }
}

const arr1 = [0, 5, 2, 1, 6, 3];
const arr = new SortableArray(arr1);
console.log(arr.partition(0, arr1.length - 1)); // 3
console.log(arr1); // [0, 1, 2, 3, 6, 5]

2) 퀵 정렬 알고리즘

(1) 설명

• 앞서 배열을 분할했다. 이제 피벗(3)은 올바른 위치에 있다.

• 다음으로 피벗(3)의 왼쪽과 오른쪽에 있는 하위 배열을 각각 또 다른 배열로 보고, 이를 다시 분할하도록 한다. 이제는 두 번째 분할 시 사용된 피벗 또한 올바른 위치에 있게 된다.

• 동일한 과정을 재귀적으로 반복하되, 기저 조건을 맨 처음에 적어준다.

(2) 코드 구현

위 예제에서 퀵 정렬 메서드를 추가했다

class SortableArray {
  constructor(arr) {
    this.arr = arr;
  }

  // 퀵 정렬 메서드 추가 ❗
  quickSort(left_index, right_index) {
    // 더 이상 재귀가 일어나지 않는 즉, 분할 메서드가 반복되지 않는
    // 기저 조건 : 하위 배열에 원소가 0개 또는 1개일 때
    if (left_index >= right_index) {
      return;
    }

    // 처음으로 배열을 분할하고, 피벗의 위치를 가져온다
    const pivot_position = this.partition(left_index, right_index);

    // 피벗 왼쪽에 대해 분할 메서드를 재귀적으로 호출한다
    this.quickSort(left_index, pivot_position - 1);
    // 피벗 오른쪽에 대해 분할 메서드를 재귀적으로 호출한다
    this.quickSort(pivot_position + 1, right_index);
  }

  // 분할 메서드
  partition(left_pointer, right_pointer) {
    const pivot = this.arr[right_pointer];
    const pivot_position = right_pointer;

    let left = left_pointer;
    let right = right_pointer - 1;

    while (true) {
      while (this.arr[left] < pivot) {
        left += 1;
      }
      while (left < right && this.arr[right] > pivot) {
        right -= 1;
      }

      if (left >= right) {
        break;
      } else {
        this.swap(left, right);
        left += 1;
      }
    }

    this.swap(left, pivot_position);

    return left;
  }

  // 배열 요소 교환 메서드
  swap(pointer_1, pointer_2) {
    const temp = this.arr[pointer_1];
    this.arr[pointer_1] = this.arr[pointer_2];
    this.arr[pointer_2] = temp;
  }
}

const arr1 = [0, 5, 2, 1, 6, 3];
const arr = new SortableArray(arr1);
arr.quickSort(0, arr1.length - 1);
console.log(arr1); // [0, 1, 2, 3, 5, 6]

(3) 빅 오

🔎 퀵 정렬 알고리즘의 효율성을 알기 위해서는, 먼저 분할의 효율성을 밝혀야 한다

분할에는 총 두 종류의 단계, 비교 & 교환이 포함되어 있다.

• 비교

  각 분할마다, 데이터가 N개일 때, '비교'는 N번 일어난다.
  배열 내 각 원소를 피벗과 비교하기 때문이다. 이 과정에서 왼쪽 포인터와 오른쪽 포인터는 서로 만날 때까지 각 셀을 이동한다.

• 교환

  교환 횟수는 데이터가 얼마나 정렬되어 있느냐에 따라 다르다.

  평균 시나리오일 때(데이터 무작위 정렬)
  데이터가 N개라면, '교환'은 대략 N / 4번 일어난다.

• 비교 + 교환

  N번의 비교와 N / 4번의 교환을 더하면, 대략 총 1.25N 단계가 걸린다.
  빅 오는 상수를 무시하므로 분할의 효율성은 O(N)이라고 할 수 있다.

🔎 그러나, 이는 한 번 분할할 때의 효율성이다. 퀵 정렬 알고리즘은 다양한 크기의 배열과 하위 배열을 여러 번 '분할'하기 때문에 퀵 정렬 알고리즘의 효율성을 알기 위해서는 좀 더 분석해야 한다.

• 각 분할마다 분할되는 하위 배열의 크기가 다양하다는 가정 하에
  데이터가 N개일 때, 대략 N * log N 단계가 걸린다.
  따라서, 퀵 정렬 알고리즘의 효율성은 O(N log N)이다.

• 이는, 하위 배열이 1개의 요소를 가질 때까지(기저 조건에 다다를 때까지), 각 하위 배열을 계속해서 반으로 나누기 때문이다. 이진 검색의 원리를 생각하면 이해하기 쉽다.

  (이때, 분할과 반으로 나누는 것을 혼동하면 안된다. 분할은 위의 코드에서 partition() 즉, 비교 & 교환에 해당하는 부분을 말하고, 반으로 나누는 것은 위의 코드에서 quickSort() 메서드에 포함되어 있는 부분을 말한다.)

• 즉, 데이터가 N개일 때, 원래 배열을 같은 크기의 하위 배열로 logN번 나눌 수 있고, 나눌 때마다 원래 배열의 N개 셀 전부를 분할하므로, 대략 총 N * log N 단계가 걸린다.

🙋‍♀️ 질문

1. 여기 바로가기

✨ 내일 할 것

1. 프로그래머스 문제 풀이

2. 책 계속 읽기