이분 탐색
(JAVA) 백준 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 풀이 처음에는 브루트 포스를 사용하여 아래와 같이 풀이해 보았다. import java.io.*; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Main { public static void main(String[] a..
(C++) 백준 18870번 - 좌표 압축
문제 링크 : https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 풀이 먼저 입력받은 배열을 sort() 메서드를 사용해서 정렬하고, 그 후 unique()와 erase() 메서드를 사용해서 중복을 제거한다. 마지막으로 lower_bound() 메서드를 사용해서 현재 어느 위치에 존재하는지 알아낸다. #include #include #include using namespace std; vector ..
(C++) 백준 10816번 - 숫자 카드 2
문제 링크 : https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 sort() 메서드와 해당 값보다 큰 값이 처음으로 나타는 index를 반환하는 upper_bound() 메서드, 해당 값이 처음으로 나타는 index를 반환하는 lower_bound() 메서드를 사용하면 간단하게 풀 수 있는 문제이다. #include #include using namespace std; int A[500005]; int n,..
(C++) 백준 1920번 - 수 찾기
문제 링크 : https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 sort() 메서드와 binary_search() 메서드를 활용하여 간단하게 풀 수 있는 문제이다. #include #include using namespace std; int A[100005]; int n, m; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ci..
(Python) 백준 10816번 - 숫자 카드 2
문제 링크 : https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 1. lower bound와 upper bound를 사용한 풀이 lower bound와 upper bound를 사용하여 해당 값이 존재하는 위치의 수를 계산하는 방식으로 문제 풀이를 진행했다. import sys def lower(arr, num): # lower bound : 해당 값이 처음으로 나타나는 인덱스 반환 low, high = 0,..