Redddy's Devlog

오늘 릿코드 데일리 풀다가 이분탐색을 사용할 일이 있어 러스트가 제공하는 이분탐색 라이브러리를 살펴보았는데, 재밌는 점을 발견하여 정리를 한다. (만약 데일리 풀이 코드가 궁금하다면 여기로) Vec에 binary_search 라는 함수가 있다. 만약 배열에 찾고자 하는 값이 있다면 해당 인덱스를 반환하고, 없다면 lower bound 즉 그 값이 들어가야 할 인덱스를 반환한다. 사실 자세한 설명은 아래에 첨부한 러스트 docs를 보는게 정확하고 친절하다. 그럼에도 이 글을 쓰는 이유는 러스트가 제공하는 이분탐색 함수가 파이썬이 제공하는 이분탐색 함수랑 다른 점이 있었고 여기서 러스트의 철학을 배웠기 때문이다. 파이썬이 제공했던 bisect 라이브러리와 달랐던 점은 무엇이었냐하면 Result로 한 번 값을..

🔈 문제 소수전공 수업을 마무리한 찬우는 축하의 의미로 학생들에게 사탕을 나누어 주려 한다. 구체적으로, 기준이 되는 음이 아닌 정수 $X$를 정한 뒤 최종 점수가 $X$점을 넘는 학생들에게 점수가 높은 만큼 많은 사탕을 줄 것이다. 즉, $X+1$점을 받은 학생은 $1$개, $X+2$점을 받은 학생은 $2$개, $T$($T > X$)점을 받은 학생은 $T - X$개의 사탕을 받게 된다. 찬우는 학생들에게 최대한 많은 사탕을 나누어주고 싶기 때문에 기준 점수 $X$를 가능한 한 낮게 정하려 한다. 하지만, 지금 가지고 있는 돈으로는 사탕을 $K$개까지만 살 수 있기 때문에 사탕의 총 개수가 $K$개를 넘으면 안 된다. 찬우의 수업은 총 $N$명이 수강했고, $i$번째 학생은 $A_i$점을 받았다. 수강생..

🧩문제 해석 갖고 랜선들을 k개의 같은 길이의 랜선으로 자르되, 자른 랜선쪼가리들은 다시 사용할 수 없다. 이때 만들 수 있는 최대 길이의 랜선을 구하는 문제이다. 📕 풀이 숫자 범위가 심상치 않다. 갖고 있는 랜선의 수가 백만개이고, 랜선이 길이는 2^31-1 보다 작은 자연수이다.ㅎ 일반적으로 접근했다가는 시간초과날 것이 분명하다. 이 문제는 이분탐색으로 풀어야 한다. 첫번째 아이디어! 가지고 있는 랜선중 최소값을 찾는다. 최소값 랜선을 end 값에 두고 이분탐색을 한다. 탐색 값들을 리스트에 저장하고, 최종적으로 그 리스트의 최대값을 출력한다. 최소값랜선을 end 값에 둔 이유는 최대값랜선을 end 값에 둔다 하여도 결국에는 최소값랜선에 올 것이라고 생각했다. 물론 맞는 말이긴 하다. 그러나 생각하..