알고리즘 알고리즘/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.. 알고리즘/BOJ 2020. 3. 29. [C++] 백준 11652번 - 카드 0. 문제 1. 아이디어 1) N개의 숫자카드에 적혀 있는 정수들을 arr 배열에 저장하고 sort 함수를 사용해서 정렬한다. 2) 오름차순으로 정렬된 arr 배열에서 어떤 정수가 몇 개가 있는지를 카운트해서 pair 쌍으로 저장한다. ex) 1이라는 값이 3개가 존재한다면 tmp 배열에 으로 저장한다. 3) tmp 배열에서 second(개수)가 가장 큰 원소의 first(값)을 출력한다. 2. 소스코드 #include #include #include long long arr[100000]; std::pair tmp[100000]; int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); int N; std::cin >> N; for (int i.. 알고리즘/BOJ 2020. 3. 29. [C++] 백준 10989번 - 수 정렬하기 3 0. 문제 1. 아이디어 1) counting sort 를 이용한다! 2. 소스코드 #include #include int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); int N, arr[10001]; std::cin >> N; memset(arr, 0, sizeof(arr)); for (int i = 0; i > input; arr[input]++; } for (int i = 1; i 이전 1 2 3 4 ··· 7 다음
