이분탐색3 [알고리즘] 숫자 카드 2 (백준 10816번) 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이분탐색이라 쉬울 줄 알았는데 중복된 수를 허용하기 때문에 처음 만나보는 유형이었다. 사실 HashMap으로 풀면 그만이지만 너무 쉬운거 보단 그래도 이분탐색으로 풀어보고 싶어서 해봤는데 계속 시간 초과가 나서 결국 질문을 보아하니 lowerBound와 upperBound를 사용해야 한다고 한다. Solution 1) HashMap 사용 그냥 입력 받는 값들을 key값으로 HashMap에 저장하고 value는 해당 key의 개수를.. 2020. 9. 1. [알고리즘] 중량제한 (백준 1939번) 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 전형적인 'BFS + BinarySearch' 유형의 문제이다. BinarySearch로 최대값 혹은 최소값을 찾되 BFS로 현재 값이 타당한지를 판단하는 문제 유형이다. Solution 이 문제는 트럭에 실릴 수 있는 최대 중량을 구하라는 문제이다. 만약 트럭의 특정 중량을 기준으로 도착지까지 갈 수 없다면, 그보다 더 높은 중량으로는 당연히 도착지까지 갈 수가 없기에 search하는 값들이 정렬이 되어 있기에 .. 2020. 9. 1. [알고리즘] 이분 탐색 (Binary Search) 이분 탐색 (Binary Search) O( log N )의 시간 복잡도로 전체 배열에서 특정 값을 찾아내는 방법 이 때 배열은 무조건 정렬이 되어있어야함 반복문 실행할 때마다 탐색 범위를 왼쪽 절반 혹은 오른쪽 절반으로 줄여 나감 응용 최대값, 혹은 최소값을 찾는 문제 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 알고리즘 left = index 최소 값 right = index 최대 값 반복문 실행 left가 right 보다 이하일 동안 반복 (left m.. 2020. 8. 31. 이전 1 다음
