728x90 이분 탐색4 BOJ - 2792, 보석 상자 매개 변수 탐색 (이분 탐색) 이번 문제는 매개 변수 탐색(parametric search) 문제입니다. 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net 그동안 그냥 이분 탐색이겠거니 하고 풀이했는데, 매개 변수 탐색 문제는 이분 탐색 기법을 적용하지만 다음과 같이 약간의 개념 차이가 있었습니다. 매개 변수 탐색이란? 이진 탐색(이분 탐색)을 사용해서 조건에 만족하는 최댓값을 구하는 방법을 의미한다. 정리하면, 기존의 이분(이진) 탐색은 수열 내에서 lower-bound 또는 upper-bound로 대소 비교를 통해 찾고자 하는 수의 위치를.. 2023. 1. 3. BOJ - 1300번, K번째 수 이분 탐색을 이용한 풀이 (C++) 이번에는 오랜만에 이분 탐색 태그가 달린 문제를 풀어봤습니다. 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 난이도가 골드 2였는데, 역시나 여러 가지 아이디어를 생각하다 다른 분의 풀이를 참고해서 해결할 수 있었습니다. 풀이 과정 정리 요새 난이도가 있는 문제 풀이를 잘 안 해서 그런지 풀이를 보고 이해하는 것도 조금 어려웠던 문제입니다. 우선, 처음 문제를 봤을 때는 배열의 특징부터 뽑아 봤습니다. A 배열은 대칭 행렬 구조이다. A 배열의 대각선 상에 위치한 원소들의 값은.. 2022. 12. 30. 백준 2434번 - 기타 레슨, 이분 탐색 (Binary Search) 풀이 (C++) 이번에 풀이한 문제는 백준 2434번 기타 레슨 문제입니다. 이분 탐색 알고리즘을 활용해서 풀이할 수 있었고, 풀이한 과정을 간단하게 정리해 보겠습니다! 언어는 C++를 이용해 풀이했습니다. 문제 링크!😀 1. 문제 설명 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 .. 2022. 9. 16. BOJ - 2110번 공유기 설치 문제, 이분 탐색 문제 풀이! (with C++) 이번에 풀이한 문제는 이분 탐색 알고리즘을 이용해 풀이해야 하는 문제였습니다. 이분 탐색 문제를 평소에 잘 풀이해보지 않아 오랜만에 풀게 되었는데, 역시나 개념 자체에 서툴러서 이전에 정리했음에도 불구하고 풀이하는데 어려움을 느껴 다른 분들의 개념을 적극적으로 참고해 풀이하게 되었습니다. 문제 링크는 여깄습니다! 😁 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 2110번 문제 설명 우선 문제는 도현이가 가진 N개의 집에 C개의 공유기를 설치하는데, 공유기.. 2022. 8. 28. 이전 1 다음 728x90
