[쓰면서 익히는 알고리즘과 자료구조](1) 배열(Array)

쓰면서 익히는 알고리즘과 자료구조

1.3 두 수의 합 찾기

def two_sum_brute_force(nums: list[int], target: int) -> list[int]:
    for i in range(0, len(nums)):
        for j in range(i+1, len(nums)):
            if (nums[i] + nums[j]) is target:
                return [i, j]
    return [-1, -1]

def two_sum_hash(nums: list[int], target: int) -> list[int]:
    hashtable_dict = {}

    for i in range(0, len(nums)):
        value = target - nums[i]

        if hashtable_dict.get(value) is not None:
            return sorted([i, hashtable_dict[value]])

        hashtable_dict[nums[i]] = i

    return [-1, -1]

1.4 정렬된 배열에서 중복 제거

def remove_duplicates(nums: list[int]) -> int:
    """
    배열에서 중복되지 않은 요소의 갯수를 구한다
    즉 책에서는 함수명이 remove_duplicates 로 되어있는데
    정확히 말하면 get_count_unique_element 정도가 될 것 같다
    :param nums: 배열
    :return: 중복되지 않은 요소의 갯수
    """
    if len(nums) == 0:
        return 0

    curr = nums[0]
    cnt = 1

    # list 순회
    for i in range(len(nums)):
        # 자신과 다른 값이면
        if curr != nums[i]:
            # curr 을 그 값으로 update
            curr = nums[i]
            nums[cnt] = curr
            cnt += 1

    return cnt

print(remove_duplicates(nums=[])) # 0
print(remove_duplicates(nums=[1, 2, 3, 4])) # 4
print(remove_duplicates(nums=[0, 0, 1, 1, 1, 2])) # 3

1.5 배열에서 삽입 위치 찾기

💡 O(N) 보다 빠르게 처리해야 하는 조건이 더 붙을 수도 있는데 이런 경우 ‘이진 탐색’을 바로 떠올려야 한다.

def search_insert(nums: list[int], target: int) -> int:
    index = 0

    while index < len(nums):
        if target <= nums[index]:
            break

        index += 1

    return index

print(search_insert(nums=[1, 3, 5, 6], target=100))  # 4

def search_insert_binary(nums: list[int], target: int) -> int:
    low = 0
    high = len(nums) - 1

    while low <= high:
        mid = int((low + high) / 2)

        if target == nums[mid]:
            return mid

        if target > nums[mid]:
            low = mid + 1
        else:
            high = mid - 1

    return low

print(search_insert_binary(nums=[1, 3, 5, 6], target=100))  # 4

1.6 정렬된 배열의 병합

주어진 두 배열(nums1, nums2)을 정렬을 유지하면서 병합해보자

def merge(nums1: list[int], m: int, nums2: list[int], n: int):
    for i, v in enumerate(nums2):
        nums1[m + i] = v

    nums1[:] = sorted(nums1)

def merge2(nums1: list[int], m: int, nums2: list[int], n: int):
    i = m - 1
    j = n - 1
    k = m + n - 1

    while i >= 0 and j >= 0:
        if nums1[i] < nums2[j]:
            nums1[k] = nums2[j]
            j -= 1
        else:
            nums1[k] = nums1[i]
            i -= 1

        k -= 1

    while j >= 0:
        nums1[k] = nums2[j]
        k -= 1
        j -= 1

1.7 정렬된 배열의 병합2

def merge(nums1: list[int], m: int, nums2: list[int], n: int):
    for i, nums1_item in enumerate(nums1):
        if nums1_item > nums2[0]:
            nums1[i] = nums2[0]
            nums2[0] = nums1_item

            for k, item in enumerate(nums2[1:], start=1):
                if nums1_item <= item:
                    nums2[k - 1] = nums1_item
                    break

                nums2[k - 1] = nums2[k]

1.8 파스칼의 삼각형

def generate_pascal_triangle(num_rows: int) -> list[list[int]]:
    pascal = []

    if num_rows <= 0:
        return pascal

    pascal.append([1])

    for i in range(1, num_rows):
        prev_len = len(pascal[i - 1])

        curr_list = []

        for j in range(prev_len + 1):
            num = 1
            if j != 0 and j != prev_len:
                num = pascal[i - 1][j - 1] + pascal[i - 1][j]

            curr_list.append(num)

        pascal.append(curr_list)

    return pascal

triangle = generate_pascal_triangle(10)

for t in triangle:
    for k in t:
        print(k, end=' ')
    print()

