문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/43236 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이- 처음 int[] rocks에서 n개의 바위를 제거하는 조합을 구하는 방식을 생각했으나 50,000C25,000으로 시간 초과 예상 - 이진 탐색 중 매개변수 탐색으로 할 경우 N * log(1억) = 50,000 * 30 시간 복잡도로 풀이 가능 절차- (중요*) int[] rocks를 오름차순 정렬 (ex. [2, 11, 14, 17, 21] )- L과 R의 범위를 지정- 바..

문제 링크 https://www.acmicpc.net/problem/22254 22254번: 공정 컨설턴트 호석 거듭된 창업 성공을 이룬 류진국 사장은 이번에는 맞춤형 선물을 제작해주는 공장을 만들기로 했다. 현재 들어온 맞춤형 선물 주문은 총 $N$개이며, 각 맞춤형 선물마다 제작에 필요한 시간이 정 www.acmicpc.net 문제 풀이 - "모든 선물을 X 시간 내에 만들 기 위한, 공정 라인의 최소값" 으로 문제 해석하여 매개변수 탐색으로 풀이 - PriorityQueue 사용하여 공정 라인 수가 정해졌을 때 X 시간내 선물 생산 가능 여부 확인 (boolean) - 선물 개수 N =최대 10^5개, 제작 완료 X = 10^9 시간 제한 걸리고, 각 선물의 공정시간이 10^9일 때 공정라인은 10..

문제 링크 https://www.acmicpc.net/problem/13702 13702번: 이상한 술집 프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다. 즉 한 번 주문에 막걸리 용 www.acmicpc.net 풀이 - 이진탐색(매개변수 탐색) 문제 - 시간복잡도 O(NlogN) - long 타입 변수를 사용해야 하는 경우 있음 뒤집은 문제 용량(ml) 을 정했을 때, 친구(K)명에 막걸리를 골고루 분배 가능한가 ? 이때 용량(ml)는 최대인가? 부등호 헷갈리는 경우 주전자(N) 1개 이고 그 안에 21억ml가 담겨 있고, 친구(K) 100만명 있을 때 - 1000ml 로 나눌 경우 주전자에 1..

문제 링크 https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 풀이 - 이진탐색(매개변수 탐색) 문제 - 시간복잡도 O(NlogN) - 굴다리 길이 N (1 ≤ N ≤ 100,000) 일 때 0번 위치에 가로등 한 개 세울 경우 H는 100,000(최대)이 되야 모두 비추는게 가능하므로 Integer로 연산가능 뒤집은 문제 가로등 높이 H일 때 굴다리 길이 N을 모두 비추는게 가능한가? 가능한 경우 가로등 높이 H는 최소 높이인가? 예제 입력 1 5 ..

문제 링크 https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 풀이 - 이진탐색(매개변수 탐색) 문제 - 시간복잡도 O(NlogN) - 은행 인출(mid) 하고 cnt = 1 한 초기 상태에서 일별 사용금액을 차감하면서 부족할 경우 추가 은행 인출(cnt += 1) - (100, 400), (300,100), (500), (101), (400) 형태가 최대값 만약 N일이 10만이고, 각 금액이 1만이면 최대 10^9이 되야 1번(M)번에 처리가 가능 =..

문제 링크 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 - 이진탐색 (매개변수 탐색) 으로 풀이하면 되는 문제 - 시간 복잡도는 O(NlogN) 범위 지정시 (L, R) L 의 경우 100,000개의 강의(N)를 100,000 개의 블루레이(M)에 담는다 할 때 (각 강의 길이 또한 최대 10,000분) 최소 10,000분이 되야함. 10,000분 이하는 담을 수가 없기 때문에, 최소 10,000분이 기준이 됨 L 은 고로 주어진 배열에서 가..

문제 링크https://www.acmicpc.net/problem/1300 1300번: K번째 수세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 Bwww.acmicpc.net2차원 배열을 1차원으로 이렇게 구할 수도 있다니 또 하나 배운다 :) 풀이 - N (최대 10만), K (10만 ~ 10억)- N * N 2차원 배열을, 1차원 배열로 변환 후 정렬했을 때 K번째 있는 임의 수를 구하는 문제 - N이 최대 10만이기 때문에 1차원 배열로 변환시 10^10 = 100억이 되어서 메모리 초과, 시간 초과 발생 가능 아래와 같은 연산..

문제 링크 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개를 만들기 위한 최대 랜선 길이 H를 구하시오. 뒤집은 지문 (매개변수 탐색*) 임의 길이 H로 랜선을 K개를 자를때, 필요한 랜선 N개를 만들 수 있는가? 이때 최대 랜선 길이 H는 얼마인가? 시간 복잡도 O(NlogN) 최대값 랜선의 길이 최대값이 2^31 ..

문제 링크 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 매개변수 (paramatrix search) 탐색 문제 (그리디 포함) 문제 지문 C 개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 최대 거리(Dmax) 를 구하시오. 뒤집은 지문 두 공유기 사이의 거리 (D)를 라 할때, C개의 공유기를 설치 가능한가(yes/no)? 이때 설치 가능한 최대 거리(Dm..

문제 링크 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 반복문을 통해 left = 1 ~ N 까지 조회할 때 - arr[left + 1 ... N] 사이에 값들 중 -arr[left] 이상이면서 가장 왼쪽에 있는 값을 찾아야 함 - N 이 최대 10만일때 O(N^2) = 10^10 시간초과 발생가능 - 이진탐색으로 풀이시 O(NlogN) 시간 복잡도 가짐 투 포인터로 풀 경우 좀 더 쉽게 풀이 가능 주..