본문 바로가기

이진 탐색20

[백준] 16498번 : 작은 벌점 (C++) 16498번 : 작은 벌점 문제) 세 명이 한 팀이 되어 정수를 조합하는 게임이 있다. 이 게임에서 각 팀의 각 플레이어는 정수가 하나씩 적혀있는 숫자 카드를 한 장 이상 받는다. 각 플레이어는 가지고 있는 숫자 카드 중 한 장을 선택해 책상에 내려 놓는다. 이렇게 되면 책상에 총 3장의 카드가 놓이게 되며, 이 때 보이는 수의 최댓값과 최솟값의 차이가 벌점이 된다. 이를 식으로 표현하면 다음과 같다. | max(a,b,c) – min(a,b,c) | 여기서 a, b, c는 각각 플레이어가 선택하여 내려놓은 카드의 숫자 값이다. 세 명의 플레이어에게 주어진 숫자 카드가 주어졌을 때, 만들 수 있는 가장 작은 벌점을 구하는 프로그램을 작성하시오. 입력 : 첫째 줄에 첫 번째 플레이어가 받은 숫자 카드의 개.. 2024. 2. 3.
[백준] 13423번 : Three Dots (C++) 13423번 : Three Dots 문제) 직선 위에 서로 다른 N개의 점이 찍혀 있다. 점 i의 위치는 Xi이다. N개의 점 중 3개를 골라 가장 왼쪽에 있는 점을 a, 가운데 있는 점을 b, 가장 오른쪽에 있는 점을 c라고 하자. 각각의 점의 위치는 Xa, Xb, Xc이다. 이때 점 a, b 사이의 거리와 점 b, c사이의 거리가 같으면 세 점의 간격이 같다고 한다. 즉, Xb - Xa = Xc – Xb일 때 세 점의 간격이 같다. 다음은 N = 5인 경우의 예시이다. 위 예시에서 점의 위치는 각각 -4, -1, 0, 2, 4이다. 이중 -4, -1, 0위치의 세 점을 각각 a, b, c라고 하면 Xb - Xa = 3, Xc – Xb = 1로 간격이 같지 않다. 그러나 -4, -1, 2 위치의 세 점.. 2024. 2. 2.
[알고리즘] 이진 탐색 (Binary Search) 개인 공부 후 자료를 남겨놓기 위한 목적이므로, 생략되거나 오류가 있을 수 있음을 알립니다. 목차 0. Intro 1. 이진탐색의 아이디어와 기본 구현 2. 이진탐색 응용 3. 매개변수 탐색 0. Intro https://namu.wiki/w/%EC%97%85%20%EC%95%A4%20%EB%8B%A4%EC%9A%B4#toc 업 앤 다운 - 나무위키 가장 많은 경우에 룰로 사용하는 5번 안에 맞히기의 경우를 생각하여 보자. 중간값만을 부르는 전략(최적의 전략)을 선택한다면 log⁡250≈5.64⋯\log_2 50 \approx 5.64 \cdotslog2​50≈5.64⋯이므로 이론상 namu.wiki 위 링크를 읽어보면 이진 탐색의 수학적 핵심을 알 수 있다. 요약하자면 중간값만을 부르는 최적의 전략을 .. 2024. 2. 2.
[백준] 1166번 : 선물 (C++) 1166번 : 선물 문제) 민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A × A × A 이다. 민식이는 이 작은 박스를 크기가 L × W × H 인 직육면체 박스에 모두 넣으려고 한다. 모든 작은 박스는 큰 박스 안에 있어야 하고, 작은 박스의 변은 큰 박스의 변과 평행해야 한다. N, L, W, H가 주어질 때, 가능한 A의 최댓값을 찾는 프로그램을 작성하시오. 입력 : 첫째 줄에 네 정수 N, L, W, H가 주어진다. 출력 : 첫째 줄에 가능한 A의 최댓값을 출력한다. 절대/상대 오차는 10^-9까지 허용한다. 풀이) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2.. 2024. 1. 8.

티스토리툴바