Programming64 21921번 - 블로그 | 슬라이딩 윈도우 알고리즘 (C++) 문제풀이슬라이딩 윈도우 알고리즘을 이용해 풀이했다. 아래의 문제와 풀이 과정이 유사하지만, 이 문제의 다른 점은 가장 많이 들어온 방문자 수와 함께 기간의 개수도 함께 출력해야 하는 것이다. 예를 들어 예제 입력 2의 경우에는 '1 1 1 1 5', '1 1 1 5 1'로 총 방문자 수가 9인 기간 두 개가 있기 때문에 출력 값이 '9 2'가 된다. 따라서, 기간의 개수를 세기 위해 cnt 값을 추가해주어야 한다. 2559번 - 수열 | 슬라이딩 윈도우 알고리즘 (C++)문제풀이슬라이딩 윈도우 알고리즘을 이용해 풀이했다. 1. 0부터 k-1까지는 모두 sum에 더한다. 이때, 최대가 되는 합을 저장할 answer에 sum의 값을 넣는다. for (int i = 0; i 2. k부터 n-1까지.. 2024. 7. 26. 2559번 - 수열 | 슬라이딩 윈도우 알고리즘 (C++) 문제풀이슬라이딩 윈도우 알고리즘을 이용해 풀이했다. 1. 0부터 k-1까지는 모두 sum에 더한다. 이때, 최대가 되는 합을 저장할 answer에 sum의 값을 넣는다. for (int i = 0; i 2. k부터 n-1까지는 arr[i]는 sum에 더하고, arr[i - k]는 sum에서 뺀다. answer과 sum 중 최댓값을 answer에 저장한다. for (int i = k; i 코드#include #include using namespace std;int arr[100001];int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, k, sum = 0, answer = 0; cin >> n >> k.. 2024. 7. 26. 1620번-나는야 포켓몬 마스터 이다솜 | 스택 오버플로우 by 지역변수 (C++) 문제풀이입력값이 숫자인 경우와 문자인 경우를 분류해 구하는게 까다로운 부분이다. 1. 입력값이 숫자인 경우 string 배열을 이용해 문자열을 저장해둔다. 입력을 받을 때 for문으로 0부터 배열에 저장되었기 때문에, -1 을 해주었다. string name[100001]; // 입력이 숫자인 경우에 사용 if (isdigit(str[0]) != 0) { // isdigit == 0: 문자 | isdigit != 0: 숫자 cout 2. 입력값이 문자인 경우 key값과 value값이 함께 저장되는 map을 이용한다. 이 문제는 입력값이 많기 때문에 시간 초과를 주의해야 하므로 map을 선택했다. 문자가 입력된 경우, map에서 key 값을 찾아 전달하도록 한다. 이때, for문으.. 2024. 6. 25. 1764번 - 듣보잡 | 시간초과, binary search (C++) 문제 풀이 1. 처음에는 이중 for문을 이용해 풀이했다. 당연히 시간초과 발생 O(n2) ➡ 애초에 최댓값이 50만씩이여서, 50만 x 50만 = 시간 초과가 날 수 밖에 없었음.. 2. 시간초과 문제를 해결하기 위해서는, map 또는 binary search를 사용해야 한다. ➡ map: O(logn), Red-Black Tree, key - valued의 pair로 저장된다. 중복 허용 X ➡ binary search: O(logn), 꼭 정렬을 먼저 해줘야 한다. 나는 binary search를 이용해 문제를 해결했다. 추가로, vector는 데이터 순차 저장이므로 검색 속도가 느리다. 검색에는 hash_map(unordered_map)과 map을 사용하는 것이 빠르다. hash_map(unord.. 2024. 4. 3. [백준] 10816번 : 숫자 카드 2 | binary search & unordered map (C++) 문제 풀이 binary_search를 이용해 풀이했다. O(logn) 문제를 맞춘 후, unordered_map을 이용해도 가능한 것을 확인해 사용해보았다. O(1) 이 문제를 풀며 놀라웠던 점은 시간복잡도가 O(logn)인 binary_search가 O(1)인 unordered_map보다 빨랐다는 것이다. 찾아보니 이에 대한 질문 글이 있어 답변을 가져왔다. 현실 세계에서는 N이 무한히 큰 경우가 거의 없기 때문에 O(lgN)과 O(1) 정도의 차이는 N의 크기에 따라 시간복잡도에 붙은 상수로 자주 뒤집어집니다. 가령, 최소한의 비교로 원하는 수를 찾아야 하는 가상의 문제가 있다고 합시다. N에 관계없이 항상 50번의 비교로 수를 찾는 어떤 O(1) 알고리즘과 N에 대해 ceil(lgN)번의 비교를 하.. 2024. 4. 1. [백준] 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. [백준] C++로 풀이 시 시간 초과가 난다면? 추가하자! ios_base::sync_with_stdio(false); cin.tie(0); 2024. 3. 28. [백준] 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. 이전 1 2 3 4 ··· 8 다음 반응형
