📌문제 출처 백준 단계별 문제풀이 - 우선순위 큐 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net ❓ 문제 ❗ 풀이 heap 자료 구조 활용 📗 풀이 코드 import sys from heapq import heappush, heappop input = sys.stdin.readline nums = [] for _ in range(int(input())): i = int(input()) if i : heappush(num..
📌문제 출처 백준 단계별 문제풀이 - 이분탐색 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net ❓ 문제 ❗ 풀이 이분탐색 활용 📗 풀이 코드 import sys input = sys.stdin.readline def binary_search(q,n): sta,end = 0,n-1 mid = (sta+end)//2 while sta
📌문제 출처 백준 단계별 문제풀이 - 분할정복 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net ❓ 문제 ❗ 풀이 분할 정복(재귀 함수) 사용 📗 풀이 코드 import sys input = sys.stdin.readline def mul_func(a1,a2): # 행렬 곱 연산 함수 mul = [[0 for _ in range(n)] for _ in range(n)] for i in range(n): a1_row = a1[i] for j in range(n)..
📌문제 출처 백준 단계별 문제풀이 - 분할정복 https://www.acmicpc.net/problem/2740 ❓ 문제 ❗ 풀이 행렬 전환하여 행렬 곱 연산 진행 📗 풀이 코드 import sys input = sys.stdin.readline n,m = map(int,input().split()) list_a = [list(map(int,input().split())) for _ in range(n)] _,k = map(int,input().split()) # 행렬 곱셈이 가능하려면 a의 열과 b의 행이 같아야하기에 m 생략 list_b = [[] for _ in range(k)] for _ in range(m): for i,num in enumerate(map(int,input().split()))..
📌문제 출처 백준 단계별 문제풀이 - 분할정복 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net ❓ 문제 ❗ 풀이 (a**n)%c == (((a**(n-1))%c)*a)%c라는 성질 이용 📗 풀이 코드 import sys input = sys.stdin.readline a,b,c = map(int,input().split()) rests = [] # a**i의 나머지 집합 i = 1 rests.append(a%c) # rests에는 a**1의 나머지, a**2의 나머지, a**4의 나머지, a**8의 나머지....
📌문제 출처 백준 단계별 문제풀이 - 분할정복 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net ❓ 문제 ❗ 풀이 재귀함수 활용 📗 풀이 코드 import sys input = sys.stdin.readline # 2차원 배열이 모두 같은 수인지 확인하고 아니면 4등분하는 함수 def division(n, sum_video, video): global ans if not sum_video%n**2 : # 모두 같은 수라면 나머지가 0..
📌문제 출처 백준 단계별 문제풀이 - 분할정복 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net ❓ 문제 ❗ 풀이 재귀함수 활용 📗 풀이 코드 import sys input = sys.stdin.readline # n*n 행렬에서 전체가 다 같은 색인지 확인 후 아니면 4등분하는 함수 def division(n,paper,sum_paper): # 모두 같은 색인 경우 if not sum_paper%(n**2) : # 전..
📌문제 출처 백준 단계별 문제풀이 - 그리디 알고리즘 https://www.acmicpc.net/problem/13305 ❓ 문제 ❗ 풀이 그리디 알고리즘 활용 📗 풀이 코드 import sys input = sys.stdin.readline n = int(input()) # 시작할 때 주유하고, 기름을 넣은 주유소보다 기름값이 싼 주유소를 만나면 거기서 주유한다. roads = list(map(int,input().split())) costs = list(map(int,input().split()))[:-1] # 도착지점에서는 기름을 안넣으니 제외 tot_cost = 0 # 최종 전체 주유비 tmp_cost = costs[0] # 주유할 주유소에서의 비용, 첫번째 주유소에서 주유 후 시작 tmp_roa..
