5장 컴퓨터 과학/Data Structure & Algorithm27 [알고리즘] 동적 프로그래밍 동적 프로그래밍 해결법 단순 하위문제들(simple subproblems): 전체적인 최적화 문제를 하위문제들로 반복적으로 쪼개는 어떠한 방법이 존재해야 한다. 더욱이 i, j, k 등과 같이 단지 약간의 색인들로서 하위문제들을 정의하는 단순한 방법이 존재해야 한다. 하위문제 최적화(subproblem optimization): 전체적인 문제에 대한 최적화 해법은 하위문제들을 위한 최적 해결법들의 합성이어야만 한다. 하위문제 중복(subproblem overlap): 관련되지 않은 하위문제들에 대한 최적화 해법들은 공통적으로 다른 하위문제들을 포함할 수 있다. LCS 문제 긴 공통의 서브시퀀스(Longest Common Subsequence, LCS) 문제는 두 개의 문자열에 대해 두 문자열의 부분문자열.. 2021. 6. 22. [자료구조] 문자열 (String) 개념 C++는 두 종류의 문자열(string)을 지원한다. C-스타일 문자열은 char 타입의 배열로서 null 문자 '\0'으로 끝난다. C-스타일 문자열 자체는 복잡한 문자열 연산을 지원하지 않는다. STL은 완벽한 string 클래스를 제공한다. string 클래스의 ADT는 다음과 같다. 추상 데이터 타입(ADT) size(): 문자열에 포함된 문자의 수 n을 반환한다. empty(): 문자열이 비었다면 true를 그렇지 않다면 false를 반환한다. operator[i]: 문자열의 인덱스 i에 있는 문자를 반환한다. insert(i,Q): 문자열의 인덱스 i앞에 문자열 Q를 삽입한다. append(Q): 문자열 뒤에 문자열 Q를 연결한다. erase(i, m): 문자열의 인덱스 i부터 m개의 문.. 2021. 6. 22. [자료구조] 셋 (Set) 개념 셋(Set)은 분리 객체들의 컨테이너이다. 즉, 집합 내에 중복되는 원소가 없고 순서나 키의 명백한 개념도 없다. 추상 데이터 타입(ADT) insert(e): 셋에 원소 e를 삽입하고, 원소의 위치 iterator를 반환한다. 만약 셋에 이미 e가 존재하면 연산을 무시한다. find(e): 만약 셋에 e가 존재하면 그 iterator를 반환하고, 그렇지 않으면 end iterator를 반환한다. erase(e): 셋에서 e를 제거한다. lower_bound(e): 셋에서 e보다 작거나 같은 원소 중 가장 큰 원소의 iterator를 반환한다. upper_bound(e): 셋에서 e보다 크거나 같은 원소 중 가장 작은 원소의 iterator를 반환한다. 2021. 6. 17. [알고리즘] 기수 정렬(Radix Sort) 기수 정렬은 정렬 시간이 $O(n\log{n})$ 이하로 소요되는 정렬이다. ...작성중... 2021. 6. 17. [알고리즘] 버킷 정렬(Bucket Sort) 버킷 정렬은 정렬 시간이 $O(n\log{n})$ 이하로 소요되는 정렬이다. 배열에 들어있는 원소에 따라 적절히 버킷을 나눈다. 배열에 들어있는 원소를 규칙에 따라 버킷에 나눠 넣는다. 각각의 버킷을 정렬한다. 버킷을 순서대로 방문하며 모든 원소를 다시 배열에 넣는다. ...작성중... 2021. 6. 17. 이전 1 2 3 4 ··· 6 다음 반응형
