알고리즘

트리 (Tree)정의: 트리는 하나의 루트 노드에서 시작하여 자식 노드로 확장되는 계층적 구조입니다. 각 노드는 자식 노드를 가질 수 있으며, 각 자식 노드는 다시 자신의 자식 노드를 가질 수 있습니다.트리에 관련 용어:루트 노드: 트리의 최상위 노드.터미널 노드 (리프 노드): 자식 노드가 없는 말단 노드.인터널 노드: 하나 이상의 자식 노드를 가진 내부 노드.서브 트리: 특정 노드를 루트로 하는 부분 트리.에지: 두 노드를 연결하는 선.특징:루트 노드에서 시작각 노드는 하나의 부모 노드와 0개 이상의 자식 노드를 가짐사이클이 없음트리는 비순환 그래프. 이는 트리 안에서 어떤 노드에서 출발하여 다시 그 노드로 돌아오는 경로가 없음을 의미. 트리에서 각 노드의 레벨은 해당 노드의 깊이를 나타내는 지표로..

동적 프로그래밍 타뷸레이션타뷸레이션(Tabulation)은 동적 프로그래밍(Dynamic Programming, DP)의 또 다른 접근 방법하향식 접근 방식인 메모이제이션과 달리 상향식 접근 방식을 사용즉, 작은 부분 문제부터 해결해 나가며 최종 문제를 해결하는 방식입니다.특징부분 문제의 중복: 작은 부분 문제를 먼저 해결해 이를 조합하여 큰 문제를 해결.상향식 접근법: 배열이나 테이블을 사용해 작은 부분 문제부터 차례대로 해결.공간 복잡도: 배열이나 테이블을 저장하기 위한 메모리가 필요.장단점 장점 단점 명확한 순서로 문제를 해결추가 메모리 사용반복적 접근으로 재귀 호출 오버헤드 없음초기 메모리 할당 및 관리 필요일부 문제에 대해 간단하고 효율적인 솔루션 제공DP가 적용되지 않는 문제도 존재 시간복잡도..

동적 프로그래밍 메모이제이션동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 해결하기 위해 작은 부분 문제로 나누어 해결하는 방법.메모이제이션(Memoization)은 이미 계산한 결과를 저장해두고, 동일한 계산을 반복하지 않도록 하는 기술.특징부분 문제의 중복: DP는 동일한 부분 문제를 여러 번 계산하는데, 메모이제이션을 통해 이를 방지합니다.탑다운 접근법: 재귀적으로 문제를 해결하면서, 이미 계산한 결과를 저장.공간 복잡도: 결과를 저장하기 위한 추가 메모리가 필요.장단점장점단점중복 계산 방지로 성능 향상추가 메모리 사용재귀적 접근으로 코드 가독성 향상초기 메모리 할당 및 관리 필요일부 문제에 대해 간단하고 효율적인 솔루션 제공DP가 적용되지 않는 문제도 존재 시간복잡도 ..

퀵정렬이란?퀵정렬(Quick Sort)은 또 다른 분할 정복 알고리즘, 배열을 하나의 피벗(pivot)을 기준으로 두 개의 부분 배열로 나누고 각각을 정렬하여 전체 배열을 정렬하는 방식. 퀵정렬은 평균적으로 매우 빠른 정렬 알고리즘 중 하나로 알려져 있음퀵정렬 요약 특징  - 분할 정복 알고리즘 - 불안정 정렬 - 재귀적 접근 - 피벗 선택 중요 장점  - 평균적으로 매우 빠름 - 추가 메모리 공간이 거의 필요 없음(제자리 정렬) 단점  - 최악의 경우 O(n^2)의 시간복잡도 - 피벗 선택에 따라 성능이 좌우됨 시간복잡도  - 최선: O(n log n) - 평균: O(n log n) - 최악: O(n^2) 공간복잡도  - O(log n) (재귀 호출 스택 공간)  자바스크립트 예..

병합정렬이란 병합정렬(Merge Sort)은 분할 정복(Divide and Conquer) 알고리즘의 일종으로, 배열을 반으로 나누어 각각을 정렬한 후 합치는 과정을 반복하여 정렬을 완료하는 알고리즘. 병합정렬은 안정 정렬로, 같은 값의 원소들 간의 순서가 바뀌지 않음.병합정렬 요약특징분할 정복 알고리즘병합정렬은 분할 정복(Divide and Conquer) 알고리즘의 일종문제를 더 작은 부분 문제로 나누고 각각을 해결한 후 합쳐서 최종 해결책을 만드는 방식.재귀적 접근병합정렬은 재귀적으로 배열을 반으로 나누어 더 이상 나눌 수 없을 때까지 나누고, 나눈 배열을 병합하여 정렬외부 정렬 가능병합정렬은 외부 정렬(external sorting)에 적합.대규모 데이터를 정렬할 때, 메모리에 모두 적재할 수 없..

