L.O.K

https://www.acmicpc.net/problem/1205 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net ◎ 문제풀이 '비오름차순'(내림차순)으로 정렬된 점수 배열에서 새로운 점수의 랭크를 구하는 문제이다. '정렬'된 배열에서 새로운 점수의 위치를 '탐색'하는 문제이므로, 이분탐색법을 발상했다. ◎ 코드 package org.example.binarySearch; import java.io.*; import java.util.*; //BOJ1205 등수 구하기 public..

1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net ◎ 문제풀이 공장1에서 공장2로 한번에 이동가능한 최대중량을 구하는 문제이다. BinarySearch와 BFS를 모두 떠올려야 하는 고난도 문제였다. 처음 이 문제를 접했을 때, DFS가 떠올랐다. 공장1에서 공장2까지 가는 모든 경로를 완전탐색해야 한다고 생각했기 때문이다. 그러나 DFS로 풀면 시간초과가 난다. visited[bridge.nextNode] = true; // 역행방지 dfs(bridg..

2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net ◎ 문제풀이 개인적으로 이분탐색 발상이 어려운 문제였다. '가장 인접한 두 공유기 사이의 최대거리를 구하라.' 의 의미를 제대로 파악해야 한다. 처음에는 공유기 개수가 3대라면, 1번, 8번, 9번에 공유기를 설치하면 1번과 8번 사이가 7이 되니 최대거리는 7이 아닌가 싶었다. 근데 이런 것을 물어보는 문제가 아니었다. 인접한 두 공유기 사이의 거리의 범위는 1 [두집 사이 최소거리] 과 8[1번 집 - 9번..

10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ◎ 문제풀이 N개의 수열에 M개의 수들이 포함되어 있는지를 탐색하려고 한다. N과M은 최대 500,000으로 이중for을 이용한 탐색은 시간복잡도가 O(NM)으로 시간초과가 발생한다. 그러므로 시간복잡도를 O(MlogN)으로 줄일 수 있는 이분탐색을 해야 한다. ◎ 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net ◎ 문제풀이 여러 개의 나무를 동일한 크기로 잘랐을 때, 자투리로 남는 나무를 가져가는 문제이다. 원하는 만큼의 나무를 가져가려면 어느 정도 동일한 크기로 잘라야 할까? 자르는 크기를 h라고 하면 h는 1 부터 가장 큰 나무의 크기 사이에 있다. 범위 안에서 적절한 값을 구하는 문제인데, 나무의 크기가 1 ≤ M ≤ 2,000,000,000 이므로 엄청나게 ..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net ◎문제풀이 랜선K개를 동일한 길이의 랜선 N개 이상으로 만들 때, 최대 랜선의 길이를 구하는 문제이다. 랜선 N개 이상으로 만드는 랜선의 길이는 1 ~ 랜선K개중 최대길이 사이에 존재한다. 범위 안에서 원하는 값을 탐색해야 하므로 범위를 반씩 줄일 수 있는 이분탐색을 사용해보자. 범위의 중간값으로 랜선K개를 나누었을 때 생성되는 랜선의 개수가 N개 이상이어야 한다. N..

https://www.acmicpc.net/problem/1790 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net ◎ 문제풀이 개인적으로 어려운 문제라 아래 포스팅을 참고하여 풀었다. 백준[ 1790 | Python ] 수 이어 쓰기 2 구현, 수학 yeoooo.github.io 수를 1부터 n까지 이어붙였을 때 k번째 수를 구하는 문제이다. 단순히 수를 모두 이어붙혀 문자열을 만들고 문자열의 k번째 수를 출력하면 될거 같지만 n이 최대 1억개라 이어붙이는 과정에서 메모리 초과가 발생한다. 그래서 실제로 이어붙이는 것이 아닌 '탐색'을 해야..

1. 문제 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기의 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M..

부품 찾기 문제 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N=5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M=3 [5, 7, 9] 이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다. 입력 첫째 줄에 ..