본문 바로가기

정렬4

[백준] 1920번 : 수 찾기 | binary search (C++) 문제 풀이 C++ 내 내장되어 있는 binary_search( ) 함수를 이용해 풀이했다. 시간복잡도는 O(logn)으로 빠른 속도로 계산할 수 있다. 입력받는 정수의 범위가 2의 31승까지 이므로 long long으로 선언한다. int n, m; long long listnum, findnum; cin >> n; vector을 이용해 입력받은 값을 저장한다. vector listv; for (int i = 0; i > listnum; listv.push_back(listnum); } binary search는 가운데에 있는 값(중간 크기의 값)을 기준으로 정렬하기 때문에, 꼭 오름차순 혹은 내림차순으로 정렬해야 한다. 따라서, sort() 함수를 이용해 정렬한 후 bian.. 2024. 4. 1.
[백준] 1431번 : 시리얼 번호 | vector 구조체 (C++) 문제 풀이 '구조체를 이용한 벡터'로 풀이했다. 비슷한 정렬 문제 풀이를 아래에 첨부한다. 아래는 vector에 구조체를 넣어 같은 방식으로 풀이한 정렬 문제이다. [백준] 10825번 : 국영수 (C++) 문제 풀이 vector에 구조체를 넣어 풀이했다. 아래는 array에 구조체를 넣어 풀이한 문제이다. 또한, vector을 이용한 sort 함수와 사용자 지정 compare을 자세히 설명해놓았으니 이 부분이 어렵다면 읽 jigoo-log.tistory.com array에 구조체를 넣어 풀이한 정렬 문제이다. 또한, vector을 이용한 sort 함수와 사용자 지정 compare을 자세히 설명해놓았으니 이 부분이 어렵다면 읽어보는걸 추천한다! 👍👍 [백준] 11650번 : 좌표 정렬하기 | Sort 함.. 2024. 3. 18.
[백준] 11656번 : 접미사 배열 | string.substr() 함수를 이용한 '부분 문자열 추출' (C++) 문제 풀이 string.substr() 함수를 이용하여 부분적으로 문자열을 추출했다. 아래는 substr() 함수에 대한 설명이다. #include //substr() 함수를 사용하기 위한 헤더 파일 string str = "CandyShop"; // str.substr(첫 번째 문자의 위치, 추출할 문자열의 길이); str.substr();// CandyShop | 인수가 없으면, 문자열 그대로 반환 str.substr(1);// andyShop | 시작 인수만 있다면, 해당 인덱스부터 마지막까지 str.substr(2);// ndyShop str.substr(3);// dyShop str.substr(4, 3); // ySh string 형식의 vector을 선언하고, substr() 함수를 이용해 .. 2024. 3. 14.
[백준] 11931번 : 수 정렬하기 4 (C++) 문제 풀이 sort함수를 사용할 때, greater 내림차순 less 오름차순 잊지말도록! #include // sort함수를 사용하기 위한 헤더 파일 sort(v.begin(), v.end(), compare); sort(v.begin(), v.end(), greater()); // 내림차순 sort(v.begin(), v.end(), less()); // 오름차순 아래는 정렬 시 시간복잡도에 대해서 자세하게 적어두었다. 이 문제에 대한 코드 설명도 있으니 꼭 읽어보시기를 추천드린다! 👍👍 아래의 글을 두 줄 요약하자면, sort함수는 퀵정렬을 이용해서 시간복잡도가 O(nlogn)으로 더 효율적이고 빠르다. 만약, 이중 for문을 이용해 정렬을 구현하면 시간복잡도는 O(n2) 으로 상대적으로 느리고, .. 2024. 3. 13.
반응형

티스토리툴바