Comments (3)
네, 좋은 알고리즘이네요.
입력값에 관계 없이 항상 고른 성능을 낸다는 점에서 매우 훌륭한 알고리즘 같습니다. 당연한 얘기지만 책 보다 더 좋은 알고리즘도 얼마든지 있을 수 있습니다. 좋은 알고리즘이 있으면 많이 소개해주세요.
한 가지 아쉬운 점은 일반적인 경우에는 기존 책에 있는 알고리즘 보다 성능이 더 떨어지는거 같습니다. 최악의 경우가 항상 있는건 아니기 때문에 전체적인 성능이 떨어진다면 좋은 알고리즘이라 할 수 없겠죠. 실제로 리트코드에도 제출해보면 기존 보다 2배 정도 더 늦게 실행됩니다. 이 부분이 개선된다면 훨씬 더 좋은 알고리즘이 될 수 있을거 같네요.
from python-algorithm-interview.
네, 맞습니다.
그런 경우가 빅오 챕터에서 얘기하는 최악의 경우입니다.
애초에 데이터가 정렬되어 있다는 정보를 사전에 알 수 있다면 어떤식으로든 최적화가 가능하겠지만 데이터가 어떤 상태인지 전혀 모르는 상황에서는 어떠한 알고리즘도 최악의 경우를 피하기 어렵습니다. 비슷한 예로 퀵소트가 있는데, 대부분의 경우에는 가장 빠른 속도를 보이지만 이미 정렬된 데이터가 입력값으로 주어지면 매 번 불필요한 파티셔닝 작업을 하게되고 버블소트와 다를 바 없는 성능이 나옵니다. 하지만 항상 느린 버블소트와 달리 퀵소트는 대부분의 데이터에서는 훨씬 더 빠른 속도를 보여주기 때문에 퀵소트를 좀 더 최적화된 알고리즘이라 얘기할 수 있는거죠.
정말로 최악의 경우를 방지하고 싶다면 맨 처음에 입력값이 역순인지 확인하고, 이 경우 다른 알고리즘을 적용하도록 분기할 수 있겠습니다. 책에서도 소개한 바 있는 팀소트 또한 입력값이 애초에 정렬된 상태인지 확인하는 로직이 포함되어 있고, 이 경우 이후 정렬 과정을 생략하기 때문에 O(n)에 정렬이 가능합니다.
from python-algorithm-interview.
답변감사합니다,
데이터가 어떤 상태인지 전혀 모르는 상황에서는 최악의 경우를 피하기 어려운게 맞지만 이번 문제는 특별히 어떤 경우에도 linear time 에 답을 낼 수 있는 알고리즘이 있는 것 같아서요~
아래는 코드인데, 큐가 항상 maximum 을 O(1)에 내놓을 수 있도록 준비시키는 알고리즘입니다. 큐는 왼쪽에 있는 숫자일수록 크기가 크도록 유지하며, 새로운 숫자가 큐에 들어올 때 오른쪽에서부터 기존의 숫자들을 비교해 새로운 숫자보다 작으면 큐에서 뺴는 방식으로 동작합니다. for 문 안에 while 문이 들어가긴 하지만 모든 while 문이 실행되는 시간은 결국 입력리스트 길이에 비례하기 때문에 O(n) 이 유지됩니다.
from typing import List
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
# [3 -1 -3] 5 -> 앞에 있는 숫자일수록 크기라도 해야 하는데, 작으면 밀려버림 -> [5]
# [5] 3 -> [5,3]
# [5,3] 6 -> [6]
# [1,3,-1] -> [3,-1]
# [3,-1] -3 -> [3, -1, -3]
# [3, -1 -3] 5 -> [5]
Q = deque()
answer = []
def control(i):
if Q and Q[0] == i-k :
Q.popleft()
while Q and nums[Q[-1]] < nums[i]:
Q.pop()
Q.append(i)
for i in range(k):
control(i)
answer.append(nums[Q[0]])
for i in range(k, len(nums)):
control(i)
answer.append(nums[Q[0]])
return answer
from python-algorithm-interview.
Related Issues (20)
- p257 스택을 이용한 큐 구현 HOT 1
- p.161 전체 코드 질문입니다. HOT 1
- p.233 페이지 18번 홀짝 연결 리스트 문제 관련 문의 입니다. HOT 1
- 67번 문제 질문입니다(leetcode 349) HOT 2
- 13번 팰린드롬 연결리스트 문제 runtime HOT 1
- p450 힙 구현에서 _percolate_up 함수 분기 HOT 1
- p. 578 문법 질문 드립니다 HOT 1
- p.696 5번줄 오타 HOT 1
- p. 581: `77. 가장 긴 반복 문자 대체` - 좀 더 가독성이 높은 코드 질문 HOT 1
- 26번 원형 데크 디자인 문제 깃허브 코드 오타
- 57번 문제 팰린드롬 페어 HOT 1
- 60번 1번 풀이 질문드립니다! HOT 1
- p. 307: `31. 상위 K 빈도 요소` - 최적화 & 파이써닉한 코드 질문 HOT 2
- P640 오타 HOT 1
- P391페이지 6번째줄 질문드립니다 HOT 1
- 31번 상위 K 빈도 요소 HOT 1
- 60번 삽입정렬 리스트 1번 풀이 질문 HOT 1
- [49]Group Anagrams 풀이 질문 HOT 1
- 이진 힙 vs 이진 탐색 트리 HOT 1
- 612p, 615p 83. 과반수 엘리먼트 구하는 문제. HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from python-algorithm-interview.