1.9 배열에서 다수의 요소 찾기

배열에서 floor(n/2) 번 이상 나타나는 요소를 찾아보자.

Constraints

• 정수형 배열
• 배열은 1개 이상의 요소를 가진다
• 다수의 수는 무조건 하나가 존재한다.

Ideas

• Brute-force [시간복잡도 O(n^2)]
  • 배열을 순회한다
  • 각 배열의 요소를 다른 모든 요소와 비교하여 배열에 몇 개가 들어있는지 파악한다
  • 개수를 세면서 다수의 수 조건에 맞는 숫자가 있으면 해당 숫자를 반환한다
• Hash Table [시간복잡도 O(n) ]
  • 해시 테이블에서 키 항목으로는 배열의 요소로 하고 값 항목으로는 횟수를 지정한다
  • 배열을 순회한다
  • 배열을 순회하면서 해당 요소를 해시 테이블에서 찾는다
  • 값이 있다면 해당 요소를 키값으로 하는 값 항목을 꺼내 1을 더해 업데이트한다
  • 값이 없다면 해당 요소를 키 항목으로 두고 1의 값으로 추가한다
  • 값을 업데이트 하고 다수의 수 조건에 맞는 숫자를 반환한다.
• 정렬 [시간복잡도 O(n log n)]
  • 배열을 정렬한다
  • 가운데 수를 반환한다

def majority_element_bruteforce(nums: list[int]) -> int:
    majority_count = int(len(nums) / 2)

    for i, item_i in enumerate(nums):
        count = 0
        for j, item_j in enumerate(nums[i:], start=i):
            if item_i == item_j:
                count += 1
            if count > majority_count:
                return item_i

    return -1

def majority_element_hash(nums: list[int]):
    majority_count = int(len(nums) / 2)

    hashmap = {}

    for num in nums:
        hashmap.setdefault(num, 0)
        hashmap[num] = hashmap[num] + 1

        if hashmap[num] > majority_count:
            return num

    return -1

def majority_element_sort(nums: list[int]):
    return sorted(nums)[int(len(nums)/2)]

1.10 배열의 회전

입력으로 정수형 배열과 k 값이 주어지면, 각 요소를 우측으로 k 번 이동 및 회전을 해보자.
예를 들어서 nums 배열에 [1, 2, 3, 4] 가 있고 k 가 1이라면 요소는 우측으로 1칸씩 이동 및 회전하여 [4, 1, 2, 3] 이 된다.

def rotate_bruteforce(nums: list[int], k: int):
    """
    nums: [1, 2, 3, 4] , k = 2
    prev = 4
    1이랑 4랑 교체 [4, 2, 3, 1]
    prev = 1 nums[i] = 2
    1이랑 2랑 교체 [4, 1, 3, 2]
    3이랑 2랑 교체 [4, 1, 2, 3] 이게 한 번 뒤집은것
    이걸 k 번째 반복,
    k대신 k % len(nums) 를 사용하면 조금 속도가 개선된다
    """
    # k 번 반복한다
    for _ in range(k):
        # 최초의 이전 요소는 배열의 마지막 요소
        prev = nums[len(nums) - 1]
        # 배열을 처음부터 순회하면서 이전 요소와 다음 요소를 계속 바꿔준다.
        for i in range(len(nums)):
            temp = nums[i]
            nums[i] = prev
            prev = temp

def rotate_elem(nums: list[int], k: int):
    temp = [0] * len(nums)
    
    for i, elem in enumerate(nums):
        temp[(i + k) % len(nums)] = nums[i]
    
    nums[:] = temp

def rotate_long(nums: list[int], k: int):
    count = 0
    
    for start in range(len(nums)):
        if count >= len(nums):
            break
        
        curr_index = start
        prev_elem = nums[start]
        
        while True:
            next_index = (curr_index + k) % len(nums)
            temp = nums[next_index]
            nums[next_index] = prev_elem
            prev_elem = temp
            
            curr_index = next_index
            count += 1
            
            if curr_index == start:
                break
    
    # 이렇게 코드 짜면 안됩니다... 뭐이리 복잡하게 꼬아놨어
    # 무슨 코드인지 해석 불가

def rotate_reverse(nums: list[int], k: int):
    k = k % len(nums)
    nums[:] = nums[::-1]  # reverse list
    nums[0:k] = nums[0:k][::-1]
    nums[k:len(nums)] = nums[k:len(nums)][::-1]

