Back to basics

문제 풀이 bool isBadVersion(version) 함수가 주어지고 Bad가 처음 발생한 버전을 찾는 문제이다. 이진 탐색을 이용해서 풀면 되는 문제다. Kotlin으로 풀었는데 한 가지 주의할 점은 middle를 구할 때 (high + low)/2 이용하면 Integer 범위를 초과할 수 있어 Time Limit Exceeded 이 나온다. 대신에 low + (high - low)/2 를 이용하면 해결할 수 있다. (low + high)/2 = low + (high-low)/2 코드 /* The isBadVersion API is defined in the parent class VersionControl. def isBadVersion(version: Int): Boolean = {} */ c..

문제 풀이 오름차순으로 정렬된 배열에 원하는 값을 찾는 문제이다. 문제 이름대로 이진 탐색을 이용해서 풀면 되는 문제다. 이진 탐색은 정렬된 리스트에서 값을 탐색하는 알고리즘이다. 아래와 같이 매번 탐색이 진행될 때마다 범위를 1/2씩 좁혀서 가면서 탐색한다. 그래서 시간 복잡도는 O(logN)이다. 배열에 원하는 값이 존재하면 원하는 값의 인덱스를 반환하고 아니면 -1을 반환하면 된다. 그래서 해당 문제의 종료 조건은 아래와 같이 구현할 수 있다. 원하는 값을 찾았을 때 return 원하는 값의 인덱스 왼쪽인덱스가 오른쪽 인덱스보다 큰 경우, 원하는 값이 배열에 없는 경우이다. return -1 코드 class Solution { public int search(int[] nums, int target..

문제 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom. Example : Consider the following matrix: ] Given target = 5, return true. Given target = 20, return false. 풀이 주어진 matrix에서 target 값이 존재하는 지를 찾는 문..