Algorithm

BOJ 2512 - 예산

https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 지방의 수 N (3

BOJ 1654 - 랜선 자르기

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 길이가 제각각인 K개의 랜선 (1

BOJ 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 '최댓값'이라는 키워드 나왔으므로 이분 탐색 고려해보기. 원래 문제 원하는 길이 M만큼 얻을 수 있는 최대 절단기 높이는 얼마인가? 매개변수 설정 후 뒤집은 문제 정답인 절단기 높이를 매개변수 H로 설정 어떤 절단기 높이(H)로 잘랐을 때, 원하는 길이 M만큼을 얻을 수 있는가? Yes/No 문제로 변신 위의 Yes/No 문제를 한 번 물어보는 데 걸리는 시..

매개 변수 탐색 (Parametric Search)

Up-Down 게임 - A가 1~1000 사이 어떤 자연수를 선택 - B는 A에게 "생각한 숫자가 X 이상이야?" 라는 질문 가능 - A는 맞으면 1, 아니면 0 대답 - 최소 횟수로 질문하려면? 방법 1) Linear Search 1부터 1000까지 전부 물어보기 "생각한 숫자가 1 이상?" "생각한 숫자가 2 이상?" ... "생각한 숫자가 1000 이상?" -> 마지막 Yes인 대답이 정답! 최악의 경우 1000번 질문해야 한다. 더 빠른 방법은 없을까? 방법 2) Binary Search A가 생각한 숫자를 매개변수로 생각해서 이분탐색으로 찾기 L=1, R=1000인 구간 L~R에서 이분탐색! 탐색할 범위의 중앙 값과 찾아야 할 숫자 K를 비교를 통해 정답이 가능한 구간 [L, R]을 좁혀나가면서..

BOJ 2470 - 두 용액

https://www.acmicpc.net/problem/2470 서로 다른 두 용액을 더해서 합이 최대한 0에 가깝게 만드는 문제 아이디어 각 용액의 범위가 -10억 ~ 10억 이므로 두 용액을 합친 값의 범위는 -20억 ~ 20억이므로 int형 변수로 처리 가능하다. 가장 먼저 생각난 방법은 이중 for문으로 두 용액을 섞을 수 있는 모든 경우를 다 비교해보는 것이다. 이렇게 하면 시간 복잡도가 O(N^2)이 된다. 이러면 N의 최댓값이 10억이니까 100억이 되버리므로 시간이 초과된다. 왼쪽 용액(left)을 골랐을 때 오른쪽 용액을 뭘 골라야 더해서 0에 가장 가까울까를 생각해보면 정렬이 된 용액들 중 A[left]를 고른 후 A[left+1 ~ N] 범위 내에서 -A[left]와 가장 가까운 수..

[BOJ 7795] 먹을 것인가 먹힐 것인가

https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 아이디어 A 원소의 크기가 B의 원소보다 작은 쌍을 구해야 한다. 먼저 순차 탐색을 생각해봤다. A의 모든 원소마다 B의 모든 원소를 비교하면 (1 ≤ N, M ≤ 20,000)이므로 시간 복잡도가 O(N^2) 즉, O(4*10^8) 이므로 1초 내에 풀 수 없다. 탐색 시간을 줄이기 위해 이분탐색을 이용한다. B를 정렬 후 A 원소들을 기준으로..

[Algorithm] 이분 탐색(Binary Search)

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다. 출처 : https://github.com/rhs0266/FastCampus 탐색 수열과 탐색 대상 x가 주어진 경우 x가 존재하는가? x 이하 or 미만 or 이상 or 초과 하는 원소의 개수는? x랑 가장 가까운 원소는 무엇인가? ... 모든 원소를 보면서 x와 비교를 하는 경우 O(N)의 시간복잡도로 위의 질문을 대답할 수 있다. 그런데 만약 정렬이 된 수열이 주어진다면 어떻게 될까? 정렬된 수열과 탐색 대상 x가 주어진 경우 이분 탐색을 이용하면 더 빠르게 위의 질문을 대답할 수 있다. 이분 탐색 (Binary Search) 정렬이 보장되는 배열에서 기준 x를 가지고 범위를 "이분"하면서 탐색하는 방법 정렬이 보장된다는 의미는 무엇일까..

BOJ 1946 - 신입 사원

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 1. 아이디어 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 것은 고등학교때 배운 여사건을 생각해보면 서류 심사 성적와 면접 시험 성적 모두 다른 지원자보다 떨어지는 경우만 탈락한다는 뜻이다. 모든 지원자의 서류 점수와 면접 점수, 그리고 탈락 여부 정보를 volunteer 클래스로 묶어주고 서류..

BOJ 1931 - 회의실 배정

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net --- 아이디어 맨 처음에는 회의 목록들을 먼저 시작 시간들을 오름차순으로 정렬 후 시작 시간이 같은 경우 끝나는 시간을 오름차순으로 정렬했다. 정렬 후 이중 for문으로 최대 회의 수인 경우를 찾았다. Arrays.sort(confs); for (int i = 0; i = pivot.end) { cnt += 1; pivo..

BOJ 15970 - 화살표 그리기

https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 아이디어 색깔이 같은 점들 중 가장 가까운 점끼리의 거리를 구해야 하니까 일단 색깔별로 ArrayList에 분류한 후 정렬해준다. 정렬의 특성을 생각해보면 정렬 후 각 원소마다 가장 가까운 원소는 자신의 양 옆 중에 있다는 것을 알 수 있다. 가장 가까운 원소를 찾는다는 문구를 보고 정렬의 특성을 떠올려 정렬로 접근할 수 있어야 한다. 가장 가까운 점끼리의 거리를 구해야 하므로 기준 점의..