알고리즘 문제 with JavaScript

FizBuzz

1부터 n까지 출력하는 프로그램. 3의 배수는 fizz, 5의 배수는 buzz, 15의 배수는 fizzbuzz를 출력.

# modulo % operator

function fizzBuzz(n) {
	for (let i = 1; i <= n; i++) {
		if (i % 15 === 0) {
			console.log('fizzbuzz')
		} else if (i % 3 === 0) {
			console.log('fizz')
		} else if (i % 5 === 0) {
			console.log('buzz')
		} else {
			console.log(i)
		}
	}
}

 

Steps

 

N을 입력받아 #으로 스텝 모양을 출력하는 프로그램

step(2)

"#  "

"##"

#1 repeat

function steps(n) {
	for (let i = 1; i <= n; i++) {
		console.log('#'.repeat(i) + ' '.repeat(n - i))
	}
}

#2 row and column

function steps(n) {
	for (let row = 0; row < n; row++) {
		let stair = ''

		for (let col = 0; col < n; col++) {
			if (col <= row) {
				stair += '#'
			} else {
				stair += ' '
			}
		}

		console.log(stair)
	}
}

#3 recursion

function steps(n, row = 0, stair = '') {
	//base case
	if (n === row) {
		return
	}

	if (n === stair.length) {
		console.log(stair)
		return steps(n, row + 1)
	}

	if (stair.length <= row) {
		stair += '#'
	} else {
		stair += ' '
	}
	steps(n, row, stair)
}

 

Two Sided Steps (Pyramids)

N을 입력받아 #을 피라미드 모양으로 출력하는 것

ex

pyramid(2)

'  #  '

'###'

# repeat

function pyramid(n) {
	for (let i = 1; i <= n; i++) {
		console.log(' '.repeat(n - i) + '#'.repeat(2 * i - 1) + ' '.repeat(n - i))
	}
}

 

피보나치

n번째 피보나치 수를 출력하기

피보나치 배열: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

아래 각각의 솔루션마다 runtime complexity가 다르다

#1 Iterative

function fib(n) {
	const arr = [0, 1]
	while (arr.length - 1 < n) {
		arr.push(arr[arr.length - 1] + arr[arr.length - 2])
	}

	return arr[n]
}

#2 Recursive (memoize)

function slowFib(n) {
	if (n < 2) {
		return n
	}

	return fib(n - 1) + fib(n - 2)
}

// 계산 결과를 저장해놓고 참조하기, 피보나치 이외에도 적용 가능
function memoize(fn) {
	const cache = {}

	return function (...args) {
		if (cache[args]) {
			return cache[args]
		}

		const result = fn.apply(this, args)
		cache[args] = result
		return result
	}
}

const fib = memoize(slowFib)