늘 겸손하게

랜선 자르기 이분 탐색의 응용 버전 문제 풀이 직관적으로 떠오르는 풀이는 가지고 있는 랜선들을 나눈 몫들의 합이 K가 되는 길이를 찾기 위해 길이 1부터 가장 길이가 짧은 랜선 길이까지 반복적으로 랜선들을 나누는 풀이법이다. 정답인 길이가 M 이라면 이 풀이법의 예상 복잡도는 O(NM)이다. 문제에서 N은 1이상 1,000,000 이하의 정수라고 명시했으므로 위 풀이는 시간초과가 발생한다. 그러므로 이분 탐색으로 검색 시간을 N 에서 logN으로 줄여야한다. 이분 탐색을 어떻게 적용할까? 1. left , right 설정 이분 탐색을 위해선 인덱스값을 저장할 변수 2개가 필요하다( left, right 혹은 low, high ). 위 문제에서 요구하는 답은 길이이므로 랜선의 최소 길이인 1을 left에,..

Gradle 사용해보자 출처 : https://docs.gradle.org/current/userguide/getting_started.html 설치 Build에 Gradle Wrapper가 포함되어 있고 이미 존재하는 Gradle build를 실행시키고 싶을뿐이면 Gradle를 설치할 필요는 없습니다. Gradle Wrapper는 build root 하위 폴더인 gradlew 혹은 gradlew.bat 파일에서 확인 가능합니다. Gradle wrapper로 build하고 싶다면 사용하시는 시스템이 Gradle의 전제조건만 만족시키는지 확인하면 됩니다. Gradle prerequisites - Gradle의 전제조건들 https://docs.gradle.org/current/userguide/instal..

IntelliJ 쓰면서 간간히 봤던 Gradle Gradle 이 대체 뭘까? 출처 : https://docs.gradle.org/current/userguide/what_is_gradle.html#five_things Gradle 오픈소스 빌드 자동화 툴로 어떤 타입의 소프트웨어든 빌드할 수 있을 만큼 유연한 특징이 있다. Gradle의 중요한 특징들 - 휼륭한 퍼포먼스 Gradle은 불필요한 작업의 수행을 피하기 위해 입출력이 바뀔 때 필요한 작업만 수행합니다. Build cache를 사용하여 지난 작업의 출력물 혹은 다른 기계의 출력물을 재사용 가능합니다. 또한 여러가지 최적화 기능이 탑재되어 있고 개발팀이 계속해서 Gradle의 퍼포먼스를 키우기 위해 노력하고 있습니다. - JVM foundatio..

숫자 카드 2 이분 탐색의 upper bound와 lower bound를 이용하여 푸는 문제이다. upper bound 와 lower bound 란? 이분 탐색으로 배열에서 숫자를 탐색할 때 찾으려는 숫자의 개수가 배열에서 여러 개 존재할 수 있다. 이때 탐색된 동일한 숫자들중 가장 작은 인덱스 값이 lower bound, 가장 큰 인덱스 값이 upper bound이다. 예로 길이가 10이고 각 원소 값이 { 1 , 3, 5, 9 , 11 , 13 ,19 , 19 , 19 , 20 } 인 배열에서 19를 찾는다고 해보자. 19가 가장 처음 나온 인덱스는 6 , 가장 나중에 나온 인덱스는 8 이므로 lower bound는 6, upper bound는 8이 된다. 이를 이용하여 문제를 해결해야 시간 초과가 ..