본문 바로가기

전체 글

 (208)
등산 (16681 백준) 각각의 목표지점까지의 거리를 하나씩 구하지 말고 집에서 목표지점까지의 거리, 학교에서 목표지점까지의 거리를 배열을 이용해 저장하고 등산 기대값의 최대를 구한다. 모든 목표지점에 대해서 다익스트라를 수행하니 시간이 초과되었다. 백준 17835번과 유사한 문제이다. https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net
근손실(백준18429) 만들어질 수 있는 모든 경우에 대해서 확인하고 그 경우의 수를 다 더한다. import sys input =sys.stdin.readline n,k = map(int, input().split()) weights = list(map(int, input().split())) selected = [] ans =0 def check(arr) : # arr가 순서를 나타낸 배열 global ans flag = 1 new = 500 for i in arr : new =new+weights[i]-k if new < 500 : return 0 return 1 def find(idx): global ans global selected if len(selected)== n: if check(selected) : ans ..
알바생 강호(백준 1758) 일반적인 그리디 알고리즘 문제로, 손님들의 팁 금액을 기준으로 내림차순 정렬해서 받을 수 있는 총 금액을 계산한다. n= int(input()) arr = [] for i in range(n): k = int(input()) arr.append(k) arr.sort(reverse = True) ans = 0 for i in range(n): ans += (arr[i]-i) if (arr[i]-i >0) else 0 print(ans)
게리맨더링(백준 17471) 도시의 집합을 하나씩 구해서 각 집합들에 대해서 bfs를 수행하여 서로 연결이 되어있는 지 확인한다. 만약 도시들의 분류가 가능한 경우, 인구 수 차이를 구해서 최소의 인구 수 차이를 갱신 해준다. import sys from collections import deque input = sys.stdin.readline inf = int(1e9) #전체 선거구 개수 n = int(input()) people = [0]+ list(map(int, input().split())) total_people =sum(people) gra = [[]for _ in range(n+1)] for i in range(n): #i+1의 선거구에 연결된 선거구들 oneline = list(map(int, input().spl..
ICMP(Internet Control Message Protocol)을 알아보자 네트워크 계층에 해당하는 프로토콜 중 하나이다. 네트워크 계층에 있는 대표적인 프로토콜은 ARP, IP, ICMP등이 있는데 여기서 ICMP는 에러를 보고하기 위한 용도로 사용된다. IP는 에러가 발생 시 에러 보고를 하지 아니하기 때문에 ICMP가 필요하다. 발생하는 에러가 종류별로 여러가지 있는데 각각에 대해서 ICMP의 타입이 다르다. 대표적으로 3,4,11,12,5번 타입이 있다. Destination Unreachable(Type 3) : 목적지에 도달하지 못하는 경우 그 패킷이 drop되고 그 패킷이 sorce로 ICMP를 전송한다. Source Quench(Type 4) : 라우터가 다 차가지고 여유 공간이 없는 경우이다. 이는 패킷이 들어오는 속도가 나가는 속도보다 더 빠른 경우 발생한다...
ARP(Address Resolution Protocol)를 알아보자 ARP는 IP 주소와 MAC 주소 간의 대응을 해주는 프로토콜로, 로컬 네트워크에서 효율적인 데이터 전송을 가능하게 한다. 다시 말해서 전송자가 특정 IP주소로 데이터를 보낼 때, 그 IP 주소를 가지고 있는 상대 컴퓨터의 MAC 주소를 모르면 ARP 프로토콜을 이용해서 MAC주소를 검색하고 맵핑한다. A 컴퓨터가 141.23.56.23의 IP주소에 연결된 다른 컴퓨터의 MAC 주소를 알고 싶은 경우, LAN (로컬 에어리어 네트워크)에 속한 다른 컴퓨터들에게 ARP 프로토콜을 보낸다. 그 결과 B,C,D,E 컴퓨터가 해당 프로토콜을 받았다고 가정하고 그 중 B가 해당 IP주소에 연결되어 있는 경우, B가 ARP reply를 A에게만 보낸다. 나머지 해당하지 않는 컴퓨터들은 이 요청을 버린다. B 컴퓨터..
애너그램 만들기(백준 1919) 하나의 알파벳들에 대해서 모두 몇 번 사용이 됐는지 확인해서 빼야하는 총 알파벳 개수를 구한다. alphabet = 'abcdefghijklmnopqrstuvwxyz' dic = {} for abc in alphabet: dic[abc] = 0 word1= input() for letter in word1 : dic[letter] += 1 word2 = input() for letter in word2 : dic[letter] -= 1 ans = 0 for i in dic: ans += abs(dic[i]) print(ans)
Traveling SCCC President (백준 28119) 문제의 조건이 일반적인 MST보다 많다고 보기 쉽지만 그냥 MST를 만들면 된다. 또한, 반복문의 깊이 범위를 더 늘려야 정답이 된다. import sys sys.setrecursionlimit(10000) input = sys.stdin.readline n,m,s = map(int, input().split()) edges =[] for i in range(m): a,b,c = map(int, input().split()) edges.append((c,a,b)) edges.sort() order = list(map(int, input().split())) parent = [i for i in range(n+1)] def find(a): if a != parent[a]: parent[a] = find(p..

티스토리툴바