All about Data Structure & Algorithm/기본 (14) 썸네일형 리스트형 동적계획법(Dynamic Programming) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 동적 계획법은 복잡한 문제를 효율적으로 해결하는 알고리즘 설계 기법 중 하나이다. ② 동적 계획법은 일반적으로 다음과 같은 단계로 수행된다. ㉠ 문제를 하위 문제로 나눈다. ㉡ 가작 작은 크기의 하위 문제부터 해를 구한다. ㉢ 작은 하위 문제의 해를 저장하고, 큰 문제의 해를 계산할 때 이를 이용한다. ㉣ 모든 하위 문제의 해를 계산하여 최종적인 문제의 해를 구성한다. ③ 동적계획법을 사용하기 위해선 문제가 최적 부분 구조와 중복 부분 문제를 만족해야 한다. ㉠ 최적 부분 구조(Optimal Substructure)를 갖는 문제는 큰 문제의 최적해가 작은 하위 문제들의 최적해로 구성되는 경우를 말한다. ⓐ 정점 A, B, C, D가 존재하고 각 .. 브루트 포스 ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. 문자열 검색 알고리즘: KMP(Knuth-Morris-Pratt) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 검색 알고리즘(string matching algorithm) 중 하나로, 특정 패턴 문자열을 찾기 위한 알고리즘이다. ㉠ 보이어-무어 알고리즘(boyer-moore algorithm)과 함께 가장 많이 사용되는 문자열 검색 알고리즘이다. ② 브루트 포스 방식을 이용하면 최악의 경우 O(N * M)의 시간 복잡도를 갖기 때문에 이를 사용하는 것은 효율적이지 않다. 브루트 포스 ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. hemahero.tistory.com ③ KMP 알고리즘은 패턴 문자열의 접두사와 접미사가 일치하는 최대 길이를 이용한다. ㉠ 패턴의 유사도를 측정하여 불필요.. 시간 복잡도(Time Complexity) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 시간 복잡도(time complexity)는 알고리즘의 수행 시간이 입력 크기에 따라 어떻게 증가하는지를 분석하는 데 사용되는 개념이다. ② 알고리즘의 시간 복잡도를 분석할 떄는 일반적으로 알고리즘이 실행하는 기본적인 연산 수행 횟수를 계산하고, 이를 입력 크기와 비교한다. ③ 시간 복잡도는 일반적인 최선, 평균, 최악의 경우로 나뉜다. ④ 시간 복잡도는 일반적으로 빅오(Big - O) 표기법을 사용하여 표기한다. 빅오 표기법은 입력 크기에 대한 함수의 상한(upper bound)을 나타내며, 알고리즘의 실행 시간이 이 함수보다 더 느리게 증가하지 않는 것을 보장한다. ㉠ 이를 수학식으로 나타내면 다음과 같이 나타낼 수 있다. ⓐ 이 부등식은 알.. 바이토닉 정렬(Bitonic Sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 바이토닉 정렬(bitonic sort)는 병렬 배열들을 정렬하기에 효과적인 정렬 방법이다. ② 바이토닉 정렬의 최악의 시간 복잡도는 O(n log^2 (n))이다. ㉠ 시간 복잡도를 볼 경우 그다지 뛰어난 성능을 가진 것 같아 보이지 않는다. ⓐ 그러나 바이토닉 정렬은 병렬 배열을 정렬할 때와 같은 특정 상황에서 쉽게 병렬화할 수 있고, 캐시 효율이 좋다는 장점이 있다. ③④⑤⑥⑦⑧⑨⑩⑪⑫⑬⑭⑮ ㉠㉡㉢㉣㉤㉥㉦㉧㉨㉩㉪㉫㉬㉭ ⓐⓑⓒⓓⓔⓕⓖⓗⓘⓙⓚⓛⓜ 기수 정렬(Radix Sort) 계수 정렬(Counting Sort) 힙 정렬(Heap Sort) 이전 1 2 다음
