Posts python algorithm 2
Post
Cancel

python algorithm 2

Posted Feb 22 2021-02-22T07:00:00+09:00 by CYM

Linear Data Structure



05. Array



032. 두 수의 합

덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴.

1
2
3
4
5
6
7
8
9
10
11

nums = [2, 7, 11, 15]
target = 9 # [0, 1]

def two_sum(nums, target):
  nums_map = {}
  for i, num in enumerate(nums):
    if target - num in nums_map:
      return [nums_map[target - num], i]
    nums_map[num] = i

print(two_sum(nums, target))


033. 빗물 트래핑

높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산.

  • 투 포인터를 최대로 이동.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

def trap(height):
  if not height:
    return 0

  volume = 0
  left, right = 0, len(height) - 1
  left_max, right_max = height[left], height[right]

  while left < right:
    left_max, right_max = max(height[left], left_max), max(height[right], right_max)
    # 더 높은 쪽을 향해 투 포인터 이동
    if left_max <= right_max:
      volume += left_max - height[left]
      left += 1
    else:
      volume += right_max - height[right]
      right -= 1

  return volume

print(trap(height))


034. 세 수의 합

배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력.

  • 투 포인터로 합 계산
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

nums = [-1, 0, 1, 2, -1, -4]

def three_sum(nums):
  results = []
  nums.sort()

  for i in range(len(nums) - 2):
    # 중복된 값 건너뛰기
    if i > 0 and nums[i] == nums[i - 1]:
      continue

    # 간격을 좁혀가며 합 sum 계산
    left, right = i + 1, len(nums) - 1
    while left < right:
      sum = nums[i] + nums[left] + nums[right]
      if sum < 0:
        left += 1
      elif sum > 0:
        right -= 1
      else:
        # sum = 0인 경우이므로 정다 및 스킵 처리
        results.append((nums[i], nums[left], nums[right]))
        
        while left < right and nums[left] == nums[left + 1]:
          left += 1
        while left < right and nums[right] == nums[right - 1]:
          right -= 1
        left += 1
        right -= 1
  
  return results

print(three_sum(nums))
---------------------
[(-1, -1, 2), (-1, 0, 1)]
  • 투 포인터: 시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제 풀이 전략.


035. 배열 파티션 1

n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력.

  • 파이썬 다운 방식
1
2
3
4
5
6
7
8

nums = [1, 4, 3, 2]

def array_pair_sum(nums):
  return sum(sorted(nums)[::2])

print(array_pair_sum(nums))
---------------------------
4


036. 자신을 제외한 배열의 곱

배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력. 나눗셈을 하지 않고 O(n)에 풀이.

  • 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

nums = [1, 2, 3, 4]

def produce_except_self(nums):
  out = []
  p = 1
  # 왼쪽 곱셈
  for i in range(0, len(nums)):
    out.append(p)
    p = p * nums[i]
  p = 1
  # 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
  for i in range(len(nums) - 1, 0 - 1, -1):
    out[i] = out[i] * p
    p = p * nums[i]
  return out

print(produce_except_self(nums))
-------------------------------
[24, 12, 8, 6]


037. 주식을 사고팔기 가장 좋은 시점

한 번의 거래로 낼 수 있는 최대 이익 산출.

  • 저점과 현재 값과의 차이 계산
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import sys

prices = [7, 1, 5, 3, 6, 4]

def max_profit(prices):
  profit = 0
  min_price = sys.maxsize

  # 최솟값과 최댓값을 계속 갱신
  for price in prices:
    min_price = min(min_price, price)
    profit = max(profit, price - min_price)

  return profit

print(max_profit(prices))
-------------------------
5





06. Linked List



038. 팰린드롬 연결 리스트

연결 리스트가 팰린드롬 구조인지 판별.

  • 런너를 이용한 우아판 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class ListNode():
    def __init__(self, x):
        self.val  = x
        self.next = None

def is_palindrome(head):
    rev = None
    slow = fast = head

    while fast and fast.next:
        fast = fast.next.next
        rev, rev.next, slow = slow, rev, slow.next
    if fast:
        slow = slow.next

    # 팰린드롬 여부 확인
    while rev and rev.val == slow.val:
        slow, rev = slow.next, rev.next

    return not rev

l = ListNode(1)
l.next = ListNode(2)
l.next.next = ListNode(2)
l.next.next.next = ListNode(1)

