전체 글 (97) 썸네일형 리스트형 heapq 모듈 힙(Heap)힙은 우선순위 큐를 위해 만들어진 자료구조로 완전 이진트리의 일종이다. 여러 값 중 최대/최소 값을 빠르게 찾아내도록 만들어진 반정렬 상태이다.최대/최소 값을 찾기 위해서 O(n)의 시간이 걸리지만, 힙을 사용하면 O(logN)만큼 소요된다. 힙 트리는 중복된 값을 허용한다는 특징을 갖고 있다. 들어간 순서와 상관 없이 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리. 만약 두 원소가 같은 우선순위를 가진다면 큐에서 그들의 순서에 의해 처리 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태마지막 레벨을 제외한 모든 노드가 완전히 채워짐최하단 좌측 노드부터 차례로 삽입 - 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리- 최소 힙 :.. [BaekJoon/Python3] 11399번 : ATM [두잇 파이썬 풀이_삽입정렬, 합배열 이용]N = int(input())A = list(map(int, input().split()))S = [0]*N# 삽입정렬for i in range(1,N): insert_point = i insert_value = A[i] for j in range(i-1, -1, -1): if A[j] - 근데 백준에서 제출하면 틀렸다고 함 ?? ...... . . .. 예시 입출력은 그대로 나옴 [정답 풀이]N = int(input())A = list(map(int, input().split())) # 기다리는 사람들 리스트 형태로 입력A.sort() # 오름차순으로 정렬ans = 0for x in range(1,N+1): ans += s.. [BaekJoon/Python3] 백준 2738번 : 행렬 덧셈 [정답 풀이]# 1. 행렬 크기 입력 받기N, M = map(int, input().split())# 2. 행렬 A,B를 저장할 리스트 초기화A,B = [],[]# 3. 행렬 A 입력 받기for i in range(N): a = list(map(int, input().split())) # 한 줄씩 입력 받아 리스트로 변환 A.append(a) # 리스트 A에 추가# 4. 행렬 B 입력 받기for i in range(N): b = list(map(int, input().split())) B.append(b)# 5. 행렬 덧셈 연산 및 출력for i in range(N): # 행 반복 for j in range(M): # 열 반복 result = A[i][j] + B[.. 우선순위 큐 # 힙 함수import sys, heapq# heapq모듈은 최소힙 --> 그러므로 최대힙을 구현하려면 뭘 해줘야함!N = int(input())max_heap = []for i in range(N): x = int(sys.stdin.readline()) * -1 if x == 0: if max_heap: print(heapq.heappop(max_heap)*-1) else: print(0) else: heapq.heappush(max_heap, x) - 최대힙 구현- import 한 줄에 쓸 수 있음- heapq모듈은 최소힙이기 때문에 최대힙을 구현하기 위해서는 부호를 변경하는 방법을 해준다. (주어진 숫자에 .. 그리디 알고리즘 N, K = map(int, input().split())coins = []for _ in range(N): coin = int(input()) coins.append(coin) # coins.append(int(input())) = coin: ans += K // coin # 몫만큼 더하기 K %= coin # 나머지 할 if K 누적 합 n,m = map(int, input().split())numbers = list(map(int, input().split()))sum = [0]tmp = 0# 누적 합 구하기for i in numbers: tmp = tmp + i sum.append(tmp)# 구간 합 구하기for _ in range(m): i,j = map(int, input().split()) print(sum[j]-sum[i-1]) - 완전 탐색 알고리즘으로 풀게 되면 시간 초과 발생할 수 있음. 그래서 누적합 기법을 사용하여 합 배열을 미리 구해 놓으면 시간 복잡도가 O(1)- 원본 리스트를 A, 누적 합 리스트를 S라고 할 때1) 누적 합 구하기 : S[i] = S[i-1] + A[i]2) 구간 합 구하기.. 누적합, 부분합 https://code-angie.tistory.com/22 [알고리즘 / Python] 누적합 (Prefix Sum)배열의 일부 구간에 대한 합을 빠르게 구할 수 있는 알고리즘이다.배열의 값들이 변하지 않는다면 누적된 합 또한 변동이 없다는 점을 적용한다.미리 구해둔 누적합을 통해 배열 중 특정 구간의code-angie.tistory.com 1. 1차원 누적합 그림과 같이 앞에서부터 차례대로 누적된 합계를 prefixSum배열에 저장한다. 첫 번째(0) 값은 arr값과 prefixSum값이 동일하다.현재 위치(i)의 arr 값에 prefixSum 배열에 저장된 직전 위치(i-1)까지의 합을 더하여 현재 위치의 누적합을 구하여 prefixSum에 입력한다.점화식 : prefixSum[i] = prefi.. 동적 계획법 1 알고리즘 수업 - 피보나치 수 1> [fib(n) 함수 시간 초과_재귀 호출 방식으로 사용했기 때문]n = int(input())f1, f2 = 0,0 # 각 함수의 실행 횟수def fib(n): # 문제에 나와있는 의사 코드 그대로 global f1 if n ==1 or n==2: f1 += 1 return 1 else: return fib(n-1) + fib(n-2) f = [0] * (n+1) # DP 테이블 초기화def fibonacci(n): f[1] = 1 f[2] = 1 global f2 for i in range(3, n+1): f[i] = f[i-1] + f[i-2] f2 += 1 .. 이전 1 2 3 4 ··· 13 다음
