본문 바로가기

🧩 Algorithm17

[백준] 11279번: 최대 힙 Hint 1. 힙 자료구조 이용하기 (힙이란?) 2. 힙에서 heappop()을 하면 가장 작은 값이 반환 됨. 그렇다면 가장 큰 값을 반환하려면..? 3. 힙에 넣은 숫자들을 마이너스 해서 넣는다면 heappop() 했을 때 어떤 숫자가 먼저 뽑힐까? 백준 11279번: 최대 힙 import heapq import sys n = int(sys.stdin.readline()) heap = [] # 힙 만들기(리스트랑 만드는 법은 똑같음) for i in range(n): num = int(sys.stdin.readline()) if num == 0: # input 숫자가 0 이면 현재 힙에 들어있는 최대대값 출력하기 print((heapq.heappop(heap))*(-1) if heap != [] el.. 2023. 2. 26.

[백준] 2075번: N번째 큰 수 Hint 1. 우선순위 큐 - 힙(heap) 자료구조 이용하기 (그게 뭐지?) 2. 힙에서 heappop()을 이용하면 작은 수 부터 출력된다! 백준 2075번: N번째 큰 수 (풀어보기) import heapq N = int(input()) heap = []# 새로운 힙 만들기 for i in range(N): for num in map(int, input().split()): heapq.heappush(heap, num)# 힙에 숫자 삽입하기 if len(heap) > N:# 힙의 원소의 개수가 N개를 넘어가면 heapq.heappop(heap)# 힙에서 가장 작은 수 제거하기 print(heapq.heappop(heap))# N번째로 큰 수 출력하기 2023. 2. 24.

[백준] 11286번: 절댓값 힙 Hint 1. 힙 자료구조에 튜플을 넣을 수 있다 2. 힙 안의 튜플은 들어있는 순서대로 작은거부터 큰거까지 정렬된다 3. 힙 응용방법 알아보기 (여기) 백준 11286번 (풀어보기) import heapq import sys heap = [] for i in range(int(sys.stdin.readline())): n = int(sys.stdin.readline()) if n == 0: if heap == []: print(0) else: print(heapq.heappop(heap)[1])# 가장 작은 절댓값을 가진 숫자 n 출력하기 else: heapq.heappush(heap, (abs(n), n))# 튜플 형태로 n의 절댓값과 n을 둘 다 넣어줌 2023. 2. 21.

[백준] 1929번: 소수 구하기 Hint 1. 1부터 n까지의 숫자가 소수인지 아닌지 확인을 하고, 소수이면 그 숫자의 배수들은 소수일까요? 2. 소수의 배수들은 소수가 아닌게 확실하기 때문에 미리 제거해주면 나중에 소수인지 확인할 필요가 없다! 3. 에라토스테네스의 체 이용하기 (그게 뭐지?) 백준 1929번: 소수 구하기 (풀어보기) import sys M, N = map(int, sys.stdin.readline().split()) # N까지의 숫자의 소수인지 아닌지에 대한 여부를 판단하는 배열 만들기 # 이것이 에레스토스테네스의 체! is_prime = [True] * (N+1) is_prime[0], is_prime[1] = False, False # 2부터 N까지의 숫자의 배수는 모두 소수가 아니라고 False로 바꿔주기 f.. 2023. 2. 18.

[백준] 1463번: 1로 만들기 Hint 1. n에서 2나 3을 나누거나 1을 뺄 생각하지 말고 1부터 고려하는 코드로 짜야함 2. 1부터 n까지의 숫자를 각각 만들기 위해선 몇번의 연산 횟수가 필요한지 생각해봐야 함 3. Memoization 기법 활용 백준 1463번: 1로 만들기 (풀어보기) n = int(input()) ans = [0] * (n+1) # ans[i] = i가 1이 되기 위한 연산 횟수 for i in range(2, n+1): ans[i] = ans[i-1] + 1 # 디폴트로는 그 전 숫자에서 +1 한거니까 횟수도 그 전 숫자의 횟수에 +1 한것임 if i % 3 == 0: ans[i] = min(ans[i], ans[i // 3] + 1) # 디폴트와 x3 하기 전의 숫자의 횟수에서 +1 한거 중에 더 작은.. 2023. 2. 17.

에라토스테네스의 체 Goal 1. 소수 정의하기 2. 소수 찾는 알고리즘 - "에라토스테네스의 체" 이해하기 소수란? 소수란 숫자 중 나 자신과 1로만 나눠지는 수다. 즉, 그 2개의 수 이외의 다른 수로 나눠진다면 소수가 아닌 "합성수" 라고 말할 수 있다! 예시) 소수 : 2, 3, 5, 7, 11, 13, 17, 19, ... 그 외 : 4 (2로 나눠지니까), 6 (2와 3으로 나눠지니까), 8 (2로 나눠지니까), 9 (3으로 나눠지니까), ... "에라토스테네스의 체"는 언제 필요한가? N이라는 숫자가 소수인지 아닌지 판단하기 위해서는 2부터 N/2 까지의 숫자로 나눠봐야 알 수 있다 하지만 2부터 100까지의 숫자 중에서 소수를 출력하라고 한다면 이중 for문을 돌려야하고 시간 복잡도는 O(n^2)으로 느리다 .. 2023. 2. 13.

힙(Heap) 응용방법 Goal 1. 힙의 응용 방법 알아보기 함수 heappop() 이용하기 중요한 점은 heapq.heappop(heap)은 항상 heap에서 가장 작은 값을 반환한다는 것이다. 작은 수 ➡️ 큰 수 아래와 같이 1에서 5까지의 숫자가 있을 때 heap을 이용하면 가장 작은 수부터 순서대로 뽑는 것은 간단하다. import heapq arr = [1, 2, 3, 4, 5] heap = [] for num in arr: heapq.heappush(heap, num) for i in range(len(heap)): print(heapq.heappop(heap))# 출력: 1 2 3 4 5 큰 수 ➡️ 작은 수 거꾸로 힙을 이용해서 큰 수부터 순서대로 뽑는 것도 가능하다. import heapq arr = [1,.. 2023. 2. 10.

우선순위 큐 Goal 1. 우선순위 큐 이해하기 2. 힙(Heap) 자료구조 이해하기 우선순위 큐란? 높은 우선순위를 가진 원소가 낮은 우선순위를 가진 원소보다 먼저 처리된다 파이썬에선 힙(heap)이라는 자료 구조로 구현이 가능하다 힙(heap)이란? 완전 이진 트리(Complete Binary Tree)로 루트 노드에 있는 값은 트리에서 최대값 (Max Heap) 혹은 최소값 (Min Heap)이다 부모 노드의 값이 자식 노드의 값보다 항상 크거나 (Max Heap) 항상 작다 (Min Heap) 2023. 2. 9.

이전 1 2 다음

티스토리툴바