Algorithm

[알고리즘] 백준 10986 나머지합 // 누적합, 나누기

https://www.acmicpc.net/problem/10986 * 아이디어 % 문제는 분배법칙으로 막 나눠라.%m으로 나눈 누적합을 구하라쌍을 찾아 C2 하면 답이다.원래 값이 0인것도 답이다. 같은 값을 선택한 예시 -> s[4] - s[2] == 원본배열에서 초록칸부분 1,2와 같음즉, 같은값 에서 2개를 선택하는 경우의수 == 정답의 경우의 수  * 전체코드c는 ret를  long long으로 해야함 (파이썬은 정수값 무제한임)#include using namespace std;int n, m;long long arr[1000000 + 4], sum[1000000 + 4];long long ret;int main() { ios_base::sync_with_stdio(0); cin.t..

[알고리즘] 백준 11660 구간합 구하기5 // 2차원 누적합

https://www.acmicpc.net/problem/11660 * 풀이data 정의를 잘해야함2차원 누적합 채우는 방법위 + 왼 - 좌측위(중복덧셈) + 원본3 + 3 - 1 + 3쿼리 구하기 x2,y2사각형 의 누적합에서 # sum(x2,y2)범위밖 위 사각형을빼고  # sum(x1-1,y2) 범위밖 좌측 사각형을 빼고  # sum(x2,y1-1) 중복제거된 교집한 부분 사각형을 더해주면 된다.  #  sum(x1-1,y1-1) 답 : sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1) + sum(x1-1,y1-1) #중복뺄셈보완 * 전체코드#include using namespace std;int n, m;int arr[1025][1025], sum[1025][1025]; ..

프로그래머스 숫자게임 c++ // 이진탐색, 투포인터

https://school.programmers.co.kr/learn/courses/30/lessons/12987[프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/12987)처음접근이분탐색 && visit 이용upper_bound로 초과인 것 선택 -> 그것 제출문제 : A가 정렬이 아니기때문에 뒤의 작은숫자에대해 B가 점수를 얻는경우를 계산못함.반례 : A [ 2 2 1]B [ 1 2 3]3제출 , 1점2보다 큰 미방문 없음 -> break, 종료실제정답 : 2점#include using names..

백준 1377 버블정렬 c++ // 버블정렬 필요 사이클 구하기

https://www.acmicpc.net/problem/1377 버블정렬이 완료될때까지 몇 사이클이 필요한지 구하는 문제.  1. 버블 정렬의 동작 방식예제: [10, 1, 5, 2, 3]첫 번째 패스:[10, 1, 5, 2, 3] -> [1, 10, 5, 2, 3] -> [1, 5, 10, 2, 3] -> [1, 5, 2, 10, 3] -> [1, 5, 2, 3, 10](10이 한 패스에서 한 칸씩 오른쪽으로 이동)두 번째 패스:[1, 5, 2, 3, 10] -> [1, 2, 5, 3, 10] -> [1, 2, 3, 5, 10](5가 제자리로 이동)세 번째 패스:[1, 2, 3, 5, 10](변화 없음, 정렬 완료)2. 핵심 아이디어각 숫자가 "최종 위치"까지 가는데 필요한 왼쪽으로의 이동 횟수를 찾..

[Algo] 플로이드 c++

* 언제 사용?모든 정점간의 최단거리를 구할때 사용시간복잡도 : O(n^3), n=100일때가 정해. n=1000일때도 비빌수는 있음.인접리스트보다는 행렬이 유리!다익스트라 : 한시작점에서 다른 모든 정점의로의 최단거리 구하는 알고리즘 / O(V ElgE) * 의사코드3중 for문을 돌면서정점 k를 하나씩 추가해가면서 이걸 거쳐서 가는게 싼지 탐색k의 for문은 맨 밖에 둬야함에 주의.연산이 대입보다 빠르기때문에, min보다는 if(d[i][j] > d[i][k]+d[k][j]) 인경우 대입하도록 바꾸면 n=1000도 비빌수있음. * 전체코드#include using namespace std;typedef long long ll;int INF = 0x3f3f3f3f;int d[105][105]; //i에..

[Algo] 백준 가장 긴 바이토닉 부분 수열 c++ // LIS, LDS, (dp), 이분탐색

* 시도완탐 : 해당 원소를 포함, 불포함 o, x로 나누어서 완탐하기2^1000 -> 불가완성된 배열에서도 바이토닉 찾기가 매우 까다로움dp -> n^2에 가능하나, n lgn풀이인 이분탐색으로 풀고자함.for (int i = 0; i lis의 len 구한후, 뒤집어서 범위제한후 len2 구하고 더하면 될듯?#include using namespace std;typedef long long ll;ll lis[1004], lis2[1004];ll nums[1004];int n,len, len2;int main(){ cin >> n; for (int i = 0; i > nums[i]; } int last_idx = 0; for (int i = 0; i  * 수정단순히 길이..

[Algo] 백준 벽부수고 이동하기 c++ // 최단거리는 bfs 3차원

* 2차원이 안되는 이유처음설계 상태 : (y, x , 그때 벽부순 count)를 두고 bfs를 돌리기if(next_cnt >= 2) continue; #include using namespace std;typedef long long ll;struct A { int y; int x; int cnt; // 여기좌표에 올때까지 부신 벽의갯수 A(int y, int x, int cnt) : y(y), x(x), cnt(cnt) {};};int n, m, arr[1004][1004], vis[1004][1004];int dy[] = { 1,0,-1,0 };int dx[] = { 0,1,0,-1 };ll ret; //배정된 예산중 최대값queue q;int main(){ cin..

[Algo] 공유기설치 c++ // 매개변수 탐색 hard

* 의사코드행동영역f(x) 정의시 최대, 최소를 쓰지마라. 우리는 이문제를 결정문제로 바꿔서 풀어야한다.간격을 고정하고 탐색하라. (x)로 고정.되는지를 구현하는게 사실 핵심이다. (go 함수)참인경우, st = mid 임에 주의 // en = mid 아님!go 함수 구현완탐하면서 간격    설치(cur갱신) , cnt+1설치된 공유기 갯수가 c 보다 큰지 return//설치간격이 x 일때, 공유기 c개 이상 설치 가능한지ll go(ll x) { ll cur = arr[0]; //현재 설치된 위치 ll cnt = 1; //공유기 설치갯수, 1st는 항상설치 for (int i = 1; i = c;}f(x) 정의, go 함수 구현 모두 빡센 문제였다.f(x)를 현재간격으로 "고정" 하고간격..