삽입정렬이란삽입정렬(Insertion Sort)은 리스트의 요소들을 하나씩 비교하여 정렬된 부분과 비교하고, 알맞은 위치에 삽입하여 정렬하는 방식두 번째 요소부터 시작하여, 현재 요소를 정렬된 부분의 적절한 위치에 삽입합니다.이를 위해, 현재 요소보다 큰 요소들을 오른쪽으로 한 칸씩 이동시킵니다.리스트의 끝까지 이 과정을 반복합니다.삽입정렬 요약 특징비교 기반의 정렬 알고리즘으로, 리스트의 요소를 하나씩 정렬된 부분에 삽입하여 정렬합니다.장점1. 구현이 간단하고 이해하기 쉬움.2. 대부분 정렬된 리스트에 대해서는 효율적. 3. 제자리 정렬(in-place sort)로, 추가적인 메모리 공간이 필요 없음.단점1. 시간복잡도가 O(n^2)로, 큰 데이터셋에서는 비효율적.2. 요소의 이동이 빈번하여 많은 교환..

선택정렬이란선택정렬(Selection Sort)은 비교 기반의 정렬 알고리즘 중 하나로, 다음과 같은 절차를 통해 배열을 정렬.주어진 리스트 중에서 최솟값을 찾음.그 최솟값을 리스트의 맨 앞에 위치한 값과 교환.맨 앞의 값을 제외한 나머지 리스트를 같은 방법으로 정렬.이 과정을 통해 리스트가 정렬될 때까지 반복.선택정렬 요약 특징 비교 기반의 정렬 알고리즘으로, 리스트에서 최솟값을 반복적으로 선택하여 정렬 장점 1. 구현이 간단하고 이해하기 쉬움2. 작은 크기의 리스트에 대해 효율적으로 작동할 수 있음 단점 1. 시간복잡도가 O(n^2)로, 큰 데이터셋에서는 비효율적2. 안정적인 정렬 알고리즘이 아님. 시간복잡도 O(n^2)  자바스크립트 예시function selectionSort(arr) {..

버블 정렬이란버블 정렬(Bubble Sort)은 간단한 정렬 알고리즘 중 하나로, 인접한 두 원소를 비교하여 필요한 경우 서로 교환하는 방식으로 배열을 정렬함. 이 과정이 배열의 마지막 원소까지 반복되며, 한 사이클이 끝나면 가장 큰 원소가 배열의 끝으로 이동하게 됨. 이러한 사이클을 배열이 완전히 정렬될 때까지 반복.버블 정렬에 대한 요약장점1. 구현이 매우 쉽다.  2. 데이터가 거의 정렬되어 있는 경우 효율적이다.단점1. 효율이 낮다. 2. 큰 데이터셋에 비효율적이다.특징1. 인접한 원소끼리 비교한다. 2. 안정 정렬 (Stable Sort)이다.시간복잡도- 최선: O(n) - 평균: O(n^2) - 최악: O(n^2)공간복잡도O(1) (In-place 정렬 알고리즘) 버블정렬 - 자바스크립트 예시..

하노이의 탑(탑의 하노이, Tower of Hanoi)은 세 개의 막대와 여러 개의 크기가 다른 원반을 사용하여 퍼즐을 푸는 문제. 퍼즐은 원반들이 한 막대에 크기 순으로 쌓여있는 상태에서 시작하며, 목표는 다음 규칙을 지키면서 다른 막대로 모든 원반을 옮기는 것:한 번에 하나의 원반만 옮길 수 있다.각 이동은 맨 위의 원반만 옮길 수 있다.더 큰 원반은 더 작은 원반 위에 놓을 수 없다.하노이의 탑 알고리즘n개의 원반이 있을 때:n-1개의 원반을 출발 막대에서 보조 막대로 옮긴다.가장 큰 원반을 출발 막대에서 목표 막대로 옮긴다.n-1개의 원반을 보조 막대에서 목표 막대로 옮긴다.이를 자바스크립트로 구현한 예시:function hanoi(n, from, to, aux) { if (n === 1) ..

재귀란재귀는 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻함.function addOne (num) { console.log(num); addOne(num + 1); // 자기 자신을 참조}재귀 함수는 기저조건이 꼭 필요함 (아니면 무한 실행됨)자기 자신을 참조하면서 함수가 끝나지 않기 때문에 스택에 계속 쌓이게 됨 => 메모리 부족으로 강제 종료됨.재귀함수가 for문보다 메모리 공간을 더 많이 차지함 => 더 복잡한 문제를 쉽게 해결하기 위함function addOne (num) { if(num > 10) return; console.log(num); addOne(num + 1); // 자기 자신을 참조}재귀 유형반복실행 : 반복문보다 효율적이지 않음하향식 계산방법 : 하위문제의 결과를 기반으로..