나디아 성장 일기

동적 프로그래밍(Dynamic Programming): 큰 문제를 작은 문제로 나누고, 그 결과를 저장하여 중복 계산을 피하는 최적화 기법 메모이제이션 (Memoization): 계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법하향식(Top-Down) 방식재귀를 사용해 큰 문제부터 내려가며 계산이미 계산한 결과는 저장해두고 다시 사용함 메모이제이션의 장단점장점재귀 덕분에 하향식 계산 방식으로 어려운 문제를 간단히 해결할 수 있음중복 계산을 하지 않아서 속도가 빠름 단점재귀를 사용하기 때문에 오버헤드가 큼 메모이제이션은 속도를 위해 메모리를 사용하기 때문에 메모리 사용량 증가 예시: 피보나치 수열 기본 재귀 방식function fibonacci1(n){ if(n == 0 || n ..

퀵 정렬 (Quick Sort): 기준값(피벗)을 정해 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누며 정렬하는 빠른 정렬 알고리즘 분할 정복 알고리즘재귀로 정렬하는 알고리즘 퀵 정렬의 성능시간 복잡도평균: Θ(n log n) → 피벗이 배열의 절반씩 나누는 경우최악: O(n²) → 피벗이 한쪽 끝에 치우친 경우→ 하지만 최악의 경우는 거의 발생하지 않음성능 평가병합 정렬이 평균 성능만 보면 더 나을 수 있지만, 퀵 정렬은 실제로 더 적은 비교와 메모리 사용량으로 인해더 빠르고 효율적인 알고리즘으로 평가됨 퀵 정렬의 장단점장점 전체적으로 성능이 좋음 단점 전체적으로 성능이 좋음 퀵 정렬의 흐름[ 5, 3, 7, 2, 6, 4, 9, 1, 8 ]정렬을 시작하기 전에 배열에서 하나를 피벗(pivot)..

병합 정렬 (Merge Sort): 큰 배열을 잘게 나눴다가, 정렬하면서 다시 합쳐 정렬을 완료하는 알고리즘분할 정복 알고리즘(divide and conquer): 복잡한 문제를 한 번에 해결하려 하지 말고, 작은 문제로 쪼개서 각각 해결한 후 결과를 합쳐 전체 문제를 해결하는 방식 재귀로 정렬하는 알고리즘 병합 정렬의 성능시간 복잡도: O(n log n)병합 정렬에서 성능을 평가하는 부분 ⇒ Merge() 함수 내에서 흩어진 배열을 합치는 부분 병합 정렬의 장단점장점전체적으로 성능이 좋음 단점이해와 구현이 어려움 병합 정렬 알고리즘 흐름원본: 3 5 2 4 1 7 8 61단계: 3 5 2 4 1 7 8 6 → 2개로 쪼갬2단계: 3 5 2 4 1 7 8 6 → 4개로 쪼갬3단계:..

삽입 정렬 (Insertion Sort): 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 하나씩 꺼내면서 알맞은 자리에 삽입해 나가는 방식 선택 정렬과 마찬가지로 정렬된 영역과 정렬되지 않은 영역으로 나눠서 계산함정렬되지 않은 영역에서 데이터를 꺼내서 정렬된 영역 내 적절한 위치에 삽입해서 정렬함 선택 정렬의 성능시간 복잡도: O(n²)성능이 좋지 않음 선택 정렬의 장단점장점이해와 구현이 간단함 단점성능이 O(n²)으로 별로 좋지 않음 삽입 정렬 흐름[ 4, 1, 5, 3, 6, 2 ]정렬된 영역: 4, 정렬되지 않은 영역: 1, 5, 3, 6, 2정렬되지 않은 영역의 첫 번째 원소인 1을 정렬된 영역의 마지막 데이터인 4와 비교함4는 1보다 크기 때문에 4를 오른쪽 인덱스에 덮어씀([..

선택 정렬 (Selection Sort): 정렬되지 않은 영역에서 가장 작은 값을 찾아서 맨 앞과 바꾸는 방식정렬된 영역과 정렬되지 않은 영역으로 나눠서 계산함배열의 정렬되지 않은 영역의 첫 번째 원소부터 마지막 원소까지 비교한 후 가장 작은 값을 첫 번째 원소와 교체함 바깥 반복문이 돌수록 정렬된 영역이 늘어나고, 안쪽 반복문의 횟수는 줄어드는 형태 선택 정렬의 성능 시간 복잡도: O(n²) 성능이 좋지 않음 선택 정렬의 장단점 장점 이해와 구현이 간단함 단점 성능이 O(n²)으로 별로 좋지 않음 예시: 숫자가 무작위로 들어있는 배열 정렬하기([4, 2, 3, 1]) 배열의 원소가 n개라면 n-1번 반복시켜줘야 함 최솟값을 가진 인덱스를 저장할 변수를 만들어줌 바깥 반복문에서 배열의 시작..

버블 정렬 (Bubble Sort): 데이터를 옆 데이터와 비교하고, 자리를 바꾸어가며 정렬하는 방식버블 정렬은 배열의 무작위로 섞인 숫자를 정렬하는 방법 중 하나구현이 쉽지만 성능은 좋지 않음앞 숫자와 그 뒷 숫자를 비교해서 자리를 바꾸며 정렬을 수행한 번 반복이 끝날 때마다 제일 큰 숫자가 제일 오른쪽에 정착함 버블 정렬의 성능시간 복잡도: O(n²)성능이 좋지 않음→ 요소가 많아질수록 느려짐 버블 정렬의 장단점장점이해와 구현이 매우 간단함 단점성능이 O(n²)으로 별로 좋지 않음실무에서는 거의 사용되지 않음 예시: 숫자가 무작위로 들어있는 배열 정렬하기([4, 2, 3, 1])배열의 원소가 4개라면, 자리 교체는 최대 3번 일어나기 때문에 → 배열의 길이보다 1 작은 횟수만큼 반복 필요첫..

재귀 (Recursion): 어떤 것을 정의할 때, 자기 자신을 참조하는 것재귀함수: 자기 자신을 호출하는 함수재귀함수는 메모리 공간을 많이 차지함재귀함수의 필요성: 팩토리얼function myFunction(number) { consloe.log(number); myFunction(number + 1);}myFunction(1); // 무한 호출 → 메모리 초과 발생하여 자동 종료 재귀함수의 필수 조건기저 조건( = 탈출 조건, Base Case)이 반드시 있어야 함기저 조건이 없으면 무한 루프가 발생하고 메모리 초과가 일어남function myFunction(number) { if(number > 10) return; consloe.log(number); myFunction(nu..