Algorithms (31) 썸네일형 리스트형 C언어 - Quick sort 구현 Pivot 선택을 위한 Partition 첫 번째 방법 int hoarePartition(int* a, int low, int high) { int p = a[low]; int i = low; int j = high; while (i C언어 - 문자열 탐색, 비교 구현해보기 이번 포스팅은 C++를 사용하지 않고 (라이브러리 없이) C언어를 이용하여 직접 문자열 관련 함수들을 구현해 보았습니다. strlen: 문자열 길이 C++의 str.size() 혹은 str.length() C언어 첫 번째 방법 (포인터) int strlen(const char* str) { int len = 0; while (*str != '\0') { ++len; ++str; } return len; } int main() { printf("%d\n", strlen("Hello")); // 5 } 두 번째 방법 (배열) int strlen(const char* str) { int len = 0; while (str[len] != '\0') { ++len; } return len; } strcpy: 문자.. 비트 연산 활용 N번째 비트 조회 변수 target의 N번째 비트가 1인지 여부: AND 연산을 수행합니다. 해당 연산이 0이면 비트가 없는 것이고, 1이면 비트가 있는 것입니다. target & (1 그리디 알고리즘 (Greedy)과 다이나믹 프로그래밍 (DP) 그리디 여러 경우 중 하나를 선택할 때마다 그 순간에 최적인 해를 선택해 나가는 근시안적인 방법이다. 특징 각 선택 시점의 결정이 지역적으로 최적이고, 그 결정들이 모여 만든 답이 최적해라는 보장이 있어야 사용가능하다. 이미 선택한 결정은 번복하지 않기 때문에 대부분의 단순하며 제한적인 문제들에 적용된다. 두 가지 필수 요소 Greedy choice property: 탐욕적 선택 속성 탐욕적 선택이 최적해로 갈 수 있음을 보이고 탐욕적 선택이 항상 안전하다는 것을 확인해야 한다 2. Optimal substructure property: 최적 부분 구조 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남아야 한다. ==> 원 문제의 최적 해 = 탐욕적 선택 + 하위 문제의 최적 해 DP ‘귀납법’을 만.. Euler's Phi (오일러 파이 함수) 개념 및 정의 오일러 파이 함수의 정의는 아래와 같습니다. 즉, 이를 해석해 보면 양의 정수 n의 오일러 파이 함수는, 1부터 n까지의 정수 가운데 n과 서로소인 것들의 개수 입니다. 성질 1. 두 정수 m과 n이 서로소인 경우 n의 서로소 개수 곱과 m의 서로소 개수 곱은 n*m의 서로소 개수입니다. 2. 정수 p가 소수인 경우 소수 p의 서로소는 1을 제외한 모든 수입니다. 3. 소수 p의 거듭제곱인 경우 1~3을 종합한 결론 위 성질들을 통해 소인수를 이용한 오일러 파이 함수를 아래와 같이 구할 수 있습니다. 그리고 아래 함수를 오일러 곱 공식이라고 합니다. 예를 들어, 20의 소인수는 2와 5 이므로, ∅(20) 은 20(1-1/2)(1-1/5) = 8로 구할 할 수 있습니다. 증명 오일러 곱 공.. KMP 알고리즘 문자열 검색 알고리즘으로 많이 등장하는 KMP 알고리즘에 대해서 알아보겠습니다. KMP는 Knuth Morris Partt의 줄임말로 이 알고리즘을 발견한 사람 이름을 딴 것입니다. 어떤 문자열 A에 문자열 B가 있는지 확인하려면 단순하게 A 문자열(길이 N)과 B 문자열(길이 M)을 하나하나 비교한다면, 시간 복잡도는 O(NM)가 될 것입니다. KMP 알고리즘은 이 시간 복잡도 보다 더 효율적으로 줄여 O(N+M) 만에 문자열을 검색할 수 있는 방법입니다. 어떻게 획기적으로 시간 복잡도를 줄일 수 있었는지 KMP에 대해서 알아보겠습니다. 먼저, KMP 알고리즘을 알기 전에 미리 알아야 할 사전 지식을 살펴보겠습니다. 사전지식 접두사(Prefix)와 접미사(Suffix) 우선 접두사와 접미사가 무엇인지 .. LCA - 최소 공통 조상 LCA(Lowest Common Ancestor) 알고리즘이란?트리에서의 두 정점 u, v에서 가장 가까운 공통 조상을 찾는 알고리즘입니다. 즉, 가장 가까운 공통 조상은 두 정점 u, v를 자손으로 가지는 노드들 중 깊이가 가장 깊은 노드를 의미합니다. 이 글에서는 LCA를 2가지 방법으로 구해보겠습니다. 첫 번째는 O(N)만에 구할 수 있는 알고리즘이고 두 번째 방법은 O(logN)만에 구할 수 있는 알고리즘입니다. 1. O(N) 알고리즘지금 소개해 드릴 이 방법은 간단합니다. 먼저 알고리즘부터 살펴보겠습니다.[알고리즘] 1. 두 정점 u, v의 깊이가 같은지 확인합니다. 만약 두 정점의 깊이가 다르다면 두 정점의 깊이가 같아질 수 있도록 한 칸씩 트리를 타고 올라가면서 깊이를 맞춰줍니다. 2. 두 .. 이전 1 2 3 4 다음
