본문 바로가기

백준

[코딩인터뷰] 백준 15683번 감시 import sys from copy import deepcopy rl = sys.stdin.readline def watch(testbed, sr, sc, direction): direction %= 4 cr = sr + DR[direction] cc = sc + DC[direction] while 0
[코딩인터뷰] 백준 16118번 달빛 여우 백준 16118번 달빛 여우 2021.04.15 00:39 기준으로 Python 3 로 통과했는데 시간이 아슬아슬하네요. 새벽이라 서버가 널널해서 통과한 거 같네요. 그래서 다른 코드는 어떻게 통과했나 보려했더니 통과한 코드가 없다? from heapq import heappush, heappop import sys rl = sys.stdin.readline INF = int(1e9) def dik_fox(): dist = [INF for _ in range(N+1)] dist[1] = 0 q = [] heappush(q, (dist[1], 1)) while q: cd, ci = heappop(q) if dist[ci] < cd: continue for vd, vi in G[ci]: nd = cd + v..
[코딩인터뷰] 백준 2110번 공유기 설치 너무 정확하게 문제를 풀려는 습관때문에 쉽게 풀 것도 어렵게 접근하게 되는 나쁜 버릇... import sys rl = sys.stdin.readline N, C = map(int, rl().split()) H = [] for _ in range(N): H.append(int(rl())) H.sort() answer = 0 # 가능한 최소 거리 lo = 1 # 가능한 최대 거리 hi = H[-1] - H[0] while lo = mid: pr = H[i] c += 1 # 설치해야 하는 공유기 수보다 적게 설치했다면, 최대 거리를 좁힌다. if c < C: hi = mid - 1 # 설치해야 하는 공유기 수보다 많이 설치했다면, 최대 거리를 늘린다. else: lo = mid + 1 # 지금 최대 거리를 ..
[코딩인터뷰] 백준 10986번 나머지 합 수학적인 추론을 이끌어 내야 풀 수 있는 문제입니다. 'A(i) ~ A(j) = S(j) - S(i-1)' 가 Prefix Sum 의 기본 공식이고 나머지가 0 이어야 한다는 점에 착안해서 새로운 공식을 도출해야 합니다. 'A(1) ~ A(i) = K (K = 정수)' 이고 'A(1) ~ A(j) = K' 라면, 'A(i) ~ A(j) = 0' 이어야 합니다. 왜냐하면 i 부터 j 까지 합으로 인한 변화가 없어야 같은 K 가 나올 수 있기 때문입니다. 그리고 'A(i) ~ A(j) = 0' 이라면 양변에 나머지 연산을 해도 동일해서 '(A(i) ~ A(j)) % M = 0' 입니다. 이점에 착안해서 Prefix Sum ..
[코딩인터뷰] 백준 13398번 연속합 2 import sys readline = sys.stdin.readline read = sys.stdin.read N = int(readline()) A = list(map(int, readline().split())) A.insert(0,0) answer = -(10**10) d = [[answer] * (N+1) for _ in range(2)] for k in range(1, N+1): # 일반적인 누적합을 계산하는 부분 # 'd[0][k-1] + A[k]' 는 이전 누적합 중 최대값과 현재 값을 더했을 경우 d[0][k] = max(d[0][k-1] + A[k], A[k]) # 'd[0][k-1]' 는 지금 A[k] 를 누적합 계산에서 제외할 경우 # 'd[1][..
[코딩인터뷰] 백준 2616번 소형기관차 DP & 누적 합 처음엔 N 개 중 간격 M 을 두고 3 개를 뽑는 모든 경우의 수를 검토하는 방법으로 풀었더니 '시간 초과' 발생했고 이 글을 참고해서 다시 풀었습니다. 핵심 코드는 dp[x][y] = max(dp[x][y-1], dp[x-1][y-M] + (s[y] - s[y-M])) 로 매 계산마다 이전 최대값과 비교하기 때문에 마지막에 답이 나오게 됩니다. 코드를 바로 이해하기 어려워서 디버거 변수를 노트에 적어가며 해보다 보니 이해하게 되었고 아래 코드로 정답을 맞출 수 있었습니다. import sys readline = sys.stdin.readline read = sys.stdin.read N = int(readline()) T = [0] for t in map(int, rea..
[코딩인터뷰] 백준 3020번 개똥벌레 Prefix Sum 누적 합 import sys N, H = map(int, input().split()) MAX = H + 2 top = [0] * MAX bottom = [0] * MAX for k in range(N): v = int(input()) if k % 2 == 1: bottom[v] += 1 else: top[v] += 1 total_top = [0] * MAX total_bottom = [0] * MAX for i in reversed(range(1, H+1)): total_bottom[i] = bottom[i] + total_bottom[i + 1] total_top[i] = top[i] + total_top[i + 1] mini = 200001 count = 1 total = [0]..
[코딩인터뷰] 백준 16437번 16437번 양 구출 작전 문제는 "파이썬으로 풀지 말라는게 아닐까" 라는 느낌의 채점 기준이었습니다. 로직이 틀리지 않은거 같은데 왜 통과를 못하고 '메모리 초과' 가 뜰까 싶어서 C++ 정답 코드를 둘러봤는데 로직이 동일한 정답이 있었습니다. 그래서 '어? 환경설정 문젠가?' 싶어서 일단 C++ 정답으로 문제 정답 처리하고 파이썬으로 통과된 코드를 보고 환경설정을 좀 했더니 통과가 되었습니다. 정리하자면, 'PyPy 3' 로 제출하면 '메모리 초과' 가 발생합니다. 'Python 3' 로 제출하면 '시간 초과' 가 발생합니다. PyPy3 메모리 초과는 아무래도 BFS 방식으로 풀어야 해결할 수 있어 보이고, Pyth..

티스토리툴바