[알고리즘] 그리디 알고리즘 알기

그리디 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미 그리디 해법은 정당성 분석이 중요하다. - 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 매 상황에서 가장 큰 값만 고르는 것이다. 일반적인 상황에서는 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. (그 순간만 판단하기 때문에) 그리디 알고리즘을 설명하기 위해 자주 등장하는 예시 문제라고 한다. 가장 큰 단위 화폐부터 돈을 거슬러 주면 된다. 1260원을 거슬러 줘야한다고 할 때 500원부터 거슬러주면, 500 x 2 = 1000, 100원 => 100 x 2 = 200, 50원 => 50 x 1 = 50, 10원 => 10 x 1 = 10 이런 식으로 그럼 이렇게 큰 화폐 단위부터 ..

→2021.01.08

[파이썬] 우선순위 큐(Priority Queue), 힙(Heap)

우선순위 큐(Priority Queue) 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조 데이터를 우선순위에 따라 처리하고 싶을 때 사용 어떤 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우에 사용을 한다. 자료구조 추출되는 데이터 스택 가장 나중에 삽입된 데이터 (불공평하다) 큐 가장 먼저 삽입된 데이터 (공평하다) 우선순위 큐 가장 우선순위가 높은 데이터 구현하는 방법에는 두 가지 방법이 있다. 1. 리스트를 이용 2. 힙을 이용 우선순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙 O(logN) O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. 이것을 힙 정렬이라고 부른다. 이 경우 시간 복잡도는 O(..

→2021.01.07

[이코테] 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기

동빈좌의 유튜브를 보며, 파이썬 알고리즘 공부하기 www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC 알고리즘 성능 평가 복잡도가 낮을수록 더 좋은 알고리즘이다! 그냥 소스 코드가 복잡해보인다. 와는 다른 얘기이다. 성능적인 측면에서의 복잡도를 이야기 하는 것이다. 시간복잡도 특정한 크기의 입력에 대해서 수행 시간 분석 공간복잡도 특정한 크기의 입력에 대해서 메모리 사용량 분석 빅오 표기법 가장 빠르게 증가하는 항만을 고려하는 표기법. (알고리즘 푸는 입장에서는 위와 같이 이해해도 상관없다고 한다.) 리스트 객체를 array에 할당해주고, for문에서 모든 데이터를 하나씩 다 확인을 하니까, 수행시간은 데이터의 개수인 N..

→2021.01.06