Algorithm283 [BOJ]15655번: N과 M(6) 조합 문제입니다. combination(idx + 1, cnt) combination(idx + 1, cnt + 1) 위 코드 두 줄의 의미가 가장 중요합니다. idx: 배열의 숫자 중 탐색을 수행할 인덱스 번호 cnt: N개 중 현재 몇 개를 뽑았는지 조합은 특정 숫자에 대해 뽑을지/말지를 결정합니다. 그러므로 매 깊이마다 최대 2개로 뻗어나갈 수 있습니다. 이를 통해 특정 숫자 num[idx]를 뽑을 수 있다면, 특정 숫자를 뽑는 combination(idx+1,cnt+1)과 뽑지 않는 combination(idx+1,cnt)을 모두 수행하고, 특정 숫자가 이미 사용되어 뽑을 수 없다면 뽑지 않는 combination(idx+1,cnt)만 수행해줍니다. 2020. 3. 6. [C++] String Split //예시1 #include #include #include /** @function: delimiter값을 기준으로 string data를 Tokenize하는 함수 @return: vector */ std::vector TokenizeByGetline(const std::string& data, const char delimiter) { std::vector result; std::string token; std::stringstream ss(data); while (getline(ss, token, delimiter)) { result.push_back(token); } return result; } //예시2 #include #include #include using namespace std; //c.. 2020. 1. 14. 힙을 사용해 K번째로 큰 수 구하기 힙을 사용해서 N개의 정렬되지 않은 데이터에 대해 K번째로 큰 숫자를 구하는 방법을 정리해보겠습니다. 1. MinHeap 사용 1ST. 최초 K개의 숫자에 대해 MinHeap을 구성합니다. (arr[0] ~ arr[k-1]) 2ND. 나머지 (N-1) - K개의 데이터값을 MinHeap의 루트와 비교하며 힙을 갱신합니다. (arr[k] ~ arr[n-1]) 2-1. 현재 데이터가 힙의 루트보다 큰 경우 → 힙 루트값 삭제, 현재 데이터 힙에 추가, 다시 MinHeap 만들기 2-2. 현재 데이터가 힙의 루트보다 작은 경우 → 무시 이렇게 N개의 데이터가 MinHeap의 루트와 비교가 끝나면, 힙의 루트값이 K번째로 큰 수가 됩니다. 그림을 통해 살펴보겠습니다. 시간복잡도는 1. K개의 원소로 MinHea.. 2019. 11. 1. 이전 1 ··· 68 69 70 71 다음
