이분탐색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. [백준 2110] 알고리즘 58일차 : 공유기 설치 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 C++ 이분탐색 지금까지 풀었던 이분탐색 문제랑 비슷한 문젠데 난이도가 조금 높은건 기준정하는 함수에 필요한 계산이 좀 많아서 때문인 것 같다. 접근방법 간격을 1부터 가장 좌표값이 큰 값을 범위로 이분탐색한다. 집 좌표값 배열은 정렬해둔다. 간격이 mid일때 공유기를 설치할 수 있는 개수가 C개 이상이면 더 큰 간격에서 이분탐색 C개 미만이면 더 좁은 간격에.. 2021. 1. 5. [백준 2805] 알고리즘 56일차 : 나무 자르기 www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 www.acmicpc.net 이분탐색 C++ 오늘도 이분탐색으로 최댓값을 구하는 스킬을 사용하는 문제 그래서 저번 랜선자르기 코드 거의 그대로 씀 접근방법 H의 길이를 0부터 가장 높은 나무길이 범위내에서 이분탐색하여 최댓값을 구한다. 오답노트 자른 나무의 길이 합과 M이랑 비교하는 함수에서 합 계산할때 음수도 같이 더하는걸로 해버려서 오류났었다. 양수일때만 더하는걸로 고치고 통과 소스코드 #incl.. 2020. 12. 30. [백준 1654]알고리즘 55일차 : 랜선 자르기 www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이분 탐색 C++ 문제 보고 어디에 이분탐색을 써야하는지 고민했던 문제 힌트로 parametric search 라고 돼있어서 개념 찾아봤는데 별 도움은 안됐음.. 1부터 max 길이 까지를 범위로 두고 그 안에서 랜선 길이를 이분 탐색하면서 찾아가는 거였다. 처음엔 랜선 개수를 계산하는게 시간이 오래걸릴 것 같아서 그걸 이분 탐색으로 대체해야하나 싶었는데 그 부분은 그냥 계산돌려도 .. 2020. 12. 29. [백준 10816] 알고리즘 54일차 : 숫자 카드 2 www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이분탐색 C++ 입력받은 숫자배열에 또 다른 배열에 주어진 숫자들이 몇개씩 포함되어있는지 출력하는 문제 (이과생의 글솜씨 ㅈㅅ) 숫자를 찾은 후에 숫자 개수를 하나씩 세어나가면 안된다. 이유는 모두 같은 수 일때는 결국 전체탐색을 하게 되기 때문. 그래서 lower_bound랑 upper_bound를 구해서 풀어야 하는 문젠데 구현 다 했는데 계속 시간초과 나서 찾아보니까 ST.. 2020. 12. 28. 이전 1 2 다음
