막내의 막무가내 프로그래밍 & 일상

www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 백준 이분탐색 유형 문제입니다. 지방마다 갖고 있는 예산이 다른데 국가에서 총 예산 M 이하를 걷으려고합니다. 총 M이하의 예산이하라는 조건에서 지방마다 최대 얼마를 걷을 수 있는지 구하는 문제입니다. N의 개수를 보아 완전탐색으로 풀면 시간초과가 뜰겁니다. 이분탐색으로 풀어야합니다. 이분탐색에서 left 는 0 (최소 예산) right 는 지방예산중 가장 큰 금액 (최대 예산) 으로 하여 탐색을 시작합니..

programmers.co.kr/learn/courses/30/lessons/43238?language=java 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 프로그래머스 LV3 이분탐색 유형인 입국심사라는 문제를 풀어봤습니다. 각자 심사하는데 걸리는 시간이 다른 심사관들이 있는데 N명을 심사하는데 걸리는 최소시간을 구하는 문제입니다. 주석에 풀이를 자세히 적어놨고 간략히 설명하면 다음과 같습니다. 1. 걸리는 시간의 최소와 최대를 이분탐색의 left, right로 설정합니다. 2. 이분탐색 시간(mid)을 ..

www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 백준 분류별 풀기에서 이분탐색문제인 숫자 카드를 풀어봤습니다. 먼저 기본적인 이분탐색문제 중 하나였습니다. 경우의 수를 보면 알다시피 보통 시간초과를 일으키는 문제라는 경고의 수인 50만개까지 데이터가 있을 수 있습니다. 완전탐색으로 문제를 해결하면 당연히 시간초과가 나게됩니다. 그러므로 이분탐색을 사용하여 O(N)을 O(logN) 시간복잡도를 줄여주도록 합시다. 추가로 출력시 S..

www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 백준 이분탐색 단계별 풀기에 있는 공유기 설치 문제를 풀어봤습니다. 처음에 문제가 이해가 잘 안갔는데 저랑 같은 생각을 한 분의 블로그를 통해 이해할 수 있었습니다. 감사합니다. dundung.tistory.com/54 백준 2110 공유기 설치 Java 이분탐색 문제인 공유기 설치 문제이다. 난 문제를 이해하는 것도 헷갈렸다.. 요즘 문제 이해하기가 넘 힘들..

www.acmicpc.net/submit/2805 로그인 www.acmicpc.net 이전 단계인 랜선자르기 문제를 풀었으면 조건만 조금 변경하면 쉽게 풀 수 있는 문제입니다. 문제는 Scanner 를 사용했을때 계속 메모리 초과가 나서 Buffered로 바꿔줬더니 해결되었습니다. 풀이는 주석에 정리했습니다. [Java] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; class Main { public static void main(String[] args) throws IOExce..

www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 백준 이분탐색 단계별풀기 랜선 자르기를 풀어봤습니다. 이분탐색을 살짝 응용한 문제입니다. 각각의 랜선을 최대 몇 cm로 잘라야 해당 자른 cm와 같은 랜선이 N개 생기냐는 문제입니다. 주의할 점은 int 범위가 벗어나므로 long 형 사용하는 것과 이분탐색시 left값을 0이 아닌 1로 세팅해야 된다는 점 입니다. 풀이는 다음과 같습니다. [Java] import java.util...

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안 www.acmicpc.net 백준 1920 수 찾기 이분탐색 단계별 풀기 첫번째 문제를 풀어봤습니다. 말 그대로 이분탐색의 가장 기초적인 문제인 것 같습니다. 그리고 몰랐는데 이분탐색을 제공하는 함수가 있다는 것을 알았습니다. 풀이와 해당 내용을 정리합니다. [Java] import java.util.Arrays; import java.util.Scanner; public class Main { p..