우선순위 큐는 데이터를 추가한 순서대로 제거하는 선입선출(FIFO) 특성을 가진 일반적인 큐의 자료구조와 달리, 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조입니다. 이 말은 내부적으로 데이터를 정렬된 상태로 보관하는 메커니즘이 있다는 뜻이고, 좀 더 구체적으로 얘기하면 heapq 모듈을 통해 구현되어 있습니다. 내부적으로 heap 모듈을 사용하는 PriorityQueue 클래스의 put(), get() 함수는 O(log n)의 시간 복잡도를 가집니다. 코드예시 from queue import PriorityQueue que = PriorityQueue() # que = PriorityQueue(maxsize=8) 디폴트사이즈는 무한대이..
전체 글
정의 및 장단점 큐는 선입선출,FIFO(First In First Out)의 방식이다. 가정 먼저 들어온 데이터가 가장 먼저 나간다. 제일 먼저 들어온 데이터를 HEAD, 맨 뒤의 데이터를 TAIL이라고 한다. 구현방법 파이썬에서는 리스트방식 또는 라이브러리를 이용한 방식으로 나뉜다. 리스트방식: pop(0) 또는 insert(0,x)등의 방법은 복잡도가 O(n)이므로 아래의 다른 방법보다 불리하다. 리스트의 마지막 원소의 삭제는 O(1)이지만, 첫번째 원소를 삭제하면 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)입니다. 자료구조 뒤에서 추가/삭제는 덱과 리스트는 속도 차이가 없지만, 첫번째 원소를 추가 삭제한다면 극명한 속도 차이가 발생합니다. 데이터가 커지고 데이터의 양끝에서 ..
정의 및 장단점 그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 현재 상황에서 지금 당장 좋은 것을 고르는 방법을 의미한다. 그리디 문제는 매우 다양한 문제가 있으며 미리 유형을 외우고 있지 않아도 알고리즘 문제를 풀 가능성이 높다. 그렇지만 많은 문제를 풀어보는 연습이 필요하다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 구현방법 보통 while문이나 조건문을 통해 구현이 된다. 문제 예시 그리디 문제의 대표적인 예시로 거스름돈 문제가 있다. 예를 들어 3800원을 거슬러줄 때 최소 지폐,동전수를 구하여라 등의 문제이다. n =1260 count = 0 coin_types = [..
2018 기업 알고리즘 대회 문제이다. 이것이 코딩테스트다 99페이지 문제이다. 나의 코드 N,K = map(int,input().split()) count=0 while N>1: if N>=K: N=N/K count+=1 else: N-=1 count+=1 print(count)
2019 국가 교육기관 코딩테스트 기출문제이다. 이것이코딩테스트다 책 96페이지 문제이다. 나의 코드 N,M = map(int,input().split()) mylist=[] for i in range(N): temp=list(map(int,input().split())) temp.sort() mylist.append(temp[0]) mylist.sort() print(mylist[-1])
2019 국가 교육기관 코딩테스트 기출문제이다. 이것이코딩테스트다 책의 92페이지 문제이다. 나의코드 N,M,K = map(int,input().split()) mylist = list(map(int,input().split())) mylist.sort() first= M//K second = M%K result = mylist[-1]*first*K + mylist[-2]*second print(result) 오늘부터 알고리즘 문제풀이 스터디를 시작하였다. (참여자: 김윤재, 전준, 심승우) 워낙 기초문제라 달 코멘트가 없다.
https://happy-coding-day.tistory.com/entry/Template-Pattern템플릿-패턴-VS-Strategy-Pattern전략-패턴 Template Pattern(템플릿 패턴) VS Strategy Pattern(전략 패턴) Photo by Mike Meyers on Unsplash 들어가기 대부분의 디자인 패턴 책에서는 이 두가지를 비교해서 설명합니다. 왜 일까요? 이 두가지 패턴은 데이터를 은닉화 시켜 구현될 수 있도록 도와주는 패턴입니 happy-coding-day.tistory.com https://lion-king.tistory.com/entry/Spring-Design-pattern-Template-Strategy (Spring / Design pattern ) ..
타이머란 주기적 시간 처리에 사용하는 디지털 카운터 회로 모듈 펄스폭 계측, 주기적인 interrupt 발생 등에 사용 주파수가 높기 때문에 우선 prescaler를 사용하여 주파수를 낮춘 후 낮아진 주파수로 8,16비트 등의 카운터 회로를 사용하여 주기를 얻는다. STM32 타이머 종류 SysTick Timer Watchdog Timer Advanced-control Timer (TIM1, TIM8) General-purpose Timer (TIM2 ~ TIM5) Basic Timer (TIM6, TIM7) Systick Timer Real-time operating system 전용이지만 standard down counter로 사용 할 수도 있음 24bit down counter Autoreload..