전체 글

[python] 백준 - 2485. 가로수

🤔문제 해결 수학 - 유클리드호제법 GCD 나무들의 간격을 구한다. 간격들의 최대 공약수를 구한다. 간격을 최대공약수로 나누고 1을 빼주면 각각의 간격 사이에 심을 나무의 숫자가 나온다. 💻소스 코드 import sys def gcd_func(a, b): while b != 0: a, b = b, a % b return a input = sys.stdin.readline N = int(input()) trees = [int(input()) for _ in range(N)] gaps = [] for i in range(1, N): # 가로수의 간격 gaps.append(trees[i] - trees[i - 1]) gaps_set = list(set(gaps)) # 간격 중복 제거 gcd = gaps_set..

[python] 백준 - 21608. 상어 초등학교

🤔문제 해결 시뮬레이션 학생: *친구들 딕셔너리를 만든다. 문제의 크기가 크지 않기 때문에 이중 포문으로 교실 전체를 탐색 좋아하는 사람 옆자리와 빈자리 개수를 각각 체크해준다. 좋아하는 사람 옆자리 수 빈자리 수 순서로 체크해가며 큰 값을 업데이트 해준다. 인덱스가 작은 값부터 탐색하기 때문에 같다면 행번호, 열번호가 작은 자리가 선택되게 된다. 다 찾았으면 교실 전체를 돌며 만족도 조사 끝 💻소스 코드 import sys input = sys.stdin.readline def is_in(ix, iy, n): if 0 max_blank): # 1. 좋아하는 사람 옆자리, 2. 같으면 빈자리 max_blank = blank max_like = like loc = i, j x, y = loc classro..

[python] 백준 - 1347. 미로 만들기

🤔문제 해결 구현 좌표를 먼저 구하자. (0, 0) 에서 시작해서 제시된 행동대로 좌표로 담아준다. x좌표, y좌표 각각의 최소와 최대를 구한다. 모든 좌표들에 대해서 최소값을 더해준다. ( 음수가 나올 수 있기 때문에 양수로 바꿔주기 위해서 ) 최대 최소로 2차원 배열을 만들고, 구한 좌표로 길을 만들어준다. 💻소스 코드 import sys input = sys.stdin.readline N = int(input()) action = input().strip() # 0,0 부터 좌표 구하기 loc_list = [(0, 0)] dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1] # 상 우 하 좌/ 북 동 남 서 status = 2 for a in action: if a == 'R': # ..

[python] 백준 - 12764. 싸지방에 간 준하

🤔문제 해결 우선순위 큐 대기중인 사람과 먼저 사용중인 사람 중 가장 빨리 끝나는 곳과 비교 대기중인 사람보다 늦게 끝나면 새로운 자리로 배정 기존의 사람이 끝나는 곳이 있으면 그게 여러 곳이 있으면 끝나는 곳을 다 뽑아서 남는 자리 우선순위 큐에 넣는다. 더 이상 없을 때 남는 자리 우선순위 큐에서 자리르 하나 뽑아서 배정한다. 사용중인 컴퓨터 끝나는 시간과 자리번호가 담긴 우선순위 큐 남아있는 자리가 담긴 우선순위 큐 이렇게 해서 두개를 사용했다. 우선순위 큐를 두개 써야해서 헷갈렸던 문제 💻소스 코드 import sys import heapq input = sys.stdin.readline N = int(input()) logs = [list(map(int, input().split())) for ..

[python] 백준 - 11085. 군사 이동

🤔문제 해결 크루스칼 C에서 출발! 갈 수 있는 곳을 찾아서 우선순위 큐에 넣는다. 우선순위 큐에서 넓이가 가장 넓은 녀석을 뽑는다. 거기서 또 갈 수 있는 곳을 찾아서 큐에 넣는다. (단, 재방문 X) V를 만나면 끝! 노드를 이동하는 동안 최소값을 계속 갱신해준다. (답을 찾아야하므로) 💻소스 코드 import sys from collections import defaultdict import heapq input = sys.stdin.readline P, W = map(int, input().split()) # P개의 지점, W개의 길 C, V = map(int, input().split()) # C 백준수도, V 큐브수도 # 인접노드 만들기 nodes = [input() for _ in range..

[python] 백준 - 19598. 최소 회의실 개수

🤔문제 해결 우선순위큐 회의를 오름차순으로 정렬한다. 사용한 회의실의 끝나는 시각을 배열로 만든다. 우선순위큐로 사용할 것 회의를 하나씩 꺼내서 가장 빨리 끝나는 회의실과 회의 시작 시간을 비교 회의 시작 시간이 더 빠르면 회의실 추가 회의 시작 시간이 더 늦으면 해당 회의실의 끝나는 시각 업데이트 🍞 heapreplace는 가장 작은 요소를 빼고, 추가할 요소를 집어 넣는다. ( pop 후 push 를 합친것 - 더 빠르다고 한다.) 💻소스 코드 import sys import heapq input = sys.stdin.readline N = int(input()) meetings = [list(map(int, input().split())) for _ in range(N)] meetings.sort(..