본문 바로가기

Algorithm/BOJ133

[백준] 22116번 - 창영이와 퇴근 (파이썬) # 창영이와 퇴근 import sys import heapq N = int(input()) arr = [list(map(int, input().split())) for _ in range(N)] dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] visited = [[sys.maxsize for _ in range(N)]for _ in range(N)] def dijkstra(a, b): q = [] heapq.heappush(q, (0, a, b)) visited[a][b] = 0 while q: height, x, y = heapq.heappop(q) if visited[x][y] < height: continue for k in range(4): nx = x + dx[k] ny = .. 2022. 4. 12.
[백준] 9019번 - DSLR (파이썬) # DSLR from collections import defaultdict from collections import deque def get_result(x, k): if k == 'D': return (x*2) % 10000 if k == 'S': return x-1 if x != 0 else 9999 if k == 'L': return (x % 1000)*10 + x//1000 if k == 'R': return (x % 10)*1000 + x//10 T = int(input()) for _ in range(T): a, b = map(int, input().split()) dict = defaultdict(str) dict[a] = '' q = deque() q.append(a) while q: .. 2022. 4. 11.
[백준] 9370번 - 미확인 도착지 (파이썬) # 미확인 도착지 import heapq import sys input = sys.stdin.readline def dijkstra(start, arr): q = [] heapq.heappush(q, (0, start)) visited = [sys.maxsize for _ in range(n+1)] visited[start] = 0 while q: dist, node = heapq.heappop(q) if visited[node] dist+ndist: visited[nnode] = dist+ndist heapq.heappush(q, (dist+ndist, nnode)) return v.. 2022. 4. 10.
[백준] 13904번 - 과제 (파이썬) # 과제 import heapq from collections import defaultdict N = int(input()) arr = defaultdict(list) for _ in range(N): dday, score = map(int, input().split()) arr[dday].append(score) q = [] answer = 0 now = max(arr.keys()) while 0 2022. 4. 9.
[백준] 9007번 - 카누 선수 (파이썬) # 카누 선수 import sys input = sys.stdin.readline T = int(input()) for _ in range(T): k, n = map(int, input().split()) arr = [] for _ in range(4): arr.append(list(map(int, input().split()))) one, two = set(), set() for idx in range(0, 4, 2): for x in arr[idx]: for y in arr[idx+1]: one.add(x+y) if idx == 0 else two.add(x+y) one = sorted(list(one)) two = sorted(list(two)) # 투포인터 result = 0 diff = sys... 2022. 4. 8.
[백준] 3151번 - 합이 0 (파이썬) # 합이 0 from bisect import bisect_left N = int(input()) arr = list(map(int, input().split())) arr.sort() answer = 0 for i in range(len(arr)-2): left, right = i+1, N-1 while left 0: right -= 1 else: if result == 0: if arr[left] == arr[right]: answer += right - left else: idx = bisect_left(arr, arr[right]) answer += right-idx+1 left += 1 pri.. 2022. 4. 8.
[백준] 17951번 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬) # 흩날리는 시험지 속에서 내 평점이 느껴진거야 N, K = map(int, input().split()) arr = list(map(int, input().split())) answer = 0 left, right = 0, int(1e5)*20+1 while left = mid: group += 1 score = 0 # 다음 if group >= K: answer = mid left = mid+1 else: right = mid-1 print(answer) 이분탐색 1. 입력을 받는다. 출력은 최대 점수 (left와 right을 얻을 수 있는 점수로 설정) 2. left = 0, right = 최대 시험 점수 + 1 (N은 최대 10^5개, 각 점수는 최대 20점) 3. 이분탐색 - 점수가 mid 일 .. 2022. 4. 6.

티스토리툴바