본문 바로가기

vividswan

Notice

블로그 이전 완료

Recent Posts

Popular Posts

Recent Comments

Link

깃허브

Calendar

Tags

더보기

Archives

Visits

Today

Yesterday

이분탐색

Algorithm/BOJ 2022. 3. 13. [BOJ] Thread Knots(17976) [백준(BOJ)] Thread Knots(17976) C++ 문제 : BOJ_17976번 Thread Knots 문제 설명 이분탐색 n 개의 thread가 주어지고, 이 thread 하나하나마다 점을 찍어야 합니다. 이때 점의 x좌표의 간격의 최솟값이 최대가 되는 거리를 구하는 것이 문제입니다. 점의 범위가 0부터 1000000000이기 때문에 완전 탐색으로 점의 간격을 파악하기는 어려우므로, 이분 탐색을 이용해야 합니다. Solution 우선 thread의 범위를 벡터로 입력받은 뒤, 벡터를 정렬합니다. 순서대로 정렬한 값을 순회하면서 현재 이분 탐색의 mid 값의 거리를 최솟값으로 각 thread마다 점을 찍을 수 있는지 확인합니다. 확인을 위해선 우선 첫 번째 thread의 시작점에 첫 번째 점을 ..

Algorithm/BOJ 2022. 3. 10. [BOJ] 백조의 호수(3197) [백준(BOJ)] 백조의 호수(3197) C++ 문제 : BOJ_3197번 백조의 호수 문제 설명 이분탐색, bfs 물 공간과 빙판 공간이 있는 지도가 주어지고, L에 두 백조의 위치가 주어집니다. 물 공간과 가로, 세로로 접한 빙판 부분이 하루에 한 번씩 녹는데, 이때 두 백조가 만날 수 있는 최소의 날을 계산하는 문제입니다. 이 문제는 하루에 한 번씩 녹는 빙판 부분도 고려해야 하고, 또 빙판이 녹았을 때 만날 수 있는 최소의 날도 구해야 하기 때문에 bfs와 이분 탐색 두 가지가 쓰이는 문제입니다. Solution 처음에 bfs를 이용하여 빙판이 모두 녹는 최대 날을 이분 탐색의 max 값으로 지정해 주고 이분 탐색을 실행합니다. 최솟값과 최댓값의 중간값으로 bfs를 돌리며 중간값의 날이 되기 전에..

Algorithm/BOJ 2022. 3. 7. [BOJ] 보석 상자(2792) [백준(BOJ)] 보석 상자(2792) C++ 문제 : BOJ_2792번 보석 상자 문제 설명 이분탐색 이분 탐색으로 해결할 수 있는 문제입니다. 사람 수 N이 있고, 보석의 종류 수 M이 있습니다. 한 사람에게는 한 종류의 보석을 나눠 줄 수 있고, 모든 사람에게 보석을 줄 필요는 없지만, 모든 보석은 나누어줘야 합니다. 이때, 보석을 가장 많이 갖고 있는 사람의 보석 수를 질투심이라고 할 때, 질투심의 최솟값을 구하는 문제입니다. Solution 질투심을 최소로 하려면, 보석의 종류와 상관없이, N 명이 넘어가지 않으면서, 한 학생에게 나누어줄 수 있는 보석의 수의 최솟값을 구해야 합니다. 그러므로, 보석 수를 증가시키면서, 모든 보석을 N명 이하의 학생에게 나눠줄 수 있는지를 이분 탐색을 통해 찾아..

이전 1 다음

티스토리툴바