Week 4

Day 1

양수 N을 이진법으로 바꿨을 때, 연속으로 이어지는 0 중에서 가장 큰 값을 return해 주세요.
이어지는 0은 1과 1사이에 있는 것을 의미합니다.이런 것을 binary gap 이라고 합니다.
input: 9
output: 2
설명: 9의 이진수는 1001 입니다. 1과 1사이에 있는 0은 2 이므로, 2를 return

def solution(N):
  binary = format(N, 'b') # N값을 이진수로 바꿔준다
  result = 0 #결과값 저장할 변수와 0의 갯수를 
  current = 0 #셀 변수를 만들어준다.

  for i in binary: #for문을 사용하여 2진수로 변경한 값 하나 하나를 if문으로 확인한다.
    if i == '1':  #먼저 1일때
      result = max(result, current) #둘 중에 큰 값 result안에 저장한다.
      current = 0 #0의 갯수를 다시 세기 위하여 current를 0으로 초기화 해준다
    if i == '0': 
      current += 1
  return result

Day 2

prices는 배열이며, 각 요소는 매일의 주식 가격입니다.
만약 한 번만 거래할 수 있다면 = 사고 팔 수 있다면, 제일 큰 이익은 얼마일까요?
예를 들어,
Input: [7,1,5,3,6,4]
Output: 5

def maxProfit(prices): 
  max_profit = 0, min_price = 0, float('inf')
  
  for price in prices:
      min_price = min(min_price, price)
      profit = price - min_price
      max_profit = max(max_profit, profit)
      
  return max_profit

float('inf')

• It acts as an unbounded upper value for comparison. This is useful for finding lowest values for something.
  for example, calculating path route costs when traversing trees.

>>> lowest_path_cost = float('inf')
>>> # pretend that these were calculated using some worthwhile algorithm
>>> path_costs = [1, 100, 2000000000000, 50]
>>> for path in path_costs:
...   if path < lowest_path_cost:
...     lowest_path_cost = path
...
>>> lowest_path_cost
1

Day 3

다음과 같이 input이 주어졌을 때,
같은 알파벳으로 이루어진 단어끼리 묶어주세요.
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:[["ate","eat","tea"],["nat","tan"],["bat"]]

def groupAnagrams(strs):
    d = {}
    
    for w in sorted(strs):
        key = tuple(sorted(w))
        d[key] = d.get(key, []) + [w]
    return list(d.values())

Day 4

숫자로 이루어진 리스트 nums를 인자로 주면,
그 안에서 어떤 연속적인 요소를 더했을 때 가장 큰 값이 나오나요?
가장 큰 값을 찾아 return해주세요.
Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6 (설명: [4,-1,2,1] 를 더하면 6이 가장 크기 때문이다)

def maxSubArray(nums):
  for i in range(1, len(nums)):
    if nums[i-1] > 0:
      nums[i] += nums[i-1]
  return max(nums)

Day 5

이진탐색을 배우기 전에 선형탐색(Linear Search)먼저 보겠습니다.

선형탐색이나, 이진탐색의 요소는 오름차순이나 내림차순으로 되어 있어야 적용할 수 있는 알고리즘입니다.

let arr = [2, 4, 6, 8, 11, 14];
let arr = [2, 4, 6, 8, 11, 14];
위의 배열에서 요소가 8인것을 찾으려면 어떻게 해야할까요?
index 0에서부터 5까지 차례대로 요소를 확인하면서 8이 나올 때까지 for 문을 돌리면 됩니다.
이렇게 첫 index 부터 하나하나 찾아나서는 것을 선형탐색이라고 합니다.

그런데 배열의 길이가 1000이고, 1000이라는 요소를 찾아야 하는데 arr[9999]에 1000이 있다고 가정한다면 몇 번의 for문이 돌아갈까요?
네, 1000번 입니다.

이렇게 선형탐색의 단점은 요소에 따라 탐색을 여러 번 해야할 수도 있다는 점입니다.
즉, 1을 찾으려면 for문을 한 번만 돌려도 되는데, 1000을 찾으려면 for문을 1000번 돌려야 한다는 말입니다.
만약 for문 내부에 복잡한 계산이 들어있다면 실행속도가 느려지고 효율적이지 않은 로직이 될 것입니다.
그럼 좀 더 효과적인 알고리즘이 있을까요?

네! 바로 이진 탐색입니다.
이진 탐색은 순서대로 찾는 것이 아니라, 중간부터 찾아 나서는 방법입니다.
만약 아래와 같은 배열에서 7을 찾아야 한다면,
첫 번째로 중간 위치의 요소를 비교하고(7<14) 찾아야할 값보다 크면 왼쪽의 중간에서 다시 비교합니다.
다시 한 번 크기를 비교해서 오른쪽의 중간으로 갈지, 왼쪽의 중간으로 갈지 결정하여 다시 찾아나서는 것을 이진 탐색법이라고 합니다.

오늘의 코드 카타
오름차순인 숫자 nums 배열과 찾아야할 target을 인자로 주면,
target이 몇 번째 index인지 return 해주세요.

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
설명: 찾지 못하면 -1로 return 해주세요.

nums 배열에 있는 요소는 서로 중복된 값이 없습니다.

def search(nums, target):
  l, r = 0, len(nums) - 1
  while l <= r:
    mid = (l + r) // 2
    if nums[mid] < target:
      l = mid + 1
    elif nums[mid] > target:
      r = mid - 1
    else:
      return mid
  return -1