Develop/algorithm10 [알고리즘] 누적합 (Prefix Sum) 개인 공부 후 자료를 남겨놓기 위한 목적이므로, 생략되거나 오류가 있을 수 있음을 알립니다. 목차 0. 쿼리 문제 1. 기본 누적합 2. 응용 3. 2차원 누적 합 4. imos 0. 쿼리 문제 쿼리 문제란? (query : 문의, 의문, 질문) 주어진 데이터나 자료 구조에서 원하는 정보를 추출하거나 계산하는 문제를 의미한다. 대표적인 쿼리 문제. https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 쉽게 말해, 특정한 데이터.. 2024. 1. 26. [알고리즘] 투 포인터 (Two pointer) 개인 공부 후 자료를 남겨놓기 위한 목적이므로, 생략되거나 오류가 있을 수 있음을 알립니다. 투 포인터는 두 가지 상황에서 많이 쓴다. 1. 특정 조건을 만족하는 두 수를 찾을 때. 2. 특정 조건을 만족하는 구간을 찾을 때. + 정렬된 두 배열을 합칠 때 + merge sort (드문 케이스) 1. 특정 조건을 만족하는 두 수를 찾을 때. 예시 문제) 3273번: 두 수의 합 (https://www.acmicpc.net/problem/3273) 1번 예제 (변형) 9 5 12 7 10 9 1 2 14 11 13 문제에서 n이 최대 100,000이기 때문에 완전 탐색을 이용해서 문제를 푼다면 시간 복잡도는 O(n^2)으로 최대 10,000,000,000 (100억)번 연산해야하기 때문에 시간 초과가 발생.. 2024. 1. 18. [알고리즘] 정수론 개인 공부 후 자료를 남겨놓기 위한 목적이므로, 생략되거나 오류가 있을 수 있음을 알립니다. 1. 소수 판정 1. 기본형 소수 판정의 기본 1부터 n까지 n이 나누어지는지 확인하면서 약수의 개수를 세어준다. 하지만 보통 문제에서는 n을 매우 크게 주기 때문에 활용하기 힘들다. (시간 복잡도 - O(n)) #include using namespace std; bool check(int n) { int cnt = 0; // 1부터 n까지 약수 검사 for(int i = 1; i > n.. 2024. 1. 13. [알고리즘] 재귀함수(recursion function) 개인 공부 후 자료를 남겨놓기 위한 목적이므로, 생략되거나 오류가 있을 수 있음을 알립니다. 설명에 대한 지적은 언제나 환영입니다. :) 재귀함수 들어가기에 앞서. 재귀함수가 무엇인지 알아보기 전에, 이 유튜브 영상을 먼저 보고 와보자. 그저 4시간 동안 의미없는 반복되는 영상으로 보일 것이다. 이 영상이 무엇을 의미하는지 이제 알아보도록 하자. 1. 재귀함수란? 재귀함수란 무엇일까? 국어사전에서 재귀 란 을 의미한다. 따라서 재귀 + 함수 이므로 설명 그대로 함수내에서 자기 자신을 불러 작업을 수행하는 함수를 의미한다. 다음과 같은 함수가 있다고 하자. 이 recur() 함수 내에서 recur를 다시 부르면 어떻게 될까? 어려울게 없다. 다음과 해당 함수안에서 자기 자신을 반복하는 형태가 될 것이고 이.. 2022. 6. 30. 이전 1 2 3 다음
