감공사

Q. 정수 n을 입력받아, Fibonacci(피보나치 수열)의 n번째 수를 출력하라.

피보나치 수열이란 처음 두 항을 1과 1로 한 후, 그 다음 항부터는 바로 앞의 두 개의 항을 더해 만드는수열을 말한다.

For example, the sequence
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
forms the first ten entries of the fibonacci series.
Example:
fib(4) === 3

Code

😢 배열을 이용한 단순 fib는 쉽게 풀었고, recursion(재귀)를 사용하는 fib는 생각하기에는 어려웠지만 단순했고, memoize(Dynamic Programming)은 매우 생소해서 익숙해지는 시간이 필요했다.

😊 Solution 1)
index 0과 1의 값을 미리 저장한 배열(array)를 선언해주고, classic for loop을 반복해주었다.
i는 1부터 시작해주고 arr.push(arr[i-1] + arr[i-2])형식으로 index를 조정해주어 값을 push해주고 arr[n]을 출력해주면 된다.

Solution 2) 재귀함수(Recursion)
재귀함수를 이용한다.
만약 n값이 2보다 작다면 n값을 return하는 Base Case를 걸어두어 간단하게 해결할 수 있다.
(무조건 index 0은 0이고, index 1은 1로 시작하기 때문이며, 최대 -2를 해주므로, 0또는 1값만 발생할 수 있다)
0, 1, 1이 합쳐져 다음 수를 만들고, 이것들이 결과적으로 피보나치 수열을 이루기 때문이다(결국 1을 찾는 것이다)
return fib(n-1) + fib(n-2);을 통해 처음부터 끝까지 모든 경우의 수를 재귀적으로 실행한다.

Solution 3) 재귀함수와 Memoize(Dynamic Programing)
재귀함수로 검색을 해주지만, 모든 경우의 수를 탐색하지 않고, cache를 생성하여 한 번 검색한 값은 저장하고, 다시 탐색하지 않는다.
재귀함수 fib(여기서는 slowFib)를 memoize함수 안에서 실행하도록 하여, 한 번 탐색한 값은 cache object에 저장하고 그 값을 다시 탐색한다면 cache에서 값을 꺼내 반환해준다. 만약 처음으로 탐색하는 값이라면 slowFib를 실행시킨다.
이렇게 재귀함수를 사용해주면 시간낭비 없이 효율적으로 재귀를 진행할 수 있다.

✔ Nested functions

Memoize function안에 inner function을 만들어줘서, 이미 검색한 값이라면 cache[args]를 리턴, 그게 아니라면 검색하게 한다.
이 과정을 통해 시간 복잡도를 줄일 수 있다. 검색하는 시간을 줄여주기 때문이다.
JavaScript - Grammar 카테고리에서 조금 더 다뤄 보겠다.

✔ Function.prototype.apply()

memoize의 inner function에서 slowFib를 실행시켜주는 방법이다.
helper method 카테고리에서 조금 더 다뤄 보겠다.

✔ this

이 문제에서는 사실 apply()의 첫 번째 parameter에 null or this를 넣어도 큰 상관은 없지만,  this로 넣어줬다.
간단히 말하자면 this는 자신의 왼쪽(소속)을 나타낸다.
 JavaScript - Grammar에서 조금 더 다뤄 보겠다.

✔ args(The arguments object)

입력값을 간접적으로(?) 넘겨주기 위해 사용했다.
function안에서 다룰 수 있는 Array-like object인 arguments이며,
JavaScript - Grammar에서 조금 더 다뤄 보겠다.

✔ ... (Spread)

args를 array처럼 만들어 줄 수 있다. apply()의 두 번째 parameter가 array이므로 array-like값을 넘어주기 위해 사용했다.
JavaScript - ES2015 카테고리에서 개념을 확인할 수 있다.

Full Code

Q. 정수 n을 입력받고, nxn 크기 나선형 행렬(달팽이)를 출력하라.

--- Examples
matrix(2)
  [[1, 2],
  [4, 3]]
matrix(3)
  [[1, 2, 3],
  [8, 9, 4],
  [7, 6, 5]]
matrix(4)
  [[1,   2,  3, 4],
  [12, 13, 14, 5],
  [11, 16, 15, 6],
  [10,  9,  8, 7]]

