본문 바로가기

분류 전체보기246

[백준 11659] 알고리즘 62일차 : 구간 합 구하기4 www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net C++ 누적합 문제 처음 보면 엥 이게 왜 실버3이지 싶은데 풀고나면 아ㅇㅇ 그냥 수배열 주고 일정 구간 수의 합 구하는건데 시간복잡도 때문에 그냥 합하는 식으로 구하면 시간초과나고 누적합.. 아 이 문제 분류가 누적합이구나.. 입력받을때 누적합을 같이 구해서 구간 합 구할때는 sum[end] - sum[start] (단, start != 1) 로 구해야 함 근데도 시간초과 나서 sync.. 2021. 1. 11.
[백준 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.
[백준 1934]알고리즘 57일차 : 최소공배수 www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net C++ 정수론 및 조합론 양아치 같지만 정수론 및 조합론에 문제가 추가돼있어서.. 공유기설치하다가 넘어왔습니다.. 접근방법 유클리드 호제법으로 풀이한 최소공배수 - 유클리드 호제법 : A에는 B를 대입하고, B에는 A%B를 대입하면서 A%B가 0이 될때 B의 값이 최대공약수이다. - 최소 공배수 = 두수의 곱 / 최대공약수 이 두가지를 적용해서 푼 코드 소스코드 #include using n.. 2021. 1. 4.
[백준 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.

티스토리툴바