본문 바로가기

Algorithm/Data Structures39

[파이썬] 백준 17612 : 쇼핑몰 (골드2) [파이썬] 백준 17612 : 쇼핑몰 (골드2)https://www.acmicpc.net/problem/17612풀이방향성 생각K개의 계산대 중 최소 정보를 계속 찾아야 함 -> 힙 사용같은 시간대에서 여러 명이 빠질 수 있는 케이스 생각하기전체코드from collections import dequeimport heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()N,M = map(int,input().split())Q = deque()for _ in range(N): Q.append(list(map(int,input().split())))# 사람들 계산대에 보내기heap = []for line in range(min(N,M)): .. 2024. 5. 28.
[파이썬] 백준 2143 : 두 배열의 합 (골드3) [파이썬] 백준 2143 : 두 배열의 합 (골드3)https://www.acmicpc.net/problem/2143풀이방향성 생각전형적인 해싱 문제각 배열 크기가 1000 -> 구간합 만들기구간합 값의 개수를 카운팅한다 -> O(1000^2)한 구간합을 카운팅한 dict에서 다른 구간합 카운팅 dict을 매칭시킨다.전체코드from collections import defaultdict as ddtarget = int(input())# 각 배열 만들어주기a = int(input())arr_A = list(map(int,input().split()))b = int(input())arr_B = list(map(int,input().split()))# 각 배열의 누적합 만들어주기cum_A = [0]for va.. 2024. 5. 26.
[파이썬] 백준 7453 : 합이 0인 네 정수 (골드2) [파이썬] 백준 7453 : 합이 0인 네 정수 (골드2) https://www.acmicpc.net/problem/7453 풀이 방향성 생각 투포인터 태그가 있긴한데 해싱이 조금 더 직관적인 풀이라고 생각한다. AB에서 N^2, CD 에서 N^2의 모든 경우의 수를 만든다. AB에 저장된 숫자로 CD에 매칭되는 숫자는 유일하니 이 경우를 카운팅하기 전체코드 from collections import defaultdict as dd import sys input = lambda : sys.stdin.readline().rstrip() N = int(input()) A,B,C,D = [],[],[],[] for _ in range(N): a,b,c,d = map(int,input().split()) A.a.. 2024. 4. 22.
[파이썬] 백준 22866 : 탑 보기 (골드3) [파이썬] 백준 22866 : 탑 보기 (골드3) https://www.acmicpc.net/problem/22866 풀이 방향성 생각 한 노드 다른 방향으로 볼 수 있는 건물의 수를 탐색하면 시간 초과. $O(nlogn)$ 밑으로 풀어야함. 한 번 순회로 앞 뒤 모두 체크하기는 어려움. 스택을 통해서 뒤의 정보만 저장하고 새로운 정보를 바탕으로 스택 바꾸기. 전체코드 N = int(input()) H = list(map(int,input().split())) def search(infos,reverse): # 볼 수 있는 개수 / 볼 수 있는 빌딩까지 최소 거리 / 볼 수 있는 빌딩 인덱스 counts,dists,close_idx = [0]*N,[10**6]*N,[10**6]*N start,end,st.. 2024. 4. 4.

티스토리툴바