알고리즘 이론/기본 이론

알고리즘에서 재귀 함수를 사용하는 이유는?

재귀함수란? 자기 자신을 호출하는 함수이다. 반복문으로도 구현될 수 있다. 재귀 함수 예제 코드 (자바스크립트) function recursive(num) { // base case, stopping condition, 종료 조건 if (num > 3) { return; } console.log(`before call itself, num: ${num}`); recursive(num + 1); console.log(`after call itself, num: ${num}`); return; } 위는 아주 간단한 재귀 함수의 예이다. 위의 주석에서 base case 라고 표기된 부분은 재귀 함수를 그만 생성하며 재귀 종료가 일어나는 시나리오를 말한다. stopping condition, 종료 조건 이라고 ..

알고리즘의 시간복잡도, 공간복잡도란? (feat. Big O Notation)

Big O 표기법 (Notation) 이란? Big O 표기법이란 알고리즘의 컴퓨터적인 복잡도를 기술하는 방식이다. 시간 복잡도 와 공간 복잡도 로 나뉘게 된다. 시간 복잡도: 입력값이 늘어남에 따라 얼마나 실행 시간이 늘어나냐를 의미한다. 공간 복잡도: 입력값이 늘어남에 따라 얼마나 메모리 공간을 많이 차지하냐를 의미한다. 일반적으로 알고리즘 문제는 더 나은 공간 복잡도보단 더 나은 시간 복잡도를 요구한다. 실제 표기 예제 O(n) O(n2) O(2n) O(log n) O(n * m) 여기서 n 은 보통 입력으로 들어온 배열의 길이거나 문자열의 길이이다. Big O 표기법에서 상수는 무시된다 ex) O(2n) 이 있다면, O(n) 으로 표기하는 것과 같다. 위에서 시간 복잡도와 공간 복잡도 모두 '입력..