본문 바로가기

전체 글

무제 보호되어 있는 글입니다.
알고리즘/BOJ 2020. 4. 14. [C++] 백준 1168번 - 요세푸스 문제 2 0. 문제 1. 아이디어 1) 1번부터 N번까지, 총 N명의 사람을 vector에 삽입하고 순서대로 K번째 사람을 탐색해가면서 vector에서 제거하고 다음 K번째 사람을 탐색하는 과정을 반복한다. 2) 이때 K번째 사람을 찾는다고 해서 index의 값을 +k 한다고 생각할 수도 있지만 그렇지 않다. 이미 앞전의 과정에서 하나의 원소를 vector에서 제거했기 때문에 결과적으론 +k-1 하면 된다! 2. 소스코드 #include #include int main() { int K, N; std::cin >> N >> K; std::vector v(N); std::vector result; for (int i = 0; i < N; i++) v[i] = i + 1; int idx = 0; while (!v.e..
알고리즘/BOJ 2020. 3. 30. [C++] 백준 11656번 - 접미사 배열 0. 문제 1. 아이디어 1) 접미사들을 vector에 넣어서 sort 함수를 이용해서 정렬한 뒤 출력한다! 2. 소스코드 #include #include #include int main() { std::vector v; std::string str; std::cin >> str; for (int i = 0; i < str.length(); i++) v.push_back(str.substr(i)); sort(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) std::cout
알고리즘/BOJ 2020. 3. 30. [C++] 백준 11655번 - ROT13 0. 문제 1. 아이디어 2. 소스코드 #include #include int main() { std::string str; std::getline(std::cin, str); for (int i = 0; i = 'a' && str[i] 'z') str[i] -= 13; else str[i] += 13; } else if (str[i] >= 'A' && str[i] 'Z')str[i] -= 13; else str[i] += 13; } } std::cout
알고리즘/BOJ 2020. 3. 30. [C/C++] 문자 입력 함수 정리 C 1. getchar() // int getchar(void) 내부에 존재 표준 입력 스트림에서 문자 하나를 읽어올 때 사용 키보드 버퍼(stdin)로부터 공백(' ')이나 개행문자('\n') 또한 입력을 받으니 주의해서 사용해야한다. 만일 파일 끝에 도달하거나, 읽기 오류가 발생한다면 함수는 EOF를 return 2. getc() // int getc(FILE* stream) getcar() 함수와 기능적으로 동일하게 작동한다! 3. getch(), getche() // int getch(void), int getche(void) 내부에 존재 키보드 버퍼를 사용하지 않고 바로 출력을 내보낸다 Enter 값을 인식할 때 getch()와 getche()는 '\r'로 인식한다. getche()는 getch..
알고리즘/BOJ 2020. 3. 29. [C++] 백준 11004번 - K번째 수 0. 문제 1. 아이디어 1) 단순히 sorting 한 후에 K번재 index를 참조하면 시간초과가 난다.. 2) 따라서 Quick Selection 이라는 방법을 새로 사용해야 했다! (nth_element) 2. 소스코드 #include #include #include std::vector v; int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); int N, K; std::cin >> N >> K; for (int i = 0; i > input; v.push_back(input); } std::nth_element(v.begin(), v.begin() + K-1, v.end())..
알고리즘/써먹기 좋은 알고리즘 2020. 3. 29. Quick Selection을 이용한 k번째 숫자 탐색: O(n)의 시간 복잡도 N개의 원소 중 k번째로 작은 수를 찾아라 라는 문제를 만났을 때 가장 많이 사용하는 방법 중 하나는 컨테이너를 sorting 후에 k번째 인덱스를 참조하는 방식을 사용한다. 하지만 이렇게 정렬을 했을 경우엔 전체 시간 복잡도가 worst case O(N^2) 혹은 O(N longN)가 되어버리므로 원소의 개수가 많을 경우엔 적합하지 않다. 따라서 Quick Selection 알고리즘을 이용해서 O(N)의 시간 복잡도를 가지는 탐색을 구현할 수 있다. 이름에서도 유추할 수 있듯이 기본 idea는 Quick Sort에서 따왔다. int quick_selection(int n, int* ArrList, int k) { if (ArrList == NULL || n = mid) { std::swap(ArrLis..
씨플플 2020. 3. 29. [C++] map, multimap container 정리 map과 multimap container은 연관 컨테이너(associative container) 중 하나이다. 1. map, multimap container의 특징 노드 기반으로 이뤄진 균형 이진 트리 구조이다. 각 노드들은 로 이뤄진 pair 객체를 가진다. (이때 map에서는 각 노드는 고유한 key 값을 가지지만, multimap은 중복된 key 값을 허용한다) 노드가 삽입이 되면서 key 값을 기준으로 자동으로 정렬이 이뤄진다. (default는 오름차순!) 저장공간의 필요에 따라서 allocator 객체를 사용한다. 2. 생성자, 연산자, 멤버함수 더보기 map과 multimap은 멤버함수가 동일하다.. 0) 생성자 map m; - int형 key와 int형 value로 이뤄진 pair 객..

티스토리툴바