print(is_palindrome(l))
  • 런너 기법
    • 연결 리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법.
    • 한 포인터가 다른 포인터보가 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용.
  • 다중 할당(Multiple Assignment): 2개 이상의 값을 2개 이상의 변수에 동시에 할당.

039. 두 정렬 리스트의 병합.

정렬되어 있는 두 연결 리스트를 합쳐라.

  • 재귀 구조로 연결
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class ListNode:
  def __init__(self, x):
    self.val = x
    self.next = None

def mergeTwoLists(l1, l2):
    if (not l1) or (l2 and l1.val > l2.val):
      l1, l2 = l2, l1

    if l1:
      l1.next = mergeTwoLists(l1.next, l2)

    return l1


l1 = ListNode(1)
l1.next= ListNode(2)
l1.next.next = ListNode(4)

l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)

answer = mergeTwoLists(l1, l2)
while answer is not None:
    print(f'{answer.val} ->', end=" ")
    answer = answer.next


040. 역순 연결 리스트

연결 리스트를 뒤집어라.

  • 반복 구조로 뒤집기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

def reverse_list(head):
  node, prev = head, None

  while node:
    next, node.next = node.next, prev
    prev, node = node, next

  return prev

head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
answer = reverse_list(head)
while answer is not None:
    print(f'{answer.val} ->', end=" ")
    answer = answer.next


041. 두 수의 덧셈

역순으로 저장된 연결 리스트의 숫자를 더하라.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class ListNode:
  def __init__(self, x):
    self.val = x
    self.next = None

def add_two_numbers(l1, l2):
  root = head = ListNode(0)

  carry = 0
  while l1 or l2 or carry:
    sum = 0
    # 두 입력값의 합 계산
    if l1:
      sum += l1.val
      l1 = l1.next
    if l2:
      sum += l2.val
      l2 = l2.next
    
    # 몫(자리올림수)과 나머지(값) 계산
    carry, val = divmod(sum + carry, 10)
    head.next = ListNode(val)
    head = head.next

  return root.next

  • 숫자형 리스트를 단일 값으로 병합하기.

    1
2
3

    >>> a = [1, 2, 3, 4, 5]
>>> functools.reduce(lambda x, y: 10 * x + y, a, 0)
12345


042. 페어의 노드 스왑

연결 리스트를 입력받아 페어pair 단위로 스왑.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 입력: 1->2->3->4
# 출력: 2->1->4->3

class ListNode:
  def __init__(self, x):
    self.val = x
    self.next = None

def swap_pairs(head):
  if head and head.next:
    p = head.next
    # 스왑된 값 리턴 받음
    head.next = swap_pairs(p.next)
    p.next = head
    return p
  return head


043. 홀짝 연결 리스트

연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성. 공간 복잡도 O(1), 시간 복잡도 O(n)에 풀이.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 입력: 2->1->3->5->6->4->7->NULL
# 출력: 2->3->6->7->1->5->4->NULL

class ListNode:
  def __init__(self, x):
    self.val = x
    self.next = None

def odd_even_list(head):
  # 예외 처리
  if head is None:
    return None

  odd = head
  even = head.next
  even_head = head.next

  # 반복하면서 홀짝 노드 처리
  while even and even.next:
    odd.next, even.next = odd.next.next, even.next.next
    odd, even = odd.next, even.next

  # 홀수 노드의 마지막을 짝수 헤드로 연결
  odd.next = even_head
  return head


044. 역순 연결 리스트 2

인덱스 m에서 n까지를 역순으로 만들어라. 인덱스 m은 1붙터 시작.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 입력: 1->2->3->4->5->NULL, m = 2, n = 4
# 출력: 1->4->3->2->5->NULL

class ListNode:
  def __init__(self, x):
    self.val = x
    self.next = None

def reverse_between(head, m, n):
  # 예외 처리
  if not head or m == n:
    return head

  root = start = ListNode(None)
  root.next = head
  # start, end 지정
  for _ in range(m - 1):
    start = start.next
  end = start.next

  for _ in range(n - m):
    tmp, start.next, end.next = start.next, end.next, end.next.next
    start.next.next = tmp
  return root.next
python
algorithm
This post is licensed under CC BY 4.0 by the author.

Contents

python algorithm 1

-