본문 바로가기

이분탐색10

[백준 12015] 알고리즘 102일차 : 가장 긴 증가하는 부분 수열 2 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이분탐색 Java (C++로 하려다가 xcode 맛가서 다시 java로 함..) 가장 긴 증가하는 부분 수열 2는 1과 달리 dp로 구하면 안되고 이분탐색으로 구해야한다. N (1 ≤ N ≤ 1,000,000) 수열의 크기가 이렇기 때문에. 접근방법 도저히 모르겠어서 서치해서 공부했다. 핵심 개념은 이 두가지라고 생각하는데 증가하는 수열을 리스트로 선언해두고 배열을 하나씩 탐색하면서 수열의 가장 .. 2021. 7. 8.
[백준 1789] 알고리즘 63일차 : 수들의 합 www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net C++ 이분탐색.. 16분전. 시간에 쫓기고 있습니다. 이분탐색인데 이분탐색으로 안해도 풀리네요. 문제 한문장 대로 서로다른 N개의 자연수의 합이 S가 될때 N의 최댓값을 구하는 문제 접근방법 합이 S가 되는 수들의 개수가 최대가 되려면 적은 수부터 연속된 수를 더하는 경우가 가장 최대가 되겠죠. 그래서 우리가 알고 있는 공식 1부터 N까지 연속된 수의 합을 구하는 공식인 N(N+1)/2 을 활용하면 됩니다. 이 N에 들어가는 수를 이분탐색으로 탐색하면 시간이 더 적게 들겠지만 1부터 차례로 대입해가면서 공식의 값이 S를 넘을때.. 2021. 1. 12.
[백준 2512] 알고리즘 61일차 : 예산 www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net C++ 이분탐색 연초에 시기적절한 문제인 것 같아서 풀어봤다(변명) 이분탐색은 진짜 한번 풀면 계속 풀 수 있을 것 같다(그러면서 왜 골드는 안푸는데요) 아무튼. 접근방법 지방의 예산요청액 입력받을때 합이랑 최댓값 같이 구해놓고 합이 전체 국가 예산보다 작으면 최댓값 출력하고 끝. 아니면 이분탐색 함수 부를때 (1,최댓값)으로 범위설정해서 보내고 이분탐색 기준 함수는 지방 예산요청액 배열 다 돌면서 상한액.. 2021. 1. 8.
[백준 1764] 알고리즘 60일차 : 듣보잡 www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net C++ 이분탐색 모닝 코딩이네요 또 쉽게가려고 이분탐색 들여다보고있는데 제목이 재밌어서요..(핑계) 근데 문제가 더 재밌네요 듣도 못한 사람과 보도 못한 사람들이 주어지고 듣도 보도 못한 사람을 구하는거라니..ㅋㅋ 문자열 벡터 이분탐색 정렬 썼습니다. 접근방법 듣도 못한 사람 명단 벡터에 저장 후 사전순으로 정렬 보도 못한 사람을 듣도 못한 사람들에서 이분탐색으로 찾고 듣도보도못한 사람 명단에 push 듣도보.. 2021. 1. 7.
[백준 10815] 알고리즘 59일차 : 숫자 카드 www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net C++ 이분탐색 쉬운 이분탐색 응용없이 그냥 이분탐색만 하면 되는 문제 이건..실버4이기엔 쉬운 문제인 것 같다. 접근방법 상근이가 갖고 있는 숫자카드는 배열로 받아서 정렬해주고 주어지는 정수 M은 바로 받아서 이분탐색하는 것 끝 오답노트 내가 코드를 잘 못짜서 그런건지는 모르겠지만 일단 기본 코드는 시간초과 났었고 sync_with_stdio 해주고 cin tie해주니까 통과됐다.. 2021. 1. 6.
반응형