목록알고리즘/이분탐색 (6)

쉬운 프로그래밍

[알고리즘] 백준 11663 선분 위의 점 - JAVA

www.acmicpc.net/problem/11663 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 문제 설명 1차원 상의 좌표와 선분이 주어진다. 선분에 올라갈 수 있는 점의 개수를 구하는 문제이다. 해결방법 이분탐색을 두 번 돌려서 해결했다. 선분의 좌표를 (x,y)라고 할 때, x를 기준으로 좌표에 대해 이분탐색을 돌려 x를 포함한 오른쪽 부분의 인덱스 y를 기준으로 좌표에 대해 이분탐색을 돌려 y를 포함한 왼쪽 부분의 인덱스 이 두개를 구하면 y - x를 통해 점으로 주어진 ..
알고리즘/이분탐색 2021. 3. 31. 18:16
[알고리즘] 백준 19637 IF 문 좀 대신 써줘

www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 문제설명 문제는 되게 간단하다. 주어진 Stat에 맞는 칭호를 출력하면 된다. 문제에서 주어진 if문을 보면 이해가 아주 잘 될 것이다. 해결과정 시간이 엄청 빡빡하다. 범위가 그래도 좁아보여서 완탐으로 풀어봤는데 바로 시간초과가 떴다. 매 유저스텟마다 칭호와 함께 주어진 스텟값을 INDEX값을 통해 이진탐색을 돌린다. 심지어 다 풀고 채점했는데 계속 틀렸길래 검색해보..
알고리즘/이분탐색 2021. 3. 31. 16:24
[알고리즘] 백준 1654 랜선 자르기 - JAVA

www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제설명 K개의 랜선이 주어졌을 때, 각각의 랜선을 똑같은 길이로 잘라서 N개의 랜선을 만들어야한다. 이 때 랜선의 길이의 최대값을 출력하면 된다. 해결방법 랜선의 길이가 정수 최대값이기에 완탐으로 돌리면 안봐도 터질게 뻔하다. 그러므로 이분탐색을 통해 문제를 해결하였다. 이분탐색 내에서 left값은 케이블 길이의 최소값인 1이 될 것이고, right는 가장 긴 케이블을 고르면 된다..
알고리즘/이분탐색 2021. 3. 31. 14:52
[프로그래머스] 입국심사 - JAVA

programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 문제 설명 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을..
알고리즘/이분탐색 2021. 3. 5. 14:59
[알고리즘] 백준 2805 나무자르기 - JAVA

www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분 탐색 문제이다. right값을 통나무중에서 가장 긴 통나무로 초기화 해준 후 m에 가장 근접하는 값을 찾아주면 된다. 맞왜틀..이 계속 나왔는데 뭔지 보니까 통나무의 길이가 최대 10억까지 들어갈 수 있으므로 구하는 과정에서 int값을 넘어가기 때문이였다. 단위!!! 한번씩 꼭 확인하는 습관을 들여야겠다. 소스코드 import java.io.BufferedReader..
알고리즘/이분탐색 2021. 3. 2. 00:23
[알고리즘] 백준 2512 예산 - JAVA

www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이분 탐색의 기초적인? 문제인것 같다. 이분 탐색 알고리즘의 개념이 제대로 잡혀있지 않았던 상태여서 풀이를 하는데 오래걸렸다. 각 부서별로 예산이 주어지고, 예산이 부족한 경우에 상한선을 정해서 상한선을 초과하는 예산을 요구하는 부서는 상한선 까지만 예산을 부여한다. 이 상한선을 찾기 위해 그냥 완탐을 돌려버리면 시간초과가 뜨기 때문에 이분 탐색이 필요하다. start를 0, end를 최대 예산으로 설정하..
알고리즘/이분탐색 2021. 3. 1. 22:59
Prev 1 Next