본문 바로가기

알고리즘18

[백준] 1508번 레이스 https://www.acmicpc.net/problem/1508 1508번: 레이스 첫째 줄에 N, M, K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, M은 K보다 작거나 같은 자연수이다. 또, K는 2보다 크거나 같고, 50보다 작거나 같다. 둘째 줄에 심판이 있을 수 있는 K개의 www.acmicpc.net 이런 류의 문제는 이분탐색을 써야겠다고 생각했지만 코드로 구현해내지 못했다. import sys N, M, K = map(int, sys.stdin.readline().split()) loc = list(map(int, sys.stdin.readline().split())) start = 0 end = loc[-1] - loc[0] def check(mid): now = -.. 2023. 7. 10.
[백준] 1826번 연료채우기 https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 로직조차 생각이 잘 나지 않았던 문제 (연료의 위치, 채울 수 있는 연료의 양)을 리스트에 담아 연료 위치 순으로 sort한다. heap에는 현재 연료양으로 지나갈 수 있는 위치들이 연료들을 최대힙으로 담는다. 만약 현재 연료양으로 지나갈 수 없는 위치라면, 그 이후는 다 지나갈 수 없으니까 일단 해결하고 봐야한다. 그래서 while heap문으로 연료양을 채.. 2023. 7. 10.
[이분탐색] 백준 3745 오름세(가장 긴 증가하는 부분수열) # 가장 긴 증가하는 부분 수열 import sys def find(x): l = 0 r = len(result)-1 while l 2022. 3. 28.
[누적합] 백준 3020 개똥벌레 생각을 좀 다르게 가져야하는 문제 창의성이 필요했다. import sys N, H = map(int, sys.stdin.readline().split()) up = [0]*(H+1) down = [0]*(H+1) # up[i] : 개똥벌레가 i(밑에서부터)로 날때 파괴해야하는 장애물 개수 for i in range(N): if i%2==0: up[int(sys.stdin.readline())]+=1 else: down[int(sys.stdin.readline())]+=1 for i in range(H, 1, -1): up[i-1]+=up[i] down[i-1]+=down[i] obs_min = N for i in range(1, H+1): up[i] = up[i] + down[H-i+1] if obs_m.. 2022. 3. 20.
[dijkstra] 백준 11779 최소비용 구하기2(다익스트라 + 경로 노드) 기존 다익스트라 문제 + 거쳐가는 경로 노드를 구해야 하는 문제 import sys import heapq # 기존 다익스트라는 최소 거리만 계산 # 하지만 이 문제에서는 거쳐가는 노드를 출력해야한다. def dijkstra(start, end, n): distances = [float('inf')]*(n+1) distances[start]=0 visit = [[] for _ in range(n+1)] visit[start].append(start) heap = [[0, start]] while heap: current_dist, current_idx = heapq.heappop(heap) if current_dist > distances[current_idx]: continue for next_idx,.. 2022. 3. 19.
[dijkstra] 백준 10282 해킹 답이 맞긴한데 시간초과.. 시간초과 import sys from collections import deque T = int(sys.stdin.readline()) def infection(graph, c, n): time = [sys.maxsize]*(n+1) time[c]=0 q = deque() q.append(c) while q: p = q.popleft() for i, w in graph[p]: time[i] = min(time[i], time[p]+w) if i not in q: q.append(i) cnt = 0 ans = 0 for t in time: if t != sys.maxsize: cnt+=1 ans = max(ans, t) print(cnt, ans) for _ in range(T).. 2022. 3. 17.

티스토리툴바