분류 전체보기

프로그래머스 달리기경주 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..

백준 2473 세용액 c++ // 이진탐색 패턴정석 외우기

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

백준 3151 합이0 c++ // 이분탐색, nC3최적화하는법

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() {..

백준 2467 두용액 c++ //이분탐색 정답후보를 탐색하라

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. 자기자신제외 ..

백준 1781 컵라면 c++ // 우선순위큐 정렬방법, 선택x인경우 처리방법

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 1. 우선순위큐 정렬방법 매개변수가 같으면 false를 리턴해야함에 주의하자. class cmp { public: bool operator () (pair p1, pair p2) { if (p1.first == p2.first) { return p1.second p2.first; } }; 2. 문제점 기한순 정렬후 최대컵라면 뽑는방법 -> 기한을 ..

백준 1655 가운데를말해요 c++ // 우선순위큐 2개로 정렬효과만들기

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 1.시간복잡도 정렬후 mid 인덱스 출력 - > N ( 10만) * NlgN(정렬) -> 시초 특정알고리즘 필요 : pq, dp, 이분탐색 등.. 정렬한효과 -> pq 2개로 구현 2. 의사코드 maxHeap의 top이 항상 중간값이 되도록 고정하면 자동정렬이 된다. 이럴려먼 maxHeap의 크기가 minHeap의 크기보다 같거나 1이 커야한다. 1. 입력온값을 어디에 넣을것인가?..