Algorithms (44) 썸네일형 리스트형 [LeetCode] 3. Longest Substring Without Repeating Characters — 슬라이딩 윈도우 개념 & 최적 풀이 (Java) ✔️ 오늘의 리트코드 공부 기록 – Longest Substring Without Repeating Characters (슬라이딩 윈도우 사고가 핵심이었다) 문제 요약 (Longest Substring Without Repeating Characters)문자열에서 중복 문자가 없는 가장 긴 “연속 부분 문자열(substring)”의 길이를 구하는 문제 문제링크: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/🤔 처음 떠올린 접근 — 하지만 실패한 방법 문제를 처음 보자마자 자연스럽게 이렇게 생각했다. “Set으로 중복만 막으면 되지 않을까?”“right 포인터만 움직이면 되겠네?” 그래서 이.. [LeetCode] 5. Longest Palindromic Substring 풀이 및 설명 (Java) ✔️ 오늘의 리트코드 공부 기록 – Longest Palindromic Substring (생각보다 사고 전환이 핵심이었다) 문제 요약 (Longest Palindromic Substring)문자열에서 가장 긴 팰린드롬(앞뒤가 동일한 연속 부분 문자열)을 찾는 문제 문제링크: https://leetcode.com/problems/longest-palindromic-substring 처음엔 가장 자연스럽게 이런 생각이 들었다.“왼쪽부터 substring 을 늘려가면서 확인하면 되지 않을까?”“아니면 길이를 1, 2, 3... 이렇게 늘리면서 가장 긴 팰린드롬을 찾을까?”그런데 조금만 생각해보니 이 방식은 결국 모든 substring 을 확인해야 한다.팰린드롬 확인(O(n)) + substring 개수(O.. 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)를 비교합니다. - 중간.. 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.. 해시 함수 (Hash Table) Hash Function 해시 함수(hash function) 또는 해시 알고리즘(hash algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이때, 이 고정된 길이는 해시 함수마다 다릅니다. 하지만 동일한 해시 함수는 동일한 길이의 데이터를 출력합니다. 아래 그림과 같이, data를 hash function에 입력하면, 이 함수는 고정된 길이의 값을 출력합니다. 해시 함수에 의해 얻어지는 값을 해시 값(Hash value) 이라고 합니다. 해시 함수의 특징 해시 값은 항상 고정된 길이의 값을 가집니다.(위 설명 참고) 같은 입력값이면 해시 값은 항상 동일합니다. 다른 입력값일 때, 1bit만 다르더라도 해시 값은 크게 달라질 수 있습니다. 다른 입력값일 때, 같은 .. 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 이전 1 2 3 4 5 6 다음
