Computer Science117 [자료구조] Chapter 12 분할 정복 분할 정복 기법의 개요1) 분할 정복 알고리즘의 배경분할 정복 알고리즘의 핵심은 문제를 잘게 나누는 것이다. 분할: 문제가 분할 가능한 경우 2개 이상의 하위 문제로 나누는 것. 정복: 하위 문제가 여전히 분할 가능한 상태라면 하위 집합에 대해 분할 단계를 수행하고, 아닌 경우 하위 문제를 푼다. 결합: 정복의 단계를 통해 답을 구하는 것. 병합 정렬1) 병합 정렬의 동작 방식병합 정렬은 나누고 합치는 것으로 정리할 수 있다. 아래의 과정을 보자면,정렬할 데이터를 반으로 나눈다.나뉜 하위 데이터의 크기가 2 이상이면 하위 데이터에 대해 단계 1을 반복한다.동일 데이터에서 나뉜 하위 데이터 둘을 병합하여 원래대로 하나의 데이터로 만든다. 단 병합할 때의 데이터 원소는 기준에 따라 정렬한다.데이터가 원래대로.. 2024. 1. 8. [자료구조] Chapter 11 알고리즘 성능 분석 알고리즘 성능 측정 기준과 수행 시간1) 알고리즘 성능 측정 기준정확성: 정확하게 동작하는가? 작업량: 얼마나 적은 연산을 수행하는가? 메모리 사용량: 얼마나 적은 메모리를 사용하는가? 단순성: 얼마나 단순한가? 최적성: 더 이상 개선할 여지가 없을 만큼 최적화되어 있는가?정확성알고리즘이 입력값에 대해 정해진 절차를 수행하여 결과적으로 정확한 출력을 제공하는가를 가리키는 기준이다.작업량작업량은 요구되는 기능을 수행하기 위해 알고리즘이 수행해야 하는 작업의 양이 얼마나 되는가를 가리키는 기준이다. 버블 정렬을 예로 들면, 정렬을 수행하기 위해 비교연산을 몇 번 수행해야 하는가가 해당한다.메모리 사용량해당 알고리즘이 작업을 수행할 때 사용해야 하는 메모리의 양을 의미한다.최적성알고리즘에 더 이상 개선할 부분.. 2024. 1. 4. [PS] while()문 해당 문제를 풀며 while문을 사용하게 되었다. 높이가 v 미터인 나무에 낮에는 a 미터 오르고 밤에는 b 미터 내려간다는 문제이다. 이 문제는 기본적으로 하루에 나무를 a - b 미터 올라가지만! 마지막 날에는 낮에 v 미터에 도달하면 더 이상 내려가지 않기 때문에 이를 고려해야 한다. 해당 부분에서 v미터 도달까지만 while문을 반복하고 아닌 경우에는 a-b의 과정을 반복하려 한다. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int A, B, V; int days = 0; int current_heights = 0; cin >> A >> B >> V; while(true){ days++; curre.. 2024. 1. 4. [PS] 문자열의 길이를 반환하는 .length() 해당 문제를 푸는 데에는 2가지 방법이 있다. 1. string 클래스의 멤버 함수를 사용하는 경우 2. 단순하게 구현하는 경우 "string 클래스의 멤버 함수를 사용하는 경우"를 먼저 보자면! .length()는 C++ 표준 라이브러리의 string 클래스에 정의된 멤버 함수이다. 해당 함수는 문자열의 길이를 반환하는데, 문자열에 포함된 문자의 개수를 반환하는 것이다. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string word; cin >> word; cout > word; for(int i=0; word[i]; i++){ count += 1; } cout 2024. 1. 3. [자료구조] Chapter 10 문자열 탐색 고지식한 탐색 알고리즘1) 고지식한 탐색의 동작 방식기본적인 문자열 검색 방식이다. 처음부터 끝까지 쭉 검색하는 것이다. 순차 탐색과 같은 맥락이다. 이러한 검색 방법은 본문의 길이를 N, 패턴의 길이를 M이라 치면 N*M번의 비교를 수행한다. 카프-라빈 알고리즘1) 카프-라빈 알고리즘의 동작 방식카프-라빈 알고리즘은 문자열 탐색을 위해 해시 함수를 이용한다. 패턴 내의 문자들을 일일이 비교하는 대신 패턴의 해시값과 본문 내에 있는 하위 문자열의 해시값만 비교하는 방식이다. 하지만 이러한 방식은 최초의 해시 함수와 새 해시 함수 모두 문자열의 길이가 늘어나면 해시값도 같이 커진다는 문제가 있다. 찾으려는 문자열의 해쉬 값을 찾고 본문에서 같은 길이만큼의 문자열의 해쉬를 구하고 체크해 보는 것이다. 이때 .. 2024. 1. 3. 이전 1 2 3 4 5 ··· 24 다음 반응형
