Algorithms과 자료구조/이분탐색, 분할정복, 스택, 큐, 우선순위큐7 프로그래머스_42587 프린터_파이썬풀이(스택,큐) 문제 : 프린터의 중요도가 적힌 리스트가 주어지고 원하는 프린트 하고자 하는 파일의 인덱스가 주어졌을 때 몇 번째로 프린터 되는지 출력하는 문제. 나의 풀이 : from collections import deque def solution(priorities, location): answer = 0 priorities = deque(priorities) #popleft를 쓰기위해 deque로 형변환 while True: maxpr = max(priorities) a=priorities.popleft() if a==maxpr: #왼쪽부터 순서대로 뽑은 값이 max라면? if location == 0: answer+=1 break else : answer+=1 location-=1 else : location.. 2021. 12. 15. 파이썬 백준 1933스카이라인_bisect 빌딩의 (왼쪽,높이) (오른쪽,높이) 정보를 집합으로 받아 정리해준다. 왼쪽의 높이에 -값을 넣어 주어 나중에 주어진 값이 왼쪽인지 오른쪽 인지 구분이 쉽도록 해준다. 왼쪽을 기준으로 집합을 오름차순 정렬한다. top 의 초기값은 0을 넣어주고 before 에 항상 이전 탑의 최대값이 저장되도록 해준다. 저장된 빌딩 집합을 for문으로 돌려주어 왼쪽값이 들어왔을때 top에 높이를 저장해준다. 저장된 탑의 높이는 insort로 넣어 자동으로 오름차순 정렬되어 top[-1]은 항상 최대값을 가진다. 만약 top[-1] 이 before(이전top[-1])과 같지 않다면 높이의 변경이 생긴것이므로 ans리스트에 append 해준다. 왼쪽으로 들어오고 이전 top보다 작은 높이가 들어왔다면 insort 하며 자동.. 2021. 11. 18. 이분탐색 (이진탐색)_백준 사냥꾼 이진 검색 : 오름 차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘. n개의 원소가 오름차순으로 정렬된 배열 A 에서 이진 검색을 하는 과정의 경우 검색 범위의 맨앞 맨 끝 중앙의 인덱스를 각각 pl, pr, pc 라고 하면 검색을 시작할 때 pl = 0 pr = n-1 pc = (pl+pr)//2 로 초기화 한다. 이때 내가 찾아야 할 값 key값(위의 그래픽에서 37)보다 pc가 작다면 배열이 오름차순 되어있어 pc이하의 값은 다시 볼 필요가 없으므로 pl = pc+1 값으로 바꿔준다. 이렇게 내가 찾고자 하는 key값과 pc값을 비교하며 같으면 검색에 성공으로 끝낸다. 이진 검색의 종료 조건 A [pc]와 key가 일치하는 경우 검색 범위가 더 이상 없는 경우 (pl.. 2021. 11. 17. 분할정복_백준 2630 색종이_파이썬 나눌 수 없을 때까지 나누어 각각 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 알고리즘 설계요령 Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다. Conquer : 나누어진 문제가 여전히 분할이 가능하면. 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다. Combine : Conquer 한 문제들을 통합하여 원래 문제의 답을 얻는다 문제를 제대로 나누면 Conquer하는 것은 쉽기 때문에 Divide를 제대로 하는 것이 가장 중요하다. 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복 알고리즘의 효율성을 깎아내릴 수 있다. 벡준 색종이 문제 import sys input = sys.stdin.readline def list_sum(a:list).. 2021. 11. 17. 우선순위 큐(힙) 백준 13334 철로 파이썬 라인 스위핑 문제 : 정렬된 어떤 자료에서 시간 복잡도를 줄일 수 있도록 선을 한 번만 훑으면서 최종 결과를 찾는 방식으로 되어있으며 우선순위 큐를 자주 사용 최종 코드 import sys import heapq input = sys.stdin.readline def subway(ho,d): i=0 while i d : i+=1 else : ho[i].sort() #아닐경우 재정렬 home_office.append(ho[i]) i+=1 if len(home_office)>0 : home_office.sort(key=lambda x: x[1]) line = [] #heap count =0 for i in home_office: if len(.. 2021. 11. 17. 모듈러 연산 백준 곱셈문제를 풀며 모듈러 연산을 공부하였다. 모듈러 연산이란 나머지를 구하는 연산자로 위의 분배법칙이 성립한다. 곱셈에 대한 분배법칙의 증명은 다음과 같다. 모듈러 연산을 응용한 백준 곱셈 문제 풀이 import sys input = sys.stdin.readline A, B, C = map(int, input().split()) r = A % C def Rest(r,B): if B == 1: return r else: tmp = Rest(r,B//2) if not B%2: return tmp*tmp%C else: return tmp*tmp*r % C print(Rest(r,B)) 2021. 11. 15. 이전 1 2 다음
