항해99, 4주차 두 수의 합

Today I learned
2022/02/04

회고록

2/04

항해 99, 알고리즘 3주차

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

이분탐색(binary search)

1. 이론

이분탐색

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

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

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

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

2. 문제

문제 설명

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

https://leetcode.com/problems/two-sum/

3. MySol

• bisect 라이브러리 미사용

def solution(target, nums):

    result = []

    def bi_search(idx):
        nonlocal result
        x = idx
        left = idx+1
        right = len(nums)-1

        while left<=right:
            mid = (left + right) //2

            if nums[x] + nums[mid] > target:
                right = mid-1
            elif nums[x] + nums[mid] < target:
                left = mid+1
            else:
                temp = [x, mid]
                result.append(x)
                result.append(mid)
                break

        return result

    for i in range(len(nums)):
        result=bi_search(i)

    return result

if __name__ == '__main__':

    target = 9
    nums = [2,7,11,15]

    result = solution(target, nums)

    print('result : ' + str(result))

-bisect 라이브러리 사용

import bisect


def solution(target, nums):

    for idx, n in enumerate(nums):
        expected = target-n
        i = bisect.bisect_left(nums, expected, idx+1)
        if i<len(nums) and nums[idx] + nums[i] == target:
            return [idx+1,i+1]

if __name__ == '__main__':

    target = 9
    nums = [2,7,11,15]

    result = solution(target, nums)

    print('result : ' + str(result))

4. 배운 점

• 이분탐색에 대한 기초 이해 및 문제 접근

5. 총평

이분탐색과 친해지는 시간