Code

😢 행렬(2차원 배열)의 패턴을 파악하는 것이 핵심!
3X3 행렬 Test Case를 그려놓고 패턴을 파악하다보니 마지막 for loop의 진행 방향을 놓쳤었다.
진행 순서를 눈으로 확인하기 위해, 진행되는 값을 출력해 보았더니 훨씬 이해가 쉬웠다(Full Code 밑에 추가)

😊 먼저, 행렬(2차원 배열)을 초기화 해주기 위해 for loop으로 n(행)만큼 array를 추가해주었다.
그리고 1부터 값을 증가해주기 위해 count를 선언해주고, 0부터 n-1까지 startRow(Column), endRow(Column)을 각각 선언해준다.
while loop을 이용해 각 StartRow(Column)와 endRow(Column)가 같은 값을 가질 때까지 반복해준다.
(StartRow(Column)는 EndRow(Column)보다 커질 수 없고, EndRow(Column)은 음수가 될 수 없다)

그리고 변경되어야하는 row 또는 column을 중심으로 i를 선언해주고 count값을 증가하며 넣어준다.
해당 row나 column작업이 끝나면 증가 또는 감소시켜준다.

패턴을 찾아줘야하는 알고리즘이기 때문에 특별한 helper method skill은 없다.

Full Code

Spiral Matrix Code For Visual(진행 순서를 눈으로 확인하기 위한 Code)

✨ 내가 찾고자하는 Pattern(character or string etc)을 찾기에 유용한 helper method
(Pattern은 사실 Regular Expression(정규표현식)이지만 쉽게 표현하기 위해 사용하였다)

💻Example Code

const str = 'Hi There!!';
const matches = str.match(/[aeiou]/gi);

console.log( matches );
console.log( matches ? matches.length : 0 )

😋 특히, 특정 문자열을 검색하는 알고리즘 문제를 풀거나, 개발을 할때 매우 유용하다. (단, RegExp를 잘 안다는 전제하에)
Vowels Algorithm(모음 찾기) 문제를 풀 때 잘 사용했다.

👉 자세한 내용은 https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/match

Q. 입력받은 string에서 vowels(모음 - a, e, i, o, u)가 몇 개인지 찾아내라.

--- Examples
vowels('Hi There!') --> 3
vowels('Why do you ask?') --> 4
vowels('Why?') --> 0

Code

😢 vowels를 손쉽게 찾도록 도와줄 includes, match를 활용하는 것이 익숙하지 않았다.

😊 Solution 1)
checker array에 모음(a, e, i, o, u)를 미리 저장해두고, for ... of loop안에서 checker.includes()를 이용해 모음이 있다면 count를 증가시키면서 모음의 개수를 찾아냈다. for ... of는 여러모로 참 유용하다.

Solution 2)
match helper method안에 RegExp를 삽입하여 매우 간단하게 모음을 찾아냈다.
입력받은 str에 match를 사용해주면, 만약 원하는 값이 match됐을 때, 그 값이 반환된다.
여기서 중요한 것은 RegExp에서 g를 넣어줘야 global로 끝까지 검색을 하여 match된 모든 값의 배열을 반환해주며, i를 넣어줘야 대소문자 구분없이 match를 확인해준다.

✔ Array.prototype.includes()

Array에 있는 값들 중에 includes()괄호 안에 넣어준 값을 포함하고 있나? 확인해준다.

✔ String.prototype.match()

String(문자열)에 있는 character중에 match(RegExp)괄호 안에 있는 RegExp의 조건과 매치되는 값이 있나? 확인해준다.

✔ /[aeiou]/gi

[a, e, i, o, u]중에 하나라도 있으면 체크된다.
g는 global search(한 번 매치되고 끝나지 않고, 끝까지 체크한다)
i는 case-insensitive search 대소문자 구분없이 같은 알파벳이라면 동일하게 체크된다.

Full Code

✨ 말 그대로 '기본 값 설정' + '나머지' + '펼치기(?)'를 사용하는 방법이다.

💻Example Code

Default
function f1(x, y = 0) {
  return x + y; }

console.log(f1(3) === 3);

Rest
function f2(x, ...y) {
  return x * y.length; }

console.log(f2(2, 'hi', true) === 4);

