✨우선순위 큐(Priority Queue) 평범한 큐나 스택과 비슷한 축약 자료형이다. 각 원소들은 우선순위를 갖고 있다. 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 자료구조 힙을 통하여 구현된다 ✨힙(Heap) 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리 부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙' 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 '최소 힙' ✨Python PriorityQueue from queue import PriorityQueue q=PriorityQueue() q.put(5) q.put(3) q.put(4) print(q.get()) #출력: 3 (우선순위,값)튜플 형태 추가 from q..
분류 전체보기
✨ 그리디 알고리즘(Greedy algorithm)최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식 ex)백준 1715번https://www.acmicpc.net/problem/1715 import sysimport heapqsum=0hq=[]for i in range(int(sys.stdin.readline().rstrip())): heapq.heappush(hq,int(sys.stdin.readline().rstrip())) sum=0if(len(hq)==1):print(0)else: while hq: a=heapq.heappop(hq) b=heapq.heap..
✨누적 합(Prefix sum) 주어진 배열에서 각 위치까지의 합을 미리 계산하여 배열에 저장해 놓는 알고리즘 빠른응답속도 추가 메모리 사용 ex) 백준 11659번 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 import sys N,M=map(int,sys.stdin.readline().rstrip().split(" ")) li=list(map(int,sys.stdin.readline().rstrip().split(" "))) li2=[0] sm=0 for i in li: sm+=i li2.append(sm) for i in range(M): a,b=map(int,sys.stdin.readline().rstrip().split(" ")) sys.stdout.w..
✨동적 계획법(dynamic programming) 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 재귀,메모이제이션을 이용한다. ✨메모이제이션(Memoization) ‘중복 계산'을 피하기 위한 기법 이전에 계산한 값을 메모리에 저장한다. ✨탑다운방식 재귀적으로 호출함 큰문제를 작은문제로 나눔 ✨바텀업방식 반복문을 사용함 작은 문제로 큰문제를 해결함 예시) 백준 알고리즘 수업 - 피보나치 수 1 https://www.acmicpc.net/problem/24416 제귀함수로 작성한 피보나치 def fib(n): if(n
✨백트래킹(backtracking) 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법 주요 개념은 해를 얻을 때까지 모든 가능성을 시도 트리를 검사하기 위해 깊이 우선 탐색을 사용 ✨ 예시문제) 백준 N과 M(1) https://www.acmicpc.net/problem/15649 끝나는 조건:리스트의 길이가 M이 되었을때 -> 정답목록에 해당 리스트를 추가, 종료 수열의 조건: 방문했던 숫자에 다시 방문하면안됨 ->방문 리스트 V를 만들어서 체크 전체 코드 import sys def back(n,li): if(n==M): answer.append(li) #종료조건 return for j in range(1,N+1,1): if(V[j]==0): V[j]=1 back(n+1,li+..
✨ 합병정렬(merge sort) 합병 정렬은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. (분할정복:그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법) ✨ 과정(2-way 합병 정렬) 길이가 1이하임을 확인(1이하인경우 정렬완료상태) 분할: 리스트를 절반으로 나눈다. 정복:각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬 결합:두 부분 리스트를 다시 하나의 정렬된 리스트로 합병( 임시배열에 저장 ) 복사:임시 배열에 저장된 결과를 원래 배열에 복사 def merge_sort(arr): #길이 1이하확인 if(arr
✨팩토리얼(factorial) 그 수보다 작거나 같은 모든 양의 정수의 곱 python 코드 import sys n=int(sys.stdin.readline().rstrip()) su=1 for i in range(1,n+1,1): su*=i sys.stdout.write(str(su)) ✨순열(permutation) 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산 n개의 요소에서 k개를 뽑는다. itertools의 permutations코드 from itertools import permutations n=[1,2,3,4] k=2 print("개수:"+str(len(list(permutations(n,k))))) for i in permutations(n,k):print(i, end="") #결과..
✨ 유클리드 호제법(Euclidean algorithm) 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. ✨과정 a,b 두개의 자연수가 있다 (a>b) a/b -> 나머지 r1 a/r1 -> 나머지 r2 3번을 반복 a/r -> 나머지 0 일때 r은 a,b의 최대공약수다. A,B=list(map(int,sys.stdin.readline().rstrip().split(" "))) if (B>A):A,B=B,A num=A r=B while True: r1=num%r if(r1==0): break num=r r=r1 print(r) 🎈참고자료 https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%9..
