목록알고리즘/이론 (11)
게으른개발너D

✨ 트리 순회 트리 순회는 트리 자료구조에서 각 노드를 한 번씩 탐색하는 알고리즘이다. 트리 순회는 여러 방법이 있지만 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder)는 재귀를 이용할 수 있다. 모든 순회는 루트 노드부터 시작하며, 어떤 노드를 먼저 방문하는지가 달라진다. 1. 전위 순회 (Preorder) 먼저 노드를 방문한 후 왼쪽 서브 트리를 전위 순회한 다음에 오른쪽 서브 트리를 전위 순회하는 방식이다. 아래와 같은 이진 트리가 있다고 가정해 보자. 1을 방문한 후, 1의 왼쪽 서브 트리로 이동한다. 2를 방문한 후, 2의 왼쪽 서브 트리로 이동한다. 4를 방문한 후, 왼쪽과 오른쪽 서브 트리가 없기 때문에 다시 올라가서 2의 오른쪽 서브 트리로 이동한다...

✨ 재귀함수 재귀함수는 자기 자신을 호출하는 함수이다. 자기 자신을 호출하는 것을 재귀 호출(Recursion call)이라고 한다. 함수 호출은 Call stack에 쌓이기 때문에 스택 자료구조와 유사하게 동작한다. 함수형 프로그래밍에선 루프 구현을 재귀로 구현하는 경우가 많다. 잘못 작성하면 무한 루프에 빠질 수 있다. Javascript에서 재귀함수 Call stack 제한이 있다. 자바스크립트 엔진마다 제한 수는 다르다. 크롬의 경우 약 1만개이다. 재귀함수 성능 개선을 위한 꼬리 재귀(Tail recursion)가 제공되지 않는다. 성능이 좋지 않다. 재귀로 구현해야 편한 알고리즘 Union-Find DFS Backtracking 불편함을 무시한다면 더 빠른 성능으로 작성할 수 있지만 코딩 테스..

✨ 소수 1 또는 자기 자신만을 약수로 가지는 수를 의미 즉, 1과 자기 자신 외에는 그 어떤 값으로도 나눠질 수 없다. ✨ 소수 구하는 방법 1. 가장 직관적인 방법 2부터 N-1까지 루프를 돌며 나눠보기 시간 복잡도 O(n) // O(n) function isPrime(num) { for(let i = 2; i < num; i++) { if (num % i === 0) { return false; } } return true; } 2. 효율성 개선하기 위의 알고리즘을 좀 더 효율적으로 개선해 보자. 그 어떤 소수도 N의 제곱근보다 큰 수로 나눠지지 않는다는 점을 이용. 시간 복잡도 O(sqrt(n)) // O(sqrt(n)) function isPrime(num) { for(let i = 2; i * i