def rotate_my_solution(nums: list[int], k: int) -> list[int]:
    length = len(nums)
    if k % length == 0:
        return nums
    
    # 결국 k 번 회전 시키면 0 ~ length - k 가 뒤로 가고, 
    # length-k ~ length 가 맨 앞으로 오는 모양이 된다 
    result = nums[length - k:length]
    tail = nums[0:length - k]
    result.extend(tail)

    return result

1.11 빠진 숫자 찾기

0 ~ n 까지 요소를 담고 있는데 이 중 빠진 값 찾기

💡 이거 문제적 남자에 나온 문제, 다 더한다음에 n*(n-1)/2 에서 빼면 빠진 숫자 나옴

def missing_number_sort(nums: list[int]) -> int:
    nums.sort()

    for i in range(len(nums)):
        if i != nums[i]:
            return i
    
    return len(nums)

def missing_number_set(nums: list[int]) -> int:
    set_nums = set(nums)

    for i in range(len(nums) + 1):
        if i not in set_nums:
            return i

    return -1

def missing_number_xor(nums: list[int]) -> int:
    """
    xor 연산을 하면 N XOR N = 0 이 된다
    배열의 크기가 4 라면 1 XOR 2 XOR 3 XOR 4 에 배열의 요소를 XOR 연산 하면 된다
    XOR 연산은 교환 법칙이 성립하나 보다.
    그러면 존재하는 숫자는 자기 자신과 XOR 되서 0이 되버리니, 없는 원소의 값이 나타나게 된다
    :param nums: 
    :return: 
    """
    missing = len(nums)
    
    for i in range(len(nums)):
        missing = missing ^ i ^ nums[i]
    
    return missing

def missing_number_gauss(nums: list[int]) -> int:
    return int((len(nums)+1) * len(nums) / 2) - sum(nums)

1.12 더 나아가기 위한 준비

재귀 공부해오세요

알고리즘은 2시간 이상 못 풀면 해결책을 확인하고 오답노트 정리하세요

1.13 부분집합(subsets)

고유한 정수의 집합으로 배열이 주어지면 가능한 모든 부분집합을 반환하자, 중복된 부분집합은 허용하지 않는다
재귀를 사용하거나 [Y,Y,N] → [1,1,0] 으로 바꿔서 반복문으로 해서 해결

def subsets_recursion(nums: list[int], res:list[list[int]], sub: list[int], index):
    if len(sub) > len(nums):
        return

    res.append(sub.copy())

    for i in range(index, len(nums)):
        sub.append(nums[i])
        subsets_recursion(nums, res, sub, i+1)
        sub.pop()

# 디버거로 실행해보면 이해 됨

def subsets_iterator(nums: list[int]) -> list[list[int]]:
    res = []
    nums_len = len(nums)
    nth_bit = 1 << nums_len 
    # 1000 을 만들어 놓고 i랑 or 연산을 해서 0b1000 만들고 3번쨰부터 쓰는 것
    # i 는 0b0 ~ 0b111 이므로

    for i in range(2 ** nums_len):
        bitmask = bin(i | nth_bit)[3:]

        res.append([nums[j] for j in range(nums_len) if bitmask[j] == '1'])

    return res

1.14 단어 찾기

[A B C E]
[S F E S]
[A D E E]

에서 ABFE 를 만들 수 있는가?

[A B C E]
[S F E S]
[A D E E]

‘인접한’ ⇒ 좌 우 위 아래

mxn , 1 ≤ m ≤ 300 , 1 ≤ n ≤ 300

word 의 길이는 1≤ len(word) ≤ 10^3 ~ 10^4

일단 맵 크기를 보니 절대 재귀는 안 됨

BackTracking 방식으로 접근? 시간 복잡도 O(m * n * 4^L) 컴퓨터 터지는데요?

근데 이 책에서는 BackTracking 방식의 답만 써있다.

def exist(board: list[list[str]], word: str) -> bool:
    direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    def search_direction(x: int, y: int, sub_word: str):
        if x < 0 or y >= len(board) or (y < 0 or y >= len(board[0])):
            return False

        if board[x][y] != sub_word[0]:
            return False

        if len(sub_word) == 1:
            return True

        board[x][y] = '.'

        for i, j in direction:
            if search_direction(x + i, y + j, sub_word[1:]):
                return True

        board[x][y] = sub_word[0]
        return False

    res = False

    for x in range(len(board)):
        for y in range(len(board[0])):
            if board[x][y] == word[0] and search_direction(x, y, word):
                res = True
                break

    return res