백준문제풀이/이분탐색
10816번-숫자카드2
문제 https://www.acmicpc.net/status?user_id=skaguq4270&problem_id=10816&from_mine=1 채점 현황 www.acmicpc.net 접근방법 1) 접근 사고 https://hyeophyeop.tistory.com/18 문제와 같습니다. 다만 갯수를 추가 해줘야 하므로 equal_range방식 또는 단순 구현으로 풀이를 해야한다. 2) 시간 복잡도 https://hyeophyeop.tistory.com/18 참조 3) 배운 점 복습하는데 좋았다! 4) PS 3가지 방법으로 구현해보았습니다. equal_range로 구현할 때 이유는 모르겠으나 배열을 사용하여 연산하니 오답처리를 받아서 Vector를 활용하는 방법으로 변경했습니다. 아무래도 메모리를 확보하..
10815번-숫자 카드
문제 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 접근방법 1) 접근 사고 n의 카드들이 있을때 m의 카드들이 n의 카드들에도 있는지도 확인하면 되는 문제였습니다. 이진 탐색을 활용하면 쉽게 해결할 수 있는 문제 입니다. 2) 시간 복잡도 n과 m의 카드의 길이가 500,000이므로 완전탐색을 돌리면 25,000,000,000,000의 연산이 일어나므로 시간복잡도를 줄여야 하는 문제였습니다. 3) 배운 점 두 ..
7453번-합이 0인 네 정수
문제 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 접근방법 1) 접근 사고 주어진 배열이 4개이고 탐색을 해야 하는 문제이므로 2개의 배열씩 짝지어서 n^2으로 조합을 맞춘 뒤에 문제에서 주어진 조건이 a, b, c, d의 배열 4개의 합이 0이어야 하므로 더한 배열에서 이분 탐색을 실시하면 되는 문제였습니다. 2) 시간 복잡도 가장 단순하게 4개의 배열이니까 n^4으로 문제를 풀면 n은 4000이고 N의 4승이므로 64,..
1300번-K번째 수
문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 접근방법 개인적으로 탐색 기준을 무엇으로 잡아야 할 지 정말 많은 고민을 한 문제이다. 이분 탐색 문제들을 모아 놓은 카테고리에서 문제를 고른거라풀었지 아니었으면 절대 못 풀었을거 같다. (알고 풀어도 너무 어려웠음) 문제에서 주어지는 n의 크기 때문에 완전탐색으로는 시간초과가 발생하는 문제이기 때문에 시간복잡도를 줄여야만 하는 문제였다. 이 문제의 탐색 기준은..
16434번-드래곤앤던전
문제 https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net 접근방법 n의 단위가 100,000만 이므로 n^2의 알고리즘은 시간초과가 발생한다는것을 깨닫고 O(logn으로 시간복잡도를 줄여야 하는 문제란걸 문제의 조건을 읽고 알아야 하며 H의 범위가 1,000,000인데 최대 연산이 발생할 경우 INT의 범위를 초과하기에 자료형을 long long으로 설정해줘야 하는 문제이다. 문..
2110번-공유기설치
문제 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 접근방법 일반적인 이분탐색 문제와 유사하지만 기준으로 정한 거리(mid)값의 변화를 측정하기 위한 이전 인덱스를 변경하는 35번째 줄에서 약간의 구현력이 필요했던 문제였습니다. 그 외에는 일반적인 이분탐색 문제였습니다. 정답코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ..
1654번-랜선자르기
문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 접근방법 분할하였을 때 랜선의 개수가 n개 이상으로 만들어야 하는 경우에 랜선의 길이를 최대로 결정해야 하는 문제였습니다. 그렇기 때문에 이 문제에서는 탐색을 해야 하는데 n의 개수가 10000개 이므로 최악의 경우 100,000,000번의 연산이 발생하게 되므로 시간초과가 발생하여 O(logn)으로 시간복잡도를 낮춰야 하는 문제였습니다. 그러므로 이분탐색을 활용..
6236번-용돈관리
문제 https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 접근방법 https://hyeophyeop.tistory.com/6 백준의 기타레슨과 매우 유사한 문제입니다. mid값을 어떻게 잡는가가 핵심이었던 문제였는데 저는 "현우가 당일날 사용할 수 있는 금액"으로 기준을 삼고 left값과 right값을 결정하였습니다. left값은 현우가 당일 사용하는 금액이 기준치보다 작으면 안됩니다. 왜냐하면 인출금액 K를 최소화하기로 했기 때문입니다. 그래서 lef..
2343번-기타레슨
문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 접근방법 이분탐색에서는 비교대상 (저의 코드에서는 mid 변수가 이것을 의미합니다.)을 어떻게 설정해줘야 하는것이 가장 중요합니다. 저는 "블루레이의 크기"를 mid 값으로 설정하였습니다. 예시를 들자면 블루레이의 크기를 10으로 설정하고 각 레슨들(arr의 값들)의 크기를 더해주면서 10을 넘을 경우 cnt값을 올려 총 블루레이의 갯수에 따라 left값과 right을 변경하였습니다. 이 문제의 주..
2512번-예산
https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 접근방법 https://hyeophyeop.tistory.com/2?category=1003847 와 유사한 문제 입니다. 문제 접근을 위한 시간복잡도 계산, 자료형 설정부터 이분 탐색을 위한 범위 지정까지 유사합니다. 차이점은 이분탐색을 시작하는 while문 안에서 기준값 mid를 활용하여 arr에 대한 값들의 비교 연산만 다릅니다. 정답코드 1 2 3 4 5 6 7 8 9 10 11 12..
2805번-나무자르기
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 접근방법 이 문제는 n이 1000000이므로 완전탐색처럼 모든 케이스의 경우를 탐색할 경우 시간초과가 발생한다. 적어도 O(logn)의 시간복잡도로 줄여줘야 하는 문제다. 문제에 따라 적어도 m개의 나무를 가지기 위한 기준값을 정해주어야 한다. 기준값은 left와 right를 이용해서 중간값을 정해주는데 left와 right의 정의는 나무의 최소길이부터 최대..