Algorithm

백준 11057 오르막수 c++ // dp

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 1. 의사코드 1. 아래칸 = 위칸의 총합인것을 발견할수 있다. 2. 전체코드 #include using namespace std; typedef long long ll; int d[1004][10]; //오큰수의 갯수 [길이][시작숫자] int n; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; fi..

프로그래머스 이중우선순위큐 c++ // pq, multiset 사용법

https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 우선순위큐 의사코드 1. 문제점 : 큐2개를두면, 실제 최대힙에서는 삭제되어도 최소힙에서는 삭제가 안되므로 제대로 비었는지 확인이 안된다 -> 해결 : cnt 변수 정의 //현재 큐에 있는원소의 갯수 2. 시키는대로 연산 구현후, cnt==0이면 실제로 pq1, pq2의 원소를 다 뺴주어야한다! (tc1번 걸림) 2. 우선순위큐 전체코드 #include using namespace std; ..

백준 7453 합이0인네정수 c++ // 이분탐색 갯수세기는 ub-lb

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

백준 2110 공유기설치 c++ // 매개변수탐색, 이분탐색 hard

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 1. 의사코드 1. 첫번째 집을 선택하는게 최선인가? ㅇㅇ 귀류법 : 첫번째집을 선택안하는게 최선이라고 가정 -> ex) 1 2 5 에서 2부터 2개선택(2,5) 하는경우 간격은 3 / (1,5)선택하는 경우 간격이4 -> 모순 - > 따라서 첫번쨰 집을 선택하는게 최적해를 보장한다. 2. 가장 중요한점은 st, en이 v의 값이 아닌 집간 최소..

프로그래머스 귤고르기 c++ // 공간복잡도 공식, 구현

https://school.programmers.co.kr/learn/courses/30/lessons/138476 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 공간복잡도 공식 512MB == int배열[1억] 임을 기억하자. 2. 의사코드 1. arr을 정렬함 //a[i] : i의 등장횟수 ex) arr : 2 2 2 1 1 k=6, O O O 2. k와 arr[i]를 -하면서 k가 0이될때까지 뺴면됨. 3. arr[i]가 0이될때마다 ret++ 4. k가 0이되면 종료 and 마지막 0이된숫자를 세주기위해 ret+1 3. 전체코드 #includ..

프로그래머스 달리기경주 c++ // 해쉬맵 기본정렬됨(키값기준오름차순), 구현

https://school.programmers.co.kr/learn/courses/30/lessons/178871 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 0. 해쉬맵은 키값기준 오름차순으로 기본정렬되어 있다. 내림차순하려면 선언시 greater 을 추가하면된다. 1. 의사코드 m1 : 이름, 인덱스 저장 m2 : 인덱스, 이름저장 1. calling(현재이름)으로 이전이름을 찾는다. 2. m1, m2를 각각 값에 알맞게 swap 해준다. ex : m1[kai]=3 , m1[pve]=2 ---> m1[kai]=2, m1[pve]=3 m2[3]=ka..

백준 1253 좋다 c++ // 이분탐색 발상, 주의점(자기자신예외처리)

https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 1. 의사코드 1 2 3 3 3 4 i 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와 같은경우 예..

백준 14921 용액합성하기 c++ // 이분탐색 정석패턴

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