본문 바로가기
반응형

[백준]214

[BaekJoon/백준] 1920번 C++ 수 찾기 문제. 이중 포문을 돌게 되면 시간복잡도가 O(n^2)이 되어 아마 시간초과가 날 것이다. 그렇기 때문에 이진 탐색(바이너리 서치)을 구현했고, 이진 탐색을 사용하기 위해서 전제조건인 오름차순 정렬을 만들어 내기 위해 sort 함수를 사용했다. + 이진 탐색 : O(log N) C를 쓰다가 C++로 넘어온 케이스라, qsort를 쓰려고 했는데 C언어에서의 호환이 안되는지 라이브러리가 먹히지 않는 것 같아서 헤맸는데 C의 qsort보다 C++의 sort가 더 빠르다고 한다.. 그래서 졸지에 더 간단하게 구현할 수 있었다. + 퀵정렬 : O(Nlog N) #include #include // sort 함수 사용 위해 using namespace std; int ori[100000]; int N; i.. 2021. 3. 20.
[BaekJoon/백준] 1259번 C++/JAVA 어떤 단어를 뒤에서부터 읽어도 똑같다면 그 단어를 팰린드롬이라고 한다. 'radar', 'sees'는 팰린드롬이다. 팰린드롬수 판단 문제. 전체 문자열의 절반 기준으로 잘라서 앞과 뒤를 비교해줬다. #include #include using namespace std; int main() { string str; int i; while(1) { cin >> str; if(str[0] == '0') return 0; for(i = 0; i < (str.length() / 2); i++) { if(str[i] != str[str.length() - 1 - i]) { break; } } if(i == str.length() / 2) cout str; if(str[0] == '0') return 0; temp =.. 2021. 3. 20.
[BaekJoon/백준] 2920번 C++/JAVA 음계 숫자배열이 오름차순과 내림차순, 또는 둘 다 아닌지 판단한다. 오늘부터 기존 C언어 중심적인 풀이에서 C++ / JAVA 류의 언어로 넘어가기로했다. C언어로만 꽤 오래 잡고있었다 보니, C++과 JAVA로 작성해나감에 있어서 문법상 정말 많은 시간 버벅댔다. #include using namespace std; int main() { int arr[8]; int i; cin >> arr[0] >> arr[1]; bool asc = (arr[0] > arr[i]; if(asc) { if(arr[i - 1] >= arr[i]) break; } else { if(arr[i - 1] 2021. 3. 19.
[BaekJoon/백준] 11444번 분할정복 피보나치를 구하는 방법 중, 행렬의 제곱을 이용한 방법이 있다. 메모이제이션을 사용한 피보나치는 O(N)의 시간복잡도를 갖는 반면 10830번에서 볼 수 있었듯, 행렬의 제곱은 분할정복을 사용해 O(logN)으로 해결할 수 있다. 사실 10830번 코드를 거의 그대로 갖다가 썼다가, 계속 메모리 초과가 나와서 애를 먹었다.. 이유는.. 10830번에서는 제곱수가 1부터지만 11444번에는 제곱수가 0부터 가능해서 예외가 있었던 것 ㅜ #include #include long long arr[2][2]; long long original[2][2]; long long temp1[2][2]; int N = 2; long long B; int i, j, m; // 재귀 속에서 정적 변수인 arr을 공용으로 사.. 2021. 3. 19.
반응형

티스토리툴바