Spread
function f3(x, y, z) {
  return x + y + z; }

console.log(f3(...[1, 2, 3]) === 6);

😋 먼저, parameter default는 재귀함수를 사용할 때 유용하다. 굳이 선언을 따로 하지 않고, parameter에서 해결이 가능하기 때문이다. Rest는 아직 사용해본 적은 없지만, 종종 쓰일 것 같고, Spread는 알고리즘 문제를 풀 때와 개발을 할 때 꽤 많이 썼다. 특히, fibonacci, sort 그리고 levelWidth 등 다양한 곳에서 사용했다. 몇 줄이나 나와야할 코드를 단 한 줄로 해결하기에 굉장히 좋다.

👉 자세한 내용은 https://babeljs.io/docs/en/learn/#default-rest-spread

Q. 입력받은 n(숫자)만큼의 층을 생성하는 피라미드를 출력하라.
(단, n은 양수이며, 각 층의 양측 공백은 space로 채워야한다)

--- Examples
pyramid(1)
    '#'
pyramid(2)
    ' # '
    '###'
pyramid(3)
    '  #  '
    ' ### '
    '#####'

Code

😢 각 층(level)의 column은 홀수로 출력되어야 하며, 가운데(midpoint)를 찾아 확장하는 것이 핵심이다.
이 두 가지 핵심 포인트를 찾는 것에 시간이 조금 걸렸다.

😊 Solution 1)
먼저, 해당 피라미드의 가운데지점(midpoint)을 세팅해준다. (2*n-1)
외부 for loop의 row(행)은 각 층수이기 때문에 받은 숫자(n)만큼 반복되고,
내부 for loop의 column(열)은 항상 홀수로 출력되어야 하기 때문에 2*n-1만큼 반복되어야 한다.
그리고 만약 각 층의 #이 채워질 범위가 midpoint - row <= column <= midpoint + row에 해당하면 #,
그게 아니라면 ' '(space)를 level에 대입해준다. 그리고 내부 for loop이 끝날 때마다 각 층을 출력해준다.

Solution 2) 재귀함수
먼저, 함수의 parameter에 row=0, level='' 을 default로 설정해준다. 초기화 후 다른 값으로 반복 대입이 필요하기 때문이다.
Base Case 1)로 만약 row(행)가 n(받은 입력값)과 같으면 return;하여 작업을 끝내주고,
Base Case 2)로 만약 각 층의 값이 level.length(2*n-1)만큼 채워지면 다음 row(층) 작업(재귀)을 실행시켜주고,
원래 하던 작업은 return; 시켜준다.(중요)(Solution 1의 column을 여기서는 level로 대체해준다)
만약 return해주지 않으면, 아래로 작업이 진행되기 때문에 의도하지 않는 실행이 발생될 수 있기 때문이다.
그 후 Solution 1)과 마찬가지로 midpoint - row <= level.length <= midpoint + row 범위에 해당하면 #,
그게 아니라면 ' '을 level에 대입하여준다.
그리고 각 층의 level.length만큼 반복시켜주기 위해 pyramid(n, row, level + add)로 각 층을 재귀함수로 반복시켜준다.

✔ default

function pyramid(n, row=0, level='') 좌측의 row와 level은 입력받지 않는 이상 default인 0과 ''로 실행된다.

https://babeljs.io/docs/en/learn/#default-rest-spread

Full Code

✨ 원하는 알파벳이나 숫자(0-9)의 아스키 코드(ASCII Code)를 알고 싶을 때, 사용하는 helper method
(e.g., str.charCodeAt(0)) 왼쪽처럼 알고 싶은 string의 index를 넣어서 사용한다. ()안에 아무것도 넣지 않으면 default 0
백준 11654번: 아스키 코드,  10809번: 알파벳 찾기 문제를 풀 때 사용하였다.

💻Example Code

const str = 'a';
const numStr = '1';

console.log( str.charCodeAt(0) );
console.log( numStr.charCodeAt(0) );
console.log( 'a'.charCodeAt(0) );

😋 JavaScript에서 string의 ASCII Code를 알고 싶을 때 사용하면 된다.

👉 자세한 내용은 https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/charCodeAt

Code

