알고리즘 공부

누적합 알고리즘 (2022 카카오 - 파괴되지 않은 건물)

해당 문제는 정확성과 효율성을 모두 고려해야하는 문제이기 때문에 매 스킬마다 해당하는 구간을 계산하면 O(KNM)의 시간 복잡도가 나오게 되어 실패한다. 그래서 처음 생각했던 방법은 큐를 만들어 치유인 경우에는 큐에 더하고 파괴 스킬일 때 큐를 먼저 차례대로 실행 후 파괴하면 어떨까 했는데 효율성에서 1개 빼고 모두 시간초과가 떴다.. 혼자서는 방법을 못찾겠어서 찾은 방법이 누적합 알고리즘 누적합 알고리즘은 알고리즘 이름대로 나열된 수(구간)의 합을 구하는 알고리즘이다. 다만, 이전처럼 매번 모든 구간에 합을 적용하는 방식이 아니다. 문제는 2차원이지만 1차원에서부터 시작한다면.. 방식은 간단하다. 구간 [i..j] 까지 n을 더하면 arr[i] = n, arr[j+1] = -n 값을 넣는 방식으로 계산..

[C++/JAVA] 이진탐색 (lower bound) (2021카카오 - 순위검색)

이진 탐색이란? 정렬된 데이터에서 특정 값을 찾아내는 divide n conquer 알고리즘. 탐색이 반복될 때마다 탐색 구간이 1/2씩 감소한다. (bigO logn) 원리 1. 데이터 집합의 가운데 원소(mid)와 타겟(target)을 비교 2. mid > target 인 경우 집합의 왼쪽 1/2 부분 탐색하여 1 반복 3. mid < target 인 경우 집합의 오른쪽 1/2 부분 탐색하여 1 반복 1. C++ (성공 코드 포함) 코드 int binarySearch(int *arr, int arr_sz, int target) { int left = 0; int right = arr_sz - 1; while(left target) { right = mid - 1; } else if (arr[mid] ..

백준에서 C++ 로 풀 때 시간초과 나는 경우

답은 맞는데 시간초과 나는 경우 iostream 때문일 수 있다. ios_base::sync_with_stdio(false); cin.tie(null); 앞에 추가하면 속도를 높일 수 있다. * 특히 입출력이 번갈아 일어나는 상황에서 속도가 빨라짐.

Leet code 가입

부계용으로 하나 만들어서 Problems - Easy 제일 첫번째꺼 문제 풀었다. 이건 너무 쉬움 1. Two Sum (C++) num에 저장된 숫자 2개 중 합이 target인 인덱스 2개를 return 하는 문제 단, 같은 인덱스의 숫자로 더하면 안됨. class Solution { public: vector twoSum(vector& nums, int target) { vector ans; int tot = 0; for (int i=0; i < nums.size(); i++) { for (int j=i+1; j < nums.size(); j++) { tot = nums[i] + nums[j]; if (target == tot) { ans.push_back(i); ans.push_back(j); } ..

[C++] vector 클래스 - 2차원 벡터 초기화

1. assign check.assign(M, vector (M, 0));