당신과 이야기하세요 시리즈 #1

**커버 이미지는 포스팅 당시의 기분을 반영합니다

일상적인 일이든 자유 시간 활동이든 매일 직면했던 문제와 잠재적인 해결책을 한동안 적어 보는 습관이 있다는 생각부터 시작하고 싶습니다.

이번 포스팅을 시작으로 "Talk with You" 시리즈를 소개하기로 결정했습니다. 여기(적어도 지금은 최대 며칠에 한 번) 게시하여 대중에게 알려드리겠습니다.

이제 잘 구성된 노트 대신 여기에서 가끔 정보를 개편하고 DevCommunity에서 저장, 오름차순 탐색 및 기타 모든 작업을 처리할 것입니다. 또 다른 한편으로는 믿습니다. 내가 여기에 글을 쓰는 것은 나뿐만 아니라 청중을 찾을 수도 있습니다. 단단히 고정하고 시작해 보세요.

발생 횟수

DS로 작업할 때 효율적인 방식으로 쿼리하려면 값과 후속 단어의 발생 횟수를 세어야 하는 경우가 많습니다. 가급적이면 시간 O(1)입니다.

분명히 HashTable을 만든 다음 DS를 순회하여 HashTable을 채우는 것을 생각할 수도 있습니다. 이는 사실이며 다음과 같이 보일 수 있습니다.

iterable = [...]
hashtable = {}
for value in iterable:
    hashtable[value] = hashtable.get(value, 0) + 1

오늘 저는 HashTable을 사용하지 않고 숫자 목록에 완벽하게 작동하는 대체 접근 방식에 직면했습니다(때로는 필요할 수도 있음).

뒤에 있는 아이디어는 먼저 목록에서 최대값을 가져오고 최대값 길이의 새 목록을 생성하여 인덱스 매핑으로 사용하는 것입니다.

list_ = [1, 1, 2, 3]
max_ = max(list_)
indices = [0] * max_   # [0, 0, 0, 0]

이제 원본 목록을 탐색하고 인덱스 목록에 있는 각 값의 발생을 매핑해 보겠습니다.

1. iteration
[1, 1, 2, 3] # list
 |

[0, 1, 0, 0] # indices

2. iteration
[1, 1, 2, 3] # list
    |

[0, 2, 0, 0] # indices

3. iteration
[1, 1, 2, 3] # list
       |

[0, 2, 1, 0] # indices

4. iteration
[1, 1, 2, 3] # list
          |

[0, 2, 1, 1] # indices

방금 무슨 일이 일어났나요? 음, 기본적으로 우리는 원본 목록에서 값을 가져와 이를 인덱스 목록의 인덱스로 사용했습니다(그리고 인덱스에서 값을 증가시켰습니다).

이제 매핑 목록을 사용하여 결과를 표현하고 싶다면 인덱스 0에는 값 0이 있고 인덱스 1에는 값 2가 있으므로 0이 0개 있다고 말할 수 있습니다. 즉, 1이 2개 있다는 뜻입니다. -s, 인덱스 2의 값은 1입니다. 즉, two-s가 1개 있다는 의미입니다.

매트릭스의 거울 요소

BSc와 석사 학위를 2개 취득했음에도 불구하고 새로운 수학 요령을 발견하면 "아, 그거 참 간단하고 효과가 있구나"라는 느낌이 여전히 듭니다.

다시 주제로 돌아가서, N*N 행렬이 있고 모든 요소의 최대 합(행 단위)을 얻기 위해 행과 열을 반대로 해야 한다고 가정해 보겠습니다.

matrix 4*4

1 2 3 9
0 9 8 2
5 1 7 4
8 2 6 7  

처음 봤을 때부터 어디서부터 시작해야 할지 모를 수도 있습니다. 하지만 여기에 미러 요소를 사용한 트릭이 있습니다.

matrix 4*4

A B B A
C D D C
C D D C 
A B B A

여기서 핵심은 행렬의 A가 다른 A로만 교체될 수 있다는 것입니다. 우리가 왼쪽 상단 모서리 A(1)에 있다고 가정하고 더 큰 또 다른 A(미러링된 A만)가 있는지 알고 싶습니다. 그리고 실제로 오른쪽 상단 모서리(9)에 그러한 항목이 있습니다.

논리에 따라 원래 문제(행과 열을 뒤집는 최대 합계)를 떠올려 보면 실제로는 역연산을 수행할 필요가 없으며 대신 미러링된 연산 중에서 최대값을 조회하기만 하면 된다는 결론을 내릴 수 있습니다. 그게 다입니다.

스택. 시간과 공간의 복잡성 사이의 균형.

(1) 팝(2) 푸시(3) get_min의 세 가지 기능만 포함하는 스택 래퍼를 구현하는 작업이 있다고 가정합니다. (1) 팝 및 (2) 푸시에 스택 인터페이스를 사용할 수 있지만 여전히 (3) get_min을 구현해야 합니다. Annnd get_min()은 O(1) 시간 동안 작동해야 합니다.

글쎄, 처음 문제를 다룰 때 "Time 성능을 최적화하면 Space 성능이 더 나빠질 수 있고 그 반대의 경우도 있다"는 절충안을 완전히 잊어버렸습니다. 이것이 중요한 이유는 HashTables로 이어지는 최적화된 DS를 생각하기 시작했지만 O(1)(상각)에서도 작동할 수 있는 순진한 목록을 정말 놓쳤기 때문입니다.

그래서 래퍼 클래스의 각 상태를 저장할 수 있는 HashTable을 만드는 시점에 도달했습니다. "간단한 것이 더 나은 옵션"(때때로)이므로 여기에서 중지하겠습니다. 스택의 모든 상태에 대한 최소값을 저장하는 추가 목록을 사용한 구현을 살펴보겠습니다.

class Wrapper:
   def __init__(self, stack):
      self.stack = stack
      self.min = []

   # Time O(1)
   def pop(self):
      self.stack.pop()
      self.min.pop()

   # Time O(1)
   def push(self, value):
      self.stack.push(value=value)
      min_ = self.min[-1]
      if value < min_:
          min_ = value
      self.min.append(min_)

   # Time O(1)
   def get_min(self):
      return self.min[-1]

간단합니다.

마무리

• 계속 코딩하고 개발하세요
• 절충점을 기억하고 지나치게 복잡하게 만들지 마십시오(요청을 받지 않은 경우)

위 내용은 당신과 이야기하세요 시리즈 #1의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!