😢 학부에서 C나 Java를 쓸 때는 자주 사용했던 ASCII Code인데, JavaScript를 주로 사용하게되면서 오랜만에 써보았다.
아니 JavaScript에서는 처음 ASCII Code를 다뤘다.

😊 C나 Java에서는 변환명세 %d, %c 등을 통해 다뤘던 기억이 나는데,
JavaScript에서는 String.charCodeAt(index) helper method를 사용하면 된다.
그리고 4번째 줄에서 trim()도 사용하였지만, 사실 이 문제에서는 굳이 사용하지 않아도 된다.
다른 정답자들도 모두 이 방법으로 풀었다. 다른 방법이 딱히 없나보다.

✔ String.charCodeAt()

String이 담겨있는 변수에 charCodeAt(알고 싶은 index)를 이용해 사용해주면 된다.

Full Code

Code

😢 문제를 보자마자 '이게 왜 정답 비율이 25%지?' 라고 생각하고 바로 풀었는데 틀렸다.
알아보니 ' '(space)만 들어오는 Test Case가 있어서 틀렸던 것이었다. 문제의 '예시 입력'에서 알려줬으면 더 좋았을 것 같다.

😊 if 조건문으로 '' 예외처리를 하였더니, 바로 정답. ' '(space)가 아니고 ''라는 것이 중요하다!
split(' ')을 사용하면, separator가 ' '(space)이기 때문에 입력값으로 ' '만 들어왔을 때 split된 array에는 [ '' ]만 들어가게 된다.
이 함정에 빠져서 다들 문제를 패스한 것 같다.

다른 풀이도 봤는데, 흠.. 조금 돌아가는 방법들이 많았다. length를 못 쓰는 경우가 없진 않을텐데..
웬만하면 다른 코드들도 참고해서 풀어보겠지만, 여기서는 개인적으로 필요성을 느끼지 못해 패스. 조금 더 생각해보자.

Full Code

Code

😢 '어떤 양의 정수 X의 자리수가 등차수열을 이룬다면'???? 지금 보면 별 것 아니지만, 처음 문제를 볼 때는 비슷한 문제를 풀어보지 못해서 그런지 이해하기 힘들었다. 문제 이해하는 것에 시간을 많이 보냈다.

😊 즉, 100미만의 수는 두 자릿수 또는 한 자릿수여서 등차수열을 확인할 수 없기 때문에 모두 '한수'가 된다.
그리고 세 자릿수부터 연속된 등차수열을 확인할 수 있다.
예를 들어, 우리에게 주어진 숫자 111을 백의 자리 1, 십의 자리1, 일의 자리1 하나씩 분리했다고 치자.
백의자리 1 - 십의자리 1 = 0 그리고 십의자리 1 - 일의자리 1 = 0 ( 1-1=0 === 1-1=0, true )
위처럼 연속된 두 개의 수 차이가 0으로 같다. 그렇다면 이건 한수이다.
그리고 1000은 '한수'가 아니다.

Solution 1) 기존 제출 코드
for loop안에서 100미만은 모두 한수로 count,
1000미만은 각 자릿수를 분리하여 Array에 넣고 각 자릿수 순서대로 빼주어 등차수열을 확인하였다.
만약 그 값이 한수라면 한수를 count해주었다. 그리고 1000은 한수가 아니기 때문에 else{ break; }으로 작성해주었다.

Solution 2) Other Solution
이 해결 방법은 다른 정답자의 답안을 참고하였다. 다른 방식으로 접근하였기 때문에 꼭 학습해두고 싶었다.
이 해결 방법에서는, classic for loop을 이용해서 function을 반복 호출하고 true값을 이용해 한수를 count해주었다.
특히, 세 자릿수가 들어오면 toString().split('').map을 이용해 Array로 만들어주고 값을 빼주어서 등차를 확인하였다.

Solution 3) 최종 제출 코드
Solution 2)의 개선 버전이다. for loop을 2번 사용하지 않고, function 안에서 한 번만 for loop을 사용했다.

자릿수를 다루는 문제와 직면할 때는, while을 이용하여 자릿수를 분리하거나
 문자열의 index를 이용하여 해결하곤 하는데, 항상 두 가지를 다 이용해보곤 한다.
프로그래밍은 한 가지 방법만 있지 않다는 게 가장 큰 매력인 것 같다.

Full Code