항해99, 4주차 2D 행렬 검색 2

Today I learned
2022/02/04

회고록

---

2/04

항해 99, 알고리즘 3주차

교재 : 파이썬 알고리즘 인터뷰 / 이것이 코딩테스트다(동빈좌)

이분탐색(Binary Search)

1. 이론

이분탐색

참이슬 병뚜껑 아래에 1-50까지 적힌 숫자 맞힐때 쓰던 방법

5번 내로 맞추면 출제자가 마시는 벌칙을 수행시 이분탐색을 하면 출제자가 상당히 불리해진다.

25 -> 12 -> 6 -> 3 -> 50%확률로 출제자 벌칙

아래 이미지를 보고 이분탐색의 컨셉을 이해하자.

2. 문제

문제 설명

Write an efficient algorithm that searches for a value target in an m x n integer matrix 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 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

https://leetcode.com/problems/merge-intervals/

3. MySol

• binary search

이분탐색X2 풀이

def solution(matrix, target):

    checker = False


    def bin_search():

        left = 0
        right = len(matrix)-1

        while left <=right:

            mid = (left + right) // 2

            if target > matrix[mid][0]:
                left = mid+1
            elif target < matrix[mid][0]:
                right = mid-1
            else:
                return mid + 1

        mid = max(left,right)
        return mid


    lineRIdx = bin_search()


    def bin_search2(lineLimit):

        temp_matrix = matrix[:lineLimit]
        i=0

        for i in range(lineLimit):

            left = 0
            right = len(temp_matrix[i])-1

            while left <= right:

                mid = (left + right) // 2

                if target > matrix[i][mid]:
                    left = mid + 1
                elif target < matrix[i][mid]:
                    right = mid - 1
                else:
                    return True

            i += 1
        return False


    checker = bin_search2(lineRIdx)

    return checker

if __name__ == '__main__':

    target = 20

    matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]

    result = solution(matrix, target)

    print(f'{result}')

파알인터뷰 책에 나온 색다른 풀이

def solution(matrix, target):

    if not matrix:
        return False

    row = 0
    col = len(matrix[0]) -1

    while row <= len(matrix) -1 and col >=0:
        if target == matrix[row][col]:
            return True
        elif target < matrix[row][col]:
            col-=1
        elif target > matrix[row][col]:
            row+=1


    return False

if __name__ == '__main__':

    target = 20

    matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]

    result = solution(matrix, target)

    print(f'{result}')

4. 배운 점

• 세로로 이분탐색 후, 가로로 이분탐색하면 문제가 풀릴 것이라고 직관적으로 생각하게 된다.

• 그렇게 풀었고 실제 책의 풀이와는 다르지만, 리트코드에서 퍼포먼스차이는 없어보였다.

5. 총평

이분탐색 익히기