ios Note

완전 이진 트리(Complete Binary Tree) 구조를 가지며, 우선순위 큐(Primary Queue)를 구현하는 데 자주 사용된다완전이진트리: 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 노드는 가장 왼쪽에 있는 트리우선순위 큐: 높은 우선순위를 가진 원소가 낮은 우선순위를 가진 원소보다 먼저 처리되는 큐  Swift의 기본 자료구조에는 Heap이 포함되지 않으므로 직접 구현해야 한다힙의 종류최소 힙(Min Heap): 부모 노드의 값이 자식 노드보다 항상 작거나 같음 → 가장 작은 값이 루트에 위치최대 힙(Max Heap): 부모 노드의 값이 자식 노드보다 항상 크거나 같음 → 가장 큰 값이 루트에 위치 https://www.geeksforgeeks.org/introduc..

동적 계획법(Dynamic Programming, DP)최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblem)를 가진 문제를 해결하기 위한 알고리즘 기법최적 부분 구조: 문제의 최적 해가 하위 문제들의 최적 해로 구성될 수 있는 성질중복 되는 부분 문제: 동일한 하위 문제가 여러 번 반복적으로 계산되는 성질 DP의 핵심 개념메모이제이션(Memoization) (Top-Down 방식)문제를 재귀적으로 푸는 과정에서, 이미 계산한 값을 저장하여 중복 계산을 방지각 결과를 캐싱하여 필요할 때 다시 사용타뷸레이션(Tabulation) (Bottom-Up 방식)하위 문제를 작은 문제부터 해결하고, 이를 이용해 상위 문제를 점진적으로 해결보통 배열을 ..

그리디 알고리즘 (탐욕 알고리즘)현재 시점에서 가장 최선의 선택을 반복하여 문제를 해결하는 알고리즘매 단계에서 현재 최적이라고 판단되는 선택을 함으로써 전체적인 최적 해에 도달하려고 함 특징지역 최적화(Local Optimal): 매 순간마다 최적의 선택을 함전역 최적화(Global Optimal): 여러 단계의 최적화 결과가 모여 전체 문제에 대한 최적 해를 보장빠른 계산 속도: 복잡한 계산 과정을 거치지 않고 매 순간 최적의 선택을 하기 때문에 계산량이 적음최적 해 보장 조건: 항상 최적의 해를 보장하는 것이 아님, 아래의 조건을 만족해야 최적의 해를 구함탐욕적 선택 속성(Greedy Choice Property): 현재의 선택이 나머지 선택에 영향을 주지 않음최적 부분 구조(Optimal Subst..

병합 정렬원리: 데이터를 반으로 나누어 정렬 후 병합특징: 안정적인 정렬이며, 추가적인 메모리 공간 필요공간 복잡도: O(n)시간 복잡도: O(n log n)예시최초에는 8개의 그룹으로 나눔이 상태에서 2개씩 그룹을 합치며 오름차순 정렬투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합함왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킴[5, 3, 8, 2, 4, 1, 6, 7]→ [5], [3], [8], [2], [4], [1], [6], [7]→ [3, 5], [2, 8], [1, 4], [6, 7]→ [2, 3, 5, 8], [1, 4, 6, 7] // 여기 병합 기준으로 설명→ [1, 2, 3, 4, 5, 6, 7, 8]왼쪽 배열: [2, ..

선택 정렬원리: 배열에서 가장 작은(큰) 데이터를 찾아 맨 앞 데이터와 교환특징: 단순하지만 비효율적, 교환 횟수가 적음공간 복잡도: O(1)시간 복잡도: O(n^2)예시[3, 2, 4, 1]→ [1, 2, 4, 3] // 1→ [1, 2, 4, 3] // 2→ [1, 2, 3, 4] // 3[3, 2, 4, 1] 중 가장 작은 수를 찾음 → 11과 인덱스 0번 데이터(3) 과 교환 → [1, 2, 4, 3]인덱스를 증가시켜 인덱스 1번 이후 [2, 4, 3] 중 가장 작은 수를 찾음 → 2인덱스 1번 데이터(2)와 스왑 → [1, 2, 4, 3]인덱스를 증가시켜 인덱스 2번 이후 [4, 3] 중 가장 작은 수를 찾음 → 3인덱스 2번 데이터(4)와 스왑 → [1, 2, 3, 4] 삽입 정렬원리: 데이터..

유클리드 알고리즘최대 공약수 (GCD, Greatest Common Divisor)를 효율적으로 구하는 알고리즘유클리드 호제법을 코드로 구현한 것https://ko.wikipedia.org/wiki/유클리드_호제법 유클리드 호제법두 정수의 최대공약수를 구하는 방법으로, 나눗셈의 나머지를 반복적으로 계산하는 방식 호제법“서로를 나눈다”라는 뜻큰 수를 작은 수로 나누고 그 나머지를 이용해 반복적으로 계산하는 알고리즘GCD(a, b) = GCD(b, a mod b)→ a mod b : a를 b로 나눈 나머지 알고리즘 과정두 수 a, b를 비교하여 a ≥ b가 되도록 설정a를 b로 나눈 나머지 r = a mod b를 계산a를 b로 b를 r로 대체나머지 r이 0일 될 때까지 2~3단계를 반복나머지가 0이 되는 순..

에라토스테네스의 체 (Erathosthenes' Sieve)소수(Prime Number)를 판별하는 알고리즘자연수 N에 대해 에라토스테네스의 체 알고리즘을 수행하면 2~N 범위의 자연수는 O(1) 만에 소수인지를 판별 가능함원리: 작은 수부터 시작하여 배수를 제거하는 방식으로 소수를 걸러냄n의 제곱근 이하의 숫자들에 대해 반복함n의 제곱근 이하의 숫자까지만 반복하는 이유어떤 수 n이 소수가 아니라면, n은 두 수의 곱으로 표현됨n = a * b이때 a, b 중 적어도 하나는 루트n 이하임예를 들어 n = 36일 때a = 2, b = 18 → a는 루트 36 = 6 이하a = 4, b = 9 → a는 루트 36 = 6 이하a = 6, b = 6 → a, b 모두 36 = 6 이하따라서 제곱근까지만 검사하면..