Mini

https://www.acmicpc.net/problem/1725* 풀이히스토그램 문제를 직관적으로 이해하는 방법은 이렇습니다:"뻗어나가기" 관점:각 막대는 자신의 높이를 유지하면서 양옆으로 최대한 뻗어나가려고 합니다예를 들어 높이 4인 막대는 "높이 4를 유지하면서 얼마나 넓은 직사각형을 만들 수 있을까?"를 생각하는 것입니다"막히는 지점" 찾기:뻗어나가다가 자신보다 낮은 높이를 만나면 거기서 멈춰야 합니다이것이 바로 우리가 스택에서 pop을 하는 시점입니다스택의 역할:스택은 "아직 더 뻗어나갈 수 있는 막대들"의 모음입니다새로운 막대를 만났을 때, 이 막대보다 높은 것들은 더 이상 뻗어나갈 수 없으므로 pop하고 계산합니다이렇게 생각하면 너비 계산도 이해하기 쉽습니다:스택이 비었다는 것은 "왼쪽으로 ..

* 풀이유사문제들의 풀이의 공통점계산이 끝난 원소를 바로 while문으로 pop 하는 특징(top 나보다 작은 top -> 나를 볼수없음 -> pop 남은 스택의 원소갯수 = 나를 볼수있는 빌딩의 갯수!예시 낚시예시는 관리인 시점에서 탐색중인 current가 아니라 탐색이 끝난 element 관점으로 서술되어있다.이러면, 상태관리가 어려워진다.문제 해결에서 "현재 위치(current)"를 중심으로 생각하는 것은 매우 좋은 접근 방법이런 관점이 유용한 이유는: 1. 문제를 더 작은 단위로 나눌 수 있음    - "전체 빌딩이 몇 개를 볼 수 있는가?" 대신    - "현재 빌딩(나)에 대해서는 어떤 일이 일어나는가?" 2. 상태 관리가 쉬워짐    - 현재 시점에서 필요한 정보만 유지    - 이 문제에..

https://www.acmicpc.net/problem/17299* 풀이오큰수의 유사문제stack을 이용해서 오큰수를 찾은 애들을 지워버린다. => 시간복잡도를 줄임F[cur]이 F[top]보다  더큰경우 -> cur이 오큰수임, 기록, pop, 반복push(cur)남아있는 애들은 오큰수가 없는애임 -> -1 기록* 전체코드#include using namespace std;typedef long long ll;ll n;vector arr;stack> s;ll F[1000000+4],ans[1000000+4];ll ret;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n ; for (int i = 0; i > tmp;..

* 완탐풀이정방향으로 탐색하면서 나보다 큰 수를 찾는다.시간복잡도 : N(N-1)/2 -> 불가능역병향으로 탐색하면?5 입장에서 좌측을 탐색한다.3의 오큰수는 나(5)다.2입장에서 나를 오큰수로 가질만한게 있나? -> 없음 -> pass이때, 3의 오큰수는 이미 정해져있다. -> 탐색할 필요가 없었다!1입장에서도 나를 오큰수로 가질것이 없다8입장에서는 3을 볼필요가 없다.(이미 오큰수가 있음)오큰수가 없는것중 나(8)를 오큰수로 가질수있음 --> 내가 오큰수다.10입장에서 8의 오큰수는 나다.len만큼 다돌았는데 오큰수가 없으면, 오큰수가 없는것이다.하지만, 시간복잡도는 정방향과 비슷하다.시간복잡도가 많은원인 : 이미 오큰수가 있는 숫자(3 같은)를 탐색하는 비용이 크다.개선 : stack에 넣고, 오큰..

https://www.acmicpc.net/problem/11003* 완전탐색N개 숫자에대해 앞의 L 개 탐색 -> O(NL) -> 불가N이 500만이므로, 1번의 탐색만으로 끝내야함! * 행동영역슬라이딩 윈도우에서 덱을 활용하라.나보다 큰값을 pop 반복으로 완탐,정렬 효과를 만들어라. * 풀이삽입하기전, 우측부터 비교 크면 pop 반복 => 완탐효과, 정렬효과, 좌측이 최소값 효과!!작으면 통과push data좌측이 윈도우를 넘어가면 삭제 (인덱스 비교)좌측(최소값) 출력 * 전체코드#include using namespace std;typedef long long ll;ll n, L;ll arr[5000000 + 4];deque> d; // int main() { ios_base::sync_w..

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..

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]; ..

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..