좋아요!

KMP 알고리즘의 시간복잡도는 O(n + m)이다. (n: 텍스트 길이, m: 패턴 길이)

KMP 알고리즘은 실패 함수(failure function)를 사용하여 불필요한 비교를 건너뛰어 O(n + m)에 패턴 매칭을 수행합니다.

병합 정렬(Merge Sort)은 in-place 정렬 알고리즘이다.

병합 정렬은 정렬 과정에서 추가적인 O(n) 메모리가 필요하므로 in-place 알고리즘이 아닙니다.

NP-완전 문제는 다항 시간 내에 해를 구할 수 있는 알고리즘이 아직 발견되지 않았다.

NP-완전 문제는 현재까지 다항 시간 알고리즘이 알려지지 않았으며, P≠NP가 증명되지 않았기에 존재 여부도 미해결입니다.

분할정복(Divide and Conquer)은 문제를 작은 부분 문제로 나누어 해결하는 방식이다.

분할정복은 문제를 더 작은 부분 문제로 분할하고, 각각을 재귀적으로 해결한 뒤 결합하는 알고리즘 설계 패러다임입니다.

O(n log n)과 O(n²) 중 O(n log n)이 더 효율적인 시간복잡도이다.

n log n은 n²보다 느리게 증가하므로 O(n log n)이 더 효율적입니다. 대표적으로 병합정렬이 O(n log n), 버블정렬이 O(n²)입니다.

동적 프로그래밍(DP)은 최적 부분 구조와 중복 부분 문제 성질을 가진 문제에 적용된다.

DP는 문제가 최적 부분 구조(Optimal Substructure)와 중복 부분 문제(Overlapping Subproblems) 두 가지 성질을 가질 때 적용할 수 있습니다.

그리디(Greedy) 알고리즘은 항상 최적해를 보장한다.

그리디 알고리즘은 각 단계에서 지역적 최적해를 선택하지만, 전체적으로 최적해를 보장하지는 않습니다. 특정 조건(그리디 선택 속성, 최적 부분 구조)이 만족될 때만 최적해를 보장합니다.

아모타이즈드(Amortized) 분석에서 동적 배열의 삽입 연산은 O(1)이다.

동적 배열은 가끔 리사이징이 필요하지만, 분할 상환 분석(amortized analysis)을 적용하면 평균적으로 삽입 연산은 O(1)입니다.

재귀 함수는 반드시 종료 조건(Base Case)이 있어야 한다.

종료 조건이 없는 재귀 함수는 무한히 자기 자신을 호출하여 스택 오버플로우가 발생합니다.

피보나치 수열을 DP로 계산하면 O(n) 시간복잡도로 구할 수 있다.

단순 재귀는 O(2^n)이지만, DP(메모이제이션 또는 타뷸레이션)를 사용하면 각 부분 문제를 한 번만 계산하여 O(n)에 해결할 수 있습니다.

크루스칼(Kruskal) 알고리즘은 최소 신장 트리(MST)를 구하는 알고리즘이다.

크루스칼 알고리즘은 간선을 가중치 순으로 정렬한 뒤, Union-Find를 사용하여 사이클 없이 최소 비용의 신장 트리를 구합니다.

이진 탐색은 정렬된 배열에서만 사용할 수 있다.

이진 탐색은 배열이 정렬되어 있어야 중간값을 기준으로 탐색 범위를 반으로 줄일 수 있습니다.

공간복잡도는 알고리즘이 사용하는 메모리의 양을 나타낸다.

공간복잡도(Space Complexity)는 알고리즘 실행에 필요한 메모리 공간의 총량을 입력 크기의 함수로 표현한 것입니다.

다익스트라(Dijkstra) 알고리즘은 음의 가중치가 있는 그래프에서도 정상 작동한다.

다익스트라 알고리즘은 음의 가중치가 있으면 정확한 최단 경로를 보장하지 못합니다. 음의 가중치가 있는 경우 벨만-포드 알고리즘을 사용해야 합니다.

해시 충돌(Hash Collision)은 절대 발생하지 않도록 설계할 수 있다.

비둘기집 원리에 의해 해시 함수의 출력 범위가 유한한 이상 충돌은 불가피합니다. 체이닝이나 개방 주소법으로 충돌을 처리합니다.