Mini

https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 의사코드 0. 오름차순 정렬조건 -> 이분탐색은 정렬시에만 사용가능하다 -> 이분탐색을 이용해 보자! 1. 누적합배열을 만들고 2. 예외처리 : 누적합에 정답(k)가 있는경우 누적합 정의에따라 [0,해당idx]가 정답후보임 3. 누적합배열을 돌면서, k + v[i]가 존재한다면, [i+1, 찾은idx]가 정답후보임 // +임에 주의, 3 일경우 10을찾아야 10-3 == 7(k) 가 됨 4..

https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 1. 의사코드 1. a+b의 결과를 답은 배열v1생성 2. c+d의 결과를 담은 배열 v2생성 3. v2에서 -v1을 이분탐색후 UB-LB == 해당순서쌍의갯수를 ret에 더해나감 2.시행착오 위의 3번과정에서 단순히 binary_search가 참이면 ret+1을 함 문제 : v1 : 2 , v2 : -2 -2 -2 일때, 순서쌍은(0,0,2,2) (0,0,2,3) (0,0,2,..

https://www.acmicpc.net/problem/1253 1253번: 좋다첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)www.acmicpc.net1. 의사코드1 2 3 3 3 4i  j LB        UB에서1. 해당수(a[i]+a[j])가 존재한다면, UB-LB로 그 갯수만큼 더해준다2.  문제 : 1 2 3 3 3 1 2 인 경우 : 3은 앞의 (1,2) 에서도 좋은수에 카운트되고, 뒤의(1,2)에서도 카운트 된다    -> 해결  : vis[LB]를 만들고, 이미 좋은수로 체크된경우 pass 하도록 했다.  3. 문제 : 이분탐색 주의점 : idx 가 i, j와 ..

https://www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신 www.acmicpc.net 1.의사코드 1. v[i]를 돌면서 -v[i]의 idx를찾는다 2. 정답후보는 idx-1, idx, idx+1이다. 3. 범위쳌 / 자기자신제외 / 정답갱신 2. 전체코드 #include using namespace std; typedef long long ll; ll ret=200000000+1; int n; vector v; int main() { ios::sync..

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 1. 의사코드 -97 -6 -2 6 98 103 104 i j LB(idx) 에서 1. 정답후보는 idx-1, idx, idx+1이고, //사실 idx+-2도 탐색을 해야 한다! 2. 조건 : 범위내 && idx가 i또는 j와 달라야되고 && 현재정답보다 최적해여야한다. 2. 내코드 #include using namespace std; typedef long long ll; ..

https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 1. 의사코드 1. 이진탐색범위 : j+1부터 탐색한다 2. UpperBbound-LowerBbound가 합이3인사람의 숫자이다. //중복없는 ※ 3이 없는경우 ub==lb가 되어 0명이다. 2.전체코드 #include using namespace std; typedef long long ll; ll ret; int n; vector v; set s; int vis[10004]; int main() {..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 0. 시간복잡도 10만*10만 -> 시간초과 -> 10만*이분탐색(log10만) -> 쌉가능 1. 의사코드 -99 -2 -1 4 98 99 100 1. lowerbound로 99를 찾는다. 2. lower_bound 특징(99이상인 위치 리턴) 으로 인해 정답후보는 98 or 99 or 100 중 하나이다. 3. 조건 : 범위내 and 현재정답보다최적 and 자기자신은제외 4. 자기자신제외 ..

https://www.acmicpc.net/problem/18869 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 1. 의사코드 1. 숫자 -> 크기순 idx로 변환한다 ex : 10 20 30 -> 0 1 2 ex2: 1 2 3-> 0 1 2 2. 변환후 같은배열이면, 같은우주이다. 2. 구현 1. v에 arr복사, 고유값만 남기기 2. v를 이분탐색하며 arr을 arr(idx)로 교체하기 3. 전체코드 #include using namespace std; int m, n,ret,arr[104][10..