티스토리

별별기록

검색하기

블로그 홈

별별기록

silver-programmer.tistory.com/m

백엔드 개발자의 기록😃

구독자: 1

방명록 방문하기

728x90

주요 글 목록

Lower_bound & Upper_bound 알고리즘 최근 leet code의 Longest Increasing Sequence (최장 부분 수열) 알고리즘 문제를 풀다가, 예전에 공부했던 lower_bound, upper_bound 개념과 구현이 기억이 나질 않아... 이번 기회에 정리해 보았습니다 ㅎㅎ 항상 두 개념이 헷갈렸었는데 이번 포스팅을 통해 개념을 계속 기억하길 바라는 마음으로 두 개념 비교 위주로 정리하였습니다.Lower_bound와 Upper_bound 비교 개념알고리즘 구현Lower_bound특정 k값의 시작 위치(k값보다 크거나 같은 위치)를 찾는 알고리즘[1, 2, 3, 3, 5, 6, 8] ^(lower bound of 3)1. 배열의 중간값 (mid) 를 가져옵니다.2. 중간 값과 검색 값(k)를 비교합니다. - 중간.. 공감수 1 댓글수 0 2025. 1. 11.
Suffix Array (접미사 배열) 접미사 배열 접미사 배열이란, 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 의미합니다. 즉 아래 예시처럼 문자열 "banana"의 모든 접미사들을 정렬한 배열이라고 할 수 있습니다. 0 banana 5 a 1 anana Sort the Suffixes 3 ana 2 nana ----------------> 1 anana 3 ana alphabetically 0 banana 4 na 4 na 5 a 2 nana 접미사 배열 구하기 접미사 배열을 구현하는 알고리즘에는, Naive 알고리즘과 Manber-Myers 알고리즘이 있습니다. Naive 알고리즘 접미사 배열을 만드는 가장 쉬운 방법으로, 단순히 비교 정렬 알고리즘을 이용해서 구현하는 방식입니다. 문자열의 길이가 n이라고 할 때, 접미사는 n.. 공감수 0 댓글수 2 2023. 12. 17.
해시 함수 (Hash Table) Hash Function 해시 함수(hash function) 또는 해시 알고리즘(hash algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이때, 이 고정된 길이는 해시 함수마다 다릅니다. 하지만 동일한 해시 함수는 동일한 길이의 데이터를 출력합니다. 아래 그림과 같이, data를 hash function에 입력하면, 이 함수는 고정된 길이의 값을 출력합니다. 해시 함수에 의해 얻어지는 값을 해시 값(Hash value) 이라고 합니다. 해시 함수의 특징 해시 값은 항상 고정된 길이의 값을 가집니다.(위 설명 참고) 같은 입력값이면 해시 값은 항상 동일합니다. 다른 입력값일 때, 1bit만 다르더라도 해시 값은 크게 달라질 수 있습니다. 다른 입력값일 때, 같은 .. 공감수 0 댓글수 0 2023. 12. 13.
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 공감수 0 댓글수 0 2023. 12. 10.
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: 문자.. 공감수 0 댓글수 0 2023. 12. 9.
비트 연산 활용 N번째 비트 조회 변수 target의 N번째 비트가 1인지 여부: AND 연산을 수행합니다. 해당 연산이 0이면 비트가 없는 것이고, 1이면 비트가 있는 것입니다. target & (1 공감수 2 댓글수 4 2023. 12. 3.
그리디 알고리즘 (Greedy)과 다이나믹 프로그래밍 (DP) 그리디 여러 경우 중 하나를 선택할 때마다 그 순간에 최적인 해를 선택해 나가는 근시안적인 방법이다. 특징 각 선택 시점의 결정이 지역적으로 최적이고, 그 결정들이 모여 만든 답이 최적해라는 보장이 있어야 사용가능하다. 이미 선택한 결정은 번복하지 않기 때문에 대부분의 단순하며 제한적인 문제들에 적용된다. 두 가지 필수 요소 Greedy choice property: 탐욕적 선택 속성 탐욕적 선택이 최적해로 갈 수 있음을 보이고 탐욕적 선택이 항상 안전하다는 것을 확인해야 한다 2. Optimal substructure property: 최적 부분 구조 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남아야 한다. ==> 원 문제의 최적 해 = 탐욕적 선택 + 하위 문제의 최적 해 DP ‘귀납법’을 만.. 공감수 0 댓글수 0 2023. 10. 18.
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로 구할 할 수 있습니다. 증명 오일러 곱 공.. 공감수 0 댓글수 2 2023. 9. 9.
KMP 알고리즘 문자열 검색 알고리즘으로 많이 등장하는 KMP 알고리즘에 대해서 알아보겠습니다. KMP는 Knuth Morris Partt의 줄임말로 이 알고리즘을 발견한 사람 이름을 딴 것입니다. 어떤 문자열 A에 문자열 B가 있는지 확인하려면 단순하게 A 문자열(길이 N)과 B 문자열(길이 M)을 하나하나 비교한다면, 시간 복잡도는 O(NM)가 될 것입니다. KMP 알고리즘은 이 시간 복잡도 보다 더 효율적으로 줄여 O(N+M) 만에 문자열을 검색할 수 있는 방법입니다. 어떻게 획기적으로 시간 복잡도를 줄일 수 있었는지 KMP에 대해서 알아보겠습니다. 먼저, KMP 알고리즘을 알기 전에 미리 알아야 할 사전 지식을 살펴보겠습니다. 사전지식 접두사(Prefix)와 접미사(Suffix) 우선 접두사와 접미사가 무엇인지 .. 공감수 0 댓글수 0 2023. 9. 2.
LCA - 최소 공통 조상 LCA(Lowest Common Ancestor) 알고리즘이란?트리에서의 두 정점 u, v에서 가장 가까운 공통 조상을 찾는 알고리즘입니다. 즉, 가장 가까운 공통 조상은 두 정점 u, v를 자손으로 가지는 노드들 중 깊이가 가장 깊은 노드를 의미합니다. 이 글에서는 LCA를 2가지 방법으로 구해보겠습니다. 첫 번째는 O(N)만에 구할 수 있는 알고리즘이고 두 번째 방법은 O(logN)만에 구할 수 있는 알고리즘입니다. 1. O(N) 알고리즘지금 소개해 드릴 이 방법은 간단합니다. 먼저 알고리즘부터 살펴보겠습니다.[알고리즘] 1. 두 정점 u, v의 깊이가 같은지 확인합니다. 만약 두 정점의 깊이가 다르다면 두 정점의 깊이가 같아질 수 있도록 한 칸씩 트리를 타고 올라가면서 깊이를 맞춰줍니다. 2. 두 .. 공감수 0 댓글수 0 2023. 8. 27.

728x90

반응형

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.